沈文明　杜翠鳳

【摘 要】為了解決傳統(tǒng)社團(tuán)發(fā)現(xiàn)算法僅考慮復(fù)雜網(wǎng)絡(luò)的局部屬性的問題，構(gòu)建以移動用戶之間的通話數(shù)據(jù)為基礎(chǔ)的移動用戶通信網(wǎng)絡(luò)，通過采用“鄰域”結(jié)構(gòu)洞衡量用戶之間的關(guān)系強(qiáng)度，利用模塊度值尋找社團(tuán)劃分的最優(yōu)“關(guān)系閾值”，提出了基于“鄰域”結(jié)構(gòu)洞的社團(tuán)發(fā)現(xiàn)算法。經(jīng)過實驗證明，該算法具有一定的有效性和擴(kuò)展性。

【關(guān)鍵詞】復(fù)雜網(wǎng)絡(luò) 社團(tuán)結(jié)構(gòu) “鄰域”結(jié)構(gòu)洞 模塊度值

1 引言

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

2 復(fù)雜網(wǎng)絡(luò)中的社團(tuán)發(fā)現(xiàn)

2.1 社團(tuán)結(jié)構(gòu)的定義

在絕大多數(shù)的研究中，社團(tuán)的定義是從功能角度上給出的，研究者們利用網(wǎng)絡(luò)節(jié)點的拓?fù)浣Y(jié)構(gòu)試圖找出社團(tuán)的功能模塊，并從拓?fù)浣Y(jié)構(gòu)給出了社團(tuán)的定義，即：社團(tuán)是一組內(nèi)部連接緊密但與組外其他節(jié)點連接稀疏的節(jié)點的集合[6]。但是，高度重疊的社團(tuán)違背了上述定義，因此Ahn于2010年將社團(tuán)定義為一組緊密相關(guān)的鏈接，讓節(jié)點繼承與之相連接的社團(tuán)的隸屬關(guān)系，從劃分鏈接的角度來解釋復(fù)雜網(wǎng)絡(luò)的重疊結(jié)構(gòu)。

本文在參考Ahn劃分社團(tuán)思路的基礎(chǔ)上，通過評價節(jié)點間的關(guān)系強(qiáng)度，采用模塊度值作為尋找關(guān)系強(qiáng)度的最優(yōu)“閾值”，在提升同類別數(shù)據(jù)社團(tuán)劃分效率的同時也符合復(fù)雜網(wǎng)絡(luò)重疊社團(tuán)劃分的原則。

2.2 社團(tuán)結(jié)構(gòu)的應(yīng)用場景

社團(tuán)結(jié)構(gòu)劃分具有多個應(yīng)用場景：通過社團(tuán)發(fā)現(xiàn)獲取道路網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)，可以更直觀地展現(xiàn)每個區(qū)域的道路分布情況、道路密集區(qū)域和道路稀疏區(qū)域的具體分布；通過社團(tuán)發(fā)現(xiàn)獲取不同消費類型的用戶社團(tuán)結(jié)構(gòu)，有利于運營商根據(jù)不同用戶的消費水平進(jìn)行有區(qū)別的市場推廣；通過社團(tuán)發(fā)現(xiàn)算法挖掘金融欺詐分子的社團(tuán)結(jié)構(gòu)，提高了反欺詐的識別率，從而保護(hù)了國家財產(chǎn)的安全，等等。

2.3 社團(tuán)結(jié)構(gòu)的評價

如何判斷一個社團(tuán)發(fā)現(xiàn)算法劃分的社團(tuán)結(jié)構(gòu)好壞，一般可由以下指標(biāo)來衡量：

（1）標(biāo)準(zhǔn)互信息是需要事先知道真實社團(tuán)劃分的結(jié)構(gòu)，當(dāng)社團(tuán)發(fā)現(xiàn)算法得到的社團(tuán)劃分結(jié)構(gòu)與真實社團(tuán)劃分結(jié)構(gòu)越接近時，它們之間的標(biāo)準(zhǔn)互信息就越接近1，該值的取值范圍為0至1。

（2）模塊度是當(dāng)前社團(tuán)發(fā)現(xiàn)領(lǐng)域最認(rèn)可的評價社團(tuán)結(jié)構(gòu)好壞的指標(biāo)，它表示社團(tuán)劃分后社團(tuán)內(nèi)部的緊湊程度，當(dāng)社團(tuán)越緊湊時，模塊度的取值就越接近1。當(dāng)然，模塊度的取值與社團(tuán)劃分的精度沒有必然的關(guān)系。

