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

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

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

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

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

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

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

8、擬某種流在網絡上的擴散。其優勢是這個算法的核心是通過標簽的擴散來模擬某種流在網絡上的擴散。其優勢是算法簡單，特別適用于分析被流所塑造的網絡。在大多數情況下可以快速收算法簡單，特別適用于分析被流所塑造的網絡。在大多數情況下可以快速收斂。其缺陷是，迭代的結果有可能不穩定，尤其在不考慮連邊的權重時，如斂。其缺陷是，迭代的結果有可能不穩定，尤其在不考慮連邊的權重時，如果社區結構不明顯，或者網絡比較小時，有可能所有的節點都被歸入同一個果社區結構不明顯，或者網絡比較小時，有可能所有的節點都被歸入同一個社區。社區。 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）從節點合并開始，）從節點合并開始， 構建第一步社團劃分結果。每個節點根據模塊度增構建第一步社團劃分結果。每個節點根據模塊度增益決定是否加入到鄰居節點的社團中和到底加入到哪個鄰居節點的社團中。益決定是否加入到鄰居節點的社團中和到底

10、加入到哪個鄰居節點的社團中。每個節點按序執行該過程。每個節點按序執行該過程。（2 2）重新構建網絡。把第一步每個社團單做一個節點，邊是原來社團之間）重新構建網絡。把第一步每個社團單做一個節點，邊是原來社團之間鏈接邊權的和。鏈接邊權的和。（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 算法的初始條件為每個結點為一個單獨的社區，然后逐步合并可使結點和算法的初始條件為每個結點為一個單獨的社區，然后逐步合并可使結點和它所在社區之間的平方距離均值達到最小的兩個社區。每一步都要更新社區它所在社區之間的平方距離均值達到最小的兩個社區。每一步都要更新社區之間的距離，其中兩個結點之間的距離對應于它們的相似度，即在一個離散之間的距離，其中兩個結點之間的距離對應于它們的相似度，即在一個離散的隨機游走過程中，它們之間的方向轉移概率。的隨機游走過程中，它們之間的方向轉移概率。 Reference: Pas

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

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

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

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

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

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