【摘要】：挖掘社交網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)對于揭示網(wǎng)絡(luò)潛在規(guī)律和把握網(wǎng)絡(luò)宏觀特征具有重要意義。目前,已涌現(xiàn)出諸多社團(tuán)挖掘算法,其中有些雖然具有復(fù)雜度近線性的優(yōu)勢,但是卻在應(yīng)用于大型網(wǎng)絡(luò)方面仍然存在兩種局限性,其一是需要預(yù)知網(wǎng)絡(luò)社團(tuán)數(shù)目,其二算法的低復(fù)雜度是以犧牲準(zhǔn)確率來換取的。因此,為了使現(xiàn)有社團(tuán)挖掘算法能夠適用于大型網(wǎng)絡(luò),本文針對這兩種局限性分別進(jìn)行了相應(yīng)地研究和改進(jìn)。主要工作如下:(1)討論常見社團(tuán)挖掘算法在應(yīng)用于大型網(wǎng)絡(luò)時存在的問題,得出低時間復(fù)雜度的算法具有優(yōu)勢但仍然存在兩種局限性的結(jié)論。因此,對社團(tuán)數(shù)目估計方法和標(biāo)號傳播社團(tuán)挖掘算法的國內(nèi)外現(xiàn)狀進(jìn)行調(diào)研,并分析這兩方面已有方法的優(yōu)劣。(2)針對已有社團(tuán)數(shù)目估計方法的準(zhǔn)確率低、計算不高效和適用范圍受限等問題,本文給出一種利用正則無回路矩陣的社團(tuán)數(shù)目估計方法。該方法通過定義一種正則無回路矩陣來描述網(wǎng)絡(luò),并觀察分析其特征值的分布規(guī)律,最后利用本征間隙的最大位置對網(wǎng)絡(luò)社團(tuán)數(shù)目進(jìn)行估計。由兩種經(jīng)典網(wǎng)絡(luò)生成模型合成的人工網(wǎng)絡(luò)上驗證該方法。(3)針對標(biāo)號傳播算法以犧牲算法準(zhǔn)確率和穩(wěn)定性為代價來換取低復(fù)雜度的問題,本文給出一種改進(jìn)的標(biāo)號傳播算法。該算法在標(biāo)號傳播順序上用新定義的復(fù)合權(quán)重對所有節(jié)點進(jìn)行優(yōu)先級排序,在標(biāo)號傳播過程中采用節(jié)點貢獻(xiàn)度對候選標(biāo)號進(jìn)行篩選,最后用新定義的平衡節(jié)點過濾機(jī)制對算法的收斂條件進(jìn)行優(yōu)化。在兩種標(biāo)準(zhǔn)大型社交網(wǎng)絡(luò)數(shù)據(jù)集上驗證該算法。實驗結(jié)果表明:利用正則無回路矩陣的社團(tuán)數(shù)目估計方法重點消除了度異質(zhì)分布對社團(tuán)數(shù)目估計的影響,從而提高了估計結(jié)果的準(zhǔn)確率,且適用范圍不受限;較之標(biāo)號傳播算法和其他兩種大型網(wǎng)絡(luò)社團(tuán)挖掘算法,改進(jìn)的標(biāo)號傳播算法不僅在性能和質(zhì)量方面具有顯著優(yōu)勢,而且社團(tuán)挖掘的效率也有所提高。
[Abstract]:It is of great significance to excavate the community structure in social networks for revealing the potential laws of the network and grasping the macroscopic characteristics of the network. At present, many community mining algorithms have emerged, some of which have the advantage of near linear complexity, but there are still two limitations in the application of large networks. One is the need to predict the number of network communities. Second, the low complexity of the algorithm is achieved at the expense of accuracy. Therefore, in order to make the existing community mining algorithms applicable to large networks, the two limitations are studied and improved accordingly in this paper. The main work is as follows: (1) the problems of common community mining algorithms in large networks are discussed. It is concluded that low time complexity algorithms have advantages but still have two limitations. Therefore, the current situation of community number estimation methods and labeling propagation community mining algorithms at home and abroad are investigated, and the advantages and disadvantages of these two existing methods are analyzed. (2) the accuracy of existing community number estimation methods is low. In this paper a method of estimating the number of communities using regular loop-free matrix is presented in which the computation is not efficient and the scope of application is limited. In this method, a regular loop free matrix is defined to describe the network, and the distribution of eigenvalues is observed and analyzed. Finally, the number of network communities is estimated by using the maximum position of the eigenspace. The proposed method is verified on artificial networks composed of two classical network generation models. (3) an improved labeling propagation algorithm is presented to deal with the problem of low complexity at the expense of the accuracy and stability of the label propagation algorithm. In this algorithm, all nodes are prioritized by the newly defined composite weights in the label propagation sequence, and the candidate labels are filtered by the contribution degree of the nodes in the process of label propagation. Finally, the new balanced node filtering mechanism is used to optimize the convergence conditions of the algorithm. The algorithm is validated on two standard large social network datasets. The experimental results show that the influence of degree heterogeneity distribution on the estimation of community number is mainly eliminated by using the regular loop free matrix estimation method, thus the accuracy of the estimation results is improved, and the range of application is not limited. Compared with label propagation algorithm and other two large network community mining algorithms, the improved labeling propagation algorithm not only has significant advantages in performance and quality, but also improves the efficiency of community mining.
【學(xué)位授予單位】：西安理工大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2017
【分類號】：TP311.13;TP393.09

【參考文獻(xiàn)】

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

1 劉功申;張浩霖;孟魁;蘇波;;非隨機(jī)的標(biāo)簽傳播社區(qū)劃分算法[J];上海交通大學(xué)學(xué)報;2015年08期

2 趙寶峰;趙菊敏;李燈熬;;一種穩(wěn)定的標(biāo)簽傳播社區(qū)發(fā)現(xiàn)算法[J];太原理工大學(xué)學(xué)報;2013年04期

3 張聰;沈惠璋;;基于譜方法的復(fù)雜網(wǎng)絡(luò)中社團(tuán)結(jié)構(gòu)的模塊度[J];系統(tǒng)工程理論與實踐;2013年05期

4 康旭彬;賈彩燕;;一種改進(jìn)的標(biāo)簽傳播快速社區(qū)發(fā)現(xiàn)方法[J];合肥工業(yè)大學(xué)學(xué)報(自然科學(xué)版);2013年01期

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

6 季青松;趙郁忻;陳樂生;陳秀真;李生紅;;有效改善標(biāo)簽傳播算法魯棒性的途徑[J];信息安全與通信保密;2012年09期

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

8 金弟;劉杰;楊博;何東曉;劉大有;;局部搜索與遺傳算法結(jié)合的大規(guī)模復(fù)雜網(wǎng)絡(luò)社區(qū)探測[J];自動化學(xué)報;2011年07期

9 汪小帆;劉亞冰;;復(fù)雜網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)算法綜述[J];電子科技大學(xué)學(xué)報;2009年05期

10 李曉佳;張鵬;狄增如;樊瑛;;復(fù)雜網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)[J];復(fù)雜系統(tǒng)與復(fù)雜性科學(xué);2008年03期

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

1 王錦錦;層次凝聚和主動學(xué)習(xí)半監(jiān)督社團(tuán)檢測算法研究[D];蘭州大學(xué);2014年

2 黃中杰;社交網(wǎng)絡(luò)中的視頻觀看質(zhì)量優(yōu)化[D];復(fù)旦大學(xué);2012年

3 李亞飛;復(fù)雜網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)檢測算法研究[D];北京交通大學(xué);2011年

，

本文編號：2159165