基于非加權(quán)圖的大型社會(huì)網(wǎng)絡(luò)檢測(cè)算法研究

1、基于非加權(quán)圖的大型社會(huì)網(wǎng)絡(luò)檢測(cè)算法研究隨著信息交互和數(shù)據(jù)共享的不斷增加，社交網(wǎng)絡(luò)的數(shù)量顯著提高。在分析此類(lèi)網(wǎng)絡(luò)時(shí)，圖論提供了一 個(gè)重要的建模模型。當(dāng)節(jié)點(diǎn)代表用戶,邊表示互聯(lián)時(shí)，可以將此類(lèi)網(wǎng)絡(luò)定義為一張圖“】,該圖中的節(jié)點(diǎn)可 以是直接或間接相連的。在分析社交網(wǎng)絡(luò)數(shù)據(jù)時(shí)，定義和計(jì)算社區(qū)是最關(guān)鍵的步驟。同時(shí)，社區(qū)可以被看作 是對(duì)整個(gè)網(wǎng)絡(luò)的概要表示(summarization),因此，在社區(qū)檢測(cè)中需要使用這種概要設(shè)計(jì)理念。當(dāng)前對(duì)于社區(qū)網(wǎng)絡(luò)劃分硏究已取得了很多硏究成果，特別是社會(huì)網(wǎng)絡(luò)分析，但其仍然是一項(xiàng)具有挑戰(zhàn) 性和吸弓i力的硏究。因?yàn)樵诮o定的圖中逬行社區(qū)檢測(cè),可以用于搜索潛在的合作者,用于優(yōu)化社會(huì)關(guān)系

2、， 或在不同的社區(qū)中搜索一個(gè)關(guān)鍵人物等?；趫D論的原理，已經(jīng)提出了不少方法用來(lái)解決社區(qū)檢測(cè)的問(wèn)題，如譜分析方法，其代表了一種非 常特殊的社區(qū)檢測(cè)技術(shù)。這種方法的特殊性表現(xiàn)在其分類(lèi)性能上，并以拉普拉斯矩陣的特征向量為基礎(chǔ)。 使用這樣一個(gè)矩陣在時(shí)間和內(nèi)存方面需要付出很高的代價(jià)。此外,在時(shí)間復(fù)雜度上，k個(gè)特征向量的計(jì)算 復(fù)雜度為0(2)。雖然，很容易計(jì)算出給定矩陣的特征向量，但是不方便計(jì)算大型拉普拉斯矩陣。這個(gè)方 法的第二個(gè)缺點(diǎn)是假設(shè)社區(qū)的數(shù)量必須是已知的，但是在實(shí)際的大型社交網(wǎng)絡(luò)中很難獲得這一信息。文獻(xiàn) 刀提出了一種基于聚類(lèi)概念的社區(qū)檢測(cè)方法。這種技術(shù)的優(yōu)點(diǎn)是它能夠提供豐富的結(jié)果，使用這種方法發(fā)

3、現(xiàn)的社區(qū)節(jié)點(diǎn)之間相互連接非常緊密。然而,在時(shí)間和內(nèi)存方面代價(jià)很高，而且非常復(fù)雜。 basuchowdhuri p等人岡提岀了一種基于最大生成樹(shù)的并發(fā)方法。該方法使用共同鄰居的相似性作為 邊的權(quán)重。將每個(gè)節(jié)點(diǎn)都與鄰居相連接，共享了大量的共同鄰居,從而建造了最大生成樹(shù)。與文獻(xiàn)刀的方 法相比較,這種方法在占用內(nèi)存方面效果較好，但是其時(shí)間運(yùn)行成本還是較高。文獻(xiàn)9提出了一種基于節(jié) 點(diǎn)和邊的檢測(cè)社區(qū)方法，可廣泛用于查找網(wǎng)橋和服務(wù)供應(yīng)商。但是，對(duì)于大型的社交網(wǎng)絡(luò)而言，這些方法 的適用性均較差。在以上文獻(xiàn)提出的方法中，運(yùn)行時(shí)間的復(fù)雜度和內(nèi)存的使用成本問(wèn)題仍然存在。因此，它們的適用性 具有一定的局限。為了解決這

