基于“鄰域”結構洞的社團發現算法

沈文明　杜翠鳳

【摘 要】為了解決傳統社團發現算法僅考慮復雜網絡的局部屬性的問題，構建以移動用戶之間的通話數據為基礎的移動用戶通信網絡，通過采用“鄰域”結構洞衡量用戶之間的關系強度，利用模塊度值尋找社團劃分的最優“關系閾值”，提出了基于“鄰域”結構洞的社團發現算法。經過實驗證明，該算法具有一定的有效性和擴展性。

【關鍵詞】復雜網絡 社團結構 “鄰域”結構洞 模塊度值

1 引言

社團結構是描述社會網絡具有一個共同的性質，即滿足同一社團內部節點連接相對緊密、不同社團節點連接相對稀疏的特點[1]。目前社團發現的研究算法大致可以劃分為圖形分割和分級聚類兩種。其中，圖形分割的主要代表算法有：基于貪婪思想實現極小化簇間連接數目與簇內連接數目之差的Kernighan-Lin算法[2]；基于特征值的相似性實現社團劃分的Laplace圖特征值的譜平分算法[3]；基于邊密度的CPM派系過濾算法[4]。分級聚類是根據網絡中不同節點的連接強度實現社團的劃分，該算法根據對網絡的操作不同分為兩種：分裂算法的典型代表是GN算法，通過刪除網絡中介數大的邊獲得社團結構；凝聚算法的典型代表是Newman快速算法，其思想是從空網絡開始，逐步添加相似性的邊，同時在計算相似性時通過模塊度來標示社團分割的質量[5]。上述的社團發現算法僅僅考慮復雜網絡的局部屬性，如考慮節點自身的信息以及其鄰居的信息而忽略鄰居的鄰域信息，會對節點與鄰居的連接強度產生大的影響，因此本文提出了基于“鄰域”結構洞的社團發現算法。該算法是利用節點以及其鄰居的“鄰域”結構洞來評價節點與鄰居的關系強度，同時采用模塊度值挖掘社團劃分的最優“關系閾值”，實現在特定數據下大幅度提高社團劃分的效率和精度。

2 復雜網絡中的社團發現

2.1 社團結構的定義

在絕大多數的研究中，社團的定義是從功能角度上給出的，研究者們利用網絡節點的拓撲結構試圖找出社團的功能模塊，并從拓撲結構給出了社團的定義，即：社團是一組內部連接緊密但與組外其他節點連接稀疏的節點的集合[6]。但是，高度重疊的社團違背了上述定義，因此Ahn于2010年將社團定義為一組緊密相關的鏈接，讓節點繼承與之相連接的社團的隸屬關系，從劃分鏈接的角度來解釋復雜網絡的重疊結構。

本文在參考Ahn劃分社團思路的基礎上，通過評價節點間的關系強度，采用模塊度值作為尋找關系強度的最優“閾值”，在提升同類別數據社團劃分效率的同時也符合復雜網絡重疊社團劃分的原則。

2.2 社團結構的應用場景

社團結構劃分具有多個應用場景：通過社團發現獲取道路網絡的社團結構，可以更直觀地展現每個區域的道路分布情況、道路密集區域和道路稀疏區域的具體分布；通過社團發現獲取不同消費類型的用戶社團結構，有利于運營商根據不同用戶的消費水平進行有區別的市場推廣；通過社團發現算法挖掘金融欺詐分子的社團結構，提高了反欺詐的識別率，從而保護了國家財產的安全，等等。

2.3 社團結構的評價

如何判斷一個社團發現算法劃分的社團結構好壞，一般可由以下指標來衡量：

（1）標準互信息是需要事先知道真實社團劃分的結構，當社團發現算法得到的社團劃分結構與真實社團劃分結構越接近時，它們之間的標準互信息就越接近1，該值的取值范圍為0至1。

（2）模塊度是當前社團發現領域最認可的評價社團結構好壞的指標，它表示社團劃分后社團內部的緊湊程度，當社團越緊湊時，模塊度的取值就越接近1。當然，模塊度的取值與社團劃分的精度沒有必然的關系。

（3）社團劃分精度與標準互信息類似，需要事先知道真實社團劃分的結構。它等于正確劃分的節點個數與節點總數的占比。

