計算機設計大賽炫酷展示

1、背景與意義背景與意義功能介紹功能介紹技術知識技術知識創(chuàng)新之處創(chuàng)新之處1234未來展望未來展望5 社會網(wǎng)絡（social network）是由圖表示的異構多關系數(shù)據(jù)集，圖中節(jié)點對應對象，邊對應表示對象間聯(lián)系或相互作用的鏈接。過去的幾十年間，社會網(wǎng)絡受到越來越多的關注。特別是移動網(wǎng)絡和互聯(lián)網(wǎng)的發(fā)展，產(chǎn)生了大量的，容易被計算機處理的社會網(wǎng)絡數(shù)據(jù)。從這些數(shù)據(jù)中獲取知識，從而理解商業(yè)行為，識別業(yè)務模式，捕捉用戶行為，更好利用資源，提高服務質量，將成為運營商的核心競爭力之一。 對于現(xiàn)在大數(shù)據(jù)的時代中，挖掘出社交網(wǎng)絡上的社區(qū)很有實用價值。社區(qū)內(nèi)用戶的共同話題，會形成一個定向的區(qū)別用戶的方式，為智能搜索、個性

2、化服務、商業(yè)應用推廣等應用提供理論依據(jù)。從廣告投放的角度來看，容易找到定向的廣告受眾; 從朋友推薦的角度看，能夠方便的將同一個社區(qū)內(nèi)的個體向其他個體進行推薦，為找尋多年沒有聯(lián)系的朋友提供一個方便快捷的途徑。 將社會網(wǎng)絡分析以一種數(shù)據(jù)可視化的形式展示給決策者，不僅能形象直觀，還有助于其在龐大的數(shù)據(jù)中能及時捕獲所需信息。數(shù)據(jù)可視化，是關于數(shù)據(jù)之視覺表現(xiàn)形式的研究。如今，可視化已經(jīng)不僅僅是點和線的簡單描繪，它成為了一種能傳遞深層數(shù)據(jù)內(nèi)涵、啟發(fā)問題解決方案的強大智能模型。 類似這樣的軟件，在國外著名的有UCINET、Pajek以及Gephi等，UCINET、Pajek側重于社會網(wǎng)絡的分析，但可視化的效

3、果較差，而且操作不簡單，忽略用戶體驗；Gephi是則偏向于社交圖譜的數(shù)據(jù)可視化，能生成漂亮的可視化圖形，并對數(shù)據(jù)進行清洗和分類，但數(shù)據(jù)分析不夠全面，提供算法較少。另外，這些軟件都需用戶下載才能使用，不支持web端，這樣導致電腦因系統(tǒng)的差異而使用不了某些軟件，如Gephi需jdk1.7以下的環(huán)境配置，不支持jdk1.8。 針對上述的不足，我們小組研發(fā)了一個基于web端的社會網(wǎng)絡可視化分析平臺，名為vina，力求將社會網(wǎng)絡分析與數(shù)據(jù)可視化充分結合，以給用戶更好的體驗效果。 項目簡介： 本系統(tǒng)是一個基于開源框架Django的社會網(wǎng)絡可視化分析網(wǎng)站，并且盡可能簡單靈活地使數(shù)據(jù)可視化。特點是UI美觀、使

4、用簡單、支持大多數(shù)瀏覽器、支持多種文件格式的輸入、提供多種社區(qū)劃分算法。數(shù)據(jù)可視化的結果包括了網(wǎng)絡圖、柱狀圖、餅圖、表格，讓用戶從不同角度獲得社區(qū)網(wǎng)絡劃分的結果。另外，本系統(tǒng)還運用了社會網(wǎng)絡分析的知識，為用戶挖掘出網(wǎng)絡中的重要信息。本系統(tǒng)的用途可分為：客戶群體細分、社交網(wǎng)絡分析、熱點事件分析、輿情監(jiān)控、社會網(wǎng)絡劃分的教學等。 支持多種文件格式的輸入提供多種社區(qū)劃分算法UI美觀使用簡單基于web項目特點： 項目用途： 登陸網(wǎng)站，登陸網(wǎng)站，注冊登錄注冊登錄 導入文件，導入文件，選擇算法選擇算法 得到輸出，得到輸出，分析結果分析結果退出登錄退出登錄系統(tǒng)使用流程：本系統(tǒng)的網(wǎng)址為http：/120.25

