社會(huì)網(wǎng)絡(luò)頂點(diǎn)間相似性度量及其應(yīng)用*

陳 曉，郭景峰，張春英

1.燕山大學(xué) 信息科學(xué)與工程學(xué)院，河北 秦皇島 066004

2.華北理工大學(xué) 遷安學(xué)院，河北 遷安 064400

3.河北省計(jì)算機(jī)虛擬技術(shù)與系統(tǒng)集成重點(diǎn)實(shí)驗(yàn)室，河北 秦皇島 066004

4.華北理工大學(xué) 理學(xué)院，河北 唐山 063009

社會(huì)網(wǎng)絡(luò)頂點(diǎn)間相似性度量及其應(yīng)用*

陳 曉1,2,3，郭景峰1,3+，張春英4

1.燕山大學(xué) 信息科學(xué)與工程學(xué)院，河北 秦皇島 066004

2.華北理工大學(xué) 遷安學(xué)院，河北 遷安 064400

3.河北省計(jì)算機(jī)虛擬技術(shù)與系統(tǒng)集成重點(diǎn)實(shí)驗(yàn)室，河北 秦皇島 066004

4.華北理工大學(xué) 理學(xué)院，河北 唐山 063009

Abstract:Set pair analysis as the mathematical theory of dealing with the interaction system of certainty and uncertainty,can be used to deal with the complexity social network of uncertain relationship.Firstly,based on the application of set pair analysis theory,this paper takes social network as an identical-different-contrary system(certain and uncertain system).Based on set pair connection degree to descript the identical,different and contrary relations between vertices,considering the contribution of local features and the topological structure to the vertex similarity,this paper defines the similarity between vertices based on the relation connection degree taking into account weightand clustering coefficient.The measurement can better describe network structure characteristics,overcome the underestimating for some similarity between vertices based on traditional local structures,and reduce the computational complexity of global similarity indices.Secondly,in order to utilize the similarity indices to community discovering,combined with agglomerative hierarchical clustering algorithm,it is applicable to detect community structures in complex networks with any object that has similarity measurement.Finally,through the experiment of community mining on the social network,and compared with the typical algorithms of community discovering,the experimental results verify the correctness and effectiveness of the similarity measurement.

Key words:social network;similarity;set pair;identical-different-contrary relations;community discovering

集對(duì)分析作為處理系統(tǒng)確定性與不確定性相互作用的數(shù)學(xué)理論，可用來(lái)處理存在不確定關(guān)系的復(fù)雜社會(huì)網(wǎng)絡(luò)。首先，應(yīng)用集對(duì)分析理論，將社會(huì)網(wǎng)絡(luò)作為一個(gè)同異反系統(tǒng)（確定不確定系統(tǒng)），采用集對(duì)聯(lián)系度刻畫(huà)頂點(diǎn)間的同異反關(guān)系，綜合考慮頂點(diǎn)的局部特征和拓?fù)浣Y(jié)構(gòu)對(duì)頂點(diǎn)相似性的貢獻(xiàn)，提出加權(quán)聚集系數(shù)聯(lián)系度的頂點(diǎn)間相似性度量方法。該度量方法可以更好地刻畫(huà)網(wǎng)絡(luò)結(jié)構(gòu)特征，克服傳統(tǒng)局部相似性度量指標(biāo)對(duì)某些頂點(diǎn)間相似性值的低估，降低全局相似性度量指標(biāo)的計(jì)算復(fù)雜度。其次，為了將該相似性度量指標(biāo)應(yīng)用于社區(qū)發(fā)現(xiàn)，與凝聚型層次聚類(lèi)算法相結(jié)合，使其適用于具有相似性度量對(duì)象的復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)問(wèn)題。最后，在社會(huì)網(wǎng)絡(luò)上進(jìn)行社區(qū)挖掘?qū)嶒?yàn)，并與經(jīng)典社區(qū)發(fā)現(xiàn)算法進(jìn)行比較，實(shí)驗(yàn)結(jié)果表明了該相似性度量指標(biāo)的正確性及有效性。

社會(huì)網(wǎng)絡(luò)；相似性；集對(duì)；同異反關(guān)系；社區(qū)發(fā)現(xiàn)

1 引言

隨著社會(huì)網(wǎng)絡(luò)分析在各領(lǐng)域的廣泛應(yīng)用，社會(huì)網(wǎng)絡(luò)分析技術(shù)[1]受到國(guó)內(nèi)外學(xué)者的廣泛關(guān)注，已成為當(dāng)前的研究熱點(diǎn)。社會(huì)網(wǎng)絡(luò)分析技術(shù)以圖論為基礎(chǔ)，通常將社會(huì)網(wǎng)絡(luò)表示為一個(gè)二元組G=(V,E)，其中頂點(diǎn)集V代表網(wǎng)絡(luò)中的個(gè)體，邊集E代表網(wǎng)絡(luò)中個(gè)體間的聯(lián)系。頂點(diǎn)間相似性的度量方法作為社會(huì)網(wǎng)絡(luò)分析的基礎(chǔ)，對(duì)社區(qū)發(fā)現(xiàn)、社區(qū)演化和鏈接預(yù)測(cè)具有重要的理論意義實(shí)用價(jià)值。

現(xiàn)有頂點(diǎn)間相似性[2]的計(jì)算方法主要分為3類(lèi)：（1）基于網(wǎng)絡(luò)全局信息的相似性度量指標(biāo)，如Katz指標(biāo)[3]、LHN（Leicht-Holme-Newman）指標(biāo)[4]、ACT（average commute time）指標(biāo)[5-6]、RWR（random walk with restart）指標(biāo)[7]等；（2）基于頂點(diǎn)公共鄰居的局部相似性度量指標(biāo)，如 CN（common neighbor）指標(biāo)[8]、Salton（又稱(chēng)為Cosine）指標(biāo)[9]、Sφrensen指標(biāo)[9]、Jaccard指標(biāo)[10]等；（3）介于全局和局部之間的半局部相似性度量指標(biāo)，如LP（local path）指標(biāo)[11]、LRW（local random walk）指標(biāo)[12]、RALP（resource allocation along local path）[13]等。其中，全局相似性度量指標(biāo)需要考慮網(wǎng)絡(luò)的整體結(jié)構(gòu)關(guān)系，通常利用網(wǎng)絡(luò)的鄰接矩陣計(jì)算逆矩陣和矩陣的特征根，或通過(guò)遍歷頂點(diǎn)間路徑度量相似性等。全局性方法雖然擁有相對(duì)較高的精度，但卻具有較高的時(shí)間和空間復(fù)雜度，不適宜較大規(guī)模的網(wǎng)絡(luò)。文獻(xiàn)[14]的研究表明，當(dāng)路徑長(zhǎng)度從2增加到5時(shí)，可以增大相似性的精度，而當(dāng)路徑長(zhǎng)度大于5時(shí)，相似性精度變化很小。局部相似性度量指標(biāo)由于僅考慮頂點(diǎn)的最近鄰，具有較低的時(shí)間復(fù)雜度，卻低估了直接連接頂點(diǎn)間和通過(guò)關(guān)聯(lián)路徑連接的頂點(diǎn)間的相似性。因此，僅利用網(wǎng)絡(luò)個(gè)體間相同的確定性評(píng)估頂點(diǎn)間的相似性，不能全面體現(xiàn)網(wǎng)絡(luò)中個(gè)體間的關(guān)系。如何基于網(wǎng)絡(luò)中的確定與不確定關(guān)系，更準(zhǔn)確地定義頂點(diǎn)間的相似性是本文的研究重點(diǎn)。

