發(fā)布時(shí)間：2020-12-09 06:28

　　現(xiàn)實(shí)世界中的許多復(fù)雜系統(tǒng)都可以抽象地表現(xiàn)為網(wǎng)絡(luò)形態(tài),隨著大型網(wǎng)絡(luò)數(shù)據(jù)可用性的提高,以及學(xué)者們對復(fù)雜網(wǎng)絡(luò)定量、定性特征研究的深入,大型復(fù)雜網(wǎng)絡(luò)的研究已變成一門極具意義的課題,而找尋復(fù)雜網(wǎng)絡(luò)數(shù)據(jù)中的社群結(jié)構(gòu)正是其中被著重研究的難點(diǎn)之一。2017年,一種圍繞找到社團(tuán)中心點(diǎn)繼而吸引拉攏周圍其他點(diǎn)的類天體萬有引力的基于種子點(diǎn)選取的重疊社區(qū)發(fā)現(xiàn)算法(CNS)被提出,隨后,在2019年被提出的一種融入了其他天體磁力干擾的基于中心邊選取的重疊社區(qū)發(fā)現(xiàn)算法(CES)是對傳統(tǒng)的CNS做出了的進(jìn)一步改進(jìn),但由于CES算法延續(xù)了CNS算法的種子節(jié)點(diǎn)的選取過程,導(dǎo)致其在對節(jié)點(diǎn)質(zhì)量的評估過程中存在一定偏差,因而極易產(chǎn)生影響力函數(shù)在對網(wǎng)絡(luò)社區(qū)描述過程中產(chǎn)生不準(zhǔn)確結(jié)果的可能,最終導(dǎo)致劃分結(jié)果與真實(shí)情況不符或精確度不高等情況。本文針對CES的種子節(jié)點(diǎn)的選取過程和聚類過程,提出了相應(yīng)的基于高影響力邊的重疊社區(qū)發(fā)現(xiàn)算法(HIE),HIE分別在以下三部分對之前的算法進(jìn)行了相應(yīng)改善:利用鄰居節(jié)點(diǎn)聯(lián)系度(neighbor node connection degree,NNCD)調(diào)整了節(jié)點(diǎn)的質(zhì)量來獲得更加合理的種子節(jié)點(diǎn),NNCD是... 

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

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

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

【部分圖文】：

重疊社區(qū)（左）和非重疊社區(qū)（右）

第2章社區(qū)發(fā)現(xiàn)算法綜述6第2章社區(qū)發(fā)現(xiàn)算法綜述本章我們將從傳統(tǒng)的、重疊的和基于邊這三個(gè)維度，對社區(qū)發(fā)現(xiàn)算法展開詳細(xì)介紹，分這三個(gè)方向只是為了更清晰的論述，需要強(qiáng)調(diào)的是，這三個(gè)維度不是完全不相交叉的分類，同時(shí)也針對每類分別列舉了一些具有代表性的和時(shí)下熱門的算法，對算法流程、特點(diǎn)和適用范圍進(jìn)行了說明。2.1傳統(tǒng)的社區(qū)發(fā)現(xiàn)算法2.1.1圖分割算法此類算法中最基本的一種算法是由Yuri等提出的最小割算法（MinimumCut），該算法在GraphCut、GrabCut等算法中得到了充分的應(yīng)用。割即是一個(gè)劃分圖中頂點(diǎn)的過程，把邊放在一個(gè)集合里便是最小割，目的是讓連接兩個(gè)劃分的邊的數(shù)目達(dá)到最小值。在下圖中，邊(e,k)和邊(d,h)是最小割。下面介紹最小割算法的原理，首先通過計(jì)算得到圖中的最小割所在邊，這個(gè)過程是按事前確定的分組數(shù)將網(wǎng)格進(jìn)行劃分，同時(shí)滿足各組連接的邊的數(shù)目最小的過程。在負(fù)載均衡中，最小割算法應(yīng)用于分布式計(jì)算，利用該算法能夠有效減少互不相關(guān)的節(jié)點(diǎn)間的聯(lián)系，對于集群節(jié)點(diǎn)尤為有效。但該算法也有局限之處，例如事先限制了網(wǎng)格的理想切割數(shù)，從而不能根據(jù)發(fā)現(xiàn)節(jié)點(diǎn)間關(guān)系劃分社區(qū)，因此該算法應(yīng)用范圍有限。理解最小割的思路對于社區(qū)發(fā)現(xiàn)有很大意義，因?yàn)樯鐓^(qū)發(fā)現(xiàn)的過程從某種方面看就是尋找最優(yōu)最小割的過程。圖2.1最小割示意圖

