【摘要】：在重疊社團(tuán)發(fā)現(xiàn)算法中,基于線圖的重疊社團(tuán)發(fā)現(xiàn)算法是最近幾年興起的比較新的領(lǐng)域,具有廣闊的研究前景,線圖是將邊看作研究對(duì)象來(lái)發(fā)現(xiàn)復(fù)雜網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)的一種方法,線圖的最大優(yōu)勢(shì)就是可以利用非重疊社團(tuán)發(fā)現(xiàn)算法發(fā)現(xiàn)重疊社團(tuán)結(jié)構(gòu)。本文就是基于線圖提出了一種重疊社團(tuán)發(fā)現(xiàn)算法。在真實(shí)世界中,很多復(fù)雜網(wǎng)絡(luò)的社團(tuán)個(gè)數(shù)是未知的,這使得一些依賴于社團(tuán)個(gè)數(shù)先驗(yàn)知識(shí)的算法無(wú)法使用。因此,本文將基于拉普拉斯矩陣的Jordan型圖特征分析應(yīng)用到線圖中,來(lái)獲取線圖社團(tuán)個(gè)數(shù)的先驗(yàn)知識(shí)。然后,將基于拉普拉斯矩陣的譜聚類應(yīng)用到線圖中,通過(guò)拉普拉斯矩陣的特征向量將網(wǎng)絡(luò)中的邊映射到歐氏空間,歐氏空間中每個(gè)特征向量分量中的元素對(duì)應(yīng)了線圖中的節(jié)點(diǎn),并且選擇其中的兩列構(gòu)成特征向量空間,同時(shí)計(jì)算特征向量之間的相似度。最后,有了社團(tuán)個(gè)數(shù)先驗(yàn)知識(shí)的支撐與鋪墊,一方面選擇K-means聚類算法對(duì)特征向量進(jìn)行聚類來(lái)確定社團(tuán)的劃分結(jié)果,既利用了K-means算法簡(jiǎn)單快速的優(yōu)點(diǎn),又符合K-means算法依賴社團(tuán)個(gè)數(shù)先驗(yàn)知識(shí)的特點(diǎn),相得益彰;另一方面,使用層次聚類算法對(duì)特征向量進(jìn)行聚類,在得到層次聚類樹(shù)狀圖后,依據(jù)社團(tuán)個(gè)數(shù)的先驗(yàn)知識(shí)對(duì)層次聚類樹(shù)狀圖進(jìn)行切割,從而確定最終的社團(tuán)劃分結(jié)果。實(shí)驗(yàn)結(jié)果表明,本文算法能夠?qū)崿F(xiàn)對(duì)復(fù)雜網(wǎng)絡(luò)重疊社團(tuán)結(jié)構(gòu)的發(fā)現(xiàn),比相關(guān)算法具有更好的性能。
[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.
【學(xué)位授予單位】：蘭州大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2016
【分類號(hào)】：O157.5

【相似文獻(xiàn)】

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

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

2 孫孝瑞,邵峰晶,劉遵仁;網(wǎng)絡(luò)系統(tǒng)清理問(wèn)題算法[J];青島大學(xué)學(xué)報(bào)(自然科學(xué)版);1997年04期

3 師瑞峰;周一民;周泓;;一種求解雙目標(biāo)job shop問(wèn)題的混合進(jìn)化算法[J];控制與決策;2007年11期

4 徐瑋;康重慶;夏清;;序列運(yùn)算的算法復(fù)雜性分析[J];中國(guó)電機(jī)工程學(xué)報(bào);2009年28期

5 劉明華;;集合性質(zhì)F,■,F~*算法復(fù)雜性的關(guān)系[J];蘭州鐵道學(xué)院學(xué)報(bào);1993年01期

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

7 董麗薇;唐恒永;趙大宇;;廣義最大并行流算法的改進(jìn)[J];系統(tǒng)管理學(xué)報(bào);2007年06期

8 劉家壯;;求樹(shù)的路長(zhǎng)序列的算法[J];山東大學(xué)學(xué)報(bào)(自然科學(xué)版);1987年03期

9 孫宏,杜文;航空公司飛機(jī)排班問(wèn)題的分階段指派算法[J];系統(tǒng)工程學(xué)報(bào);2003年02期

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

相關(guān)會(huì)議論文 前1條

1 韓渭賓;江道崇;鄧建平;袁海良;洪時(shí)中;;算法復(fù)雜性與地震預(yù)報(bào)的研究[A];中國(guó)地震學(xué)會(huì)第五次學(xué)術(shù)大會(huì)論文摘要集[C];1994年

相關(guān)重要報(bào)紙文章 前2條

1 PALADIN;對(duì)算法進(jìn)行分析（2）[N];電腦報(bào);2003年

2 ;編程沙龍[N];電腦報(bào);2003年

相關(guān)博士學(xué)位論文 前10條

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

2 楊智應(yīng);若干算法的復(fù)雜性分析問(wèn)題研究[D];復(fù)旦大學(xué);2004年

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

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

5 孫宏;航空公司飛機(jī)排班問(wèn)題：模型及算法研究[D];西南交通大學(xué);2003年

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

7 曹蓓;粒子濾波改進(jìn)算法及其應(yīng)用研究[D];中國(guó)科學(xué)院研究生院(西安光學(xué)精密機(jī)械研究所);2012年

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

9 李斌;LZ復(fù)雜性算法及其在生物序列分析中的應(yīng)用研究[D];中南大學(xué);2008年

10 曹明;智能算法及其在信息安全若干關(guān)鍵問(wèn)題中的應(yīng)用與研究[D];北京郵電大學(xué);2008年

相關(guān)碩士學(xué)位論文 前10條

1 黃國(guó)明;基于線圖譜分析的復(fù)雜網(wǎng)絡(luò)重疊社團(tuán)發(fā)現(xiàn)算法研究[D];蘭州大學(xué);2015年

2 金巧;基于QSP的MIMO信號(hào)檢測(cè)技術(shù)研究[D];江西理工大學(xué);2015年

3 田苗狀;拍賣算法研究及其應(yīng)用[D];青島大學(xué);2015年

4 焦蓬斐;基于TLD的目標(biāo)跟蹤改進(jìn)算法研究[D];中北大學(xué);2016年

5 嚴(yán)正飛;基于HADOOP云計(jì)算平臺(tái)的聚類算法研究[D];南京大學(xué);2014年

6 何曉婷;基于線圖的復(fù)雜網(wǎng)絡(luò)重疊社團(tuán)發(fā)現(xiàn)算法研究[D];蘭州大學(xué);2016年

7 王凱;差異工件單機(jī)批調(diào)度的自適應(yīng)蟻群退火算法研究[D];中國(guó)科學(xué)技術(shù)大學(xué);2011年

8 蔣文霞;有時(shí)間窗車輛路徑問(wèn)題的模型及算法[D];武漢理工大學(xué);2007年

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

10 車潁濤;時(shí)間約束下的應(yīng)急資源調(diào)度模型及算法研究[D];河南大學(xué);2007年

，

本文編號(hào)：2482149