4、些問(wèn)題，本文提出了一種有效的社區(qū)檢測(cè)算法方法，該方法基于聚類(lèi)系數(shù)和 共同鄰居指標(biāo)。實(shí)驗(yàn)結(jié)果表明，在大規(guī)模社會(huì)網(wǎng)絡(luò)數(shù)據(jù)集中提出的方法提供了較高質(zhì)量的社區(qū)劃分結(jié)果， 并具備線，性運(yùn)行時(shí)間的復(fù)雜度特，性。1.1問(wèn)題描述在一個(gè)網(wǎng)絡(luò)模型中,一張圖g由有限集合(v , e)構(gòu)成,其中v表示節(jié)點(diǎn)集合(網(wǎng)絡(luò)的用戶)，e表示邊 或節(jié)點(diǎn)之間相互聯(lián)系的集合,v=vj|i=l, . , n , e=eij|vi, vjev , n = |v|為節(jié)點(diǎn)總數(shù),m = |e|為邊的總 f 和 i ' c i 數(shù)。此外，當(dāng)圖g中節(jié)點(diǎn)的集合e和邊的集合v'都是圖g中v和e的子集山“丨 j 時(shí),g'表示g的

5、子圖。社交網(wǎng)絡(luò)可以建模為一個(gè)有向圖或一個(gè)無(wú)向圖，其中節(jié)點(diǎn)表示個(gè)體,邊表示節(jié)點(diǎn)之 間的關(guān)系。本文重點(diǎn)是在社交網(wǎng)絡(luò)中進(jìn)行社區(qū)檢測(cè)，它可以用一個(gè)無(wú)向圖來(lái)表示。這個(gè)社區(qū)可以被定義為 節(jié)點(diǎn)的一個(gè)子集,與網(wǎng)絡(luò)的其他節(jié)點(diǎn)相比較，這些節(jié)點(diǎn)更有可能連接在一起。圖1顯示了一張具有3個(gè)社 區(qū)的信息圖。1.2采用的度量標(biāo)準(zhǔn)本文采用共同鄰居的相似性來(lái)衡量?jī)蓚€(gè)節(jié)點(diǎn)的相似度,這意味著,當(dāng)此度量指標(biāo)較高時(shí)，節(jié)點(diǎn)更有可 能是在同一個(gè)社區(qū)內(nèi)。相比應(yīng)用平均聚類(lèi)系數(shù)來(lái)衡量集群的方法，本文提出的結(jié)果準(zhǔn)確性更高。本文采用 了兩種度量標(biāo)準(zhǔn)：(1) 共同鄰居的相似性：在參考文獻(xiàn)8和10中使用共同的鄰居來(lái)定義節(jié)點(diǎn)之間的相似性。如果兩個(gè) 節(jié)點(diǎn)有

6、大量的共同鄰居，那么它們更相似。這個(gè)指標(biāo)由以下公式進(jìn)彳亍計(jì)算。式中，a表示鄰居相似性。(2) 聚類(lèi)系數(shù)：采用此類(lèi)度量標(biāo)準(zhǔn)的目的是評(píng)估節(jié)點(diǎn)在一個(gè)集群中的集群化趨勢(shì)。其中最受歡迎的一 個(gè)測(cè)量標(biāo)準(zhǔn)是模塊性最大化，但是它存在兩個(gè)問(wèn)題：它合并小型子圖,當(dāng)分辨率較低時(shí),它占主導(dǎo)地位； 它分裂大型子圖，當(dāng)分辨率較高時(shí)，它占主導(dǎo)地位。另一種被廣泛使用的度量稱(chēng)為聚類(lèi)系數(shù)"o-m ,在一 個(gè)社區(qū)內(nèi)提供了一個(gè)強(qiáng)大的鄰居結(jié)構(gòu)。這項(xiàng)標(biāo)準(zhǔn)被廣泛應(yīng)用于社會(huì)網(wǎng)絡(luò)分析中，它被定義為封閉的三聯(lián)體 (三角形)數(shù)量和給定圖的三聯(lián)體數(shù)量之間的比率，式(2)給出了其定義：式中，c表示聚類(lèi)系數(shù)。本研究的目的是研究社區(qū)之間的邊所存