2.4 基于“鄰域”結構洞的用戶關系評價

（1）結構洞理論

結構洞是學者Burt在研究社會網絡的競爭關系時提出的經典社會學理論[7]。結構洞是指非冗余聯系人之間存在的缺口，一旦結構洞存在，那么結構洞兩邊的聯系人可以帶來累加而非重疊的網絡收益。結構洞示意圖如圖1所示：

從圖1可知，節點A和節點B存在結構洞，而充當聯系角色的中間人“E”獲得了更多的網絡收益，因為節點A和節點B之間的信息傳播必須由中間人“E”來完成，所以在該網絡中，中間人“E”的重要性大于其他節點。

（2）基于結構洞理論的節點重要性評價

在進行節點重要性評價之前，本文通過節點的度選取種子節點，因為只有選取種子節點后，結構洞的評價系數才能為社團發現帶來實質的價值。節點重要性評價的計算示意圖如圖2所示：

從圖2可知，I作為網絡中度數最多的節點，本文將以I為種子節點，計算它與各節點的關系，以便劃分以I為中心的社團。根據Burt對網絡節點形成的結構洞的約束系數定義，CIA表示評價節點I和節點A之間的緊密程度，節點I的鄰居數量為Г（I）={A， B， C， D， E， F， G， H}，pij表示節點i為維持節點j的鄰居關系所投入的精力與總精力之比，piq、pqj分別表示節點i和節點j與共同鄰居q維持關系投入的精力與總精力之比。

但是，上述公式僅僅衡量了節點與最鄰近節點的緊密度關系，沒有進一步考慮鄰居節點與其他節點相連的拓撲結構會對該節點的影響程度，比如存在一些重要的“橋接”節點，那么作為種子節點，I很可能為了維持自身的地位，需要向“橋接”節點投入更多的“精力”，才能維持社團的穩定性。

（3）基于“鄰域”結構洞理論的節點重要性評價[8]

根據上述約束系數的計算公式，CIF=CIG=

[1/8+（1/8）×（1/3）]2。那么，對于種子節點I來說，節點F與節點G對節點I來說同等重要。但是從圖2得知，與G點相連的鄰居以及鄰居的拓撲結構使得I必須對G付出更多的“精力”才能穩定社團的結構，而上述約束系數無法體現這一點，因此需要改進該約束系數，可通過“鄰域”結構洞約束系數來體現這一點。endprint

節點I與鄰居節點的關系仍用公式（2）表示，則在新的約束系數定義下，CIF=[12/71+（14/71）×（12/44）]2，CIG=[15/71+（14/71）×（15/44）]2。很明顯，節點I在一定精力的情況下，向G投入的“精力”比F更多，該約束系數在一定程度上更加真實地反映了節點與節點的緊密關系。

3 基于“鄰域”結構洞的社團發現算法

3.1 算法的思路

基于“鄰域”結構洞的社團發現算法的基本思路如下：

（1）根據前面改進的“鄰域”結構洞約束系數得到節點與節點的關系評價值，粗略劃分社團。

（2）針對上一步劃分的結果，同時采用模塊度值尋找關系強度的最優“閾值”，對數據進一步優化，從而對社團進行更精準的劃分。

3.2 粗略劃分社團

根據圖3可知，每次設定的關系閾值θ都會輸出一些不確定數量的社團數，由于社團的大小受到關系閾值的影響，如果關系閾值設置較大，則輸出的社團個數較多，社團相對較小；相反，則輸出的社團個數較少，社團相對較大。那么，如何確定關系閾值以便更好地進行社團劃分，本文將通過模塊度值來衡量不同的閾值劃分社團的質量情況。

3.3 采用模塊度值尋找最優“閾值”

模塊度是評價一個社區劃分好壞的度量方法，它是指社區內節點連邊數與隨機情況下的邊數之差。首先把網絡上每個節點看成獨立的節點，并隨機選取一個節點作為開始節點；然后采用每次并入一個節點的方式來計算兩個并入節點的社區模塊度值；最后根據模塊度增加值的大小來決定該節點是否適合并入該社區。每個閾值下社區劃分的模塊度值計算公式為：

