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

黃藍(lán)會(huì)(寶雞文理學(xué)院計(jì)算機(jī)學(xué)院， 寶雞 721016)

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

黃藍(lán)會(huì)
(寶雞文理學(xué)院計(jì)算機(jī)學(xué)院， 寶雞 721016)

基于復(fù)雜網(wǎng)絡(luò)模型，將數(shù)據(jù)挖掘中的聚類分析方法應(yīng)用到社團(tuán)發(fā)現(xiàn)中，提出了結(jié)合模塊度的基于層次聚類的社團(tuán)發(fā)現(xiàn)算法。由層次樹(shù)得到的社團(tuán)結(jié)構(gòu)層次清晰，仿真實(shí)驗(yàn)證明，利用該算法，當(dāng)信號(hào)傳播次數(shù)取值為3時(shí)社團(tuán)劃分準(zhǔn)確度最高。

復(fù)雜網(wǎng)絡(luò)； 網(wǎng)絡(luò)聚類； 數(shù)據(jù)挖掘； 社團(tuán)發(fā)現(xiàn)

0 引言

復(fù)雜網(wǎng)絡(luò)是一個(gè)涉及數(shù)學(xué)、統(tǒng)計(jì)物理學(xué)、計(jì)算機(jī)科學(xué)、生態(tài)學(xué)、生物學(xué)、經(jīng)濟(jì)學(xué)、社會(huì)學(xué)、自動(dòng)控制等眾多領(lǐng)域的交叉學(xué)科。[1]復(fù)雜網(wǎng)絡(luò)利用數(shù)學(xué)上圖論的概念，將網(wǎng)絡(luò)中的個(gè)體抽象為圖中的節(jié)點(diǎn)，個(gè)體之間的相互作用抽象為圖中節(jié)點(diǎn)之間的連邊。因此，任何包含大量個(gè)體單元的復(fù)雜系統(tǒng)都可以當(dāng)作復(fù)雜網(wǎng)絡(luò)來(lái)研究，如豆瓣網(wǎng)、當(dāng)當(dāng)網(wǎng)等。復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)具有小世界、無(wú)標(biāo)度、高聚集和社團(tuán)結(jié)構(gòu)等特性，其中社團(tuán)結(jié)構(gòu)的特點(diǎn)是同一個(gè)社團(tuán)內(nèi)部節(jié)點(diǎn)之間連接緊密，不同社團(tuán)之間連接松散。針對(duì)復(fù)雜網(wǎng)絡(luò)進(jìn)行社團(tuán)劃分是數(shù)據(jù)挖掘領(lǐng)域最活躍的研究方向之一，比如豆瓣網(wǎng)中大部分用戶是根據(jù)自己的興趣愛(ài)好選擇好友，社團(tuán)劃分可以讓用戶注冊(cè)成功后快捷地找到其想加入的群體；當(dāng)當(dāng)網(wǎng)進(jìn)行社團(tuán)劃分后，可以針對(duì)同一社團(tuán)群體用戶建立推薦系統(tǒng)，引導(dǎo)用戶消費(fèi)。

聚類分析是將物理或抽象對(duì)象的集合分成由類似的對(duì)象組成的多個(gè)類(Class)或簇(Cluster)的分析過(guò)程，聚類分析的結(jié)果是同一個(gè)簇中的對(duì)象有極大的相似性，而不同簇之間的對(duì)象則差別較大[2]。從定義上發(fā)現(xiàn)復(fù)雜網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)的概念和聚類分析中的類的概念很相似，復(fù)雜網(wǎng)絡(luò)中的社團(tuán)相當(dāng)于聚類分析中的類，復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)的連接相當(dāng)于類的相似性，尋找復(fù)雜網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)相當(dāng)于與在聚類數(shù)據(jù)中發(fā)現(xiàn)數(shù)據(jù)潛在的規(guī)律。本文考慮將聚類分析方法應(yīng)用到復(fù)雜網(wǎng)絡(luò)的社團(tuán)發(fā)現(xiàn)中。

1 相關(guān)研究