集對(duì)分析[15]（set pair analysis，SPA）理論是我國(guó)學(xué)者趙克勤于l989年提出的理論方法，是一種用聯(lián)系度統(tǒng)一處理模糊、隨機(jī)和信息不完全所致不確定性系統(tǒng)的理論和方法，在科學(xué)技術(shù)和社會(huì)經(jīng)濟(jì)的許多領(lǐng)域得到了廣泛應(yīng)用。2011年，文獻(xiàn)[16]首先將集對(duì)理論應(yīng)用到社會(huì)網(wǎng)絡(luò)分析中，提出了集對(duì)社交網(wǎng)絡(luò)分析模型及其性質(zhì)，為基于集對(duì)理論的社會(huì)網(wǎng)絡(luò)分析研究拉開(kāi)了序幕。2013年，文獻(xiàn)[17-18]基于集對(duì)理論和共同鄰居提出了一種新的頂點(diǎn)間相似性度量方法，并根據(jù)社會(huì)網(wǎng)絡(luò)特性分別實(shí)現(xiàn)了靜態(tài)和動(dòng)態(tài)α關(guān)系社區(qū)的挖掘算法，證明了α關(guān)系社區(qū)的挖掘更能體現(xiàn)社區(qū)存在的動(dòng)態(tài)性。2014年，文獻(xiàn)[19]基于屬性圖提出了集對(duì)社交網(wǎng)絡(luò)實(shí)體相似性的計(jì)算方法，并基于集對(duì)態(tài)勢(shì)實(shí)現(xiàn)了社區(qū)發(fā)現(xiàn)。然而，現(xiàn)有基于集對(duì)的頂點(diǎn)間相似性度量方法，僅考慮了網(wǎng)絡(luò)中不確定的共同鄰居屬性數(shù)量對(duì)社區(qū)形成及網(wǎng)絡(luò)分析的影響，忽略了頂點(diǎn)間的拓?fù)浣Y(jié)構(gòu)、頂點(diǎn)的度等對(duì)頂點(diǎn)間相似性的影響。

本文將無(wú)向無(wú)權(quán)無(wú)符號(hào)的社會(huì)網(wǎng)絡(luò)作為研究對(duì)象，基于集對(duì)分析理論的思想，將社會(huì)網(wǎng)絡(luò)作為一個(gè)同異反系統(tǒng)（確定不確定系統(tǒng)），在考慮頂點(diǎn)度和頂點(diǎn)間拓?fù)浣Y(jié)構(gòu)兩個(gè)因素對(duì)頂點(diǎn)相似度的影響前提下，提出了一種新的頂點(diǎn)間相似性度量指標(biāo)——加權(quán)聚集系數(shù)聯(lián)系度。為了更深入地驗(yàn)證本文提出的頂點(diǎn)間相似性度量方法，將該相似性指標(biāo)應(yīng)用到社會(huì)網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)中，通過(guò)實(shí)驗(yàn)結(jié)果進(jìn)一步驗(yàn)證頂點(diǎn)間相似性度量指標(biāo)的正確性及有效性。

本文主要貢獻(xiàn)如下：

（1）提出加權(quán)聚集系數(shù)聯(lián)系度的頂點(diǎn)間相似性度量方法。綜合考慮網(wǎng)絡(luò)局部關(guān)系（共同鄰居等）和網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)屬性（聚集系數(shù)和頂點(diǎn)間路徑等），采用聯(lián)系度刻畫(huà)影響頂點(diǎn)間相似性的頂點(diǎn)集合的同異反關(guān)系，提出加權(quán)聚集系數(shù)聯(lián)系度的頂點(diǎn)間相似性度量方法。該方法根據(jù)宏觀異（不確定）關(guān)系F和微觀異（不確定）關(guān)系i轉(zhuǎn)化為同關(guān)系S時(shí)對(duì)頂點(diǎn)間相似性的貢獻(xiàn)，考慮頂點(diǎn)間連接密度影響，采用頂點(diǎn)的聚集系數(shù)作為i的取值方法；根據(jù)頂點(diǎn)度和頂點(diǎn)間路徑對(duì)相似性貢獻(xiàn)的影響，為同異反關(guān)系進(jìn)行加權(quán)。該方法既避免了從單一數(shù)量上考慮頂點(diǎn)間同異反關(guān)系的不全面性，又避免了計(jì)算頂點(diǎn)間路徑的復(fù)雜性，不僅更好地體現(xiàn)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)特點(diǎn)，而且可以提高相似性指標(biāo)的精確性。

（2）提出頂點(diǎn)間相似性優(yōu)先凝聚和社區(qū)間均值凝聚相結(jié)合的層次聚類(lèi)算法VSFCM（vertices similarity first and communities mean）。傳統(tǒng)基于平均距離的凝聚型層次聚類(lèi)算法有大量更新平均距離的操作并且有社區(qū)聚類(lèi)不合理現(xiàn)象。為了確保相似性大的頂點(diǎn)在同一社區(qū)中，相似性小的頂點(diǎn)在不同社區(qū)中，提出VSFCM算法，即將相似性大的頂點(diǎn)對(duì)優(yōu)先合并為小社區(qū)，然后再進(jìn)行社區(qū)間的合并，有效避免了頻繁更新操作，提高了算法效率。

本文組織結(jié)構(gòu)如下：第2章介紹頂點(diǎn)間相似性度量指標(biāo)的研究現(xiàn)狀；第3章討論基于聯(lián)系度的頂點(diǎn)間相似性模型及定理；第4章對(duì)社區(qū)發(fā)現(xiàn)算法進(jìn)行描述；第5章通過(guò)實(shí)驗(yàn)驗(yàn)證頂點(diǎn)間相似性度量指標(biāo)的正確性和合理性；最后總結(jié)全文，并對(duì)下一步工作進(jìn)行展望。

2 相關(guān)工作及問(wèn)題定義

現(xiàn)有多種計(jì)算頂點(diǎn)間相似性的方法，其中基于鄰接點(diǎn)（局部）的相似性方法具有較低的時(shí)間復(fù)雜度，文獻(xiàn)[2]研究結(jié)果表明，指標(biāo)RA（resource allocation）的計(jì)算精度最佳，CN次之；基于路徑（全局）的相似性方法具有較高的時(shí)間復(fù)雜度，但具有較好的計(jì)算精度，如Katz；基于聯(lián)系度的方法是一種介于局部和全局之間的半全局方法，是借鑒同異反關(guān)系定義相似性的新方法。因此，主要介紹CN、RA、Katz和現(xiàn)有兩種基于聯(lián)系度的頂點(diǎn)間相似性定義方法。

2.1 基于鄰接點(diǎn)（局部）的相似性方法

公共鄰居CN指標(biāo)[8]如式（1）所示：

資源配置RA指標(biāo)[11]如式（2）所示：

2.2 基于路徑（全局）的相似性方法

Katz指標(biāo)[3]如式（3）所示：

