University of Tasmania
Browse
131577 - Parallel community detection based on distance dynamics for large-scale network.pdf (2.58 MB)

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

Download (2.58 MB)
journal contribution
posted on 2023-05-20, 02:10 authored by He, T, Cai, L, Meng, T, Chen, L, Deng, Z, Cao, Z
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.

History

Publication title

IEEE Access

Volume

6

Pagination

42775-42789

ISSN

2169-3536

Department/School

School of Information and Communication Technology

Publisher

Institute of Electrical and Electronics Engineers

Place of publication

United States

Rights statement

Copyright 2018 IEEE.

Repository Status

  • Open

Socio-economic Objectives

Information systems, technologies and services not elsewhere classified

Usage metrics

    University Of Tasmania

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC