復雜網(wǎng)絡(luò)種類繁多,遍及人類社會的方方面面,涉及到的學科領(lǐng)域也復雜多樣,復雜網(wǎng)絡(luò)研究工作吸引了相關(guān)領(lǐng)域研究人員的關(guān)注,也越來越受重視。特別是二十一世紀以來,互聯(lián)網(wǎng)技術(shù)取得了前所未有的跨越式發(fā)展,對復雜網(wǎng)絡(luò)研究工作具有很大的推進作用。近年來,來自相關(guān)領(lǐng)域的專家學者提出了很多復雜網(wǎng)絡(luò)進行社團檢測算法,標簽傳播算法就是其中比較經(jīng)典的一個,該算法具有高效快速、無需先驗信息等優(yōu)點,但也存在穩(wěn)定性不足、容易形成巨型社區(qū)等缺點。本文對已有的復雜網(wǎng)絡(luò)社團檢測算法做了較為細致的研究,尤其對標簽傳播算法的具體步驟和優(yōu)缺點進行了認真研究,并對網(wǎng)絡(luò)的聚類系數(shù)性質(zhì)進行深入分析,由節(jié)點的聚類系數(shù)和網(wǎng)絡(luò)的聚類系數(shù),擴展提出了社團聚類系數(shù)的概念。針對標簽傳播算法存在的結(jié)果不穩(wěn)定、容易形成巨片社區(qū)等問題,本文結(jié)合點聚類系數(shù)和社團聚類系數(shù)的概念,分別提出了基于點聚類系數(shù)的標簽傳播改進算法和基于社團聚類系數(shù)的標簽傳播改進算法。其中,基于點聚類系數(shù)的標簽傳播改進算法首先根據(jù)節(jié)點的聚類系數(shù)和度對節(jié)點進行優(yōu)先級排序,在初始化標簽階段改進策略,僅對優(yōu)先級較高的節(jié)點進行標簽初始化,在標簽傳播過程中根據(jù)節(jié)點的聚類系數(shù)對鄰節(jié)點進行排序,選... 

【文章來源】：蘭州大學甘肅省 211工程院校 985工程院校 教育部直屬院校

【文章頁數(shù)】：62 頁

【學位級別】：碩士

【部分圖文】：

無權(quán)無向圖

蘭州大學碩士學位論文基于聚類系數(shù)的社團檢測算法研究122.2.3聚類系數(shù)節(jié)點的聚類系數(shù)是節(jié)點的重要屬性，通俗來講，它描述節(jié)點的鄰居節(jié)點之間互連的概率。除了節(jié)點的聚類系數(shù)，還有邊的聚類系數(shù)、網(wǎng)絡(luò)的聚類系數(shù)以及社團的聚類系數(shù)，為避免歧義，一般會加上限定詞，比如稱點聚類系數(shù)或稱為某節(jié)點的聚類系數(shù)。假設(shè)節(jié)點的度為，即節(jié)點有個鄰居節(jié)點，如果該節(jié)點的鄰居節(jié)點之間也都兩兩互連，那么，這些鄰居節(jié)點之間就存在(1)/2條邊。這時，節(jié)點和它的鄰居節(jié)點就構(gòu)成一個完全圖。然而實際情況中，節(jié)點的鄰居節(jié)點之間不一定全部互相連接，所以鄰居節(jié)點之間實際存在的邊數(shù)是小于等于(1)/2的。點聚類系數(shù)的計算公式為：=((1))/2=2(1)(2-3)，上式中，代表節(jié)點的個鄰居節(jié)點之間實際存在的邊數(shù)。當=0或=1時，必有=0，此時上式的分母也為0，我們記=0。那么，的范圍就是[0,1]。節(jié)點聚類系數(shù)的定義也可以從網(wǎng)絡(luò)中三角形的數(shù)量方面來闡述。等價于以節(jié)點為頂點之一的三角形的個數(shù)，而根據(jù)節(jié)點有個鄰居節(jié)點，所以以節(jié)點為頂點的三角形至多有(1)/2個。而以節(jié)點為中心的連通三元組的數(shù)目，就等于以節(jié)點為頂點的三角形的最大可能數(shù)目。因此，從幾何上給出節(jié)點的聚類系數(shù)如下：=包含節(jié)點的三角形的數(shù)目以節(jié)點為中心的連通三元組的數(shù)目(2-4)圖2-2以節(jié)點i為中心的連通三元組的兩種可能形式公式（2-3）和公式（2-4）給出了節(jié)點的點聚類系數(shù)的兩種定義，網(wǎng)絡(luò)的聚類系數(shù)的定義因此也有兩種。網(wǎng)絡(luò)聚類系數(shù)的第一種定義為根據(jù)公式（2-3）推廣，即求出該網(wǎng)絡(luò)所有節(jié)點的點聚類系數(shù)的均值，公式如下：=1∑=1(2-5)