通過(guò)實(shí)驗(yàn)證明β=0.000 5的實(shí)驗(yàn)效果較好[20]，并保證指標(biāo)收斂于(I-βA)-1-I。

2.3 基于聯(lián)系度的相似性方法

集對(duì)理論的基本定義和性質(zhì)可以見(jiàn)文獻(xiàn)[15]。

文獻(xiàn)[17-18]首先將聯(lián)系度應(yīng)用于社會(huì)網(wǎng)絡(luò)分析領(lǐng)域，以網(wǎng)絡(luò)結(jié)構(gòu)為基礎(chǔ)，令頂點(diǎn)vk和vs為兩個(gè)研究對(duì)象，將頂點(diǎn)間的鄰接關(guān)系作為頂點(diǎn)屬性，兩個(gè)頂點(diǎn)的共有屬性記為N，則頂點(diǎn)間相似性度量指標(biāo)定義如下。

注：N(v)1表示頂點(diǎn)v的1級(jí)鄰居；N(v)2表示頂點(diǎn)v的2級(jí)鄰居，具體定義詳見(jiàn)下節(jié)。

Fig.1 Instance networkA圖1 實(shí)例網(wǎng)絡(luò)A

3 基于聯(lián)系度的頂點(diǎn)間相似性模型

基于聯(lián)系度刻畫(huà)頂點(diǎn)間相似性度量工作的重點(diǎn)是，如何定義影響頂點(diǎn)間相似度的頂點(diǎn)集合的同異反關(guān)系。為了更好地表達(dá)鄰居頂點(diǎn)對(duì)頂點(diǎn)間相似性的影響，介紹相關(guān)定義如下。

3.1 相關(guān)定義

定義1（頂點(diǎn)鄰居集）給定社會(huì)網(wǎng)絡(luò)G=(V,E),?vk∈V，vk的1級(jí)鄰居集記為N(vk)1，如式（6）所示。

vk的2級(jí)鄰居集記為N(vk)2，如式（7）所示。

定義2（頂點(diǎn)的共同鄰居集）給定社會(huì)網(wǎng)絡(luò)G=(V,E)，?vk,vs,vq∈V，若vq∈N(vk)1?N(vs)1，則vq為vk和vs的共同1級(jí)鄰居。vk和vs的共同1級(jí)鄰居集記為CN(vk,vs)1，如式（8）所示。

同理vk和vs的共同2級(jí)鄰居集記為CN(vk,vs)2,如式（9）所示。

同理vk和vs的共同1?2級(jí)鄰居集記為CN(vk,vs)1?2,如式（10）所示。

同理vk和vs的共同2?1級(jí)鄰居集記為CN(vk,vs)2?1,如式（11）所示。

vk和vs的鄰居集關(guān)系如圖2所示。其中，代表CN(vk,vs)1，代表CN(vk,vs)1?2或CN(vk,vs)2?1，代表CN(vk,vs)2。

Fig.2 Neighbors set relation betweenvkandvs圖2 頂點(diǎn)vk和vs的鄰居集關(guān)系

3.2 頂點(diǎn)間相似性模型

在基于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的頂點(diǎn)間相似性度量方法中，如果兩個(gè)頂點(diǎn)間共同鄰居和短路徑越多，可能使得兩個(gè)頂點(diǎn)的相似性越強(qiáng)?；谶@一思想，將兩個(gè)頂點(diǎn)的共同1級(jí)鄰居作為相同屬性，將1?2、2?1和2級(jí)鄰居作為宏觀層次上的不確定屬性，可以更好地刻畫(huà)不確定屬性對(duì)相同的確定屬性的影響。具體頂點(diǎn)間同異反關(guān)系定義如下。

定義3（頂點(diǎn)間同異反關(guān)系）給定社會(huì)網(wǎng)絡(luò)G=(V,E),?vk,vs∈V，相同屬性為vk和vs的共同1級(jí)鄰居，即S=|CN(vk,vs)1|；相異屬性為vk和vs的共同1?2、2?1和2級(jí)鄰居，即F=|CN(vk,vs)1?2|+|CN(vk,vs)2?1|+|CN(vk,vs)2|;其余為vk和vs的相反屬性，即P=N-S-F，其中，N=|V|。

然而，如果僅從頂點(diǎn)間同異反關(guān)系的個(gè)數(shù)方面刻畫(huà)頂點(diǎn)間的相似性，將存在明顯的局限性和不合理性。因此，為了更準(zhǔn)確地刻畫(huà)頂點(diǎn)間的相似性，本文綜合考慮網(wǎng)絡(luò)密度和頂點(diǎn)度等特征，對(duì)各屬性關(guān)系進(jìn)行加權(quán)，提出基于加權(quán)聚集系數(shù)的頂點(diǎn)間聯(lián)系度，具體定義如下。

定義4（相似性指標(biāo)WCCD（weighted clustering coefficient connection degree））給定社會(huì)網(wǎng)絡(luò)G=(V,E),?vk,vs∈V，基于加權(quán)聚集系數(shù)的頂點(diǎn)間聯(lián)系度SWCCDks如式（12）所示。

其中，N、S、F、P的含義如定義3所示，(1)1×S、(1)1×F和(1)1×P分別代表相同、相異和相反屬性的行向量，向量值均為1；w(vi)為頂點(diǎn)對(duì)應(yīng)的權(quán)值；(i(vi))F×1向量值為相異屬性頂點(diǎn)vi對(duì)應(yīng)的差異i值，j表示相反屬性的標(biāo)記作用。

式（12）中存在3個(gè)參數(shù)(i(vi))F×1、w(vi)和j，這3個(gè)參數(shù)如何取值對(duì)計(jì)算頂點(diǎn)間聯(lián)系度起著至關(guān)重要的影響，下面主要介紹這3個(gè)參數(shù)的取值方法。

3.2.1i的取值方法

基于集對(duì)理論思想，i作為微觀層次上的差異標(biāo)記，如何取值對(duì)不確定屬性如何向確定屬性轉(zhuǎn)換有著至關(guān)重要的影響。現(xiàn)有基于灰度[21]等的取值方法不能直接應(yīng)用于社會(huì)網(wǎng)絡(luò)中頂點(diǎn)間相似性的計(jì)算中，需要重新定義差異標(biāo)記i的取值方法。

在圖2所示的網(wǎng)絡(luò)中，v2∈CN(v1,v7)1?2，v5∈CN(v1,v7)2?1,由于頂點(diǎn)v2和v5的不同，使得它們轉(zhuǎn)化為CN(v1,v7)1的可能性也是不同的。考慮到不同的不確定屬性向確定屬性轉(zhuǎn)換的不同可能性，針對(duì)不同屬性將i的取值轉(zhuǎn)化為一個(gè)向量組；考慮到網(wǎng)絡(luò)的密度結(jié)構(gòu)特性，采用頂點(diǎn)的聚集系數(shù)[22]值來(lái)量化該不確定屬性的i值。由于不確定屬性包括頂點(diǎn)對(duì)的共同1?2、2?1和2級(jí)鄰居，分別考慮上述3種情況轉(zhuǎn)換為共同1級(jí)鄰居的可能性來(lái)量化i值，具體計(jì)算方法如下。

3.2.2w的取值方法

