Research On Community Discovery In Large Dynamic Social Networks

Many systems in the real world can be abstracted as complex networks,such as scientific cooperation networks,power grid,traffic networks,etc.Community structure is one of the most important features of the complex networks.The vertices inside a community are closely connected while the vertices belong to different communities are loosely connected.The goal of community discovery is to partition the vertices of a network into a number of subgraphs according to the closeness of the connection among the vertices.The traditional community discovery algorithms suffer from the defections of inefficiency,poor scalability,etc.when applied to large complex networks with tremendous vertices and complicated connections.The incremental dynamic community discovery algorithms take into account the information of the previous moment when finding communities,so that they avoid time-consuming clustering of the whole network,which can greatly reduce running time.Moreover,when the parallel computation frameworks are applied,the efficiency can be further improved.In the paper,the problem of community discovery in large dynamic social networks are studied intensively.The main contributions are as follows:(1)A community discovery algorithm based on the combination of the structural stability of the communities and the incremental relative vertices is proposed.The algorithm determines the community a vertex belongs to according to the communities discovered at previous moment.The belongingness of the vertices are adjusted by the Jaccard index.The dynamic communities can be discovered by considering the structural stability of the communities.The repartitioning of the whole networks can be avoided by analyzing the difference between consecutive intervals through incremental methods.Therefore,the time complexity of the algorithm is greatly reduced.The experiments on the network datasets show that the proposed algorithm is capable of discovering dynamic communities efficiently in the large social networks.(2)A parallel incremental community discovery algorithm based on density clustering is proposed.First,a density clustering algorithm is employed to discover the initial communities.Then,the topological changes between the adjacent moments are transformed into the edge changes by considering the network topology of the previous moment.Different strategies are used to update or merge the communities according to different conditions of the edge changes.Finally,the experiments on the network datasets show that the proposed algorithm is efficient in discovering overlapping communities in the large networks.