第2章社區(qū)發(fā)現(xiàn)算法綜述813交換A中的（12kaaa，，，）與B中的（12kbbb，，，）；14until（G≤0）；15returnA和B。在該算法中，V是一個(gè)包含2n個(gè)節(jié)點(diǎn)的集合，E是邊集合，C是一個(gè)2n*2n的權(quán)重矩陣，ijC代表節(jié)點(diǎn)i和j的直接邊權(quán)重，其中0iiC=。Kernighan-Lin算法分為以下幾個(gè)步驟：第一步把待劃分的圖G中的節(jié)點(diǎn)隨機(jī)劃分到兩個(gè)指定規(guī)模的A、B社區(qū)中；第二步從兩個(gè)社區(qū)中分別選擇節(jié)點(diǎn)i和j，交換兩節(jié)點(diǎn)的位置并計(jì)算交換前后G值的變化情況；第三步重復(fù)上述步驟，其中已交換過的節(jié)點(diǎn)不再交換；第四步當(dāng)所有節(jié)點(diǎn)交換完成后停止。2.1.2基于模塊度的算法基于模塊度的方法亦是一類比較有特色的傳統(tǒng)算法[5]。社區(qū)挖掘之初，難以定量評估算法效果。直到2003年Newman基于將相同類型的節(jié)點(diǎn)的鏈接分?jǐn)?shù)與從隨機(jī)結(jié)構(gòu)中出現(xiàn)的相同類型的節(jié)點(diǎn)的鏈接分?jǐn)?shù)進(jìn)行比較的思想提出了模塊度的概念，即：=linkNQm···············································(2.1)其中，Q是模塊度，分子部分表示的是同種節(jié)點(diǎn)之間的鏈路邊數(shù)，分母則表示的是所有的鏈路數(shù)。比方說我們有這么一個(gè)網(wǎng)絡(luò)，其中0、1號節(jié)點(diǎn)屬性相同，2、3、4號節(jié)點(diǎn)屬性相同，那么同種節(jié)點(diǎn)之間的邊數(shù)為3，總邊數(shù)為5。圖2.2模塊度示意圖對于這種簡單的圖可以數(shù)得過來，可以依次去計(jì)算，但復(fù)雜的網(wǎng)絡(luò)須依靠算法來完成。同種節(jié)點(diǎn)之間的鏈路邊可以通過公式(2.2)得到。

【參考文獻(xiàn)】：
期刊論文
[1]面向?qū)傩跃W(wǎng)絡(luò)的重疊社區(qū)發(fā)現(xiàn)算法[J]. 杜航原,裴希亞,王文劍.  計(jì)算機(jī)應(yīng)用. 2019(11)
[2]一種新型的基于Levenshtein距離層次聚類的時(shí)序操作優(yōu)化方法[J]. 朱堅(jiān),楊博,王永健,唐曉婕,李宏光.  化工學(xué)報(bào). 2019(02)
[3]基于深度游走模型的標(biāo)簽傳播社區(qū)發(fā)現(xiàn)算法[J]. 馮曦,朱福喜,劉世超.  計(jì)算機(jī)工程. 2018(03)
[4]基于種子節(jié)點(diǎn)選擇的重疊社區(qū)發(fā)現(xiàn)算法[J]. 齊金山,梁循,王怡.  計(jì)算機(jī)應(yīng)用研究. 2017(12)
[5]引入極值非相鄰連接的連接聚類方法[J]. 王貴參,黃嵐,王巖,宋立明,歐歌.  吉林大學(xué)學(xué)報(bào)(工學(xué)版). 2016(05)
[6]基于復(fù)雜網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)算法[J]. 楊曉光,朱保平.  南京理工大學(xué)學(xué)報(bào). 2016(03)
[7]基于加權(quán)邊相似度的重疊社區(qū)發(fā)現(xiàn)算法[J]. 王元欣,劉培強(qiáng).  山東師范大學(xué)學(xué)報(bào)(自然科學(xué)版). 2016(02)
[8]基于相關(guān)系數(shù)和最佳閾值的股票網(wǎng)絡(luò)模型構(gòu)建[J]. 吳翎燕,韓華,宋寧寧.  復(fù)雜系統(tǒng)與復(fù)雜性科學(xué). 2013(04)

碩士論文
[1]基于中心邊選擇的重疊社區(qū)發(fā)現(xiàn)算法研究[D]. 張方.吉林大學(xué) 2019
[2]面向復(fù)雜交通網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)方法研究[D]. 吳永科.山西大學(xué) 2018
[3]局部拓展類重疊社區(qū)發(fā)現(xiàn)算法的研究[D]. 袁闖.重慶大學(xué) 2018



本文編號：2906443