Finding Community of Brain Networks Based on Neighbor Index and DPSO with Dynamic Crossover

Author(s): Jie Zhang, Junhong Feng*, Fang-Xiang Wu*

Journal Name: Current Bioinformatics

Volume 15 , Issue 4 , 2020

Become EABM
Become Reviewer

Graphical Abstract:


Abstract:

Background: The brain networks can provide us an effective way to analyze brain function and brain disease detection. In brain networks, there exist some import neural unit modules, which contain meaningful biological insights.

Objective: Therefore, we need to find the optimal neural unit modules effectively and efficiently.

Method: In this study, we propose a novel algorithm to find community modules of brain networks by combining Neighbor Index and Discrete Particle Swarm Optimization (DPSO) with dynamic crossover, abbreviated as NIDPSO. The differences between this study and the existing ones lie in that NIDPSO is proposed first to find community modules of brain networks, and dose not need to predefine and preestimate the number of communities in advance.

Results: We generate a neighbor index table to alleviate and eliminate ineffective searches and design a novel coding by which we can determine the community without computing the distances amongst vertices in brain networks. Furthermore, dynamic crossover and mutation operators are designed to modify NIDPSO so as to alleviate the drawback of premature convergence in DPSO.

Conclusion: The numerical results performing on several resting-state functional MRI brain networks demonstrate that NIDPSO outperforms or is comparable with other competing methods in terms of modularity, coverage and conductance metrics.

Keywords: Brain networks, community detection, modularity, discrete particle swarm optimization, dynamic crossover, dynamic mutation.