在圖1所示的網(wǎng)絡(luò)中，v2,v4∈CN(v1,v3)1，由于v2和v4度的值不同，可見(jiàn)它們對(duì)v1和v3聯(lián)系度的貢獻(xiàn)也不盡相同。基于“頂點(diǎn)度越小對(duì)聯(lián)系度的貢獻(xiàn)越大，頂點(diǎn)度越大對(duì)聯(lián)系度的貢獻(xiàn)越小”的啟發(fā)式思想，以及路徑的可達(dá)性以及轉(zhuǎn)移概率來(lái)描述頂點(diǎn)對(duì)聯(lián)系度的貢獻(xiàn)。本文中頂點(diǎn)類(lèi)型主要分為直接相連，共同1、1?2、2?1和2級(jí)鄰居頂點(diǎn)等，下面分別介紹以上5種類(lèi)型的頂點(diǎn)權(quán)值w(vi)的定義方法，其中d(vi)表示頂點(diǎn)vi的度。

3.2.3j的取值方法

在社區(qū)發(fā)現(xiàn)算法中，由于期望將相似性大的頂點(diǎn)劃分到同一社區(qū)，則更希望考慮頂點(diǎn)間相同屬性，以及不確定性屬性轉(zhuǎn)向相同屬性的程度，對(duì)頂點(diǎn)間相似性的貢獻(xiàn)值。因此，令式（12）中j=0，忽略對(duì)立屬性的影響，認(rèn)為不確定屬性全部轉(zhuǎn)向相同屬性。

4 社會(huì)網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)算法

社區(qū)發(fā)現(xiàn)的主要目的是將社會(huì)網(wǎng)絡(luò)G=(V,E)劃分為K個(gè)互不相交的子社區(qū)，使得，且Gki?Gkj=?(i≠j)，保證同一社區(qū)內(nèi)頂點(diǎn)間的關(guān)系緊密，不同社區(qū)關(guān)系稀疏。因此，基于相似性的社區(qū)發(fā)現(xiàn)問(wèn)題就可以轉(zhuǎn)化為基于相似性的凝聚層次聚類(lèi)問(wèn)題。為了實(shí)現(xiàn)社區(qū)發(fā)現(xiàn)，首先給出社區(qū)間相似性的計(jì)算方法。

定義5（社區(qū)間相似性）設(shè)CK=(VK,EK)和CS=(VS,ES)為社會(huì)網(wǎng)絡(luò)中的兩個(gè)社區(qū)，則社區(qū)CK和CS間的相似性表示社區(qū)間頂點(diǎn)對(duì)相似性的均值，記為Sim(CK,CS)，如式（13）所示。

經(jīng)典凝聚層次聚類(lèi)AGNES（agglomerative nesting）算法[23]在進(jìn)行社區(qū)合并時(shí)，首先計(jì)算頂點(diǎn)間的相似性值Sim(vk,vs)，其次選取max{Sim(vk,vs)}，然后將頂點(diǎn)vk和vs合并，記為Cnew。該方法在每次合并后，均需要重新計(jì)算Cnew與其他頂點(diǎn)或社區(qū)的相似性值，因此有大量Sim(Cnew,vi)值的更新操作。Sim(Cnew,vi)實(shí)質(zhì)上是計(jì)算社區(qū)間頂點(diǎn)對(duì)的相似性均值，由于大社區(qū)中某頂點(diǎn)與獨(dú)立社區(qū)中頂點(diǎn)相似性較大，容易導(dǎo)致Sim(Cnew,vi)≥Sim(vj,vi)，即均值降低vi對(duì)大社區(qū)中相對(duì)距離較遠(yuǎn)頂點(diǎn)（即相似性較低的頂點(diǎn)）的敏感性，導(dǎo)致vi不斷聚合到大社區(qū)中的現(xiàn)象，而不是優(yōu)先合并相似性大的vi與vj。為了保證兩兩相似性大的頂點(diǎn)優(yōu)先聚合，另一種方法實(shí)質(zhì)上是比較每個(gè)頂點(diǎn)對(duì)的相似性度量是否均為最大值。即?vk∈V，當(dāng)且僅當(dāng)Sim(vj,vi)≥Sim(vj,vk), 且Sim(vj,vi)≥Sim(vi,vk)，將vi與vj合并，否則不合并。由于聚合條件嚴(yán)格，很難形成大規(guī)模社區(qū)?；谏鲜鰞蓚€(gè)方法的優(yōu)缺點(diǎn)，考慮將兩種方法相結(jié)合。即將相似性值比較法融入到AGNES算法中，以減少社區(qū)間相似性值的計(jì)算次數(shù)，并避免頂點(diǎn)不斷聚合到大社區(qū)的現(xiàn)象；然后再將初步合并的社區(qū)按照AGNES算法進(jìn)行聚合，以避免比較法中無(wú)法形成大規(guī)模社區(qū)的現(xiàn)象。因此，基于加權(quán)聚集系數(shù)聯(lián)系度，提出一種新的層次聚類(lèi)算法VSFCM。具體算法描述如下。

算法1 VSFCM

輸入：社會(huì)網(wǎng)絡(luò)G=(V,E)的鄰接矩陣A

輸出：層次聚類(lèi)樹(shù)

算法VSFCM主要分為三步：計(jì)算頂點(diǎn)間相似性，初始社區(qū)合并，非獨(dú)立社區(qū)合并。第一步：計(jì)算vk和vs間的相似性值SWCCDks。設(shè)社會(huì)網(wǎng)絡(luò)中頂點(diǎn)數(shù)N=|V|，基于聯(lián)系度思想的計(jì)算路徑長(zhǎng)度為1至4步，路徑長(zhǎng)度為5的頂點(diǎn)間相似性值為0。因此，僅需計(jì)算和存儲(chǔ)任意頂點(diǎn)vk與其4步內(nèi)鄰居的相似性值。令任意頂點(diǎn)vk的4步內(nèi)鄰居集個(gè)數(shù)為L(zhǎng)，則空間復(fù)雜度為O(NL)。對(duì)于大部分實(shí)際網(wǎng)絡(luò)中，頂點(diǎn)的4級(jí)內(nèi)鄰居集個(gè)數(shù)L的取值遠(yuǎn)小于N，且L值不會(huì)隨著網(wǎng)絡(luò)規(guī)模的增長(zhǎng)而快速增長(zhǎng)，因此，適用于大規(guī)模網(wǎng)絡(luò)頂點(diǎn)間相似性的存儲(chǔ)。第二步：初始獨(dú)立社區(qū)合并，如代碼第3～13行。此步選取最大值的頂點(diǎn)對(duì)進(jìn)行合并，因此，時(shí)間復(fù)雜度為O(NL)。第三步：非獨(dú)立社區(qū)合并，如代碼第14～18行。設(shè)有K個(gè)社區(qū)，K遠(yuǎn)小于N，時(shí)間復(fù)雜度為O(K2)。社區(qū)發(fā)現(xiàn)算法VSFCM最終的時(shí)間復(fù)雜度為O(NL+K2)。

