【摘要】：在重疊社團發(fā)現算法中,基于線圖的重疊社團發(fā)現算法是最近幾年興起的比較新的領域,具有廣闊的研究前景,線圖是將邊看作研究對象來發(fā)現復雜網絡社團結構的一種方法,線圖的最大優(yōu)勢就是可以利用非重疊社團發(fā)現算法發(fā)現重疊社團結構。本文就是基于線圖提出了一種重疊社團發(fā)現算法。在真實世界中,很多復雜網絡的社團個數是未知的,這使得一些依賴于社團個數先驗知識的算法無法使用。因此,本文將基于拉普拉斯矩陣的Jordan型圖特征分析應用到線圖中,來獲取線圖社團個數的先驗知識。然后,將基于拉普拉斯矩陣的譜聚類應用到線圖中,通過拉普拉斯矩陣的特征向量將網絡中的邊映射到歐氏空間,歐氏空間中每個特征向量分量中的元素對應了線圖中的節(jié)點,并且選擇其中的兩列構成特征向量空間,同時計算特征向量之間的相似度。最后,有了社團個數先驗知識的支撐與鋪墊,一方面選擇K-means聚類算法對特征向量進行聚類來確定社團的劃分結果,既利用了K-means算法簡單快速的優(yōu)點,又符合K-means算法依賴社團個數先驗知識的特點,相得益彰;另一方面,使用層次聚類算法對特征向量進行聚類,在得到層次聚類樹狀圖后,依據社團個數的先驗知識對層次聚類樹狀圖進行切割,從而確定最終的社團劃分結果。實驗結果表明,本文算法能夠實現對復雜網絡重疊社團結構的發(fā)現,比相關算法具有更好的性能。
[Abstract]:Among the overlapping community discovery algorithms, the overlapping community discovery algorithm based on graph is a relatively new field rising in recent years, and has a broad research prospect. Graph is a method to find the complex network community structure by taking the edge as the research object. The biggest advantage of graph is that the non-overlapping community discovery algorithm can be used to find the overlapping community structure. In this paper, an overlap community discovery algorithm based on graph is proposed. In the real world, the number of societies in many complex networks is unknown, which makes some algorithms that depend on the prior knowledge of the number of communities unusable. Therefore, in this paper, the Jordan type graph feature analysis based on Laplace matrix is applied to the graph to obtain the prior knowledge of the number of graph societies. Then, the spectral clustering based on Laplace matrix is applied to the graph, and the edges in the network are mapped to Euclidean space by the eigenvector of Laplace matrix. The elements in each eigenvector component in Euclidean space correspond to the nodes in the graph. Two columns are selected to form the feature vector space, and the similarity between the feature vectors is calculated at the same time. Finally, with the support and foreshadowing of the prior knowledge of the number of communities, on the one hand, the K-means clustering algorithm is selected to cluster the feature vectors to determine the segmentation results of the community, which makes use of the advantages of simple and fast K-means algorithm. It also accords with the characteristic that K-means algorithm depends on the prior knowledge of the number of communities and complements each other. On the other hand, the hierarchical clustering algorithm is used to cluster the feature vector. After the hierarchical clustering tree is obtained, the hierarchical clustering tree is cut according to the prior knowledge of the number of communities, so as to determine the final community partition results. The experimental results show that the proposed algorithm can discover the overlapping community structure of complex networks, and has better performance than the related algorithms.
【學位授予單位】：蘭州大學
【學位級別】：碩士
【學位授予年份】：2016
【分類號】：O157.5

【相似文獻】

相關期刊論文 前10條

1 王明;一種基于排序的旅行售貨員問題算法──（Ⅰ）算法原理與算法復雜性估計[J];華南理工大學學報(自然科學版);1994年05期

2 孫孝瑞,邵峰晶,劉遵仁;網絡系統清理問題算法[J];青島大學學報(自然科學版);1997年04期

3 師瑞峰;周一民;周泓;;一種求解雙目標job shop問題的混合進化算法[J];控制與決策;2007年11期

4 徐瑋;康重慶;夏清;;序列運算的算法復雜性分析[J];中國電機工程學報;2009年28期

5 劉明華;;集合性質F,■,F~*算法復雜性的關系[J];蘭州鐵道學院學報;1993年01期

6 佟冶;;線性平移策略降低算法復雜度的研究與實踐[J];上海師范大學學報(自然科學版);2010年06期

7 董麗薇;唐恒永;趙大宇;;廣義最大并行流算法的改進[J];系統管理學報;2007年06期

8 劉家壯;;求樹的路長序列的算法[J];山東大學學報(自然科學版);1987年03期

9 孫宏,杜文;航空公司飛機排班問題的分階段指派算法[J];系統工程學報;2003年02期

10 徐精明,曹先彬,王煦法;多態(tài)蟻群算法[J];中國科學技術大學學報;2005年01期

相關會議論文 前1條

1 韓渭賓;江道崇;鄧建平;袁海良;洪時中;;算法復雜性與地震預報的研究[A];中國地震學會第五次學術大會論文摘要集[C];1994年

相關重要報紙文章 前2條

1 PALADIN;對算法進行分析（2）[N];電腦報;2003年

2 ;編程沙龍[N];電腦報;2003年

相關博士學位論文 前10條

1 馮思玲;生物地理學優(yōu)化算法及其在生物序列模式發(fā)現中的應用[D];電子科技大學;2014年

2 楊智應;若干算法的復雜性分析問題研究[D];復旦大學;2004年

3 李相勇;車輛路徑問題模型及算法研究[D];上海交通大學;2007年

4 韓麗霞;自然啟發(fā)的優(yōu)化算法及其應用研究[D];西安電子科技大學;2009年

5 孫宏;航空公司飛機排班問題：模型及算法研究[D];西南交通大學;2003年

6 劉玉身;離散模型光滑算法的研究[D];清華大學;2006年

7 曹蓓;粒子濾波改進算法及其應用研究[D];中國科學院研究生院(西安光學精密機械研究所);2012年

8 劉道建;SLI的條件冗余性及LP問題的算法研究[D];西南交通大學;2013年

9 李斌;LZ復雜性算法及其在生物序列分析中的應用研究[D];中南大學;2008年

10 曹明;智能算法及其在信息安全若干關鍵問題中的應用與研究[D];北京郵電大學;2008年

相關碩士學位論文 前10條

1 黃國明;基于線圖譜分析的復雜網絡重疊社團發(fā)現算法研究[D];蘭州大學;2015年

2 金巧;基于QSP的MIMO信號檢測技術研究[D];江西理工大學;2015年

3 田苗狀;拍賣算法研究及其應用[D];青島大學;2015年

4 焦蓬斐;基于TLD的目標跟蹤改進算法研究[D];中北大學;2016年

5 嚴正飛;基于HADOOP云計算平臺的聚類算法研究[D];南京大學;2014年

6 何曉婷;基于線圖的復雜網絡重疊社團發(fā)現算法研究[D];蘭州大學;2016年

7 王凱;差異工件單機批調度的自適應蟻群退火算法研究[D];中國科學技術大學;2011年

8 蔣文霞;有時間窗車輛路徑問題的模型及算法[D];武漢理工大學;2007年

9 詹士昌;蟻群算法及其在連續(xù)性空間優(yōu)化問題中的應用[D];浙江大學;2002年

10 車潁濤;時間約束下的應急資源調度模型及算法研究[D];河南大學;2007年

，

本文編號：2482149