Discrete Jaya Algorithm for Complex Network Community Detection
CSTR:
Author:
  • Article
  • | |
  • Metrics
  • |
  • Reference [39]
  • |
  • Related [20]
  • | | |
  • Comments
    Abstract:

    Community structure is one of most important characteristics of complex networks. The community detection problem based on modularity is NP-hard as a combinatorial optimization problem, which is often solved by heuristic algorithms. Jaya algorithm is a simple and effective meta-heuristic method for solving continuous optimization problems. In this study, the strategy of discreting Jaya algorithm for complex network community discovery is given on the basis of updating the population individuals according to the way Jaya algorithm works, that is, an individual is updated close to the best solution and far away from the worst solution, and thus a discrete Jaya algorithm for complex network community discovery is proposed. Experiments show that the proposed algorithm has the advantages of high resolution and automatic determination of the number of communities compared with the classical algorithms in several real network instances and a class of artificial network instances.

    Reference
    [1] Girvan M, Newman MEJ. Community structure in social and biological networks. Proceedings of the National Academy of Sciences of the United States of America, 2002, 99(12): 7821-7826. [doi: 10.1073/pnas.122653799
    [2] Newman MEJ, Girvan M. Finding and evaluating community structure in networks. Physical Review E, 2004, 69(2): 026113. [doi: 10.1103/PhysRevE.69.026113
    [3] Kernighan BW, Lin S. An efficient heuristic procedure for partitioning graphs. The Bell System Technical Journal, 1970, 49(2): 291-307. [doi: 10.1002/j.1538-7305.1970.tb01770.x
    [4] Clauset A, Newman MEJ, Moore C. Finding community structure in very large networks. Physical Review E, 2004, 70(6): 066111. [doi: 10.1103/PhysRevE.70.066111
    [5] Newman MEJ. Fast algorithm for detecting community struc-ture in networks. Physical Review E, 2004, 69(5): 066133.
    [6] Newman MEJ. Modularity and community structure in networks. Proceedings of the National Academy of Sciences of the United States of America, 2006, 103(23): 8577-8582. [doi: 10.1073/pnas.0601602103
    [7] Xing Y, Meng FR, Zhou Y, et al. A node influence based label propagation algorithm for community detection in networks. The Scientific World Journal, 2014, 2014: 627581
    [8] Van Dongen S. Graph clustering by flow simulation [Ph. D. thesis]. Utrecht: University of Utrecht, 2000. 1-173.
    [9] Rosvall M, Bergstrom CT. Maps of random walks on complex networks reveal community structure. Proceedings of the National Academy of Sciences of the United States of America, 2008, 105(4): 1118-1123. [doi: 10.1073/pnas.0706851105
    [10] Jia GB, Cai ZX, Musolesi M, et al. Community detection in social and biological networks using differential evolution. Proceedings of the 6th International Conference on Learning and Intelligent Optimization. Paris, France. 2012. 71-85.
    [11] Cai Q, Gong MG, Ma LJ, et al. Greedy discrete particle swarm optimization for large-scale social network clustering. Information Sciences, 2015, 316: 503-516. [doi: 10.1016/j.ins.2014.09.041
    [12] Tasgin M, Herdagdelen A, Bingol H. Community detection in complex networks using genetic algorithms. arXiv: 0711.0491, 2006.
    [13] 金弟, 刘杰, 杨博, 等. 局部搜索与遗传算法结合的大规模复杂网络社区探测. 自动化学报, 2011, 37(7): 873-882
    [14] 张英杰, 龚中汉, 陈乾坤. 基于免疫离散差分进化算法的复杂网络社区发现. 自动化学报, 2015, 41(4): 749-757
    [15] Duch J, Arenas A. Community detection in complex networks using extremal optimization. Physical Review E, 2005, 72(2): 027104. [doi: 10.1103/PhysRevE.72.027104
    [16] Guimerà R, Amaral LAN. Functional cartography of complex metabolic networks. Nature, 2005, 433(7028): 895-900. [doi: 10.1038/nature03288
    [17] Blondel VD, Guillaume JL, Lambiotte R, et al. Fast unfolding of communities in large networks. Journal of Statistical Mechanics: Theory and Experiment, 2008, 2008(10): 10008. [doi: 10.1088/1742-5468/2008/10/P10008
    [18] Pizzuti C. Evolutionary computation for community detection in networks: A review. IEEE Transactions on Evolutionary Computation, 2018, 22(3): 464-483. [doi: 10.1109/TEVC.2017.2737600
    [19] Cai Q, Ma LJ, Gong MG, et al. A survey on network community detection based on evolutionary computation. International Journal of Bio-Inspired Computation, 2016, 8(2): 84-98. [doi: 10.1504/IJBIC.2016.076329
    [20] Liu J, Abbass HA, Tan KC. Evolutionary community detection algorithms. In: Liu J, Abbass HA, Tan KC, eds. Evolutionary Computation and Complex Networks. Cham: Springer, 2019. 77-115.
    [21] Talbi EG. A parallel genetic algorithm for the graph partitioning problem. Proceedings of the 5th International Conference on Supercomputing. New York, NY, USA. 1991. 312-320.
    [22] Bui TN, Moon BR. Genetic algorithm and graph partitioning. IEEE Transactions on Computers, 1996, 45(7): 841-855. [doi: 10.1109/12.508322
    [23] Tasgin M, Herdagdelen A, Bingol H. Community detection in complex networks using genetic algorithms. arXiv: 0711.0491, 2007.
    [24] Gog A, Dumitrescu D, Hirsbrunner B. Community detection in complex networks using collaborative evolutionary algorithms. Proceedings of the 9th European Conference on Artificial Life. Lisbon, Portugal. 2007. 886-894.
    [25] Pizzuti C. Ga-Net: A genetic algorithm for community detection in social networks. Proceedings of the 10th International Conference on Parallel Problem Solving from Nature. Dortmund, Germany. 2008. 1081-1090.
    [26] Gong MG, Fu B, Jiao LC, et al. Memetic algorithm for community detection in networks. Physical Review E, 2011, 84(5): 056101
    [27] Chang HH, Feng ZR, Ren ZG. Community detection using ant colony optimization. Proceedings of 2013 IEEE Congress on Evolutionary Computation. Cancun, Mexico. 2013. 3072-3078.
    [28] Said A, Abbasi RA, Maqbool O, et al. CC-GA: A clustering coefficient based genetic algorithm for detecting communities in social networks. Applied Soft Computing, 2018, 63: 59-70. [doi: 10.1016/j.asoc.2017.11.014
    [29] Rao RV. Jaya: A simple and new optimization algorithm for solving constrained and unconstrained optimization problems. International Journal of Industrial Engineering Computations, 2016, 7(1): 19-34
    [30] Gao KZ, Yang FJ, Zhou MC, et al. Flexible job-shop rescheduling for new job insertion by using discrete Jaya algorithm. IEEE Transactions on Cybernetics, 2019, 49(5): 1944-1955. [doi: 10.1109/TCYB.2018.2817240
    [31] Gao KZ, Zhang YC, Sadollah A, et al. Jaya, harmony search and water cycle algorithms for solving large-scale real-life urban traffic light scheduling problem. Swarm and Evolutionary Computation, 2017, 37: 58-72. [doi: 10.1016/j.swevo.2017.05.002
    [32] Hruschka ER, Campello RJGB, Freitas AA. A survey of evolutionary algorithms for clustering. IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 2009, 39(2): 133-155. [doi: 10.1109/TSMCC.2008.2007252
    [33] Lancichinetti A, Fortunato S, Radicchi F. Benchmark graphs for testing community detection algorithms. Physical Review E, 2008, 78(4): 046110. [doi: 10.1103/PhysRevE.78.046110
    [34] Raghavan UN, Albert R, Kumara S. Near linear time algorithm to detect community structures in large-scale networks. Physical Review E, 2007, 76(3 Pt 2): 036106
    [35] Danon L, Díaz-Guilera A, Duch J, et al. Comparing community structure identification. Journal of Statistical Mechanics: Theory and Experiment, 2005, 2005(9): 09008. [doi: 10.1088/1742-5468/2005/09/P09008
    [36] Zachary WW. An information flow model for conflict and fission in small groups. Journal of Anthropological Research, 1977, 33(4): 452-473. [doi: 10.1086/jar.33.4.3629752
    [37] Lusseau D. The emergent properties of a dolphin social network. Proceedings of the Royal Society B: Biological Sciences, 2003, 270(S2): S186-S188
    [38] Aloise D, Cafieri S, Caporossi G, et al. Column generation algorithms for exact modularity maximization in networks. Physical Review E, 2010, 82(4): 046112. [doi: 10.1103/PhysRevE.82.046112
    [39] Fortunato S, Barthelemy M. Resolution limit in community detection. Proceedings of the National Academy of Sciences of the United States of America, 2007, 104(1): 36-41. [doi: 10.1073/pnas.0605965104
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

李剑雄,鲍志强.离散Jaya算法的复杂网络社区发现.计算机系统应用,2020,29(6):146-154

Copy
Share
Article Metrics
  • Abstract:1994
  • PDF: 3273
  • HTML: 1538
  • Cited by: 0
History
  • Received:October 25,2019
  • Revised:November 20,2019
  • Online: June 12,2020
Article QR Code
You are the first990357Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-3
Address:4# South Fourth Street, Zhongguancun,Haidian, Beijing,Postal Code:100190
Phone:010-62661041 Fax: Email:csa (a) iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063