eCite Digital Repository

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

Citation

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]


Preview
PDF
3Mb
  

Copyright Statement

Copyright 2018 IEEE.

DOI: doi:10.1109/ACCESS.2018.2859788

Abstract

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:Artificial Intelligence and Image Processing
Research Field:Pattern Recognition and Data Mining
Objective Division:Information and Communication Services
Objective Group:Computer Software and Services
Objective Field:Information Processing Services (incl. Data Entry and Capture)
UTAS Author:Cao, Z (Mr Zehong Cao)
ID Code:131577
Year Published:2018
Web of Science® Times Cited:5
Deposited By:Information and Communication Technology
Deposited On:2019-03-23
Last Modified:2019-05-13
Downloads:12 View Download Statistics

Repository Staff Only: item control page