Hu等人提出了在復(fù)雜網(wǎng)絡(luò)中利用信號(hào)傳播將網(wǎng)絡(luò)中的節(jié)點(diǎn)轉(zhuǎn)化成代數(shù)空間上的數(shù)據(jù)對(duì)象的方法[3]。Pan等人[4]提出了基于相似度的復(fù)雜網(wǎng)絡(luò)社團(tuán)劃分算法，該算法采用節(jié)點(diǎn)之間的共同鄰居數(shù)來(lái)對(duì)節(jié)點(diǎn)之間的相似度進(jìn)行評(píng)估，進(jìn)而對(duì)網(wǎng)絡(luò)進(jìn)行社團(tuán)劃分。Lou等人[5]通過(guò)共同鄰居對(duì)節(jié)點(diǎn)相似度進(jìn)行計(jì)算，然后在此基礎(chǔ)上使用標(biāo)簽傳播算法進(jìn)行社團(tuán)劃分。Yuan等人[6]提出了一種基于簇相似度的復(fù)雜網(wǎng)絡(luò)社團(tuán)劃分算法，該算法主要用于檢測(cè)邊密度較高的復(fù)雜網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)。王興元等人[7]在共同鄰居的基礎(chǔ)上提出了節(jié)點(diǎn)依賴度，并依據(jù)節(jié)點(diǎn)依賴度對(duì)社團(tuán)進(jìn)行劃分。

2 社團(tuán)發(fā)現(xiàn)算法

本文根據(jù)豆瓣網(wǎng)設(shè)計(jì)了一個(gè)基于復(fù)雜網(wǎng)絡(luò)的在線社會(huì)網(wǎng)絡(luò)演化模型[8]，該模型將網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)看作一個(gè)信號(hào)節(jié)點(diǎn)，具有n維向量，n個(gè)節(jié)點(diǎn)就有n個(gè)n維向量，將這n個(gè)向量標(biāo)準(zhǔn)化后投射到代數(shù)空間后，認(rèn)為每個(gè)向量即為代數(shù)空間中的一個(gè)數(shù)據(jù)。定義了相似性系數(shù)公式，通過(guò)比較兩個(gè)節(jié)點(diǎn)的相似性系數(shù)來(lái)判斷是否屬于同一社團(tuán)。

復(fù)雜網(wǎng)絡(luò)中層次凝聚聚類方法被廣泛用來(lái)進(jìn)行社團(tuán)的劃分，其基本思想是先將網(wǎng)絡(luò)中的每一個(gè)節(jié)點(diǎn)視為一個(gè)社團(tuán)，同時(shí)設(shè)定一個(gè)判斷兩社團(tuán)相似的衡量標(biāo)準(zhǔn)，然后計(jì)算社團(tuán)之間的相似度，相似度高的社團(tuán)合并后產(chǎn)生一個(gè)新的社團(tuán)，繼而重新計(jì)算相似度，直至所有節(jié)點(diǎn)都凝聚成一個(gè)社團(tuán)或者到達(dá)網(wǎng)絡(luò)中最大的Q值后終止凝聚，通過(guò)這個(gè)思想最終得到的是一棵層次聚類樹(shù)。

基于上述定義，本文設(shè)計(jì)了一個(gè)考慮局部模塊度，基于層次聚類的社團(tuán)發(fā)現(xiàn)算法，算法步驟如下：

(1) 假定復(fù)雜網(wǎng)絡(luò)定義為G=(V,E,R,F)；

(4) 計(jì)算所有節(jié)點(diǎn)的綜合特征值CFi，并按照特征值的升序排列；

(5) 選擇CFi最小的節(jié)點(diǎn)作為起始節(jié)點(diǎn)，設(shè)置該節(jié)點(diǎn)的局部模塊度值為0；

(6) 合并節(jié)點(diǎn)，選擇節(jié)點(diǎn)的相似性系數(shù)disij最大的兩個(gè)合并，根據(jù)合并后的Q值判斷是否停止聚類，當(dāng)Q值最大時(shí)得到最終的社團(tuán)分類。

3 實(shí)驗(yàn)結(jié)果與分析

本文以豆瓣網(wǎng)為實(shí)證網(wǎng)絡(luò)，使用自己編寫(xiě)的網(wǎng)絡(luò)數(shù)據(jù)抓取及解析程序[10]，采用多次仿真取平均值的方法來(lái)獲得演化模型的網(wǎng)絡(luò)拓?fù)渲?。本次?shí)驗(yàn)主要測(cè)試傳播次數(shù)T的選擇和社團(tuán)劃分準(zhǔn)確性的關(guān)系，算法中仿真網(wǎng)絡(luò)選擇100個(gè)節(jié)點(diǎn)，T值從1-10，Cout表示每個(gè)節(jié)點(diǎn)和其他社團(tuán)節(jié)點(diǎn)之間有連邊的最大值，當(dāng)Cout變化時(shí)，T取不同的值社團(tuán)劃分的準(zhǔn)確率，如圖1所示。