7、在的一些性質(zhì)，最后提取新的社區(qū)。引理1 ：假設(shè)g是一張無(wú)向非加權(quán)圖，e表示g的邊集合，v表示g的節(jié)點(diǎn)集合，得到如下公式：厶他)=2(嘆宀)w £!必，巧w v(3)3x三角形的數(shù)量二工厶(坯)(4)uc v其中，l表示節(jié)點(diǎn)vi鄰居之間的關(guān)聯(lián)數(shù)量。論證：假設(shè)g為一張圖，僅僅包含一個(gè)三角形t ,本文假設(shè)它由3個(gè)節(jié)點(diǎn)組成(vi , v2, v3)o如果計(jì)算l(v1),則發(fā)現(xiàn)一對(duì)關(guān)聯(lián)(v2和v3)；如果計(jì)算v2的這一度量，則發(fā)現(xiàn)vi和v?之間的關(guān)聯(lián)； 最后計(jì)算v3 ,得到了 vi和v2之間的關(guān)聯(lián)。之后，如果計(jì)算總和l(vi) + l(v2)+ l(v3),那么得到的結(jié)果是3 對(duì)關(guān)聯(lián)?？傊?當(dāng)

8、本文計(jì)算一張圖中每個(gè)節(jié)點(diǎn)與其鄰居之間的關(guān)聯(lián)數(shù)量時(shí)，對(duì)同一個(gè)三角形計(jì)算了 3次。圖2闡釋了一張無(wú)向圖，由7個(gè)節(jié)點(diǎn)和10條邊構(gòu)成。該圖由3個(gè)三角形組成。當(dāng)本文計(jì)算這7個(gè)節(jié) 點(diǎn)鄰居之間的關(guān)聯(lián)數(shù)量總和時(shí)，得到表1所示結(jié)果。根據(jù)這些結(jié)果，3個(gè)三角形共計(jì)算了 3次,這意味著3 x (在g1中的三角形數(shù)量)等于在g1中每個(gè)節(jié)點(diǎn)鄰居之間的關(guān)聯(lián)數(shù)量總和。性質(zhì)1:運(yùn)用式(1),本文可以得出結(jié)論：兩個(gè)社區(qū)之間的一條邊的節(jié)點(diǎn)是不同的。它們沒(méi)有或僅有少 數(shù)幾個(gè)共同的鄰居。性質(zhì)2 :本文研究的重點(diǎn)在于在社區(qū)內(nèi)最大化聚類(lèi)系數(shù)(式(2)。為了達(dá)到這一目標(biāo)，三角形的數(shù)量以 及式(4)中的度量必須盡可能地最大化。實(shí)際上，在一個(gè)社

9、區(qū)中每個(gè)節(jié)點(diǎn)鄰居之間的關(guān)聯(lián)數(shù)量必須最大化。 這意味著對(duì)于具有較高聚類(lèi)系數(shù)(大量三角形)的兩個(gè)社區(qū)之間的節(jié)點(diǎn)，其鄰居之間的關(guān)聯(lián)數(shù)量較大。引理2 :假設(shè)g是一張無(wú)向非加權(quán)的圖。在兩個(gè)社區(qū)之間一條邊e(vi, v的節(jié)點(diǎn)沒(méi)有或有幾個(gè)共同鄰 居，節(jié)點(diǎn)vi和vj具有較高的度量l。論據(jù):通過(guò)使用性質(zhì)1和性質(zhì)2獲得引理2。本文將節(jié)點(diǎn)鄰居之間的關(guān)聯(lián)數(shù)量標(biāo)準(zhǔn)化。由以下方程來(lái)定義標(biāo)準(zhǔn)化：式中，b表示的是節(jié)點(diǎn)鄰居關(guān)聯(lián)數(shù)據(jù)標(biāo)準(zhǔn)。通過(guò)式可知節(jié)點(diǎn)之間共同鄰居的數(shù)量。從引理2可以得知，本文的目標(biāo)是找到這些邊e(vi, v， 它們?cè)卩従觟和j之間的關(guān)聯(lián)數(shù)量較大(見(jiàn)式)，而在i和j之間的共同鄰居數(shù)量較少(見(jiàn)式)。因此，以 這些邊

10、為基礎(chǔ)，所提方法的目標(biāo)是找到度量w , w可以由如下公式定義：在過(guò)去的幾年中，在社交網(wǎng)絡(luò)中進(jìn)行社區(qū)檢測(cè)已經(jīng)吸引了很多研究人員，但它仍是一項(xiàng)具有挑戰(zhàn)性的 任務(wù)。事實(shí)上，大多數(shù)現(xiàn)有方法的適用性受限于它們的計(jì)算成本。本文提出的方法通過(guò)刪除在未加權(quán)圖中 的社區(qū)之間的邊，從社交網(wǎng)絡(luò)中找到社區(qū)。本文假設(shè)一個(gè)社區(qū)必須至少有4個(gè)節(jié)點(diǎn)，如參考文獻(xiàn)2所使用 的社區(qū)。刪除邊是為了最小化每條邊節(jié)點(diǎn)之間的共同鄰居數(shù)量(少于共同鄰居的20%),并且提高社區(qū)劃分 的質(zhì)量。下面介紹算法步驟和實(shí)例分析。3.1算法描述本文提出的方法使用了以下步驟：輸入：無(wú)向非加權(quán)的網(wǎng)絡(luò)g(v, e)輸出:n 個(gè)社區(qū)，gs = gsi , gs2

11、 , . , gsn首先，本文計(jì)算在圖g中每個(gè)節(jié)點(diǎn)鄰居之間的關(guān)聯(lián)數(shù)量l(vi)。然后，本文計(jì)算每條邊e共同聚類(lèi) 數(shù)量c,以及這條邊的節(jié)點(diǎn)之間鄰居u的結(jié)合情況。之后，設(shè)l二l(w)+l(vj)和s=|鄰居")+鄰居山)| ,其 中w、切表示由邊e相連的兩個(gè)節(jié)點(diǎn)。爐二丄丄 0(),-<0.2cxsu(7)w=lxu c=0本文使用w在表格t中以遞減順序?qū)呥M(jìn)行分類(lèi)。一旦這個(gè)操作完成，就按照在t中的順序找到 第一條邊e(vi , vj)。如果在刪除這條邊之后，w鄰居的數(shù)量和vj鄰居的數(shù)量均會(huì)超過(guò)0,那么將這條邊從g 中刪除，否則不刪除。本文需要對(duì)t中的其他邊重復(fù)測(cè)試，直到表格t是空為

12、止。g)本文應(yīng)用了一個(gè)社區(qū)必須至少包含4個(gè)節(jié)點(diǎn)的假設(shè)。為了確保該假設(shè)成立，需要把每張少于4個(gè) 節(jié)點(diǎn)的子圖g加入到在步驟中已經(jīng)被分離的最后一張子圖中。3.2實(shí)例分析設(shè)一個(gè)網(wǎng)絡(luò)n1結(jié)構(gòu)如圖3所示，圖4體現(xiàn)了提出的方法應(yīng)用于網(wǎng)絡(luò)ni的結(jié)果。首先，運(yùn)用步驟 在未加權(quán)的圖中計(jì)算每條邊的w值。然后，本文選擇符合以下條件的邊e(vi, v：在節(jié)點(diǎn)w和vj之間共 同鄰居的數(shù)量較低(少于20%)。本文運(yùn)用w值對(duì)這些邊進(jìn)行分類(lèi),按照遞減順序?qū)⑦@些邊儲(chǔ)存在表格t中。重復(fù)步驟中邊的刪除 操作，直到為空白為止。注意，大小小于2的群組不可以被分為獨(dú)立的群組。最后,本文將少于4個(gè)節(jié)點(diǎn)的每張子圖g加入到已經(jīng)被分離的最后一張子

13、圖中。為了驗(yàn)證本算法的有效性，采用真實(shí)的較大規(guī)模社會(huì)網(wǎng)絡(luò)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)分析,并與生成樹(shù)算法【8】、 cbcd算法心】進(jìn)行比較分析。實(shí)驗(yàn)環(huán)境中服務(wù)器設(shè)備參數(shù)為：xeon e7-4820雙核處理器，2.5 ghz cpu頻率，16 gb內(nèi)存， windows server 2012系統(tǒng)。本文在核心圖社區(qū)檢測(cè)時(shí)采用gn算法(girvan-newman)o本文采用模塊性q函數(shù)問(wèn)來(lái)評(píng)價(jià)劃分出的模塊性，采用nmi3來(lái)評(píng)價(jià)劃分結(jié)果的相似性，兩個(gè)評(píng)價(jià) 扌旨標(biāo)的數(shù)值越接近1 ,說(shuō)明算法劃分的效果和質(zhì)量越高。實(shí)驗(yàn)采用的4個(gè)較大社會(huì)網(wǎng)絡(luò)數(shù)據(jù)集的具體參數(shù) 如表2所示。4.1結(jié)果分析采用生成樹(shù)算法、cbcd算法和本文提