其中，Q為模塊度值；Aij為節點i和節點j之間邊的個數；ki、kj分別為節點i和節點j的度；m為拓撲結構圖的總邊數；δ（i， j）表示當社區劃分結果中節點i和節點j屬于同一社區時，則δ（i， j）=1，當社區劃分結果中節點i和節點j不屬于同一社區時，則δ（i， j）=0。

關系閾值θ的設定由數據集模塊度值分布現狀決定，也就是每個閾值都需要計算一個對應的模塊度值，然后選取最大的模塊度值對應的關系值作為閾值。根據約束系數的定義可知，關系閾值取值為0到1，因此本文在設定關系閾值的過程中，讓θ從0到1，步長為0.005，逐漸增大，計算201個θ值對應的模塊度，根據模塊度值的變化來確定θ的取值范圍。

上述改進能夠適應移動運營商不同消費類型的用戶社團劃分，滿足移動運營商的用戶信息具有動態性和多樣化的特點，利用該方法進行社區劃分有利于運營商進行市場推廣。

3.4 實驗及結果分析

本次實驗的數據來源是某地市3個村960名移動用戶的通話數據，按照用戶是否有通話關系分別建立三個無向通信網絡，如果用戶i和j之間有聯系，那么i和j之間有邊相連；否則，無邊相連。

圖4分別反映了三個網絡數據集中關系閾值θ與社團劃分模塊度值的對應關系。

從圖4可知，第一個數據集的最優關系閾值為0.060；第二個數據集的最優關系閾值為0.065；第三個數據集的最優關系閾值為0.055。對圖形進一步分析可知，閾值是先單調遞增后單調遞減，最優的關系閾值出現在拐點位置，因此本文把閾值區間定為[0.055， 0.070]。

本文基于上述三個真實的社會網絡進行社團發現的實驗，通過對比這三個社會網絡真實的社團劃分情況，給出了實驗劃分結果的準確率對比，如圖5所示。

從圖5可知，除了第三個數據集的準確率較低外，其余數據集的準確率均達到95%以上，并且網絡節點的數量與社團劃分的準確率沒有必然的聯系。

4 結束語

本文基于真實的用戶通信數據和所建立通信網絡的拓撲結構，提出了基于“鄰域”結構洞的社團發現算法，首先通過節點的度提取種子節點，然后采用改進的“鄰域”結構洞約束系數計算節點與鄰居的關系強度，最后通過采用模塊度值確定社團劃分的最優“關系閾值”。實驗證明，基于“鄰域”結構洞的社團發現算法具有較高精度。本文的方法僅適用于特定數量的網絡節點，未來的研究將會針對特大型網絡的社團發現算法進行優化，采用啟發式算法進一步提升社團發現的效率和精度。

參考文獻：

[1] M Girvan， M E J Newman. Community structure in social and biological networks[J]. Proceedings of the National Academy of Sciences of the United States of America， 2002，99（12）： 7821-7826.

[2] Kernighan B W， Lin S. An Efficient Heuristic Procedure for Partitioning Graphs[J]. Bell System Technical Journal， 2014，49（2）： 291-307.

[3] A Pothen， H D Simon， K P Liou. Partitioning Sparse Matrices with Eigenvectors of Graphs[J]. SIAM Journal on Matrix Analysis and Applications， 1990，11（3）： 430-452.

[4] G Palla， I J Farkas， P Pollner， et al. Directed network modules[J]. New Journal of Physics， 2007，9（6）： 186-207.

[5] 張洋洋. 復雜網絡中社團結構發現算法的研究與實現[D]. 南京： 南京理工大學， 2014.

[6] 何東曉. 復雜網絡社團結構發現方法研究[D]. 長春： 吉林大學， 2014.

[7] Burt R S. Structural Holes： The Social Structure of Competition[M]. Boston： Harvard University Press， 1993.

[8] 蘇曉萍，宋玉蓉. 利用鄰域“結構洞”尋找社會網絡中最具影響力節點[J]. 物理學報， 2015，64（2）： 1-11.

[9] 許鴻. 基于鄰居相似性和半監督社團檢測算法研究[D]. 蘭州： 蘭州大學， 2014.

[10] 華燁. 基于相對關系親密度的局部社團發現算法研究[D]. 合肥： 中國科學技術大學， 2014.endprint