（3）社團(tuán)劃分精度與標(biāo)準(zhǔn)互信息類似，需要事先知道真實社團(tuán)劃分的結(jié)構(gòu)。它等于正確劃分的節(jié)點個數(shù)與節(jié)點總數(shù)的占比。

2.4 基于“鄰域”結(jié)構(gòu)洞的用戶關(guān)系評價

（1）結(jié)構(gòu)洞理論

結(jié)構(gòu)洞是學(xué)者Burt在研究社會網(wǎng)絡(luò)的競爭關(guān)系時提出的經(jīng)典社會學(xué)理論[7]。結(jié)構(gòu)洞是指非冗余聯(lián)系人之間存在的缺口，一旦結(jié)構(gòu)洞存在，那么結(jié)構(gòu)洞兩邊的聯(lián)系人可以帶來累加而非重疊的網(wǎng)絡(luò)收益。結(jié)構(gòu)洞示意圖如圖1所示：

從圖1可知，節(jié)點A和節(jié)點B存在結(jié)構(gòu)洞，而充當(dāng)聯(lián)系角色的中間人“E”獲得了更多的網(wǎng)絡(luò)收益，因為節(jié)點A和節(jié)點B之間的信息傳播必須由中間人“E”來完成，所以在該網(wǎng)絡(luò)中，中間人“E”的重要性大于其他節(jié)點。

（2）基于結(jié)構(gòu)洞理論的節(jié)點重要性評價

在進(jìn)行節(jié)點重要性評價之前，本文通過節(jié)點的度選取種子節(jié)點，因為只有選取種子節(jié)點后，結(jié)構(gòu)洞的評價系數(shù)才能為社團(tuán)發(fā)現(xiàn)帶來實質(zhì)的價值。節(jié)點重要性評價的計算示意圖如圖2所示：

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

但是，上述公式僅僅衡量了節(jié)點與最鄰近節(jié)點的緊密度關(guān)系，沒有進(jìn)一步考慮鄰居節(jié)點與其他節(jié)點相連的拓?fù)浣Y(jié)構(gòu)會對該節(jié)點的影響程度，比如存在一些重要的“橋接”節(jié)點，那么作為種子節(jié)點，I很可能為了維持自身的地位，需要向“橋接”節(jié)點投入更多的“精力”，才能維持社團(tuán)的穩(wěn)定性。

（3）基于“鄰域”結(jié)構(gòu)洞理論的節(jié)點重要性評價[8]

根據(jù)上述約束系數(shù)的計算公式，CIF=CIG=

[1/8+（1/8）×（1/3）]2。那么，對于種子節(jié)點I來說，節(jié)點F與節(jié)點G對節(jié)點I來說同等重要。但是從圖2得知，與G點相連的鄰居以及鄰居的拓?fù)浣Y(jié)構(gòu)使得I必須對G付出更多的“精力”才能穩(wěn)定社團(tuán)的結(jié)構(gòu)，而上述約束系數(shù)無法體現(xiàn)這一點，因此需要改進(jìn)該約束系數(shù)，可通過“鄰域”結(jié)構(gòu)洞約束系數(shù)來體現(xiàn)這一點。endprint

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

3 基于“鄰域”結(jié)構(gòu)洞的社團(tuán)發(fā)現(xiàn)算法

3.1 算法的思路

基于“鄰域”結(jié)構(gòu)洞的社團(tuán)發(fā)現(xiàn)算法的基本思路如下：

（1）根據(jù)前面改進(jìn)的“鄰域”結(jié)構(gòu)洞約束系數(shù)得到節(jié)點與節(jié)點的關(guān)系評價值，粗略劃分社團(tuán)。

（2）針對上一步劃分的結(jié)果，同時采用模塊度值尋找關(guān)系強(qiáng)度的最優(yōu)“閾值”，對數(shù)據(jù)進(jìn)一步優(yōu)化，從而對社團(tuán)進(jìn)行更精準(zhǔn)的劃分。

3.2 粗略劃分社團(tuán)

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

3.3 采用模塊度值尋找最優(yōu)“閾值”

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

