本文選題：復雜網(wǎng)絡　切入點：社區(qū)結構　出處：《太原理工大學》2017年碩士論文

【摘要】：社會中存在的各種關系都可以抽象成網(wǎng)絡拓撲,對網(wǎng)絡拓撲學的研究一直是復雜網(wǎng)絡研究課題中的重要方面,研究內(nèi)容涉及到劃分社區(qū)以及對網(wǎng)絡中關鍵屬性特征的研究。近來社區(qū)發(fā)現(xiàn)方法層出不窮,從研究方向上分有靜態(tài)社區(qū)研究和動態(tài)社區(qū)研究,從研究社區(qū)發(fā)現(xiàn)的算法上分有全局視角和局部視角,從社區(qū)發(fā)現(xiàn)的評價機制上分有計算社區(qū)模塊度和社區(qū)互信息,也有另辟蹊徑將社區(qū)穩(wěn)定性作為社區(qū)評價標準,社區(qū)發(fā)現(xiàn)結果的好壞直接反映出社區(qū)發(fā)現(xiàn)方法的優(yōu)劣。本文針對復雜網(wǎng)絡的社區(qū)發(fā)現(xiàn)算法,從全局和局部兩個角度對社區(qū)的穩(wěn)定性進行分析,并對社區(qū)發(fā)現(xiàn)的質量進行評價,主要研究內(nèi)容包括以下兩個方面:(1)研究了如何運用局部擴張社區(qū)的方法探測網(wǎng)絡中存在的穩(wěn)定社區(qū)結構。局部優(yōu)化網(wǎng)絡不需要掌握整個網(wǎng)絡的信息規(guī)模,對于大型網(wǎng)絡在計算復雜度上會更有優(yōu)勢。研究發(fā)現(xiàn)網(wǎng)絡的穩(wěn)定性對于社區(qū)結構的發(fā)現(xiàn)有很大影響,對同一個網(wǎng)絡運用不同的局部優(yōu)化算法得到的社區(qū)劃分結果并不是完全一樣的,其中對相同的部分深入分析,能夠發(fā)現(xiàn)網(wǎng)絡中存在的穩(wěn)定社區(qū)以及常駐節(jié)點。同時引入了節(jié)點和網(wǎng)絡穩(wěn)定度計算的方法,提出一種可探測社區(qū)穩(wěn)定結構的局部社區(qū)發(fā)現(xiàn)算法。最后通過在LFR集成網(wǎng)絡和真實網(wǎng)絡中驗證表明該算法能夠準確的發(fā)現(xiàn)網(wǎng)絡中存在的核心穩(wěn)定社區(qū)。(2)研究了如何從全局角度出發(fā)探索網(wǎng)絡中存在的穩(wěn)定社區(qū)結構。全局優(yōu)化方法最早為網(wǎng)絡中的社區(qū)發(fā)現(xiàn)提供了思路,如圖劃分,層次聚類等。由于整個網(wǎng)絡的節(jié)點數(shù)和連邊數(shù)特別多,而且很大部分連接并不緊密,本文首先對網(wǎng)絡進行預處理,通過對網(wǎng)絡的隨機震蕩,發(fā)現(xiàn)網(wǎng)絡中的核心穩(wěn)定社區(qū)。所發(fā)現(xiàn)的核心穩(wěn)定社區(qū)只是網(wǎng)絡的一部分不能充分反映網(wǎng)絡的整體信息,基于此將發(fā)現(xiàn)的核心社團作為超點,與剩余節(jié)點合并構成一個新的網(wǎng)絡,使用最大化模塊度的算法,發(fā)現(xiàn)出具有模塊度高且穩(wěn)定性高的社區(qū)。最后在真實網(wǎng)絡和集成網(wǎng)絡上測試算法結果,發(fā)現(xiàn)經(jīng)過網(wǎng)絡預處理后的網(wǎng)絡穩(wěn)定值和模塊度都較高,提高了網(wǎng)絡的魯棒性。綜上,本文分別應用了全局優(yōu)化和局部優(yōu)化的思想對復雜網(wǎng)絡中的社區(qū)結構進行研究,主要內(nèi)容是發(fā)現(xiàn)網(wǎng)絡中固有的核心穩(wěn)定社區(qū)。最后通過實驗證明了本文算法的有效性,對于社區(qū)發(fā)現(xiàn)算法的進一步研究提供了理論資料。
[Abstract]:All kinds of relationships in society can be abstracted into network topology. The study of network topology has always been an important aspect in the research of complex networks. The research involves the division of communities and the study of the characteristics of key attributes in the network. Recently, community discovery methods have been emerging in endlessly, including static community research and dynamic community research. The algorithm of community discovery is divided into global perspective and local perspective, the evaluation mechanism of community discovery includes computing community module degree and community mutual information, and there is a new way to use community stability as community evaluation standard. The community discovery results directly reflect the advantages and disadvantages of the community discovery methods. This paper analyzes the community stability from the global and local perspectives, and evaluates the quality of community discovery, aiming at the community discovery algorithm of complex networks. The main research contents include the following two aspects: 1) how to use the method of local expansion community to detect the stable community structure in the network. The local optimization network does not need to master the information scale of the whole network. It is found that the stability of the network has great influence on the discovery of community structure. The results of community partition obtained by using different local optimization algorithms for the same network are not exactly the same, in which the same part is deeply analyzed. The stable community and resident nodes in the network can be found. At the same time, the method of node and network stability calculation is introduced. A local community discovery algorithm with detectable community stability structure is proposed. Finally, the verification in LFR integrated network and real network shows that the algorithm can accurately find the core stable community in the network. He explored the stable community structure in the network from a global perspective. The global optimization method was the first to provide ideas for community discovery in the network. Such as graph partition, hierarchical clustering and so on. Because there are many nodes and connected edges in the whole network, and most of the connections are not close, this paper preprocesses the network first, and through the random oscillation of the network, The core stable community found in the network is only a part of the network that can not fully reflect the overall information of the network. Based on this, the core community found in the network is regarded as a super point and merged with the remaining nodes to form a new network. Using the algorithm of maximization of modularity, the community with high degree of modularity and high stability is found. Finally, the results of the algorithm are tested on real network and integrated network, and it is found that the network stability and modularity are higher after network preprocessing. The robustness of the network is improved. In summary, the idea of global optimization and local optimization is applied to study the community structure in complex networks. The main content is to find the core stable community in the network. Finally, the effectiveness of the algorithm is proved by experiments, which provides theoretical data for the further study of the community discovery algorithm.
【學位授予單位】：太原理工大學
【學位級別】：碩士
【學位授予年份】：2017
【分類號】：O157.5