VSFCM算法是對(duì)經(jīng)典層次聚類(lèi)算法的改進(jìn)，主要區(qū)別是，在聚類(lèi)初期，僅通過(guò)判斷頂點(diǎn)間相似度先生成小規(guī)模的初始社區(qū)，并不進(jìn)行新社區(qū)與原有社區(qū)間值的更新操作；在聚類(lèi)期間，對(duì)初始社區(qū)進(jìn)行合并，最終生成層次聚類(lèi)樹(shù)。盡管合并順序不同，但VSFCM算法保證了其產(chǎn)生的結(jié)果和經(jīng)典方法是相同的。

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

實(shí)驗(yàn)的硬件環(huán)境是Intel?CoreTMDuo E7500雙核的CPU，內(nèi)存4 GB；軟件環(huán)境是Windows 7系統(tǒng)，Matlab R2012a。

主要從兩方面進(jìn)行實(shí)驗(yàn)驗(yàn)證：（1）與現(xiàn)有頂點(diǎn)間相似性度量指標(biāo)進(jìn)行比較，驗(yàn)證WCCD度量指標(biāo)的合理性和正確性；（2）通過(guò)與經(jīng)典社區(qū)發(fā)現(xiàn)方法進(jìn)行比較，驗(yàn)證WCCD度量指標(biāo)在解決社區(qū)發(fā)現(xiàn)問(wèn)題時(shí)的正確性和有效性。其中，利用模塊度函數(shù)評(píng)價(jià)社區(qū)結(jié)構(gòu)的優(yōu)劣。

模塊度函數(shù)（Q函數(shù)）是Newman[24]提出的衡量網(wǎng)絡(luò)劃分質(zhì)量的標(biāo)準(zhǔn)。Q函數(shù)定義如下：

其中，K表示社區(qū)個(gè)數(shù)；m表示網(wǎng)絡(luò)連接總數(shù)；ms表示社區(qū)s中的連接總數(shù)；ds表示社區(qū)s中頂點(diǎn)度之和。Q函數(shù)的取值范圍是0～1之間。通常認(rèn)為最大Q函數(shù)值對(duì)應(yīng)的社區(qū)劃分為網(wǎng)絡(luò)社區(qū)的最佳劃分；Q函數(shù)值越接近于1，說(shuō)明網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)越明顯。在實(shí)際的網(wǎng)絡(luò)中，Q函數(shù)值通常在0.3～0.7之間。文獻(xiàn)[25]指出模塊度Q函數(shù)存在分辨率極限問(wèn)題[26]，但當(dāng)前未見(jiàn)其他更合適的評(píng)價(jià)指標(biāo)，模塊度Q函數(shù)仍作為研究者們廣泛應(yīng)用于評(píng)價(jià)社區(qū)質(zhì)量的標(biāo)準(zhǔn)之一[27-28]。

5.1 相似性度量指標(biāo)的實(shí)驗(yàn)分析

為了驗(yàn)證采用聯(lián)系度綜合刻畫(huà)網(wǎng)絡(luò)局部關(guān)系和網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的頂點(diǎn)間相似性度量指標(biāo)WCCD，比單一考慮局部關(guān)系、路徑及同異反數(shù)量的相似性度量指標(biāo)具有更高的準(zhǔn)確性，本文選取了經(jīng)典的最具代表性的CN、RA和Katz相似性度量指標(biāo)，選取了現(xiàn)有基于聯(lián)系度的SPCD1和SPCD2相似性度量指標(biāo)，與本文提出的WCCD相似性度量指標(biāo)進(jìn)行比較。在模擬網(wǎng)絡(luò)[29]、空手道俱樂(lè)部Karate網(wǎng)絡(luò)[30]和Dolphin網(wǎng)絡(luò)[30]3種網(wǎng)絡(luò)中，如圖3所示，應(yīng)用VSFCM算法進(jìn)行社區(qū)挖掘，通過(guò)社區(qū)的劃分效果對(duì)6種頂點(diǎn)間相似性指標(biāo)定義的合理性和正確性進(jìn)行驗(yàn)證。應(yīng)用6種頂點(diǎn)間相似性度量指標(biāo)，利用VSFCM算法進(jìn)行層次聚類(lèi)，選取模塊度最大的層作為社區(qū)劃分結(jié)果，各度量指標(biāo)的網(wǎng)絡(luò)最大模塊度值、社區(qū)個(gè)數(shù)對(duì)比情況如表1所示。

Table 1 Experimental results of 6 indicators表1 6種指標(biāo)的實(shí)驗(yàn)結(jié)果

Fig.3 Social network圖3 社會(huì)網(wǎng)絡(luò)圖

在模擬網(wǎng)絡(luò)中，不同社區(qū)個(gè)數(shù)對(duì)應(yīng)的模塊度值的大小變化曲線如圖4所示。因?yàn)楦鞫攘恐笜?biāo)在VSFCM算法中形成的初始社區(qū)個(gè)數(shù)不同，所以各度量指標(biāo)的模塊度曲線在圖6中的長(zhǎng)短不同。在模擬網(wǎng)絡(luò)中，采用CN指標(biāo)的網(wǎng)絡(luò)最大模塊度為0.624，劃分為6個(gè)社區(qū)，分別為（16，18，10，11，17，22）、（26，27，28，32，36，35，33）、（12，23，19，20，24）、（25，34，30，29，31）、（1，3，4，2，6，7，5）和（8，9，21，13，14，15）；采用RA指標(biāo)的網(wǎng)絡(luò)最大模塊度為0.589，劃分為 6 個(gè)社區(qū)，分別為（3，1，4）、（18，16，11，10，17）、（34，25，30，31，29）、（20，19，24，23，12）、（33，32，36，35，27，22，28，26）和（6，2，14，5，7，13，15，21，8，9）；采用Katz指標(biāo)的網(wǎng)絡(luò)最大模塊度為0.637，劃分為6個(gè)社區(qū)，分別為（1，2，3，4，6，7，5）、（8，13，14，21，9，15）、（16，18，10，11，17）、（20，23，19，24，12）、（30，31，34，29，25）和（35，36，32，33，26，27，22，28）；采用SPCD1指標(biāo)的網(wǎng)絡(luò)最大模塊度為0.603，劃分為7個(gè)社區(qū)，分別為（16，18，17，10，11）、（35，36，32，33，26，27，22，28）、（30，31，29，34，25）、（1，3，4，2，6，7，5）、（8，13，14，21）、（9，15）和（12，20，23，24，19）；采用SPCD2指標(biāo)的網(wǎng)絡(luò)最大模塊度為0.596，劃分為5個(gè)社區(qū)，分別為（5，7，4，2，6，1，3）、（8，9，21，13，14，15）、（16，18，10，11，17，19，20，12，23）、（22，27，33，26，28，32，35，36）和（24，25，34，29，31，30）；采用WCCD指標(biāo)的網(wǎng)絡(luò)最大模塊度為0.637，劃分為6個(gè)社區(qū)，分別為（1，2，3，4，6，7，5）、（8，13，14，21，9，15）、（16，18，10，11，17）、（20，23，19，24，12）、（30，31，34，29，25）和（35，36，32，33，26，27，22，28）。由此可見(jiàn)，本文WCCD指標(biāo)與全局性Katz指標(biāo)具有最大的網(wǎng)絡(luò)模塊度值，優(yōu)于其他4種局部度量指標(biāo)；在不同社區(qū)劃分層次中，都取得了較大的模塊度值，并實(shí)現(xiàn)了社區(qū)的正確劃分。