14、岀算法在以上4個(gè)社會(huì)網(wǎng)絡(luò)數(shù)據(jù)集上分別進(jìn)行了 100次運(yùn)行 測(cè)試，實(shí)驗(yàn)結(jié)果的平均指標(biāo)數(shù)據(jù)如表3所示。通過(guò)表3可以看出，在q函數(shù)指標(biāo)結(jié)果上，本文提出算法比其他兩種算法都表現(xiàn)更好，即社會(huì)發(fā)現(xiàn) 更有效，更好地體現(xiàn)了社區(qū)結(jié)構(gòu)的劃分。在nmi指標(biāo)結(jié)果上，相比其他兩種算法，本文算法的數(shù)值更接近 于1,即劃分結(jié)果和真實(shí)的劃分更相似。從表4中可以看出，本文算法在4個(gè)社會(huì)網(wǎng)絡(luò)數(shù)據(jù)集上的運(yùn)行時(shí)間均比其他兩種算法少，即相比其 他兩種算法，本算法具有更高的效率。4.2復(fù)雜度分析該方法不是對(duì)所有的邊進(jìn)行分類(lèi)，而僅僅對(duì)共同鄰居少于20%的邊進(jìn)行分類(lèi)。例如，在ca-condmat 網(wǎng)絡(luò)中，包含186 936條邊，本文僅僅對(duì)其