【參考文獻】

相關期刊論文 前10條

1 邵鐵林;;基于復雜網(wǎng)絡拓撲結構的評估體系研究[J];微型機與應用;2017年01期

2 余成進;趙姝;陳潔;張燕平;段震;;復雜網(wǎng)絡中的層次結構挖掘[J];南京大學學報(自然科學);2016年05期

3 樊夢佳;鈕艷;杜翠蘭;張仰森;;一種基于聚集系數(shù)的社區(qū)發(fā)現(xiàn)算法[J];計算機工程與科學;2016年02期

4 伍杰華;朱岸青;;基于社區(qū)結構的科研合作關系分析與預測[J];計算機應用研究;2016年03期

5 李建華;汪曉鋒;吳鵬;;基于局部優(yōu)化的社區(qū)發(fā)現(xiàn)方法研究現(xiàn)狀[J];中國科學院院刊;2015年02期

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

7 周濤;張子柯;陳關榮;汪小帆;史定華;狄增如;樊瑛;方錦清;韓筱璞;劉建國;劉潤然;劉宗華;陸君安;呂金虎;呂琳媛;榮智海;汪秉宏;許小可;章忠志;;復雜網(wǎng)絡研究的機遇與挑戰(zhàn)[J];電子科技大學學報;2014年01期

8 龔尚福;陳婉璐;賈澎濤;;層次聚類社區(qū)發(fā)現(xiàn)算法的研究[J];計算機應用研究;2013年11期

9 吳祖峰;王鵬飛;秦志光;蔣紹權;;改進的Louvain社團劃分算法[J];電子科技大學學報;2013年01期

10 杜巍;蔡萌;杜海峰;;網(wǎng)絡結構魯棒性指標及應用研究[J];西安交通大學學報;2010年04期

相關博士學位論文 前9條

1 周旭;復雜網(wǎng)絡中社區(qū)發(fā)現(xiàn)算法研究[D];吉林大學;2016年

2 張希昀;復雜網(wǎng)絡上的爆炸式同步[D];華東師范大學;2016年

3 柴變芳;基于生成模型的大規(guī)模網(wǎng)絡廣義社區(qū)發(fā)現(xiàn)方法研究[D];北京交通大學;2015年

4 閔磊;復雜網(wǎng)絡社區(qū)發(fā)現(xiàn)算法研究[D];華中師范大學;2015年

5 林臻;面向復雜網(wǎng)絡的結構模式挖掘及傳播動力學模型研究[D];浙江大學;2015年

6 姜雅文;復雜網(wǎng)絡社區(qū)發(fā)現(xiàn)若干問題研究[D];北京交通大學;2014年

7 晉建志;復雜網(wǎng)絡基于節(jié)點重要性的社團探測及社團演化模型研究[D];華中師范大學;2014年

8 潘磊;若干社區(qū)發(fā)現(xiàn)算法研究[D];南京大學;2014年

9 孔兵;基于連接度量的社區(qū)發(fā)現(xiàn)研究[D];云南大學;2012年

相關碩士學位論文 前6條

1 吳磊;復雜網(wǎng)絡的社團劃分算法研究[D];太原理工大學;2016年

2 黃保淞;復雜網(wǎng)絡的社區(qū)發(fā)現(xiàn)算法研究[D];吉林大學;2016年

3 張成建;基于重疊社區(qū)結構的社交網(wǎng)絡最大影響力研究[D];燕山大學;2015年

4 魏愛英;社會網(wǎng)絡中的社區(qū)發(fā)現(xiàn)算法研究[D];燕山大學;2014年

5 張睿;基于點聚集系數(shù)和邊聚集系數(shù)的社區(qū)發(fā)現(xiàn)算法[D];云南大學;2013年

6 彭燕;基于局部信息的復雜網(wǎng)絡社區(qū)發(fā)現(xiàn)算法研究[D];吉林大學;2013年

，

本文編號：1653241