eCite Digital Repository

Parallel community detection based on distance dynamics for large-scale network


He, T and Cai, L and Meng, T and Chen, L and Deng, Z and Cao, Z, Parallel community detection based on distance dynamics for large-scale network, IEEE Access, 6 pp. 42775-42789. ISSN 2169-3536 (2018) [Refereed Article]


Copyright Statement

Copyright 2018 IEEE.

DOI: doi:10.1109/ACCESS.2018.2859788


Data mining task is a challenge on finding a high-quality community structure from largescale networks. The distance dynamics model was proved to be active on regular-size network community, but it is difficult to discover the community structure effectively from the large-scale network (0.1-1 billion edges), due to the limit of machine hardware and high time complexity. In this paper, we proposed a parallel community detection algorithm based on the distance dynamics model called P-Attractor, which is capable of handling the detection problem of large networks community. Our algorithm first developed a graph partitioning method to divide large network into lots of sub-networks, yet maintaining the complete neighbor structure of the original network. Then, the traditional distance dynamics model was improved by the dynamic interaction process to simulate the distance evolution of each sub-network. Finally, we discovered the real community structure by removing all external edges after evolution process. In our extensive experiments on multiple synthetic networks and real-world networks, the results showed the effectiveness and efficiency of P-Attractor, and the execution time on 4 threads and 32 threads are around 10 and 2 h, respectively. Our proposed algorithm is potential to discover community from a billion-scale network, such as Uk-2007.

Item Details

Item Type:Refereed Article
Keywords:community detection, complex network, graph clustering, web mining, data
Research Division:Information and Computing Sciences
Research Group:Computer vision and multimedia computation
Research Field:Pattern recognition
Objective Division:Information and Communication Services
Objective Group:Information systems, technologies and services
Objective Field:Information systems, technologies and services not elsewhere classified
UTAS Author:Cao, Z (Dr Zehong Cao)
ID Code:131577
Year Published:2018
Web of Science® Times Cited:15
Deposited By:Information and Communication Technology
Deposited On:2019-03-23
Last Modified:2019-05-13
Downloads:41 View Download Statistics

Repository Staff Only: item control page