15、中的67 297條邊進(jìn)行分類(lèi)。同樣，本文在cit-hepth網(wǎng)絡(luò)中 僅僅對(duì)352 807條邊中的176 403條邊進(jìn)行分類(lèi)。在步驟中，本文對(duì)一部分共同鄰居少于20%的邊進(jìn)行分類(lèi)。如果本文假設(shè)這些邊的數(shù)量為k ,那 么復(fù)雜度為o(klog(k),即具有線性復(fù)雜度。在本算法的實(shí)施過(guò)程中，運(yùn)用了 python 3.3分類(lèi)算法。如 果假設(shè)在步驟g)的操作之后發(fā)現(xiàn)子圖的數(shù)量為c ,由少于4個(gè)節(jié)點(diǎn)構(gòu)成的子圖數(shù)量為ci,那么復(fù)雜度為 o(clog2(c)。因?yàn)閛(clog2(c)v<o(n),根據(jù)所選擇的網(wǎng)絡(luò)，本文得到岀算法的復(fù)雜度取決于 o(k log(k)。因此，本文提出的算法具有線性復(fù)雜度，即使在運(yùn)行時(shí)間最壞的情況下，復(fù)雜度為o(klog(k)。本文提岀了一種適用于社交網(wǎng)絡(luò)的新型社區(qū)檢測(cè)新方法。該方法使用了兩個(gè)最重要的度量來(lái)定義