蘭州大學碩士學位論文基于聚類系數(shù)的社團檢測算法研究22（3）根據(jù)增量矩陣每一行的最大增量，求出增量最大堆。（4）根據(jù)增量最大堆，求出其中的最大增量。（5）根據(jù)最大增量對應的兩個節(jié)點，合并他們的社團，并更新增量矩陣、最大堆和最大增量。（6）重復步驟（4）和（5），直到網(wǎng)絡(luò)所有節(jié)點都劃分到一個社團。由以上算法步驟可知，在CNM算法的計算過程中，模塊度只有一個最大值，所以取模塊度取最大值時對應的社團劃分結(jié)果作為網(wǎng)絡(luò)的社團結(jié)構(gòu)。CNM算法的計算過程采用了最大堆來計算模塊度增量，算法時間復雜度為(2)。2.6.4BGLL算法BGLL算法是Blondel等人[17]提出的一種基于模塊度優(yōu)化的社團檢測算法，該算法能夠用于檢測加權(quán)網(wǎng)絡(luò)。由于提出該算法時，作者均在魯汶大學就職，因此該算法又名Louvain算法。該算法步驟如下：（1）首先，遍歷所有節(jié)點，根據(jù)節(jié)點間的連接情況和網(wǎng)絡(luò)的總結(jié)點數(shù)等屬性，依次計算節(jié)點之間的模塊度增量，構(gòu)成一個模塊度增量矩陣，再由矩陣得到其中最大的模塊度增量，若該增量為正，則將當前節(jié)點加入該鄰居節(jié)點所在社團，若為負，保持節(jié)點的社團不變。重復上述步驟直到合并現(xiàn)象不再發(fā)生，就得到第一個階段的結(jié)果。圖2-3BGLL算法的處理過程（取自文獻[17]）（2）其次，根據(jù)（1）的結(jié)果，把社團作為節(jié)點，將原社團之間存在的邊數(shù)作為新節(jié)點之間的權(quán)重，重新構(gòu)建一個新的網(wǎng)絡(luò)，然后對新網(wǎng)絡(luò)執(zhí)行（1）的步驟。直到整個網(wǎng)絡(luò)劃分為一個社團或不能再劃分為止。圖2-3顯示了BGLL算法對包含16個節(jié)點的網(wǎng)絡(luò)的社團檢測的處理過程：第一層結(jié)果包含4個社團，第二層包含2個社團。

【參考文獻】：
期刊論文
[1]一種面向社區(qū)發(fā)現(xiàn)的高魯棒性標簽傳播算法[J]. 鄭少強,趙中英,馮慧子,李超.  小型微型計算機系統(tǒng). 2018(08)
[2]基于加權(quán)聚類集成的標簽傳播算法[J]. 張美琴,白亮,王俊斌.  智能系統(tǒng)學報. 2018(06)
[3]基于矢量影響力聚類系數(shù)的高效有向網(wǎng)絡(luò)社團劃分算法[J]. 鄧小龍,翟佳羽,尹欒玉.  電子與信息學報. 2017(09)
[4]基于模塊度優(yōu)化的標簽傳播社區(qū)發(fā)現(xiàn)算法[J]. 李磊,倪林.  計算機系統(tǒng)應用. 2016(09)
[5]基于標簽傳播概率的重疊社區(qū)發(fā)現(xiàn)算法[J]. 劉世超,朱福喜,甘琳.  計算機學報. 2016(04)
[6]標簽傳播算法理論及其應用研究綜述[J]. 張俊麗,常艷麗,師文.  計算機應用研究. 2013(01)
[7]一種基于聚集系數(shù)的局部社團劃分算法[J]. 李孔文,顧慶,張堯,陳道蓄.  計算機科學. 2010(07)
[8]復雜網(wǎng)絡(luò)研究概述[J]. 周濤,柏文潔,汪秉宏,劉之景,嚴鋼.  物理. 2005(01)



本文編號：3278976