5、.203.152:8000文件導入格式： 我們導入的文件有兩個，第一個是網(wǎng)絡信息文件，文件的內(nèi)容以source，target，weight為格式，source代表源點，target代表目標點，weight代表連邊權重，例如節(jié)點1對節(jié)點6有連邊，連邊權重為2，我們記錄的格式為“1,6,2”。 第二個是節(jié)點標簽文件，文件的內(nèi)容是節(jié)點所對應的標簽，以node，label為格式，例如節(jié)點1的標簽叫quincy。 兩份文件均支持txt，xls和csv格式 網(wǎng)絡信息文件：網(wǎng)絡信息文件：標簽文件標簽文件LPABGLL WALK-TRAPFAST-GREEDY WorldCannotReceiveWorldC

6、annotSeeWorld doesNot KnowWillDwell inDisciples社區(qū)劃分算法社區(qū)劃分算法四種算法都具有良好的社區(qū)劃分效果，四種算法都具有良好的社區(qū)劃分效果，不同的算法適用于不同的場景不同的算法適用于不同的場景LPA：快速高效：快速高效 BGLL：穩(wěn)定準確穩(wěn)定準確 Walktrap：劃分效果好：劃分效果好 Fastgreedy： 適用大型加適用大型加權網(wǎng)絡權網(wǎng)絡 算法特點：算法特點：1、label propagation Algorithm(LPA) 標簽傳播算法（標簽傳播算法（LPALPA）是由）是由ZhuZhu等人于等人于20022002年提出，它是一種基于圖的

7、半年提出，它是一種基于圖的半監(jiān)督學習方法該算法的基本原理如下：首先，給全網(wǎng)每個節(jié)點分配一個不重監(jiān)督學習方法該算法的基本原理如下：首先，給全網(wǎng)每個節(jié)點分配一個不重復的標簽（復的標簽（labellabel）；其次，在迭代的每一步，讓一個節(jié)點采用在它所有的）；其次，在迭代的每一步，讓一個節(jié)點采用在它所有的鄰居節(jié)點中最流行的標簽（如果最佳候選標簽超過一個，則在其中隨機抽一鄰居節(jié)點中最流行的標簽（如果最佳候選標簽超過一個，則在其中隨機抽一個），；最后，在迭代收斂時，采用同一種標簽的節(jié)點被歸入同一個社區(qū)。個），；最后，在迭代收斂時，采用同一種標簽的節(jié)點被歸入同一個社區(qū)。 這個算法的核心是通過標簽的擴散來模

8、擬某種流在網(wǎng)絡上的擴散。其優(yōu)勢是這個算法的核心是通過標簽的擴散來模擬某種流在網(wǎng)絡上的擴散。其優(yōu)勢是算法簡單，特別適用于分析被流所塑造的網(wǎng)絡。在大多數(shù)情況下可以快速收算法簡單，特別適用于分析被流所塑造的網(wǎng)絡。在大多數(shù)情況下可以快速收斂。其缺陷是，迭代的結果有可能不穩(wěn)定，尤其在不考慮連邊的權重時，如斂。其缺陷是，迭代的結果有可能不穩(wěn)定，尤其在不考慮連邊的權重時，如果社區(qū)結構不明顯，或者網(wǎng)絡比較小時，有可能所有的節(jié)點都被歸入同一個果社區(qū)結構不明顯，或者網(wǎng)絡比較小時，有可能所有的節(jié)點都被歸入同一個社區(qū)。社區(qū)。 Reference:Raghavan, U.N. and Albert, R. and Ku