Fig.4 Experimental results of 6 indicators in simulation network圖4 6種指標(biāo)在模擬網(wǎng)絡(luò)中的實(shí)驗(yàn)結(jié)果

同樣，采用6種相似性度量指標(biāo)，在Karate網(wǎng)絡(luò)和Dolphin網(wǎng)絡(luò)中進(jìn)行社區(qū)劃分，不同社區(qū)個(gè)數(shù)對(duì)應(yīng)的模塊度值的大小變化曲線如圖5、圖6所示；各度量指標(biāo)的網(wǎng)絡(luò)最大模塊度值、社區(qū)個(gè)數(shù)對(duì)比情況如表1所示。通過(guò)對(duì)模塊度值大小的比較，采用本文WCCD度量指標(biāo)進(jìn)行社區(qū)劃分，均可得到最大的模塊度值；在不同的社區(qū)劃分層次中，也取得了較大的模塊度值，較好地體現(xiàn)了社區(qū)劃分結(jié)果。由此可見(jiàn)，WCCD指標(biāo)接近甚至優(yōu)于全局性Katz度量指標(biāo)，明顯優(yōu)于其他局部相似性度量指標(biāo)，合理地刻畫(huà)了網(wǎng)絡(luò)中頂點(diǎn)間的關(guān)系值。

Fig.5 Experimental results of 6 indicators in Karate network圖5 6種指標(biāo)在Karate網(wǎng)絡(luò)中的實(shí)驗(yàn)結(jié)果

Fig.6 Experimental results of 6 indicators in Dolphin network圖6 6種指標(biāo)在Dolphin網(wǎng)絡(luò)中的實(shí)驗(yàn)結(jié)果

5.2 社區(qū)發(fā)現(xiàn)實(shí)驗(yàn)分析

現(xiàn)有多種社區(qū)發(fā)現(xiàn)算法，主要分為基于分裂的方法，如GN算法[31]；基于模塊度的方法，如CNM算法[32]；基于標(biāo)簽傳播的方法，如LP（label propagation）算法[33]；基于譜聚類(lèi)的方法，如SC（spectral clustering）[34]等經(jīng)典社區(qū)發(fā)現(xiàn)算法[35]。為了驗(yàn)證基于WCCD相似性度量指標(biāo)在VSFCM算法下社區(qū)劃分結(jié)構(gòu)的優(yōu)劣，在10種具有代表性的真實(shí)網(wǎng)絡(luò)中，與上述4種算法進(jìn)行比較實(shí)驗(yàn)。真實(shí)網(wǎng)絡(luò)包括：空手道俱樂(lè)部Karate網(wǎng)絡(luò)[30]、海豚Dolphin網(wǎng)絡(luò)[30]、美國(guó)大學(xué)足球聯(lián)賽FB網(wǎng)絡(luò)[30]、爵士音樂(lè)家合作Jazz網(wǎng)絡(luò)[36]、線蟲(chóng)神經(jīng)Neural網(wǎng)絡(luò)[30]、美國(guó)航空 USAir網(wǎng)絡(luò)[36]、電子郵件 Email網(wǎng)絡(luò)[30]、科學(xué)家合作NS網(wǎng)絡(luò)[30]、美國(guó)大選政治博客PB網(wǎng)絡(luò)[30]、美國(guó)電力PG網(wǎng)絡(luò)[30]。本文將全部數(shù)據(jù)集視為無(wú)向無(wú)權(quán)的二元網(wǎng)絡(luò)。研究表明，很多真實(shí)網(wǎng)絡(luò)中的頂點(diǎn)具有模塊性特征[37]，且真實(shí)網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)比模擬網(wǎng)絡(luò)更具挑戰(zhàn)，不能事先預(yù)知其社區(qū)結(jié)構(gòu)，因此只能采用模塊度進(jìn)行比較。實(shí)驗(yàn)結(jié)果如表2所示。

在表2中，第1列為真實(shí)網(wǎng)絡(luò)列表，第2列和第3列為網(wǎng)絡(luò)的基本統(tǒng)計(jì)數(shù)據(jù)（頂點(diǎn)數(shù)和邊數(shù)），第4至13列為5種社區(qū)發(fā)現(xiàn)算法，對(duì)每種算法統(tǒng)計(jì)了社區(qū)發(fā)現(xiàn)的最大模塊度值和社區(qū)數(shù)目。例如，在Karate網(wǎng)絡(luò)中，采用GN算法得出的最大模塊度值為0.401，劃分的社區(qū)數(shù)為5?？紤]到具有較高復(fù)雜度的GN算法具有較好的社區(qū)劃分結(jié)果，因此在表2中取每個(gè)網(wǎng)絡(luò)模塊度值的前兩位，其中加粗?jǐn)?shù)據(jù)表示最大值，加粗加下劃線表示次大值。由表2可見(jiàn)，從模塊度值角度比較，采用WCCD度量指標(biāo)的VSFCM算法取得了7次領(lǐng)先，而采用全局性度量指標(biāo)的GN算法取得了6次領(lǐng)先，尤其是在USAir網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)中，GN算法和LP算法給出了接近0的模塊度值，而VSFCM算法仍取得了較好的社區(qū)結(jié)構(gòu)效果；考慮模塊度增量作為社區(qū)劃分標(biāo)準(zhǔn)的CNM算法取得了5次領(lǐng)先，相對(duì)較好，而LP算法與SC算法表現(xiàn)較差，LP算法僅取得了1次領(lǐng)先，SC算法一次領(lǐng)先也沒(méi)有。從社區(qū)劃分?jǐn)?shù)目角度比較，GN算法傾向于給出較多的社區(qū)劃分?jǐn)?shù)目，例如PB網(wǎng)絡(luò)分為205個(gè)社區(qū)，顯著高于其他算法；此外LP和VSFCM為3個(gè)社區(qū)，較為接近真實(shí)的社區(qū)數(shù)目，其余方法給出的社區(qū)數(shù)均為10個(gè)以上，顯然相應(yīng)的方法有過(guò)于擬合的傾向。

5種算法在數(shù)據(jù)集中的運(yùn)行時(shí)間如圖7所示。在圖7中，橫坐標(biāo)表示頂點(diǎn)數(shù)及真實(shí)網(wǎng)絡(luò)，縱坐標(biāo)表示算法的運(yùn)行時(shí)間。由圖7可知，隨著網(wǎng)絡(luò)中頂點(diǎn)數(shù)和邊數(shù)的增加，各個(gè)算法的運(yùn)行時(shí)間顯著增長(zhǎng)?？傮w來(lái)看，貪婪的CNM算法和LP算法運(yùn)行速度較快，比較適合處理大型網(wǎng)絡(luò)。SC算法由于采用了ARPACK加速特征根的計(jì)算方法，隨著網(wǎng)絡(luò)規(guī)模的增加，運(yùn)行時(shí)間增加緩慢。但LP算法和SC算法獲得的模塊度值偏低，其速度的增加是以社區(qū)劃分效果為代價(jià)的。消耗時(shí)間最多的是GN算法，該算法需要從全局角度計(jì)算邊界數(shù)。VSFCM算法的運(yùn)行效率明顯優(yōu)于GN算法，雖然遜于SC算法和LP算法，但社區(qū)劃分效果明顯優(yōu)于SC算法和LP算法。