[1]
Rudie JD, Brown JA, Beck-Pancer D, et al. Altered functional and structural brain network organization in autism. Neuroimage Clin 2012; 2: 79-94.
[http://dx.doi.org/10.1016/j.nicl.2012.11.006] [PMID: 24179761]
[2]
Zhu X, et al. One-step multi-view spectral clustering. IEEE Trans Knowl Data Eng 2019; 31(10): 2022-34.
[3]
Newman ME. Fast algorithm for detecting community structure in networks. Phys Rev E Stat Nonlin Soft Matter Phys 2004; 69(6) 066133
[http://dx.doi.org/10.1103/PhysRevE.69.066133] [PMID: 15244693]
[4]
Zhu X, Li HD, Xu Y, et al. A hybrid clustering algorithm for identifying cell types from Single-Cell RNA-Seq data. Genes 2019; 10(2): 1-17.
[http://dx.doi.org/10.3390/genes10020098] [PMID: 30700040]
[5]
Liu J, Liu T. Detecting community structure in complex networks using simulated annealing with k-means algorithms. Physica A 2010; 389(11): 2300-9.
[http://dx.doi.org/10.1016/j.physa.2010.01.042]
[6]
Duch J, Arenas A. Community detection in complex networks using extremal optimization. Phys Rev E Stat Nonlin Soft Matter Phys 2005; 72(2) 027104
[http://dx.doi.org/10.1103/PhysRevE.72.027104]
[7]
Pizzuti C. Ga-net: A genetic algorithm for community detection in social networks. International Conference on Parallel Problem Solving from Nature 2008; 1081-90.
[http://dx.doi.org/10.1007/978-3-540-87700-4_107]
[8]
Shang R, Bai J, Jiao L, Jin C. Community detection based on modularity and an improved genetic algorithm. Physica A 2013; 392(5): 1215-31.
[http://dx.doi.org/10.1016/j.physa.2012.11.003]
[9]
Shang R, Luo S, Zhang W, Stolkin R, Jiao L. A multiobjective evolutionary algorithm to find community structures based on affinity propagation. Physica A 2016; 453: 203-27.
[http://dx.doi.org/10.1016/j.physa.2016.02.020]
[10]
Guerrero M, Montoya FG, Baños R, Alcayde A, Gil C. Adaptive community detection in complex networks using genetic algorithms. Neurocomputing 2017; 266: 101-13.
[http://dx.doi.org/10.1016/j.neucom.2017.05.029]
[11]
Bilal S, Abdelouahab M. Evolutionary algorithm and modularity for detecting communities in networks. Physica A 2017; 473: 89-96.
[http://dx.doi.org/10.1016/j.physa.2017.01.018]
[12]
Saida A, Abbasi RA, Maqbool O, Daud A, Aljohani NR. CC-GA: a clustering coefficient based genetic algorithm for detecting communities in social networks. Appl Soft Comput 2018; 63: 59-70.
[http://dx.doi.org/10.1016/j.asoc.2017.11.014]
[13]
Hassan EA, Hafez AI, Hassanien AE, Fahmy AA. Community detection algorithm based on artificial fish swarm optimization. In: Intelligent Systems. Springer 2014; pp. 509-21.
[14]
Li Y, Wang Y, Chen J, Jiao L, Shang R. Overlapping community detection through an improved multi-objective quantum-behaved particle swarm optimization. J Heuristics 2015; 21(4): 549-75.
[http://dx.doi.org/10.1007/s10732-015-9289-y]
[15]
Rahimi S, Abdollahpouri A, Moradi P. A multi-objective particle swarm optimization algorithm for community detection in complex networks. Swarm Evol Comput 2017; 39: 297-309.
[http://dx.doi.org/10.1016/j.swevo.2017.10.009]
[16]
Zhou X, Zhao X, Liu Y. A multiobjective discrete bat algorithm for community detection in dynamic networks. Appl Intell 2018; 48(9): 3081-93.
[http://dx.doi.org/10.1007/s10489-017-1135-5]
[17]
Hassan EA, Hafez AI, Hassanien AE, Fahmy AA. A discrete bat algorithm for the community detection problem. International Conference on Hybrid Artificial Intelligence Systems 2015; 188-99.
[http://dx.doi.org/10.1007/978-3-319-19644-2_16]
[18]
Song A, Li M, Ding X, Cao W, Pu K. Community detection using discrete bat algorithm. Int J Comput Sci 2016; 43(1): 37-43.
[19]
Awange J, Palancz B, Lewis RH, Völgyesi L. Particle swarm optimization, Mathematical Geosciences. Springer 2018; pp. 167-84.
[20]
Chatterjee S, Sarkar S, Hore S, Dey N, Ashour AS, Balas VE. Particle swarm optimization trained neural network for structural failure prediction of multistoried RC buildings. Neural Comput Appl 2017; 28(8): 2005-16.
[http://dx.doi.org/10.1007/s00521-016-2190-2]
[21]
Zhu X, Zhang J, Feng J. Multi-objective particle swarm optimization based on PAM and uniform design. Math Probl Eng 2015; 2015(2): 1-17.
[22]
Zhang J, Wang Y, Feng J. A novel hybrid clustering algorithms with chaotic particle swarm optimization. J Comput Inf Syst 2012; 8(21): 8827-34.
[23]
Zhang J, Wang Y, Feng J. A hybrid clustering algorithm based on PSO with dynamic crossover. Soft Comput 2014; 18(5): 961-79.
[http://dx.doi.org/10.1007/s00500-013-1115-6]
[24]
Kennedy J, Eberhart R. Particle swarm optimization. IEEE International Conference on Neural Networks 1995; 1942-8.
[25]
Eberhart R, Kennedy J. A new optimizer using particle swarm theory. Proceedings of Sixth International Symposium Micro Machine and Human Science 1995; 39-43.
[http://dx.doi.org/10.1109/MHS.1995.494215]
[26]
Kennedy J, Eberhart RC. A discrete binary version of the particle swarm algorithm. Proceedings of the IEEE International Conference on Systems, Man, and Cybernetics Systems, Man, and Cybernetics USA 1997; 4104-8.
[27]
Clerc M, Kennedy J. The particle swarm: explosion, stability and convergence in a multi-dimensional complex space. IEEE Trans Evol Comput 2002; 6(1): 58-73.
[http://dx.doi.org/10.1109/4235.985692]
[28]
Sen G, Krishnamoorthy M. Discrete particle swarm optimization algorithms for two variants of the static data segment location problem. Appl Intell 2018; 48(3): 771-90.
[http://dx.doi.org/10.1007/s10489-017-0995-z]
[29]
Krause J, et al. A survey of swarm algorithms applied to discrete optimiza-tion problems, In Swarm Intelligence and Bio-Inspired Computation 2013; 169-91.
[30]
Banati H, Bajaj M. Fire fly based feature selection approach. Int J Comput Sci 2011; 8(4): 473-80.
[31]
Chen H, Li S, Tang Z. Hybrid gravitational search algorithm with random-key encoding scheme combined with simulated annealing. IJCSNS 2011; 11(6): 208.
[32]
Yousif A, Abdullah AH, Abdelaziz AA, Nor SM. Scheduling jobs on grid computing using firefly algorithm. J Theor Appl Inform Technol 2011; 33(2): 155-64.
[33]
Congying LV, Zhao H, Yang X. Particle swarm optimization algorithm for quadratic assignment problem. Proceedings of 2011 International Conference on Computer Science and Network Technology 2011; 1728-31.
[34]
Burnwal S, Deb S. Scheduling optimization of flexible manufacturing system using cuckoo search-based approach. Int J Adv Manuf Technol 2013; 64(5-8): 951-9.
[http://dx.doi.org/10.1007/s00170-012-4061-z]
[35]
Pan Q-K, Fatih Tasgetiren M, Liang Y-C. A discrete particle swarm optimization algorithm for the no-wait flowshop scheduling problem. Comput Oper Res 2008; 35(9): 2807-39.
[http://dx.doi.org/10.1016/j.cor.2006.12.030]
[36]
Zhang J, Zhu X, Feng J, Yang Y. Finding community of brain networks based on artificial bee colony with uniform design. Multimedia Tools Appl 2019; 78(4): 33297-317.
[http://dx.doi.org/10.1007/s11042-019-7472-0]
[37]
Fortunato S. Community detection in graphs. Phys Rep 2010; 486(3): 75-174.
[http://dx.doi.org/10.1016/j.physrep.2009.11.002]
[38]
Rubinov M, Sporns O. Complex network measures of brain connectivity: uses and interpretations. Neuroimage 2010; 52(3): 1059-69.
[http://dx.doi.org/10.1016/j.neuroimage.2009.10.003] [PMID: 19819337]
[39]
Newman ME, Girvan M. Finding and evaluating community structure in networks. Phys Rev E Stat Nonlin Soft Matter Phys 2004; 69(2): 026113-1.
[http://dx.doi.org/10.1103/PhysRevE.69.026113] [PMID: 14995526]
[40]
Newman ME. Modularity and community structure in networks. Proc Natl Acad Sci USA 2006; 103(23): 8577-82.
[http://dx.doi.org/10.1073/pnas.0601602103] [PMID: 16723398]
[41]
Newman ME. Finding community structure in networks using the eigenvectors of matrices. Phys Rev E Stat Nonlin Soft Matter Phys 2006; 74(3): 036104-1.
[http://dx.doi.org/10.1103/PhysRevE.74.036104] [PMID: 17025705]
[42]
Wang G, Shen Y, Luan E. A measure of centrality based on modularity matrix. Prog Nat Sci 2008; 18(8): 1043-7.
[http://dx.doi.org/10.1016/j.pnsc.2008.03.015]
[43]
Li Z, Zhang S, Wang RS, Zhang XS, Chen L. Quantitative function for community detection. Phys Rev E Stat Nonlin Soft Matter Phys 2008; 77(3): 036109-10.
[http://dx.doi.org/10.1103/PhysRevE.77.036109]
[44]
Garcia JO, Ashourvan A, Muldoon SF, Vettel JM, Bassett DS. Applications of community detection techniques to brain graphs: algorithmic considerations and implications for neural function. Proc IEEE Inst Electr Electron Eng 2018; 106(5): 846-67.
[http://dx.doi.org/10.1109/JPROC.2017.2786710]
[45]
Brown JA, Rudie JD, Bandrowski A, Van Horn JD, Bookheimer SY. The UCLA multimodal connectivity database: a web-based platform for brain connectivity matrix sharing and analysis. Front Neuroinform 2012; 6: 28.
[http://dx.doi.org/10.3389/fninf.2012.00028] [PMID: 23226127]
[46]
Newman ME. Spectral methods for community detection and graph partitioning. Phys Rev E Stat Nonlin Soft Matter Phys 2013; 88(4) 042822
[http://dx.doi.org/10.1103/PhysRevE.88.042822] [PMID: 24229240]
[47]
Danon L, Díaz-Guilera A, Arenas A. The effect of size heterogeneity on community identification in complex networks. J Stat Mech 2006; 2006(11) P11010
[http://dx.doi.org/10.1088/1742-5468/2006/11/P11010]


Rights & PermissionsPrintExport Cite as

Article Details

VOLUME: 15
ISSUE: 4
Year: 2020
Page: [287 - 299]
Pages: 13
DOI: 10.2174/1574893614666191017100657
Price: $65

Article Metrics

PDF: 12
HTML: 1