9、mara, S. Near linear time algorithm to detect community structures in large-scale networks. Phys Rev E76:036106, 2007. /abs/0709.2938 .技術知識技術知識2、BGLL 這個方法分兩步：這個方法分兩步：（1 1）從節(jié)點合并開始，）從節(jié)點合并開始， 構建第一步社團劃分結果。每個節(jié)點根據(jù)模塊度增構建第一步社團劃分結果。每個節(jié)點根據(jù)模塊度增益決定是否加入到鄰居節(jié)點的社團中和到底加入到哪個鄰居節(jié)點的社團中。益決定是否加入到鄰居節(jié)點的社團中和到底

10、加入到哪個鄰居節(jié)點的社團中。每個節(jié)點按序執(zhí)行該過程。每個節(jié)點按序執(zhí)行該過程。（2 2）重新構建網(wǎng)絡。把第一步每個社團單做一個節(jié)點，邊是原來社團之間）重新構建網(wǎng)絡。把第一步每個社團單做一個節(jié)點，邊是原來社團之間鏈接邊權的和。鏈接邊權的和。（3 3）迭代（迭代（1 1），（），（2 2），直到收斂。），直到收斂。 Reference: VD Blondel, J-L Guillaume, R Lambiotte and E Lefebvre: Fast unfolding of community hierarchies in large networks. J Stat Mech P10008(

11、2008), /abs/0803.04763、Walktrap 算法的初始條件為每個結點為一個單獨的社區(qū)，然后逐步合并可使結點和算法的初始條件為每個結點為一個單獨的社區(qū)，然后逐步合并可使結點和它所在社區(qū)之間的平方距離均值達到最小的兩個社區(qū)。每一步都要更新社區(qū)它所在社區(qū)之間的平方距離均值達到最小的兩個社區(qū)。每一步都要更新社區(qū)之間的距離，其中兩個結點之間的距離對應于它們的相似度，即在一個離散之間的距離，其中兩個結點之間的距離對應于它們的相似度，即在一個離散的隨機游走過程中，它們之間的方向轉移概率。的隨機游走過程中，它們之間的方向轉移概率。 Reference: Pas

12、cal Pons, Matthieu Latapy: Computing communities in large networks using random walks, /abs/physics/0512106 4、Fastgreedy 一種基于貪婪法思想的凝聚算法，并稱這種算法為快速算法。將網(wǎng)絡劃分一種基于貪婪法思想的凝聚算法，并稱這種算法為快速算法。將網(wǎng)絡劃分為為K K個社團，定義一個個社團，定義一個k k* *k k維的對稱矩陣維的對稱矩陣E=E=（），其中元素，表示網(wǎng)絡連接兩（），其中元素，表示網(wǎng)絡連接兩個不同社團的節(jié)點的邊在所有邊中占的比例；這兩個節(jié)

13、點分別位于第個不同社團的節(jié)點的邊在所有邊中占的比例；這兩個節(jié)點分別位于第i i個社個社區(qū)和第區(qū)和第j j個社區(qū)。個社區(qū)。1.1.初始化網(wǎng)絡為初始化網(wǎng)絡為N N個社團，即每個節(jié)點就是一個獨立社團。個社團，即每個節(jié)點就是一個獨立社團。2.2.依次合并有邊相連的社團對，并計算合并后的模塊度增量，根據(jù)貪婪算法依次合并有邊相連的社團對，并計算合并后的模塊度增量，根據(jù)貪婪算法的原理，每次合并應該沿著模塊度增大最多或者減少最少的方向進行。每次的原理，每次合并應該沿著模塊度增大最多或者減少最少的方向進行。每次合并以后，對對應的元素更新，并將與合并以后，對對應的元素更新，并將與i i、j j社團相關的行和列相加

