A Physarum-inspired ant colony optimization for community mining

Mingxin Liang; Chao Gao; Xianghua Li; Zili Zhang

doi:10.1007/978-3-319-57454-7_57

A Physarum-inspired ant colony optimization for community mining

Mingxin Liang, Chao Gao, Xianghua Li, Zili Zhang

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

4 Scopus citations

Abstract

Community mining is a powerful tool for discovering the knowledge of networks and has a wide application. The modularity is one of very popular measurements for evaluating the efficiency of community divisions. However, the modularity maximization is a NP-complete problem. As an effective optimization algorithm for solving NP-complete problems, ant colony based community detection algorithm has been proposed to deal with such task. However the low accuracy and premature still limit its performance. Aiming to overcome those shortcomings, this paper proposes a novel nature-inspired optimization for the community mining based on the Physarum, a kind of slime molds cells. In the proposed strategy, the Physarum-inspired model optimizes the heuristic factor of ant colony algorithm by endowing edges with weights. With the information of weights provided by the Physarum-inspired model, the optimized heuristic factor can improve the searching abilities of ant colony algorithms. Four real-world networks and two typical kinds of ant colony optimization algorithms are used for estimating the efficiency of proposed strategy. Experiments show that the optimized ant colony optimization algorithms can achieve a better performance in terms of robustness and accuracy with a lower computational cost.

Original language	English
Title of host publication	Advances in Knowledge Discovery and Data Mining - 21st Pacific-Asia Conference, PAKDD 2017, Proceedings
Editors	Kyuseok Shim, Jae-Gil Lee, Longbing Cao, Xuemin Lin, Jinho Kim, Yang-Sae Moon
Publisher	Springer Verlag
Pages	737-749
Number of pages	13
ISBN (Print)	9783319574530
DOIs	https://doi.org/10.1007/978-3-319-57454-7_57
State	Published - 2017
Externally published	Yes
Event	21st Pacific-Asia Conference on Knowledge Discovery and Data Mining, PAKDD 2017 - Jeju, Korea, Republic of Duration: 23 May 2017 → 26 May 2017

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	10234 LNAI
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	21st Pacific-Asia Conference on Knowledge Discovery and Data Mining, PAKDD 2017
Country/Territory	Korea, Republic of
City	Jeju
Period	23/05/17 → 26/05/17

Keywords

Ant colony algorithm
Community mining
Physarum

Access to Document

10.1007/978-3-319-57454-7_57

Cite this

Liang, M., Gao, C., Li, X., & Zhang, Z. (2017). A Physarum-inspired ant colony optimization for community mining. In K. Shim, J.-G. Lee, L. Cao, X. Lin, J. Kim, & Y.-S. Moon (Eds.), Advances in Knowledge Discovery and Data Mining - 21st Pacific-Asia Conference, PAKDD 2017, Proceedings (pp. 737-749). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10234 LNAI). Springer Verlag. https://doi.org/10.1007/978-3-319-57454-7_57

Liang, Mingxin ; Gao, Chao ; Li, Xianghua et al. / A Physarum-inspired ant colony optimization for community mining. Advances in Knowledge Discovery and Data Mining - 21st Pacific-Asia Conference, PAKDD 2017, Proceedings. editor / Kyuseok Shim ; Jae-Gil Lee ; Longbing Cao ; Xuemin Lin ; Jinho Kim ; Yang-Sae Moon. Springer Verlag, 2017. pp. 737-749 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{3bfe808c43f84fdfa2e61fb1b76ca01c,

title = "A Physarum-inspired ant colony optimization for community mining",

abstract = "Community mining is a powerful tool for discovering the knowledge of networks and has a wide application. The modularity is one of very popular measurements for evaluating the efficiency of community divisions. However, the modularity maximization is a NP-complete problem. As an effective optimization algorithm for solving NP-complete problems, ant colony based community detection algorithm has been proposed to deal with such task. However the low accuracy and premature still limit its performance. Aiming to overcome those shortcomings, this paper proposes a novel nature-inspired optimization for the community mining based on the Physarum, a kind of slime molds cells. In the proposed strategy, the Physarum-inspired model optimizes the heuristic factor of ant colony algorithm by endowing edges with weights. With the information of weights provided by the Physarum-inspired model, the optimized heuristic factor can improve the searching abilities of ant colony algorithms. Four real-world networks and two typical kinds of ant colony optimization algorithms are used for estimating the efficiency of proposed strategy. Experiments show that the optimized ant colony optimization algorithms can achieve a better performance in terms of robustness and accuracy with a lower computational cost.",

keywords = "Ant colony algorithm, Community mining, Physarum",

author = "Mingxin Liang and Chao Gao and Xianghua Li and Zili Zhang",

note = "Publisher Copyright: {\textcopyright} 2017, Springer International Publishing AG.; 21st Pacific-Asia Conference on Knowledge Discovery and Data Mining, PAKDD 2017 ; Conference date: 23-05-2017 Through 26-05-2017",

year = "2017",

doi = "10.1007/978-3-319-57454-7_57",

language = "英语",

isbn = "9783319574530",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "737--749",

editor = "Kyuseok Shim and Jae-Gil Lee and Longbing Cao and Xuemin Lin and Jinho Kim and Yang-Sae Moon",

booktitle = "Advances in Knowledge Discovery and Data Mining - 21st Pacific-Asia Conference, PAKDD 2017, Proceedings",

}

