大規(guī)模復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)與社區(qū)進(jìn)化分析技術(shù)研究
發(fā)布時(shí)間：2018-09-05 21:20
【摘要】：隨著移動(dòng)互聯(lián)時(shí)代的到來(lái),網(wǎng)絡(luò)日益得以普及,各種社交網(wǎng)絡(luò)平臺(tái)的興起,人們或多或少通過(guò)網(wǎng)絡(luò)與其他人或物發(fā)生著聯(lián)系,形成復(fù)雜的關(guān)系網(wǎng)絡(luò),產(chǎn)生了海量的網(wǎng)絡(luò)數(shù)據(jù)。復(fù)雜網(wǎng)絡(luò)的研究對(duì)廣告投放、精準(zhǔn)營(yíng)銷(xiāo)、內(nèi)容推薦、用戶行為預(yù)測(cè)等具有極大的價(jià)值,而社區(qū)發(fā)現(xiàn)與社區(qū)進(jìn)化作為復(fù)雜網(wǎng)絡(luò)分析中的研究熱點(diǎn),自提出以來(lái),一直受到學(xué)者們的廣泛關(guān)注,提出了大量的研究成果。對(duì)于社區(qū)發(fā)現(xiàn),隨著網(wǎng)絡(luò)規(guī)模增大,傳統(tǒng)社區(qū)發(fā)現(xiàn)算法已無(wú)法有效和高效地處理大規(guī)模網(wǎng)絡(luò)數(shù)據(jù),本文結(jié)合GraphX圖計(jì)算框架,提出了新的大規(guī)模復(fù)雜網(wǎng)絡(luò)社區(qū)并行發(fā)現(xiàn)算法。實(shí)驗(yàn)表明本文算法能夠有效的處理大規(guī)模復(fù)雜網(wǎng)絡(luò)數(shù)據(jù),百萬(wàn)級(jí)以上節(jié)點(diǎn)處理時(shí)間約為4分鐘,是Hadoop平臺(tái)下并行發(fā)現(xiàn)算法運(yùn)行時(shí)間的1/20,社區(qū)識(shí)別準(zhǔn)確率比傳統(tǒng)社區(qū)發(fā)現(xiàn)算法提高了 3%。對(duì)于社區(qū)進(jìn)化,隨著傳統(tǒng)事件框架限制條件越來(lái)越寬松,挖掘出的事件雖然增多,但同時(shí)也挖掘出了大量冗余事件,而且這些框架沒(méi)有考慮到事件的重疊性和伴隨性。為了克服傳統(tǒng)事件框架的問(wèn)題,本文基于事件框架,提出了弱事件的概念,并對(duì)傳統(tǒng)事件框架進(jìn)行了改進(jìn),重新定義了各種事件,并給出了新的限制條件,最后提出了適用于弱事件挖掘的框架。實(shí)驗(yàn)表明本文社區(qū)演化框架發(fā)現(xiàn)事件比傳統(tǒng)框架多22.9%,事件準(zhǔn)確率提高了 4%,解決了弱社區(qū)挖掘問(wèn)題。本文主要工作包括:(1)介紹了復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)及社區(qū)進(jìn)化的研究背景與意義,并介紹了當(dāng)前社區(qū)發(fā)現(xiàn)與社區(qū)進(jìn)化方向的國(guó)內(nèi)外研究現(xiàn)狀及最新成果。(2)根據(jù)模塊度思想,結(jié)合圖論、網(wǎng)絡(luò)性質(zhì)及近似優(yōu)化理論,提出多社區(qū)選擇模型,并設(shè)計(jì)了新的模塊度增量更新方法,算法首先計(jì)算出所有節(jié)點(diǎn)間的模塊度增量,然后選取網(wǎng)絡(luò)中所有具有最大模塊度增量的社區(qū)進(jìn)行合并,最后利用新的模塊度增量更新方法,更新與合并社區(qū)相關(guān)的模塊度增量,再結(jié)合GraphX設(shè)計(jì)了并行處理算法。(3)根據(jù)事件框架定義,提出了“弱擴(kuò)張”、“弱收縮”、“弱分裂”、“弱合并”等新的事件,以解決在一段時(shí)間內(nèi)社區(qū)結(jié)構(gòu)同時(shí)發(fā)生多種事件的情況。為了能夠準(zhǔn)確的發(fā)現(xiàn)這些事件,提出了社區(qū)重疊度、社區(qū)隸屬度、事件發(fā)現(xiàn)準(zhǔn)確率等新概念。根據(jù)以上理論提出了基于弱事件的社區(qū)進(jìn)化分析方法。(4)給出了上述算法的具體實(shí)現(xiàn),并將本文所提的分別在仿真復(fù)雜網(wǎng)絡(luò)和真實(shí)復(fù)雜網(wǎng)絡(luò)數(shù)據(jù)上,同多個(gè)算法進(jìn)行了對(duì)比,驗(yàn)證了本文所提算法的準(zhǔn)確性和高效性,全面的分析了本文算法及對(duì)比算法的優(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.
【學(xué)位授予單位】：西南交通大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2017
【分類號(hào)】：O157.5
本文編號(hào)：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.
【學(xué)位授予單位】：西南交通大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2017
【分類號(hào)】：O157.5
【參考文獻(xiàn)】
相關(guān)期刊論文 前10條
1 楊春明;王玉金;;基于模塊度優(yōu)化的加權(quán)復(fù)雜網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)算法分析[J];西南科技大學(xué)學(xué)報(bào);2016年04期
2 張學(xué)武;沈浩東;趙沛然;張卓;李敏;許海燕;;基于事件框架的社區(qū)進(jìn)化預(yù)測(cè)研究[J];計(jì)算機(jī)學(xué)報(bào);2017年03期
3 喬少杰;郭俊;韓楠;張小松;元昌安;唐常杰;;大規(guī)模復(fù)雜網(wǎng)絡(luò)社區(qū)并行發(fā)現(xiàn)算法[J];計(jì)算機(jī)學(xué)報(bào);2017年03期
4 冷作福;;基于貪婪優(yōu)化技術(shù)的網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法研究[J];電子學(xué)報(bào);2014年04期
5 潘磊;金杰;王崇駿;謝俊元;;社會(huì)網(wǎng)絡(luò)中基于局部信息的邊社區(qū)挖掘[J];電子學(xué)報(bào);2012年11期
6 馬磊;任成磊;韓定定;;模塊度優(yōu)化啟發(fā)式算法應(yīng)用[J];現(xiàn)代電子技術(shù);2012年19期
7 武志昊;林友芳;Steve Gregory;萬(wàn)懷宇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 竇炳琳;李澍淞;張世永;;基于結(jié)構(gòu)的社會(huì)網(wǎng)絡(luò)分析[J];計(jì)算機(jī)學(xué)報(bào);2012年04期
9 吳斌;王柏;楊勝琦;;基于事件的社會(huì)網(wǎng)絡(luò)演化分析框架[J];軟件學(xué)報(bào);2011年07期
10 陳端兵;黃晟;尚明生;;復(fù)雜網(wǎng)絡(luò)模型及其在疫情傳播和控制中的應(yīng)用研究[J];計(jì)算機(jī)科學(xué);2011年06期
相關(guān)博士學(xué)位論文 前1條
1 田慶飛;基于復(fù)雜網(wǎng)絡(luò)理論的城市公交網(wǎng)絡(luò)生成與優(yōu)化研究[D];吉林大學(xué);2013年
相關(guān)碩士學(xué)位論文 前3條
1 陳召群;在線社交網(wǎng)絡(luò)數(shù)據(jù)挖掘[D];清華大學(xué);2015年
2 李金朋;基于Hadoop平臺(tái)的重疊社區(qū)發(fā)現(xiàn)算法研究[D];吉林大學(xué);2014年
3 黃偉平;Web社區(qū)發(fā)現(xiàn)算法的研究[D];北京郵電大學(xué);2013年
，本文編號(hào)：2225494
本文鏈接：http://www.sikaile.net/kejilunwen/yysx/2225494.html
最近更新
教材專著
