Font Size: a A A

Research On Community Detection Algorithm Based On Dynamic Network

Posted on:2019-08-14Degree:MasterType:Thesis
Country:ChinaCandidate:J J NieFull Text:PDF
GTID:2370330566491416Subject:Computer system architecture
Abstract/Summary:PDF Full Text Request
With the deepening of the research on complex network theory,it is found that complex networks can depict many phenomena in the real world.Complex networks are systems that cosists of a series of nodes that connected in a certain way by a number of nodes with complex relationships in the network topology.Community detection can reveal the changes and development laws of natural phenomena in society,and has a strong practical significance in the study of dynamic networks.The traditional method of dynamic network evolution analysis is basically to extract the network snapshot to find the community structure at this time,and analyze the association of adjacent times.In view of the shortcomings of traditional community detection algorithms that can not depict dynamic networks and have high time complexity,this paper proposes an optimization analysis of the function which can characterize the quality of community in the framework of time smoothness and find out the optimal community.The traditional community detection algorithm has the disadvantage of high time complexity,and the time complexity of the spectrum analysis method is low,and it can convert the matrix into the form of easy to understand trace.But spectral analysis needs to know the number of communities in advance,and combining spectral analysis with k-means algorithm can solve this problem well.Based on the above basic knowledge,this paper combines the spectral analysis method with the k-means algorithm,and uses the evolutionary clustering framework to introduce the historical information to guide the association strategy at the present time.The module function Q,module density function D and negative average function NA,which can represent the quality of the community,are optimized.Therefore,the problem of dynamic network community quality detection is solved,and the need to know the number of communities in advance is overcome.With the help of synthetic data sets and real network data sets,and combining the two criteria of normalized mutual information NMI and genetic probability,the algorithm proposed in this paper is compared with FaceNet algorithm and dynamic multi-objective genetic algorithm(DYNOMGA).It can be seen from the experimental results that,in the effective time,the proposed algorithm has achieved better results compared with other algorithms in detecting the community,and can be used for large-scale complex dynamic network community evolution analysis.
Keywords/Search Tags:Dynamic Networks, Evolutionary Clustering, Spectral optimization, Community Detection, Community Evolution Analysis
PDF Full Text Request
Related items