Liang, M, Gao, C, Li, X & Zhang, Z 2017, A Physarum-inspired ant colony optimization for community mining. in K Shim, J-G Lee, L Cao, X Lin, J Kim & Y-S Moon (eds), Advances in Knowledge Discovery and Data Mining - 21st Pacific-Asia Conference, PAKDD 2017, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10234 LNAI, Springer Verlag, pp. 737-749, 21st Pacific-Asia Conference on Knowledge Discovery and Data Mining, PAKDD 2017, Jeju, Korea, Republic of, 23/05/17. https://doi.org/10.1007/978-3-319-57454-7_57

A Physarum-inspired ant colony optimization for community mining. / Liang, Mingxin; Gao, Chao; Li, Xianghua et al.
Advances in Knowledge Discovery and Data Mining - 21st Pacific-Asia Conference, PAKDD 2017, Proceedings. ed. / Kyuseok Shim; Jae-Gil Lee; Longbing Cao; Xuemin Lin; Jinho Kim; Yang-Sae Moon. Springer Verlag, 2017. p. 737-749 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10234 LNAI).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - A Physarum-inspired ant colony optimization for community mining

AU - Liang, Mingxin

AU - Gao, Chao

AU - Li, Xianghua

AU - Zhang, Zili

PY - 2017

Y1 - 2017

N2 - Community mining is a powerful tool for discovering the knowledge of networks and has a wide application. The modularity is one of very popular measurements for evaluating the efficiency of community divisions. However, the modularity maximization is a NP-complete problem. As an effective optimization algorithm for solving NP-complete problems, ant colony based community detection algorithm has been proposed to deal with such task. However the low accuracy and premature still limit its performance. Aiming to overcome those shortcomings, this paper proposes a novel nature-inspired optimization for the community mining based on the Physarum, a kind of slime molds cells. In the proposed strategy, the Physarum-inspired model optimizes the heuristic factor of ant colony algorithm by endowing edges with weights. With the information of weights provided by the Physarum-inspired model, the optimized heuristic factor can improve the searching abilities of ant colony algorithms. Four real-world networks and two typical kinds of ant colony optimization algorithms are used for estimating the efficiency of proposed strategy. Experiments show that the optimized ant colony optimization algorithms can achieve a better performance in terms of robustness and accuracy with a lower computational cost.

AB - Community mining is a powerful tool for discovering the knowledge of networks and has a wide application. The modularity is one of very popular measurements for evaluating the efficiency of community divisions. However, the modularity maximization is a NP-complete problem. As an effective optimization algorithm for solving NP-complete problems, ant colony based community detection algorithm has been proposed to deal with such task. However the low accuracy and premature still limit its performance. Aiming to overcome those shortcomings, this paper proposes a novel nature-inspired optimization for the community mining based on the Physarum, a kind of slime molds cells. In the proposed strategy, the Physarum-inspired model optimizes the heuristic factor of ant colony algorithm by endowing edges with weights. With the information of weights provided by the Physarum-inspired model, the optimized heuristic factor can improve the searching abilities of ant colony algorithms. Four real-world networks and two typical kinds of ant colony optimization algorithms are used for estimating the efficiency of proposed strategy. Experiments show that the optimized ant colony optimization algorithms can achieve a better performance in terms of robustness and accuracy with a lower computational cost.

KW - Ant colony algorithm

KW - Community mining

KW - Physarum

UR - http://www.scopus.com/inward/record.url?scp=85018443402&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-57454-7_57

DO - 10.1007/978-3-319-57454-7_57

M3 - 会议稿件

AN - SCOPUS:85018443402

SN - 9783319574530

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 737

EP - 749

BT - Advances in Knowledge Discovery and Data Mining - 21st Pacific-Asia Conference, PAKDD 2017, Proceedings

A2 - Shim, Kyuseok

A2 - Lee, Jae-Gil

A2 - Cao, Longbing

A2 - Lin, Xuemin

A2 - Kim, Jinho

A2 - Moon, Yang-Sae

PB - Springer Verlag

T2 - 21st Pacific-Asia Conference on Knowledge Discovery and Data Mining, PAKDD 2017

Y2 - 23 May 2017 through 26 May 2017

ER -

Liang M, Gao C, Li X, Zhang Z. A Physarum-inspired ant colony optimization for community mining. In Shim K, Lee JG, Cao L, Lin X, Kim J, Moon YS, editors, Advances in Knowledge Discovery and Data Mining - 21st Pacific-Asia Conference, PAKDD 2017, Proceedings. Springer Verlag. 2017. p. 737-749. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-57454-7_57

A Physarum-inspired ant colony optimization for community mining

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this