14、。社團相關的行和列相加。3.3.重復步驟重復步驟2 2，不斷合并社團，直到整個網(wǎng)絡都合并為一個社團。，不斷合并社團，直到整個網(wǎng)絡都合并為一個社團。4.4.整個算法完成后，得到一個社區(qū)結構分解的樹狀圖。再通過選擇在不同位整個算法完成后，得到一個社區(qū)結構分解的樹狀圖。再通過選擇在不同位置斷開可以得到不同的網(wǎng)絡社區(qū)結構。在這些社區(qū)結構中，選擇一個對應局置斷開可以得到不同的網(wǎng)絡社區(qū)結構。在這些社區(qū)結構中，選擇一個對應局部最大模塊度值的結構，就得到最好的網(wǎng)絡社區(qū)結構。部最大模塊度值的結構，就得到最好的網(wǎng)絡社區(qū)結構。 Reference: A. Clauset, M. E. J. Newman and C

15、. Moore: Finding community structure in very large networks. Phys Rev E 70, 066111 (2004).社區(qū)劃分 通過社區(qū)劃分算法將一個網(wǎng)絡劃分成不同社區(qū)，同一個社區(qū)的節(jié)點聯(lián)系較為緊密，不同社區(qū)的節(jié)點聯(lián)系較為稀疏。效果如下： 社會網(wǎng)絡分析社區(qū)結構分析核心人物挖掘好友推薦核心人物挖掘：中心性分析： 描述圖中任何一點在網(wǎng)絡中占據(jù)的核心性源于社會計量學的”明星“概念，一個核心點是那種處于一系列關系核心的位置，即該點與其他點有眾多的直接聯(lián)系。若某點具有最高點度中心度，則稱該點居于中心。 我們通過點度中心度挖掘出網(wǎng)絡中核心人物，

16、而點度中心度可分為絕度中心度和相對中心度。一般采用相對中心度較為準確。社區(qū)結構分析：社區(qū)結構分析：1.1.社區(qū)密度：社區(qū)密度： 反映社區(qū)內(nèi)的緊密程度，密度值反映社區(qū)內(nèi)的緊密程度，密度值0 0到到1 1之間，越接近之間，越接近1 1則代表彼此關系越則代表彼此關系越緊密。緊密。 一般將密度定義為一般將密度定義為“圖中實際存在的線的條數(shù)圖中實際存在的線的條數(shù)/ /圖中理論上最多可能產(chǎn)圖中理論上最多可能產(chǎn)生的生的 線的條數(shù)線的條數(shù)”。當圖中點的個數(shù)為。當圖中點的個數(shù)為n n時，密度可以表示為時，密度可以表示為l/n(n-l/n(n-1)/2.1)/2. 其中分子其中分子l l是圖中實際存在的線的條數(shù)，

17、是所有點度數(shù)總和的一半，也是圖中實際存在的線的條數(shù)，是所有點度數(shù)總和的一半，也就是就是 鄰接陣中所有元素總和的一半。而分母可以用簡單的排列組合方鄰接陣中所有元素總和的一半。而分母可以用簡單的排列組合方法計算得到。法計算得到。2.2.點度中心勢點度中心勢 反映社區(qū)內(nèi)的集中程度，也間接反映核心人物對社區(qū)的影響程度。反映社區(qū)內(nèi)的集中程度，也間接反映核心人物對社區(qū)的影響程度。 思路：思路： 首先找到圖中的最大中心度數(shù)值；然后計算該值與任何其他點的中心度的差，首先找到圖中的最大中心度數(shù)值；然后計算該值與任何其他點的中心度的差， 從而得出多個從而得出多個“差值差值”；再計算這些；再計算這些“差值差值”的總和；最后用這個總和除的總和；最后用這個總和除以各個以各個“差值差值”總和的最大可能值。總和的最大可能值。 公式：公式：好友推薦：把好友關系轉化成圖的形式，點代表一個用戶，連接兩點的邊代表兩個用戶是好友，邊可以有權重，也可以沒有。直接認識的朋友，叫一度好友。朋友的朋友，叫二度好友，而我們主要通過二度好友進行好友推薦，即“朋友的朋友”的思想。 1