Deakin University
Browse

File(s) under permanent embargo

An enhanced Markov clustering algorithm based on Physarum

conference contribution
posted on 2017-01-01, 00:00 authored by M Liang, C Gao, X Li, Zili ZhangZili Zhang
Community mining is a vital problem for complex network analysis. Markov chains based algorithms are known as its easy-to-implement and have provided promising solutions for community mining. Existing Markov clustering algorithms have been optimized from the aspects of parallelization and penalty strategy. However, the dynamic process for enlarging the inhomogeneity attracts little attention. As the key mechanism of Markov chains based algorithms, such process affects the qualities of divisions and computational cost directly. This paper proposes a hybrid algorithm based on Physarum, a kind of slime. The new algorithm enhances the dynamic process of Markov clustering algorithm by embedding the Physarum-inspired feedback system. Specifically, flows between vertexes can enhance the corresponding transition probability in Markov clustering algorithms, and vice versa. Some networks with known and unknown community structures are used to estimate the performance of our proposed algorithms. Extensive experiments show that the proposed algorithm has higher NMI, Q values and lower computational cost than that of the typical algorithms.

History

Event

Advances in Knowledge Discovery and Data Mining. Pacific-Asia Conference (21st : 2017 : Jeju, South Korea)

Volume

10234

Series

Lecture Notes in Artificial Intelligence

Pagination

486 - 498

Publisher

Springer

Location

Jeju, South Korea

Place of publication

Berlin, Germany

Start date

2017-05-23

End date

2017-05-26

ISSN

0302-9743

eISSN

1611-3349

ISBN-13

9783319574530

Language

eng

Publication classification

E Conference publication; E1 Full written paper - refereed

Copyright notice

2017, Springer

Editor/Contributor(s)

J Kim, K Shim, L Cao, J Lee, X Lim, Y Moon

Title of proceedings

PAKDD 2017 : Part 1 of the Proceedings of the Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining

Usage metrics

    Research Publications

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC