【摘要】：許多研究表明,復雜網(wǎng)絡中普遍存在著社區(qū)結(jié)構(gòu),即社區(qū)內(nèi)部的節(jié)點聯(lián)系緊密,而社區(qū)之間的節(jié)點聯(lián)系則相對稀疏。復雜網(wǎng)絡內(nèi)部的社區(qū)結(jié)構(gòu)具有十分重要的理論意義和應用價值,可以幫助人們理解復雜網(wǎng)絡的功能、發(fā)現(xiàn)復雜網(wǎng)絡中潛在的規(guī)律和預測復雜網(wǎng)絡的行為。本課題主要圍繞復雜網(wǎng)絡社區(qū)發(fā)現(xiàn)和仿射傳播算法進行了研究,包括以下三個方面的內(nèi)容:首先,提出一種基于結(jié)構(gòu)相似度仿射傳播的社區(qū)發(fā)現(xiàn)算法(SS-FAP)。該算法首先選取結(jié)構(gòu)相似度作為節(jié)點之間的相似性度量,并采用一種優(yōu)化的方法來計算相似度矩陣;其次將計算得到的相似度矩陣作為輸入,采用快速仿射傳播算法進行聚類;最后得到最終的社區(qū)結(jié)構(gòu)集合。實驗結(jié)果表明,無論在模擬網(wǎng)絡上還是在真實網(wǎng)絡上,SS-FAP都具有很好的社區(qū)發(fā)現(xiàn)能力,能夠發(fā)現(xiàn)高質(zhì)量的社區(qū)結(jié)構(gòu)。其次,提出一種基于模塊度仿射傳播的社區(qū)發(fā)現(xiàn)算法(MAP)。該算法的主要思想是將模塊度函數(shù)Q嵌入到AP算法的迭代過程中,基于模塊度優(yōu)化來得到最優(yōu)的社區(qū)發(fā)現(xiàn)結(jié)果。實驗結(jié)果表明,與傳統(tǒng)的LPA算法、FN算法、BGLL算法以及原始的AP算法對比,MAP算法能夠更加有效地發(fā)現(xiàn)網(wǎng)絡中的社區(qū)結(jié)構(gòu)。最后,實現(xiàn)一個社區(qū)發(fā)現(xiàn)算法原型系統(tǒng),該原型系統(tǒng)主要實現(xiàn)了SS-FAP算法、MAP算法、LPA算法以及4種社區(qū)發(fā)現(xiàn)評價標準,分別是規(guī)范化互信息、FM指標、準確率與模塊度,并且利用力引導布局算法來可視化顯示網(wǎng)絡。
[Abstract]:Many studies have shown that there is a common community structure in complex networks, that is, the nodes within the community are closely connected, but the node connections between the communities are relatively sparse. The community structure within complex networks has very important theoretical significance and application value, which can help people understand the functions of complex networks, discover the potential laws in complex networks and predict the behavior of complex networks. This paper mainly focuses on the complex network community discovery and affine propagation algorithms, including the following three aspects: first, a community discovery algorithm based on structural similarity affine propagation (SS-FAP) is proposed. Firstly, the structural similarity is selected as the similarity measure between nodes, and an optimized method is used to calculate the similarity matrix. Secondly, the calculated similarity matrix is used as input, and the fast affine propagation algorithm is used to cluster. Finally, the final community structure set is obtained. The experimental results show that SS-FAP has good community discovery ability and high quality community structure both on simulated and real networks. Secondly, a community discovery algorithm (MAP). Based on modular affine propagation is proposed. The main idea of the algorithm is to embed the modular degree function Q into the iterative process of the AP algorithm and obtain the optimal community discovery result based on the modularity optimization. The experimental results show that compared with the traditional LPA algorithm, FN algorithm, BGLL algorithm and the original AP algorithm, the MAP algorithm can find the community structure in the network more effectively. Finally, a community discovery algorithm prototype system is implemented. The prototype system mainly implements SS-FAP algorithm, MAP algorithm, LPA algorithm and four community discovery evaluation criteria, which are normalized mutual information, FM index, accuracy and module degree, respectively. And the force-guided layout algorithm is used to visualize the network.
【學位授予單位】：中國礦業(yè)大學
【學位級別】：碩士
【學位授予年份】：2017
【分類號】：O157.5

【參考文獻】

相關(guān)期刊論文 前10條

1 劉大有;金弟;何東曉;黃晶;楊建寧;楊博;;復雜網(wǎng)絡社區(qū)挖掘綜述[J];計算機研究與發(fā)展;2013年10期

2 黃健斌;鐘翔;孫鶴立;茆婉婷;;基于相似性模塊度最大約束標記傳播的網(wǎng)絡社團發(fā)現(xiàn)算法[J];北京大學學報(自然科學版);2013年03期

3 黃健斌;白楊;康劍梅;鐘翔;張鑫;孫鶴立;;一種基于同步動力學模型的網(wǎng)絡社團發(fā)現(xiàn)方法[J];計算機研究與發(fā)展;2012年10期

4 林旺群;盧風順;丁兆云;吳泉源;周斌;賈焰;;基于帶權(quán)圖的層次化社區(qū)并行計算方法[J];軟件學報;2012年06期

5 金弟;楊博;劉杰;劉大有;何東曉;;復雜網(wǎng)絡簇結(jié)構(gòu)探測——基于隨機游走的蟻群算法[J];軟件學報;2012年03期

6 劉旭;易東云;;基于局部相似性的復雜網(wǎng)絡社區(qū)發(fā)現(xiàn)方法[J];自動化學報;2011年12期

7 馮曉磊;于洪濤;;基于流形距離的半監(jiān)督近鄰傳播聚類算法[J];計算機應用研究;2011年10期

8 劉旭;易東云;;基于向量劃分的復雜網(wǎng)絡社區(qū)結(jié)構(gòu)發(fā)現(xiàn)[J];中國科學:物理學 力學 天文學;2011年09期

9 趙卓翔;王軼彤;田家堂;周澤學;;社會網(wǎng)絡中基于標簽傳播的社區(qū)發(fā)現(xiàn)新算法[J];計算機研究與發(fā)展;2011年S3期

10 黃發(fā)良;肖南峰;;基于線圖與PSO的網(wǎng)絡重疊社區(qū)發(fā)現(xiàn)[J];自動化學報;2011年09期

相關(guān)碩士學位論文 前4條

1 王淑靖;非重疊社區(qū)發(fā)現(xiàn)中近鄰傳播算法的研究與應用[D];中國礦業(yè)大學;2016年

2 周然然;社會網(wǎng)絡中局部社區(qū)發(fā)現(xiàn)算法研究[D];中國礦業(yè)大學;2015年

3 包偉偉;無線傳感器網(wǎng)絡低延遲鄰居發(fā)現(xiàn)算法研究[D];中國礦業(yè)大學;2015年

4 石夢雨;基于改進標簽傳播算法的社區(qū)挖掘研究[D];中國礦業(yè)大學;2015年

，

本文編號：2321392