綜上，與其他4種算法相比，采用WCCD度量指標(biāo)的社區(qū)發(fā)現(xiàn)算法VSFCM均取得了較大社區(qū)模塊度值，表明本文提出的WCCD相似性度量指標(biāo)可以實(shí)現(xiàn)較好的社區(qū)劃分結(jié)果。

Table 2 Experimental results of 5 community discovering algorithms表2 5個(gè)算法社區(qū)劃分結(jié)果的比較

6 結(jié)束語(yǔ)

本文將社會(huì)網(wǎng)絡(luò)定義為一個(gè)同異反系統(tǒng)，針對(duì)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，基于聯(lián)系度刻畫(huà)分析了頂點(diǎn)間相似性，給出了基于加權(quán)聚集系數(shù)聯(lián)系度的頂點(diǎn)間相似性模型的表示及計(jì)算方法；進(jìn)一步給出了網(wǎng)絡(luò)社區(qū)間相似性模型。為了進(jìn)一步考察上述相似性度量指標(biāo)的實(shí)際性能，將其應(yīng)用于現(xiàn)有社會(huì)網(wǎng)絡(luò)數(shù)據(jù)集中實(shí)現(xiàn)社區(qū)發(fā)現(xiàn)，實(shí)驗(yàn)結(jié)果顯示，基于本文提出的頂點(diǎn)間相似性度量指標(biāo)可以正確和有效地實(shí)現(xiàn)社區(qū)發(fā)現(xiàn)。如何刻畫(huà)有向有權(quán)等更復(fù)雜網(wǎng)絡(luò)中頂點(diǎn)間的相似性，以及如何研究網(wǎng)絡(luò)動(dòng)態(tài)演化是下一步的研究目標(biāo)。

Fig.7 Comparison of vertices number and running time圖7 頂點(diǎn)數(shù)與運(yùn)行時(shí)間對(duì)比圖

[1]Girvan M,Newman M E J.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]Lv Linyuan,Zhou Tao.Link prediction in complex networks:a survey[J].Physica A Statistical Mechanics&Its Applications,2011,390(6):1150-1170.

[3]Katz L.A new status index derived from sociometric analysis[J].Psychometrika,1953,18(1):39-43.

[4]Leicht E A,Holme P,Newman M E J.Vertex similarity in networks[J].Physical Review E,2006,73(2):026120.

[5]Fouss F,Pirotte A,Renders J,et al.Random-walk computation of similarities between nodes of a graph with application to collaborative recommendation[J].IEEE Transactions on Knowledge&Data Engineering,2007,19(3):355-369.

[6]G?bel F,Jagers A A.Random walks on graphs[J].Stochastic Processes&TheirApplications,1974,2:311-336.

[7]Brin S,Page L.The anatomy of a large-scale hypertextual Web search engine[J].Computer Networks&ISDN Systems,1998:107-117.

[8]Lorrain F,White H C.Structural equivalence of individuals in social networks[J].Journal of Mathematical Sociology,1971,1(1):49-80.

[9]Salton G,McGill M J.Introduction to modern information retrieval[M].New York:McGraw-Hill,1983.

[10]Hamers L,Hemeryck Y,Herweyers G,et al.Similarity measures in scientometric research:the Jaccard index versus Salton's cosine formula[J].Information Processing&Management,1989,25(89):315-318.

[11]Zhou Tao,Lv Linyuan,Zhan Yicheng.Predicting missing links via local information[J].The European Physical Journal B:Condensed Matter and Complex Systems,2009,71(4):623-630.

[12]Liu Weiping,Lv Linyuan.Link prediction based on local random walk[J].Europhysics Letters,2010,89(5):58007-58012.

[13]Bai Meng.Link prediction of complex network:the algorithm based on structure similarity[D].Xiangtan:Xiangtan University,2011.

[14]Chiang K Y,Natarajan N,Tewari A,et al.Exploiting longer cycles for link prediction in signed networks[C]//Proceedings of the 20th Conference on Information and Knowledge Management,Glasgow,UK,Oct 24-28,2011.New York:ACM,2011:1157-1162.

[15]Zhao Keqin.Set pair analysis and its preliminary application[M].Hangzhou:Zhejiang Science and Technology Press,2000.

[16]Zhang Chunying,Liang Ruitao,Liu Lu.Set pair social network analysis is model and its application[J].Journal of Hebei Polytechnic University:Natural Science Edition,2011,33(3):99-103.

[17]Zhang Chunying,Guo Jingfeng.The α relation communities of set pair social networks and its dynamic mining algorithms[J].Chinese Journal of Computers,2013,36(8):1682-1692.

[18]Zhang Chunying.Research on modeling and situation analysis theory of social network based on attribute graph[D].Qinhuangdao:Yanshan University,2013.

[19]Zhang Chunying,Guo Jingfeng.The attribute graph model of social networks and its application[M].Beijing:Beijing University of Posts and Telecommunications Press,2014:186-198.

[20]Zhao Chanyuan.The research on link prediction method in social network[D].Harbin:Harbin Engineering University,2012.

[21]Li Tao,Fu Qiang,Ding Hong.Research for variation coefficient in set pair analysis based on correlation degree of grey theory[J].Journal of Heilongjiang Hydraulic Engineering,2010,37(1):97-99.

[22]Esley D,Kleinberg J.Networks,crowds,and markets[M].Cambridge:Cambridge University Press,2010:49-50.

[23]Han Jiawei,Kamber M.Data mining:concepts and techniques[M].San Francisco,USA:Morgan Kaufmann Publishers Inc,2011:457-470.

[24]Newman M E J,Girvan M.Finding and evaluating community structure in networks[J].Physical Review E,2004,69(2):292-313.

[25]Fortunato S,Barthélemy M.Resolution limit in community detection[J].Proceedings of the National Academy of Sciences of the United States ofAmerica,2007,104(1):36-41.

[26]Zhang Jiali.The problem of modularity and its algorithm research in community detection[D].Shanghai:East China Normal University,2015.

[27]Jiang Shengyi,Yang Bohong,Wang Lianxi.An adaptive dynamic community detection algorithm based on incremental spectral clustering[J].Acta Automatica Sinica,2015,41(12):2017-2025.

[28]Li Huijia,Li Huiying,Li Aihua.Analysis of multi-scale stability in community structure[J].Chinese Journal of Computers,2015,38(2):301-311.

[29]Bhatia M P S,Gaur P.Statistical approach for community mining in social networks[C]//Proceedings of the 2008 International Conference on Service Operations&Logistics,&Informatics,Beijing,Oct 12-15,2008.Piscataway,USA:IEEE,2008:207-211.

[30]Newman M.Network datasets[EB/OL].[2016-05-21].http://www-personal.umich.edu/～mejn/netdata/.

[31]Newman M E J,Girvan M.Finding and evaluating community structure in networks[J].Physical Review E,2004,69(2):026113.

[32]Clauset A,Newman M E J,Moore C.Finding community structure in very large networks[J].Physical Review E,2004,70(6):066111.

[33]Raghavan U N,Albert R,Kumara S.Near linear time algorithm to detect community structures in large-scale networks[J].Physical Review E,2007,76(3):036106.

[34]Newman M E J.Finding community structure using the eigenvectors of matrices[J].Physical Review E,2006,74(3):036104.