其中，Q為模塊度值；Aij為節(jié)點i和節(jié)點j之間邊的個數(shù)；ki、kj分別為節(jié)點i和節(jié)點j的度；m為拓?fù)浣Y(jié)構(gòu)圖的總邊數(shù)；δ（i， j）表示當(dāng)社區(qū)劃分結(jié)果中節(jié)點i和節(jié)點j屬于同一社區(qū)時，則δ（i， j）=1，當(dāng)社區(qū)劃分結(jié)果中節(jié)點i和節(jié)點j不屬于同一社區(qū)時，則δ（i， j）=0。

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

上述改進(jìn)能夠適應(yīng)移動運營商不同消費類型的用戶社團(tuán)劃分，滿足移動運營商的用戶信息具有動態(tài)性和多樣化的特點，利用該方法進(jìn)行社區(qū)劃分有利于運營商進(jìn)行市場推廣。

3.4 實驗及結(jié)果分析

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

圖4分別反映了三個網(wǎng)絡(luò)數(shù)據(jù)集中關(guān)系閾值θ與社團(tuán)劃分模塊度值的對應(yīng)關(guān)系。

從圖4可知，第一個數(shù)據(jù)集的最優(yōu)關(guān)系閾值為0.060；第二個數(shù)據(jù)集的最優(yōu)關(guān)系閾值為0.065；第三個數(shù)據(jù)集的最優(yōu)關(guān)系閾值為0.055。對圖形進(jìn)一步分析可知，閾值是先單調(diào)遞增后單調(diào)遞減，最優(yōu)的關(guān)系閾值出現(xiàn)在拐點位置，因此本文把閾值區(qū)間定為[0.055， 0.070]。

本文基于上述三個真實的社會網(wǎng)絡(luò)進(jìn)行社團(tuán)發(fā)現(xiàn)的實驗，通過對比這三個社會網(wǎng)絡(luò)真實的社團(tuán)劃分情況，給出了實驗劃分結(jié)果的準(zhǔn)確率對比，如圖5所示。

從圖5可知，除了第三個數(shù)據(jù)集的準(zhǔn)確率較低外，其余數(shù)據(jù)集的準(zhǔn)確率均達(dá)到95%以上，并且網(wǎng)絡(luò)節(jié)點的數(shù)量與社團(tuán)劃分的準(zhǔn)確率沒有必然的聯(lián)系。

4 結(jié)束語

本文基于真實的用戶通信數(shù)據(jù)和所建立通信網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，提出了基于“鄰域”結(jié)構(gòu)洞的社團(tuán)發(fā)現(xiàn)算法，首先通過節(jié)點的度提取種子節(jié)點，然后采用改進(jìn)的“鄰域”結(jié)構(gòu)洞約束系數(shù)計算節(jié)點與鄰居的關(guān)系強(qiáng)度，最后通過采用模塊度值確定社團(tuán)劃分的最優(yōu)“關(guān)系閾值”。實驗證明，基于“鄰域”結(jié)構(gòu)洞的社團(tuán)發(fā)現(xiàn)算法具有較高精度。本文的方法僅適用于特定數(shù)量的網(wǎng)絡(luò)節(jié)點，未來的研究將會針對特大型網(wǎng)絡(luò)的社團(tuán)發(fā)現(xiàn)算法進(jìn)行優(yōu)化，采用啟發(fā)式算法進(jìn)一步提升社團(tuán)發(fā)現(xiàn)的效率和精度。

參考文獻(xiàn)：

[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] 張洋洋. 復(fù)雜網(wǎng)絡(luò)中社團(tuán)結(jié)構(gòu)發(fā)現(xiàn)算法的研究與實現(xiàn)[D]. 南京： 南京理工大學(xué)， 2014.

[6] 何東曉. 復(fù)雜網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)發(fā)現(xiàn)方法研究[D]. 長春： 吉林大學(xué)， 2014.

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

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

[9] 許鴻. 基于鄰居相似性和半監(jiān)督社團(tuán)檢測算法研究[D]. 蘭州： 蘭州大學(xué)， 2014.

[10] 華燁. 基于相對關(guān)系親密度的局部社團(tuán)發(fā)現(xiàn)算法研究[D]. 合肥： 中國科學(xué)技術(shù)大學(xué)， 2014.endprint