Mining communities in social network based on information diffusion

Based on the locality of information diffusion in social network, a new community detection algorithm DC_ID is proposed in this paper. Different from that of the traditional community discovery algorithms, the goal of the DC_ID algorithm is that the difference between the node's influence degree in its community and its influence degree in the whole network is small, which paves the way for further research on the influence maximization problem based on the detected community structure. Moreover, the algorithm can tackle the community detecting program in directed and weighted networks, which makes it different from other existing algorithms. The algorithm consists of two stages: partition and combination. During the first stage, the algorithm first estimates all nodes' influence in the network, then chooses the most influential non-community node as the seed, and expands its influence along diffusion paths layer by layer. Finally, the local community with the node as its core is found. During the second stage, the closeness of two local communities will be evaluated by their combination entropy'. When the combination entropy of any two communities is higher than some predefined threshold, they will be combined into one. To evaluate the quality of the detected community structure, two new measures, LEW and CRC, are introduced. Empirical studies on three real-world social networks show that the algorithm outperforms the benchmark algorithm in runtime, LEW, and CRC. (c) 2016 Institute of Electrical Engineers of Japan. Published by John Wiley & Sons, Inc.