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

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

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

【學(xué)位級(jí)別】：碩士

【部分圖文】：

無權(quán)無向圖

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

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

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



本文編號(hào)：3278976