An Improved Algorithm for Community Discovery in Weighted Social Networks

摘要

The problems of AGMA (Automatic Graph Mining Algorithm) are improved and a novel algorithm, namely CRMA (Clustering Re-clustering Merging Algorithm) is proposed which can realize more reasonable community division for weighted social networks. Firstly, when re-clustering nodes, AGMA neglected the clustering situation of its neighbors and didn't take into account the weight of the edge connecting the current node and its unclustered neighbor, which led to unreasonable clustering. Aiming to this, the concept of the connection compactness is introduced. Then according to the node weight, the edge weight and the friend coefficient, each node would be clustered into the community has the largest connection compactness with itself. Secondly, for community division in some unweighted networks and signed networks, if there are many nodes whose clustered neighbors is less than its unclustered neighbors, the division results of AGMA tend to produce many small communities, which would result in the lower modularity. In view of this problem, the concepts of positive edge weight density, the cluster density and the connection coefficient between clusters are proposed. Lastly, we merge communities based on the above three concepts and the modularity is effectively enhanced finally. The higher correctness and better generality of the improved algorithm are verified through experiments.