[35]Jiang Shengyi,Yang Bohong,Li Minmin,et al.Overlapping community detection algorithm based on two-stage clustering[J].Pattern Recognition and Artificial Intelligence,2015,28(11):983-991.

[36]Batageli,Mrvar A.Pajek datasets[EB/OL].[2016-05-21].http://vlado.fmf.unilj.si/pub/networks/data/default.htm.

[37]Li Yafang,Jia Caiyan,Yu Jian.Survey on community detection algorithms using nonnegative matrix factorization model[J].Journal of Frontiers of Computer Science and Technology,2016,10(1):1-13.

附中文參考文獻(xiàn):

[13]白萌.復(fù)雜網(wǎng)絡(luò)的鏈路預(yù)測(cè):基于結(jié)構(gòu)相似性的算法研究[D].湘潭:湘潭大學(xué),2011.

[15]趙克勤.集對(duì)分析及其初步應(yīng)用[M].杭州:浙江科學(xué)技術(shù)出版社,2000.

[16]張春英,梁瑞濤,劉璐.集對(duì)社會(huì)網(wǎng)絡(luò)圖分析模型及其應(yīng)用[J].河北理工大學(xué)學(xué)報(bào):自然科學(xué)版,2011,33(3):99-103.

[17]張春英,郭景峰.集對(duì)社會(huì)網(wǎng)絡(luò)α關(guān)系社區(qū)及動(dòng)態(tài)挖掘算法[J].計(jì)算機(jī)學(xué)報(bào),2013,36(8):1682-1692.

[18]張春英.基于屬性圖的社交網(wǎng)絡(luò)建模與態(tài)勢(shì)分析理論研究[D].秦皇島:燕山大學(xué),2013.

[19]張春英,郭景峰.社交網(wǎng)絡(luò)屬性圖模型與應(yīng)用[M].北京:北京郵電大學(xué)出版社,2014:186-198.

[20]趙嬋媛.一種社會(huì)網(wǎng)絡(luò)鏈接預(yù)測(cè)算法研究[D].哈爾濱:哈爾濱工程大學(xué),2012.

[21]李陶,付強(qiáng),丁紅.基于灰色關(guān)聯(lián)度的集對(duì)分析差異系數(shù)研究[J].黑龍江水專(zhuān)學(xué)報(bào),2010,37(1):97-99.

[26]張家利.社區(qū)發(fā)現(xiàn)的模塊度問(wèn)題及其算法研究[D].上海:華東師范大學(xué),2015.

[27]蔣盛益,楊博泓,王連喜.一種基于增量式譜聚類(lèi)的動(dòng)態(tài)社區(qū)自適應(yīng)發(fā)現(xiàn)算法[J].自動(dòng)化學(xué)報(bào),2015,41(12):2017-2025.

[28]李慧嘉,李慧穎,李?lèi)?ài)華.多尺度的社團(tuán)結(jié)構(gòu)穩(wěn)定性分析[J].計(jì)算機(jī)學(xué)報(bào),2015,38(2):301-311.

[35]蔣盛益,楊博泓,李敏敏,等.基于二階段聚類(lèi)的重疊社區(qū)發(fā)現(xiàn)算法[J].模式識(shí)別與人工智能,2015,28(11):983-991.

[37]李亞芳,賈彩燕,于劍.應(yīng)用非負(fù)矩陣分解模型的社區(qū)發(fā)現(xiàn)方法綜述[J].計(jì)算機(jī)科學(xué)與探索,2016,10(1):1-13.

Measuring Similarity Between Vertices and ItsApplication in Social Network*

CHEN Xiao1,2,3,GUO Jingfeng1,3+,ZHANG Chunying4
1.College of Information Science and Engineering,Yanshan University,Qinhuangdao,Hebei 066004,China
2.College of Qian'an,North China University of Science and Technology,Qian’an,Hebei 064400,China
3.The Key Laboratory for Computer Virtual Technology and System Integration of Hebei Province,Qinhuangdao,Hebei 066004,China
4.College of Science,North China University of Science and Technology,Tangshan,Hebei 063009,China

A

TP391

+Corresponding author:E-mail:jfguo@ysu.edu.cn

CHEN Xiao,GUO Jingfeng,ZHANG Chunying.Measuring similarity between vertices and its application in social network.Journal of Frontiers of Computer Science and Technology,2017,11(10)：1629-1641.

ISSN 1673-9418 CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology

1673-9418/2017/11(10)-1629-13

10.3778/j.issn.1673-9418.1607025

E-mail:fcst@vip.163.com

http://www.ceaj.org

Tel:+86-10-89056056

*The National Natural Science Foundation of China under Grant No.61472340(國(guó)家自然科學(xué)基金);the National Youth Science Foundation of China under Grant No.61602401(國(guó)家青年科學(xué)基金項(xiàng)目);the Natural Science Foundation of Hebei Province under Grant Nos.F2017209070,F2016209344(河北省自然科學(xué)基金).

Received 2016-07,Accepted 2016-12.

CNKI網(wǎng)絡(luò)優(yōu)先出版:2016-12-06,http://www.cnki.net/kcms/detail/11.5602.TP.20161206.1712.002.html

CHEN Xiao was born in 1983.She is a Ph.D.candidate at Yanshan University,a lecturer at North China University of Science and Technology,and the member of CCF.Her research interests include graph mining and social network analysis,etc.

陳曉（1983—），女，河北秦皇島人，燕山大學(xué)博士研究生，華北理工大學(xué)講師，CCF會(huì)員，主要研究領(lǐng)域?yàn)閳D挖掘，社會(huì)網(wǎng)絡(luò)分析等。發(fā)表學(xué)術(shù)論文20余篇。

GUO Jingfeng was born in 1962.He received the Ph.D.degree from Yanshan University in 2002.Now he is a professor and Ph.D.supervisor at Yanshan University,and the senior member of CCF.His research interests include database theory and application,data mining and social network analysis,etc.

郭景峰（1962—），男，黑龍江哈爾濱人，2002年于燕山大學(xué)獲得博士學(xué)位，現(xiàn)為燕山大學(xué)教授，CCF高級(jí)會(huì)員，主要研究領(lǐng)域?yàn)閿?shù)據(jù)理論應(yīng)用，數(shù)據(jù)挖掘，社會(huì)網(wǎng)絡(luò)分析等。發(fā)表學(xué)術(shù)論文100余篇，主持國(guó)家自然科學(xué)基金項(xiàng)目2項(xiàng)，省級(jí)科研項(xiàng)目3項(xiàng)。

ZHANG Chunying was born in 1968.She received the Ph.D.degree from Yanshan University in 2013.Now she is a professor at North China University of Science and Technology,and the senior member of CCF.Her research interests include data mining and social network analysis,etc.

張春英（1968—），女，河北唐山人，2013年于燕山大學(xué)獲得博士學(xué)位，現(xiàn)為華北理工大學(xué)教授，CCF高級(jí)會(huì)員，主要研究領(lǐng)域?yàn)閿?shù)據(jù)挖掘，社會(huì)網(wǎng)絡(luò)分析等。發(fā)表學(xué)術(shù)論文30余篇，主持省級(jí)科研項(xiàng)目1項(xiàng)。