File(s) under permanent embargo
Network community detection based on the physarum-inspired computational framework
journal contribution
posted on 2018-11-01, 00:00 authored by C Gao, M Liang, X Li, Zili ZhangZili Zhang, Z Wang, Z ZhouIEEE Community detection is a crucial and essential problem in the structure analytics of complex networks, which can help us understand and predict the characteristics and functions of complex networks. Many methods, ranging from the optimization-based algorithms to the heuristic-based algorithms, have been proposed for solving such a problem. Due to the inherent complexity of identifying network structure, how to design an effective algorithm with a higher accuracy and a lower computational cost still remains an open problem. Inspired by the computational capability and positive feedback mechanism in the wake of foraging process of Physarum, which is a large amoeba-like cell consisting of a dendritic network of tube-like pseudopodia, a general Physarum-based computational framework for community detection is proposed in this paper. Based on the proposed framework, the inter-community edges can be identified from the intra-community edges in a network and the positive feedback of solving process in an algorithm can be further enhanced, which are used to improve the efficiency of original optimization-based and heuristic-based community detection algorithms, respectively. Some typical algorithms (e.g., genetic algorithm, ant colony optimization algorithm, and Markov clustering algorithm) and real-world datasets have been used to estimate the efficiency of our proposed computational framework. Experiments show that the algorithms optimized by Physarum-inspired computational framework perform better than the original ones, in terms of accuracy and computational cost. Moreover, a computational complexity analysis verifies the scalability of our framework.
History
Journal
IEEE/ACM transactions on computational biology and bioinformaticsVolume
15Issue
6Season
Nov-DecPagination
1916 - 1928Publisher
IEEELocation
Piscataway, N.J.Publisher DOI
ISSN
1545-5963Language
engPublication classification
C1 Refereed article in a scholarly journalCopyright notice
2016, IEEEUsage metrics
Categories
No categories selectedKeywords
Science & TechnologyLife Sciences & BiomedicineTechnologyPhysical SciencesBiochemical Research MethodsComputer Science, Interdisciplinary ApplicationsMathematics, Interdisciplinary ApplicationsStatistics & ProbabilityBiochemistry & Molecular BiologyComputer ScienceMathematicsCommunity detectionPhysarumgenetic algorithmant colony optimizationMarkov clustering algorithmTRANSPORT NETWORKMODEL
Licence
Exports
RefWorks
BibTeX
Ref. manager
Endnote
DataCite
NLM
DC