Research On Dynamic Community Detection Methods In Social Network

Social networks are changing from time to time,which results in social networks showing a unique dynamic character.The detection and analysis of dynamic community is one of the basic researches of social network analysis,which not only helps to better understand the structure of social networks,but also can effectively predict the future trend of network evolution.It has practical significance for information dissemination,network marketing and community event supervision and other applications.The traditional dynamic community discovery algorithm analyzes the community sequence of social networks at different time points through cluster analysis,and then compares the community excavated at adjacent time points according to a certain index to find the most matching result.Based on this analysis result,the law of how the structure of community in social networks changes over time is discovered.The disadvantage of this approach is that it completely separates the connections of social networks at adjacent time points,ignoring the fact that social networks at adjacent time points are closely related.Based on the short-time smoothness assumption,the incremental dynamic community detection method adjusts the community excavated at previous time points according to the changes of social network topology to obtain community structure of social networks at the current time point.The time complexity of the incremental dynamic community detection algorithm is greatly reduced at the same time the consistency of community structure at adjacent time points is obtained.In this thesis,two incremental dynamic community discovery algorithms are proposed for nodes in social networks.The incremental dynamic community discovery algorithm based on node force draws the idea of the gravitation in the field of physics,and the interaction force is introduced between nodes.Each node is affected by the force not only from nodes of the same community but also different communities.According to the size of the two forces to determine whether an incremental node at time point t to change its community attribution,and the incremental nodes that change community attribution at time point t are assigned to the community with the greatest force.The incremental dynamic community discovery algorithm based on node force needs to keep the number of communities in social networks unchanged,and the incremental dynamic community discovery algorithm based on node distance can solve this problem.The algorithm has two steps.Firstly,basing on node distance and the amount of neighborhood node,nodes in social network are divided into three parts: core node,boundary node and noise node,and communities is excavated by core nodes according to the node reachable index.Based on this,analyzing and adjusting the community attribution of each incremental node according to its change in the type of node and the node reachable index.Experiments on the Enron mail data set and the Facebook social network dataset show that algorithms proposed in this thesis can excavate well-structured communities in a short time.