大規(guī)模復雜網(wǎng)絡社區(qū)發(fā)現(xiàn)與社區(qū)進化分析技術研究
發(fā)布時間：2018-09-05 21:20
【摘要】：隨著移動互聯(lián)時代的到來,網(wǎng)絡日益得以普及,各種社交網(wǎng)絡平臺的興起,人們或多或少通過網(wǎng)絡與其他人或物發(fā)生著聯(lián)系,形成復雜的關系網(wǎng)絡,產(chǎn)生了海量的網(wǎng)絡數(shù)據(jù)。復雜網(wǎng)絡的研究對廣告投放、精準營銷、內(nèi)容推薦、用戶行為預測等具有極大的價值,而社區(qū)發(fā)現(xiàn)與社區(qū)進化作為復雜網(wǎng)絡分析中的研究熱點,自提出以來,一直受到學者們的廣泛關注,提出了大量的研究成果。對于社區(qū)發(fā)現(xiàn),隨著網(wǎng)絡規(guī)模增大,傳統(tǒng)社區(qū)發(fā)現(xiàn)算法已無法有效和高效地處理大規(guī)模網(wǎng)絡數(shù)據(jù),本文結合GraphX圖計算框架,提出了新的大規(guī)模復雜網(wǎng)絡社區(qū)并行發(fā)現(xiàn)算法。實驗表明本文算法能夠有效的處理大規(guī)模復雜網(wǎng)絡數(shù)據(jù),百萬級以上節(jié)點處理時間約為4分鐘,是Hadoop平臺下并行發(fā)現(xiàn)算法運行時間的1/20,社區(qū)識別準確率比傳統(tǒng)社區(qū)發(fā)現(xiàn)算法提高了 3%。對于社區(qū)進化,隨著傳統(tǒng)事件框架限制條件越來越寬松,挖掘出的事件雖然增多,但同時也挖掘出了大量冗余事件,而且這些框架沒有考慮到事件的重疊性和伴隨性。為了克服傳統(tǒng)事件框架的問題,本文基于事件框架,提出了弱事件的概念,并對傳統(tǒng)事件框架進行了改進,重新定義了各種事件,并給出了新的限制條件,最后提出了適用于弱事件挖掘的框架。實驗表明本文社區(qū)演化框架發(fā)現(xiàn)事件比傳統(tǒng)框架多22.9%,事件準確率提高了 4%,解決了弱社區(qū)挖掘問題。本文主要工作包括:(1)介紹了復雜網(wǎng)絡社區(qū)發(fā)現(xiàn)及社區(qū)進化的研究背景與意義,并介紹了當前社區(qū)發(fā)現(xiàn)與社區(qū)進化方向的國內(nèi)外研究現(xiàn)狀及最新成果。(2)根據(jù)模塊度思想,結合圖論、網(wǎng)絡性質(zhì)及近似優(yōu)化理論,提出多社區(qū)選擇模型,并設計了新的模塊度增量更新方法,算法首先計算出所有節(jié)點間的模塊度增量,然后選取網(wǎng)絡中所有具有最大模塊度增量的社區(qū)進行合并,最后利用新的模塊度增量更新方法,更新與合并社區(qū)相關的模塊度增量,再結合GraphX設計了并行處理算法。(3)根據(jù)事件框架定義,提出了“弱擴張”、“弱收縮”、“弱分裂”、“弱合并”等新的事件,以解決在一段時間內(nèi)社區(qū)結構同時發(fā)生多種事件的情況。為了能夠準確的發(fā)現(xiàn)這些事件,提出了社區(qū)重疊度、社區(qū)隸屬度、事件發(fā)現(xiàn)準確率等新概念。根據(jù)以上理論提出了基于弱事件的社區(qū)進化分析方法。(4)給出了上述算法的具體實現(xiàn),并將本文所提的分別在仿真復雜網(wǎng)絡和真實復雜網(wǎng)絡數(shù)據(jù)上,同多個算法進行了對比,驗證了本文所提算法的準確性和高效性,全面的分析了本文算法及對比算法的優(yōu)劣之處。
[Abstract]:With the arrival of the era of mobile interconnection, the network is becoming more and more popular. With the rise of various social network platforms, people are more or less connected with other people or things through the network, forming a complex relationship network, and producing massive network data. The research of complex network has great value for advertising, accurate marketing, content recommendation, user behavior prediction, etc. Community discovery and community evolution have been the research focus of complex network analysis since they were put forward. It has been widely concerned by scholars and a large number of research results have been put forward. For community discovery, with the increase of network size, the traditional community discovery algorithm can not deal with large-scale network data effectively and efficiently. In this paper, a new parallel discovery algorithm for large-scale and complex network communities is proposed based on the GraphX graph computing framework. Experiments show that the algorithm can deal with large-scale complex network data effectively, and the processing time of multi-level nodes is about 4 minutes. It is 1 / 20 of the running time of parallel discovery algorithm based on Hadoop, and the accuracy of community recognition improves by 3% compared with traditional community discovery algorithm. For community evolution, with the loosening of the constraints of traditional event frameworks, the number of excavated events increases, but at the same time a large number of redundant events are mined, and these frameworks do not take into account the overlap and concomitant of events. In order to overcome the problem of traditional event framework, this paper proposes the concept of weak event based on event framework, and improves the traditional event framework, redefines all kinds of events, and gives new limiting conditions. Finally, a framework for weak event mining is proposed. The experiments show that the community evolution framework in this paper finds more events 22. 9 more than the traditional framework, and the accuracy of the event is improved by 4%, and the mining problem of weak communities is solved. The main work of this paper is as follows: (1) the research background and significance of complex network community discovery and community evolution are introduced, and the current research status and latest achievements of community discovery and community evolution at home and abroad are introduced. (2) according to modularity, Combined with graph theory, network properties and approximate optimization theory, a multi-community selection model is proposed, and a new modular degree increment updating method is designed. The algorithm first calculates the modularity increment among all nodes. Then all the communities with the largest modular degree increment in the network are selected to merge. Finally, the modular degree increment related to the merged community is updated by using the new modular degree increment updating method. The parallel processing algorithm is designed with GraphX. (3) according to the definition of event frame, new events such as "weak extension", "weak contraction", "weak splitting" and "weak merging" are proposed. To address multiple events that occur at the same time within the community structure. In order to find these events accurately, some new concepts, such as community overlap degree, community membership degree and event discovery accuracy rate, are proposed. Based on the above theory, a method of community evolution analysis based on weak event is proposed. (4) the realization of the above algorithm is given, and the simulation data of complex network and real complex network are compared with other algorithms. The accuracy and efficiency of the proposed algorithm are verified, and the advantages and disadvantages of the algorithm and the contrast algorithm are analyzed.
【學位授予單位】：西南交通大學
【學位級別】：碩士
【學位授予年份】：2017
【分類號】：O157.5
本文編號：2225494
[Abstract]:With the arrival of the era of mobile interconnection, the network is becoming more and more popular. With the rise of various social network platforms, people are more or less connected with other people or things through the network, forming a complex relationship network, and producing massive network data. The research of complex network has great value for advertising, accurate marketing, content recommendation, user behavior prediction, etc. Community discovery and community evolution have been the research focus of complex network analysis since they were put forward. It has been widely concerned by scholars and a large number of research results have been put forward. For community discovery, with the increase of network size, the traditional community discovery algorithm can not deal with large-scale network data effectively and efficiently. In this paper, a new parallel discovery algorithm for large-scale and complex network communities is proposed based on the GraphX graph computing framework. Experiments show that the algorithm can deal with large-scale complex network data effectively, and the processing time of multi-level nodes is about 4 minutes. It is 1 / 20 of the running time of parallel discovery algorithm based on Hadoop, and the accuracy of community recognition improves by 3% compared with traditional community discovery algorithm. For community evolution, with the loosening of the constraints of traditional event frameworks, the number of excavated events increases, but at the same time a large number of redundant events are mined, and these frameworks do not take into account the overlap and concomitant of events. In order to overcome the problem of traditional event framework, this paper proposes the concept of weak event based on event framework, and improves the traditional event framework, redefines all kinds of events, and gives new limiting conditions. Finally, a framework for weak event mining is proposed. The experiments show that the community evolution framework in this paper finds more events 22. 9 more than the traditional framework, and the accuracy of the event is improved by 4%, and the mining problem of weak communities is solved. The main work of this paper is as follows: (1) the research background and significance of complex network community discovery and community evolution are introduced, and the current research status and latest achievements of community discovery and community evolution at home and abroad are introduced. (2) according to modularity, Combined with graph theory, network properties and approximate optimization theory, a multi-community selection model is proposed, and a new modular degree increment updating method is designed. The algorithm first calculates the modularity increment among all nodes. Then all the communities with the largest modular degree increment in the network are selected to merge. Finally, the modular degree increment related to the merged community is updated by using the new modular degree increment updating method. The parallel processing algorithm is designed with GraphX. (3) according to the definition of event frame, new events such as "weak extension", "weak contraction", "weak splitting" and "weak merging" are proposed. To address multiple events that occur at the same time within the community structure. In order to find these events accurately, some new concepts, such as community overlap degree, community membership degree and event discovery accuracy rate, are proposed. Based on the above theory, a method of community evolution analysis based on weak event is proposed. (4) the realization of the above algorithm is given, and the simulation data of complex network and real complex network are compared with other algorithms. The accuracy and efficiency of the proposed algorithm are verified, and the advantages and disadvantages of the algorithm and the contrast algorithm are analyzed.
【學位授予單位】：西南交通大學
【學位級別】：碩士
【學位授予年份】：2017
【分類號】：O157.5
【參考文獻】
相關期刊論文 前10條
1 楊春明;王玉金;;基于模塊度優(yōu)化的加權復雜網(wǎng)絡社團發(fā)現(xiàn)算法分析[J];西南科技大學學報;2016年04期
2 張學武;沈浩東;趙沛然;張卓;李敏;許海燕;;基于事件框架的社區(qū)進化預測研究[J];計算機學報;2017年03期
3 喬少杰;郭俊;韓楠;張小松;元昌安;唐常杰;;大規(guī)模復雜網(wǎng)絡社區(qū)并行發(fā)現(xiàn)算法[J];計算機學報;2017年03期
4 冷作福;;基于貪婪優(yōu)化技術的網(wǎng)絡社區(qū)發(fā)現(xiàn)算法研究[J];電子學報;2014年04期
5 潘磊;金杰;王崇駿;謝俊元;;社會網(wǎng)絡中基于局部信息的邊社區(qū)挖掘[J];電子學報;2012年11期
6 馬磊;任成磊;韓定定;;模塊度優(yōu)化啟發(fā)式算法應用[J];現(xiàn)代電子技術;2012年19期
7 武志昊;林友芳;Steve Gregory;萬懷宇School of Computer and Information Technology,Beijing Jiaotong University;田盛豐;;Balanced Multi-Label Propagation for Overlapping Community Detection in Social Networks[J];Journal of Computer Science & Technology;2012年03期
8 竇炳琳;李澍淞;張世永;;基于結構的社會網(wǎng)絡分析[J];計算機學報;2012年04期
9 吳斌;王柏;楊勝琦;;基于事件的社會網(wǎng)絡演化分析框架[J];軟件學報;2011年07期
10 陳端兵;黃晟;尚明生;;復雜網(wǎng)絡模型及其在疫情傳播和控制中的應用研究[J];計算機科學;2011年06期
相關博士學位論文 前1條
1 田慶飛;基于復雜網(wǎng)絡理論的城市公交網(wǎng)絡生成與優(yōu)化研究[D];吉林大學;2013年
相關碩士學位論文 前3條
1 陳召群;在線社交網(wǎng)絡數(shù)據(jù)挖掘[D];清華大學;2015年
2 李金朋;基于Hadoop平臺的重疊社區(qū)發(fā)現(xiàn)算法研究[D];吉林大學;2014年
3 黃偉平;Web社區(qū)發(fā)現(xiàn)算法的研究[D];北京郵電大學;2013年
，本文編號：2225494
本文鏈接：http://sikaile.net/kejilunwen/yysx/2225494.html
最近更新
教材專著
