Research And Implementation Of Community Detection Algorithms In Large-scale Dynamic Social Networks

Communities are sets of nodes which the nodes inside them are connected frequently and the nodes between them connected occasionally.Detecting communities in social networks can provide help for personalized recommendation service and information dissemination.With the development of the social network,there are more and more large-scale graphs changing over time.Sometimes the change is little.The traditional community detection algorithms define an objective function Q which can measure the quality of the communities.Once the graph changes,we must re-compute the function Q to detect new communities of the whole graph.In order to solve the problem of local community detection in dynamic networks,we first put forward a new method for detecting local community.This method start to find the communities with a collection of nodes instead of one node.It can reduce the number computation iterations and it can enhance the stability of the community.When the graph changes,three rules of adding edges and four rules of deleting edges are considered,so we can get a fast update scheme.If the changes of the graph are uniform,there are many changes of the edges are not related to the current query.So we can update the community very quickly.In order to solve the problem of global community detection in dynamic networks,this thesis first puts forward a technique to detect the global community which can speed up the detection.When the graph changes,we can re-compute the communities by analysis of the function Q.We can update the communities by the vertices and edges which are changed during the evolution of the graph.At last,experiments show that the algorithms we proposed have a better time efficiency and high accuracy.The local community detection algorithm that we proposed has a higher accuracy.The global community detection algorithm that we proposed has a better time efficiency.