圖1 T值的選擇與社團(tuán)劃分準(zhǔn)確率的關(guān)系

從圖1中可以看到，Cout=6和Cout=4比較，Cout取值越大，社團(tuán)發(fā)現(xiàn)準(zhǔn)確率變差，同時(shí)發(fā)現(xiàn)T的取值和Cout的關(guān)系有一個(gè)共同的規(guī)律，當(dāng)T=3時(shí)，都是該條折線圖準(zhǔn)確率的最高點(diǎn)，因此可以得出一個(gè)結(jié)論，當(dāng)T=3時(shí)，社團(tuán)劃分準(zhǔn)確率最高。

4 總結(jié)

社團(tuán)發(fā)現(xiàn)是復(fù)雜網(wǎng)絡(luò)的重要研究?jī)?nèi)容之一，互聯(lián)網(wǎng)上存在著大量Web 服務(wù)，這些服務(wù)通過(guò)用戶的需求的交互連接，形成了一個(gè)復(fù)雜的交互網(wǎng)絡(luò)，發(fā)現(xiàn)并利用這些交互網(wǎng)絡(luò)上的社團(tuán)結(jié)構(gòu)有助于理解這類復(fù)雜軟件系統(tǒng)的行為，促進(jìn)在網(wǎng)絡(luò)中開(kāi)展信息分享、商品推薦、廣告投放等個(gè)性化商業(yè)應(yīng)用。

[1] 郭世澤, 陸哲明. 復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論[M].北京:科學(xué)出版社, 2012.

[2] Jain A K, Murty M N, Flynn P J. Data clustering: a review[J]. ACM Computing Surveys(CSUR),1999,3l(3):264-323.

[3] Yan-qing Hu，Meng-hui Li，Peng Zhang. Community detection by signaling on complex networks[J]. Phys. Rev. E,2008,78:016115.

[4] Pan Y, Li D H, Liu J G, et al. Detecting community structure in complex networks via node similarity [J]. Physical A Statistical Mechanics & Its Applications, 2010, 389(14):2849-2857.

[5] Lou Hao, Li Sheng hong, Zhao Yu xin. Detecting community structure using label propagation with weighted coherent neighborhood propinquity[J]. Physical A: Statistical Mechanics and its Applications, 2013, 392(14): 3095-3105.

[6] Yuan C, Chai Y. Group similarity based algorithm for network community structure detection[J]. Acta Physica Sinica, 2012, 61(21):514-518.

[7] 王興元, 趙仲祥.基于節(jié)點(diǎn)間依賴度的社團(tuán)結(jié)構(gòu)劃分方法[J].物理學(xué)報(bào), 2014, 63(17):178901.

[8] 黃藍(lán)會(huì). 基于社會(huì)媒體網(wǎng)絡(luò)的聚類方法的研究[J].微型電腦應(yīng)用,2016,32(6):1-2.

[9] 賓晟. 基于多子網(wǎng)復(fù)合復(fù)雜網(wǎng)絡(luò)模型的多關(guān)系在線社會(huì)網(wǎng)絡(luò)研究[D].濟(jì)南：山東科技大學(xué),2014.

[10] 黃藍(lán)會(huì). 基于在線社會(huì)網(wǎng)絡(luò)的網(wǎng)絡(luò)爬蟲(chóng)的研究和設(shè)計(jì)[J].電子設(shè)計(jì)工程,2014,22(6):106-108.

ReseachontheCommunityDiscoveryinComplexNetwork

Huang Lanhui
(School of Computer, Baoji University of Arts and Science, Baoji 721016)

Based on complex network，clustering analysis method in data mining is applied to the research of community detection. A new measured method for node similarity--node dissimilarity coefficient in multi-subnet composited complex network is proposed. A community detection algorithm in complex network based on hierarchical clustering is proposed. By using this algorithm, community classification derive from the hierarchical tree is very clear. Experiments prove that when the number of signal propagation is 3, high accuracy rate of community classification are

in network.

Complex network; Network clustering; Data Mining; Community discovery

TP311

A

2016.07.25)

國(guó)家自然科學(xué)基金(61379030)，陜西省教育廳專項(xiàng)科研項(xiàng)目(15JK1028)

黃藍(lán)會(huì)(1980-)，女，湖南岳陽(yáng)人，碩士，講師，研究方向：物聯(lián)網(wǎng)應(yīng)用，數(shù)據(jù)挖掘.

1007-757X(2017)10-0011-02