發(fā)布時間：2018-09-12 14:05

【摘要】：隨著互聯(lián)網(wǎng)的飛速發(fā)展,互聯(lián)網(wǎng)上的數(shù)據(jù)正以爆炸式的速度增長,互聯(lián)網(wǎng)上由用戶構(gòu)成的各種網(wǎng)絡(luò)的規(guī)模也飛速增長,大規(guī)模網(wǎng)絡(luò)的時代已經(jīng)到來。在分析大規(guī)模網(wǎng)絡(luò)的時候,希望能夠有一種快速、高效的方法分析復(fù)雜網(wǎng)絡(luò)中隨著時間改變社團(tuán)結(jié)構(gòu)的演化。盡管過去很多工作致力于靜態(tài)社團(tuán)發(fā)現(xiàn)算法,相對較少的工作發(fā)現(xiàn)動態(tài)網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu),并且傳統(tǒng)的靜態(tài)社區(qū)發(fā)現(xiàn)算法直接用于動態(tài)社團(tuán)發(fā)現(xiàn)普遍存在諸多缺點。為了解決動態(tài)網(wǎng)絡(luò)中社團(tuán)發(fā)現(xiàn)的問題,本文根據(jù)基于頂點的叫做持久力的度量,提出了一種增量式計算的動態(tài)社團(tuán)發(fā)現(xiàn)新方法。該算法的中心思想利用動態(tài)網(wǎng)絡(luò)短時平滑性假設(shè),增量地分析動態(tài)網(wǎng)絡(luò)中部分節(jié)點的社團(tuán)歸屬,從而避免了對整個網(wǎng)絡(luò)的節(jié)點全部重新計算社團(tuán)歸屬,并且引入了一個叫做演化強度的新的度量來衡量增量計算過程中可能引入的誤差以及網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)發(fā)生突變導(dǎo)致的誤差。同時,由于包含真實社團(tuán)結(jié)構(gòu)的動態(tài)網(wǎng)絡(luò)數(shù)據(jù)很少,現(xiàn)有的人工合成方法的局限性,本文提出了一種新穎的包含真實社團(tuán)結(jié)構(gòu)的人工合成動態(tài)網(wǎng)絡(luò)數(shù)據(jù)的方法,通過定義演化事件以及事件的演化率,我們能夠得到更加真實的人工合成數(shù)據(jù)。除此之外,為了提供一種研究大規(guī)模動態(tài)網(wǎng)絡(luò)中社團(tuán)演化的途徑,提出了基于Spark并行計算框架的動態(tài)社團(tuán)發(fā)現(xiàn)算法,并通過不同規(guī)模的動態(tài)網(wǎng)絡(luò)數(shù)據(jù)實驗驗證和分析了我們的并行算法。
[Abstract]:With the rapid development of the Internet, the data on the Internet is increasing at an explosive rate, and the scale of various networks made up of users on the Internet is also growing rapidly. The era of large-scale networks has arrived. When analyzing large-scale networks, it is hoped that there will be a fast and efficient way to analyze the evolution of community structures over time in complex networks. Although much work has been done in the past on static community discovery algorithms, relatively little work has been done to discover community structures in dynamic networks, and traditional static community discovery algorithms directly used in dynamic community discovery have many disadvantages. In order to solve the problem of community discovery in dynamic networks, a new dynamic community discovery method based on vertex called persistence is proposed in this paper. The central idea of this algorithm is to analyze the community ownership of some nodes in dynamic network incrementally by using the assumption of short-term smoothness of dynamic network, thus avoiding the recalculating of all nodes in the whole network. A new measure called evolutionary strength is introduced to measure the errors that may be introduced in the incremental computation process as well as the errors caused by the abrupt changes in the network topology. At the same time, due to the few dynamic network data containing real community structure and the limitations of existing artificial synthesis methods, this paper proposes a novel method of artificial synthesis dynamic network data containing real community structure. By defining evolutionary events and their evolution rates, we can obtain more realistic synthetic data. In addition, in order to provide a way to study community evolution in large-scale dynamic networks, a dynamic community discovery algorithm based on Spark parallel computing framework is proposed. The parallel algorithm is verified and analyzed by dynamic network data experiments of different scales.
【學(xué)位授予單位】：北京郵電大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2016
【分類號】：O157.5;TP301.6

【參考文獻(xiàn)】

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

1 王莉;程學(xué)旗;;在線社會網(wǎng)絡(luò)的動態(tài)社區(qū)發(fā)現(xiàn)及演化[J];計算機學(xué)報;2015年02期

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

1 熊站營;基于增量和密度的動態(tài)網(wǎng)絡(luò)社團(tuán)檢測算法[D];西安電子科技大學(xué);2012年

，

本文編號：2239241