Volume 19, Issue 1 (5-2022)
JSDP 2022, 19(1): 87-100 |
Back to browse issues page
Download citation:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:
Alipour M M, Abdolhosseinzadeh M. A Multiagent Reinforcement Learning algorithm to solve the Community Detection Problem. JSDP 2022; 19 (1) : 7
URL: http://jsdp.rcisp.ac.ir/article-1-1084-en.html
URL: http://jsdp.rcisp.ac.ir/article-1-1084-en.html
University of Bonab
Abstract: (1834 Views)
Recent researches show that diverse systems in many different areas can be represented as complex networks. Examples of these include the Internet, social networks and so on. In each case, the system can be modeled as a complex and very large network consisting of a large number of entities and associations between them. Most of these networks are generally sparse in global yet dense in local. They have vertices in a group structure and the vertices within a group have higher density of edges while vertices among groups have lower density of edges. Such a structure is called community and is one of the important features of the network and is able to reveal many hidden characteristics of the networks. Today, community detection is used to improve the efficiency of search engines and discovery of terrorist organizations on the World Wide Web.
Community detection is a challenging NP-hard optimization problem that consists of searching for communities. It is assumed that the nodes of the same community share some properties that enable the detection of new characteristics or functional relationships in a network. Although there are many algorithms developed for community detection, most of them are unsuitable when dealing with large networks due to their computational cost.
Nowadays, multiagent systems have been used to solve different problems, such as constraint satisfaction problems and combinatorial optimization problems with satisfactory results. In this paper, a new multiagent reinforcement learning algorithm is proposed for community detection in complex networks. Each agent in the multiagent system is an autonomous entity with different learning parameters. Based on the cooperation among the learning agents and updating the action probabilities of each agent, the algorithm interactively will identify a set of communities in the input network that are more densely connected than other communities. In other words, some independent agents interactively attempt to identify communities and evaluate the quality of the communities found at each stage by the normalized cut as objective function; then, the probability vectors of the agents are updated based on the results of the evaluation. If the quality of the community found by an agent in each of the stages is better than all the results produced so far, then it is referred to as the successful agent and the other agents will update their probability vectors based on the result of the successful agent.
In the experiments, the performance of the proposed algorithm is validated on four real-world benchmark networks: the Karate club network, Dolphins network, Political books network and College football network, and synthetic LFR benchmark graphs with scales of 1000 and 5000 nodes. LFR networks are suitable for systematically measuring the property of an algorithm.
Experimental results show that proposed approach has a good performance and is able to find suitable communities in large and small scale networks and is capable of detecting the community in complex networks In terms of speed, precision and stability. Moreover, according to the systematic comparison of the results obtained by the proposed algorithm with four state-of-the-art community detection algorithms, our algorithm outperforms the these algorithms in terms of modularity and NMI; also, it can detect communities in small and large scale networks with high speed, accuracy, and stability, where it is capable of managing large-scale networks up to 5000 nodes.
Community detection is a challenging NP-hard optimization problem that consists of searching for communities. It is assumed that the nodes of the same community share some properties that enable the detection of new characteristics or functional relationships in a network. Although there are many algorithms developed for community detection, most of them are unsuitable when dealing with large networks due to their computational cost.
Nowadays, multiagent systems have been used to solve different problems, such as constraint satisfaction problems and combinatorial optimization problems with satisfactory results. In this paper, a new multiagent reinforcement learning algorithm is proposed for community detection in complex networks. Each agent in the multiagent system is an autonomous entity with different learning parameters. Based on the cooperation among the learning agents and updating the action probabilities of each agent, the algorithm interactively will identify a set of communities in the input network that are more densely connected than other communities. In other words, some independent agents interactively attempt to identify communities and evaluate the quality of the communities found at each stage by the normalized cut as objective function; then, the probability vectors of the agents are updated based on the results of the evaluation. If the quality of the community found by an agent in each of the stages is better than all the results produced so far, then it is referred to as the successful agent and the other agents will update their probability vectors based on the result of the successful agent.
In the experiments, the performance of the proposed algorithm is validated on four real-world benchmark networks: the Karate club network, Dolphins network, Political books network and College football network, and synthetic LFR benchmark graphs with scales of 1000 and 5000 nodes. LFR networks are suitable for systematically measuring the property of an algorithm.
Experimental results show that proposed approach has a good performance and is able to find suitable communities in large and small scale networks and is capable of detecting the community in complex networks In terms of speed, precision and stability. Moreover, according to the systematic comparison of the results obtained by the proposed algorithm with four state-of-the-art community detection algorithms, our algorithm outperforms the these algorithms in terms of modularity and NMI; also, it can detect communities in small and large scale networks with high speed, accuracy, and stability, where it is capable of managing large-scale networks up to 5000 nodes.
Article number: 7
Keywords: Complex networks, Community detection, Multiagent systems, Reinforcement learning, Modularity Q
Type of Study: Research |
Subject:
Paper
Received: 2019/10/15 | Accepted: 2021/12/6 | Published: 2022/06/22 | ePublished: 2022/06/22
Received: 2019/10/15 | Accepted: 2021/12/6 | Published: 2022/06/22 | ePublished: 2022/06/22
References
1. [1] D. J. Watts and S. H. Strogatz, "Collective dynamics of 'small-world'networks," nature, vol. 393, no. 6684, pp. 440, 1998. [DOI:10.1038/30918] [PMID]
2. [2] S. Boccaletti, V. Latora, Y. Moreno, M. Chavez, and D.-U. Hwang, "Complex networks: Structure and dynamics," Physics reports, vol. 424, no. 4-5, pp. 175-308, 2006. [DOI:10.1016/j.physrep.2005.10.009]
3. [3] M. E. Newman, "The structure and function of complex networks," SIAM review, vol. 45, no. 2, pp. 167-256, 2003. [DOI:10.1137/S003614450342480]
4. [4] S. Wasserman and K. Faust, Social network analysis: Methods and applications. Cambridge university press, 1994. [DOI:10.1017/CBO9780511815478]
5. [5] R. Milo, S. Shen-Orr, S. Itzkovitz, N. Kashtan, D. Chklovskii, and U. Alon, "Network motifs: simple building blocks of complex networks," Science, vol. 298, no. 5594, pp. 824-827, 2002. [DOI:10.1126/science.298.5594.824] [PMID]
6. [6] U. Brandes et al., "On modularity clustering," IEEE transactions on knowledge and data engineering, vol. 20, no. 2, pp. 172-188, 2007. [DOI:10.1109/TKDE.2007.190689]
7. [7] J. Liu, W. Zhong, and L. Jiao, "A multiagent evolutionary algorithm for combinatorial optimization problems," IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), vol. 40, no. 1, pp. 229-240, 2009. [DOI:10.1109/TSMCB.2009.2025775] [PMID]
8. [8] J. Liu, W. Zhong, and L. Jiao, "A multiagent evolutionary algorithm for constraint satisfaction problems," IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), vol. 36, no. 1, pp. 54-73, 2006. [DOI:10.1109/TSMCB.2005.852980] [PMID]
9. [9] M. M. Alipour and S. N. Razavi, "A new multiagent reinforcement learning algorithm to solve the symmetric traveling salesman problem," Multiagent and Grid Systems, vol. 11, no. 2, pp. 107-119, 2015. [DOI:10.3233/MGS-150232]
10. [10] M. M. Alipour, S. N. Razavi, M. R. F. Derakhshi, and M. A. Balafar, "A hybrid algorithm using a genetic algorithm and multiagent reinforcement learning heuristic to solve the traveling salesman problem," Neural Computing and Applications, pp. 1-17, 2017. [DOI:10.1007/s00521-017-2880-4]
11. [11] M. M. Alipour and M. Abdolhosseinzadeh, "A multiagent reinforcement learning algorithm to solve the maximum independent set problem," Multiagent and Grid Systems, vol. 16, no. 1, pp. 101-115, 2020. [DOI:10.3233/MGS-200323]
12. [12] M. E. Newman, "Modularity and community structure in networks," Proceedings of the national academy of sciences, vol. 103, no. 23, pp. 8577-8582, 2006. [DOI:10.1073/pnas.0601602103] [PMID] [PMCID]
13. [13] A. Clauset, M. E. Newman, and C. Moore, "Finding community structure in very large networks," Physical review E, vol. 70, no. 6, p. 066111, 2004. [DOI:10.1103/PhysRevE.70.066111] [PMID]
14. [14] J. M. Kumpula, J. Saramäki, K. Kaski, and J. Kertész, "Limited resolution and multiresolution methods in complex network community detection," Fluctuation and Noise Letters, vol. 7, no. 03, pp. L209-L214, 2007. [DOI:10.1142/S0219477507003854]
15. [15] S. Fortunato, "Community detection in graphs," Physics reports, vol. 486, no. 3-5, pp. 75-174, 2010. [DOI:10.1016/j.physrep.2009.11.002]
16. [16] L. Donetti and M. A. Munoz, "Detecting network communities: a new systematic and efficient algorithm," Journal of Statistical Mechanics: Theory and Experiment, vol. 2004, no. 10, pp. P10012, 2004. [DOI:10.1088/1742-5468/2004/10/P10012]
17. [17] M. Girvan and M. E. Newman, "Community structure in social and biological networks," Proceedings of the national academy of sciences, vol. 99, no. 12, pp. 7821-7826, 2002. [DOI:10.1073/pnas.122653799] [PMID] [PMCID]
18. [18] M. E. Newman and M. Girvan, "Finding and evaluating community structure in networks," Physical review E, vol. 69, no. 2, pp. 026113, 2004. [DOI:10.1103/PhysRevE.69.026113] [PMID]
19. [19] F. Radicchi, C. Castellano, F. Cecconi, V. Loreto, and D. Parisi, "Defining and identifying communities in networks," Proceedings of the national academy of sciences, vol. 101, no. 9, pp. 2658-2663, 2004. [DOI:10.1073/pnas.0400054101] [PMID] [PMCID]
20. [20] L. Hagen and A. B. Kahng, "A new approach to effective circuit clustering," in ICCAD, 1992, vol. 92, pp. 422-427. [DOI:10.1109/ICCAD.1992.279334]
21. [21] P. De Meo, E. Ferrara, G. Fiumara, and A. Provetti, "Mixing local and global information for community detection in large networks," Journal of Computer and System Sciences, vol. 80, no. 1, pp. 72-87, 2014. [DOI:10.1016/j.jcss.2013.03.012]
22. [22] J. Cao, Z. Bu, Y. Wang, H. Yang, J. Jiang, and H.-J. Li, "Detecting prosumer-community groups in smart grids from the multiagent perspective," IEEE Transactions on Systems, Man, and Cybernetics: Systems, vol. 49, no. 8, pp. 1652-1664, 2019. [DOI:10.1109/TSMC.2019.2899366]
23. [23] C.-K. Han, S.-F. Cheng, and P. Varakantham, "A Homophily-Free Community Detection Framework for Trajectories with Delayed Responses," in Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, 2019: International Foundation for Autonomous Agents and Multiagent Systems, pp. 2003-2005.
24. [24] X. Feng and X. Yang, "Fast convergent average consensus of multiagent systems based on community detection algorithm," Advances in Difference Equations, vol. 2018, no. 1, pp. 1-13, 2018. [DOI:10.1186/s13662-018-1901-7]
25. [25] P. Pons and M. Latapy, "Computing communities in large networks using random walks," J. Graph Algorithms Appl., vol. 10, no. 2, pp. 191-218, 2006. [DOI:10.7155/jgaa.00124]
26. [26] P. Ronhovde and Z. Nussinov, "Multiresolution community detection for megascale networks by information-based replica correlations," Physical Review E, vol. 80, no. 1, p. 016109, 2009. [DOI:10.1103/PhysRevE.80.016109] [PMID]
27. [27] M. Zhou and J. Liu, "A memetic algorithm for enhancing the robustness of scale-free networks against malicious attacks," Physica A: Statistical Mechanics and its Applications, vol. 410, pp. 131-143, 2014. [DOI:10.1016/j.physa.2014.05.002]
28. [28] T. N. Bui and B. R. Moon, "Genetic algorithm and graph partitioning," IEEE Transactions on computers, vol. 45, no. 7, pp. 841-855, 1996. [DOI:10.1109/12.508322]
29. [29] M. Tasgin, A. Herdagdelen, and H. Bingol, "Community detection in complex networks using genetic algorithms," arXiv preprint arXiv:0711.0491, 2007.
30. [30] C. Pizzuti, "Ga-net: A genetic algorithm for community detection in social networks," in International conference on parallel problem solving from nature, 2008: Springer, pp. 1081-1090. [DOI:10.1007/978-3-540-87700-4_107]
31. [31] A. Gog, D. Dumitrescu, and B. Hirsbrunner, "Community detection in complex networks using collaborative evolutionary algorithms," in European Conference on Artificial Life, 2007: Springer, pp. 886-894. [DOI:10.1007/978-3-540-74913-4_89]
32. [32] M. Gong, B. Fu, L. Jiao, and H. Du, "Memetic algorithm for community detection in networks," Physical Review E, vol. 84, no. 5, p. 056101, 2011. [DOI:10.1103/PhysRevE.84.056101] [PMID]
33. [33] J. Liu, W. Zhong, H. A. Abbass, and D. G. Green, "Separated and overlapping community detection in complex networks using multiobjective evolutionary algorithms," in IEEE Congress on Evolutionary Computation, 2010: IEEE, pp. 1-7. [DOI:10.1109/CEC.2010.5586522]
34. [34] X. Liu and T. Murata, "Advanced modularity-specialized label propagation algorithm for detecting communities in networks," Physica A: Statistical Mechanics and its Applications, vol. 389, no. 7, pp. 1493-1500, 2010. [DOI:10.1016/j.physa.2009.12.019]
35. [35] J. Duch and A. Arenas, "Community detection in complex networks using extremal optimization," Physical review E, vol. 72, no. 2, p. 027104, 2005. [DOI:10.1103/PhysRevE.72.027104] [PMID]
36. [36] B. Yang and D.-Y. Liu, "Force-based incremental algorithm for mining community structure in dynamic network," Journal of Computer Science and Technology, vol. 21, no. 3, pp. 393-400, 2006. [DOI:10.1007/s11390-006-0393-1]
37. [37] I. Gunes and H. Bingol, "Community detection in complex networks using agents," arXiv preprint cs/0610129, 2006.
38. [38] Z. Li and J. Liu, "A multi-agent genetic algorithm for community detection in complex networks," Physica A: Statistical Mechanics and its Applications, vol. 449, pp. 336-347, 2016. [DOI:10.1016/j.physa.2015.12.126]
39. [39] J. Huang, B. Yang, D. Jin, and Y. Yang, "Decentralized mining social network communities with agents," Mathematical and Computer Modelling, vol. 57, no. 11-12, pp. 2998-3008, 2013. [DOI:10.1016/j.mcm.2013.03.005]
40. [40] G. Palla, I. Derényi, I. Farkas, and T. Vicsek, "Uncovering the overlapping community structure of complex networks in nature and society," nature, vol. 435, no. 7043, p. 814, 2005. [DOI:10.1038/nature03607] [PMID]
41. [41] S. J. Russell and P. Norvig, Artificial intelligence: a modern approach. Malaysia; Pearson Education Limited, 2016.
42. [42] R. S. Sutton and A. G. Barto, Reinforcement learning: An introduction. Cambridge: MIT press, 1998. [DOI:10.1109/TNN.1998.712192]
43. [43] L. P. Kaelbling, M. L. Littman, and A. W. Moore, "Reinforcement learning: A survey," Journal of Artificial Intelligence Research, vol. 4, pp. 237-285, 1996. [DOI:10.1613/jair.301]
44. [44] P. Stone and M. Veloso, " Multiagent systems: A survey from the machine learning perspective," Autonomous Robots, vol. 8, no. 3, pp. 345-383, 2000. [DOI:10.1023/A:1008942012299]
45. [45] S. Sen and G. Weiss, "Learning in multiagent systems," in Multiagent Systems: A Modern Approach to Distributed Artificial Intelligence, G. Weiss Ed.: MIT Press, 1999, ch. 6, pp. 259-298.
46. [46] R. S. Sutton and A. G. Barto, Reinforcement Learning: An Introduction. MIT Press, 1998. [DOI:10.1109/TNN.1998.712192]
47. [47] I. S. Dhillon, Y. Guan, and B. Kulis, "Kernel k-means: spectral clustering and normalized cuts," in Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, 2004: ACM, pp. 551-556. [DOI:10.1145/1014052.1014118] [PMID]
48. [48] J. Shi and J. Malik, "Normalized cuts and image segmentation," Departmental Papers (CIS), pp. 107, 2000.
49. [49] W. W. Zachary, "An information flow model for conflict and fission in small groups," Journal of anthropological research, vol. 33, no. 4, pp. 452-473, 1977. [DOI:10.1086/jar.33.4.3629752]
50. [50] D. Lusseau, K. Schneider, O. J. Boisseau, P. Haase, E. Slooten, and S. M. Dawson, "The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations," Behavioral Ecology and Sociobiology, vol. 54, no. 4, pp. 396-405, 2003. [DOI:10.1007/s00265-003-0651-y]
51. [51] V. Krebs, "Books about us politics," unpublished, http://www.orgnet.com, 2004.
52. [52] A. Lancichinetti, S. Fortunato, and F. Radicchi, "Benchmark graphs for testing community detection algorithms," Physical review E, vol. 78, no. 4, p. 046110, 2008. [DOI:10.1103/PhysRevE.78.046110] [PMID]
53. [53] L. Danon, A. Diaz-Guilera, J. Duch, and A. Arenas, "Comparing community structure identification," Journal of Statistical Mechanics: Theory and Experiment, vol. 2005, no. 09, pp. P09008, 2005. [DOI:10.1088/1742-5468/2005/09/P09008]
54. [54] M. Tokic, F. Schwenker, and G. Palm, "Meta-learning of exploration and exploitation parameters with replacing eligibility traces," presented at the In IAPR International Workshop on Partially Supervised Learning (pp. 68-79). Springer Berlin Heidelberg, 2013, May. [DOI:10.1007/978-3-642-40705-5_7]
55. [55] K. Kobayashi, H. Mizoue, T. Kuremoto, and M. Obayashi, "A meta-learning method based on temporal difference error," presented at the In International Conference on Neural Information Processing (pp. 530-537). Springer Berlin Heidelberg, 2009, December. [DOI:10.1007/978-3-642-10677-4_60]
Send email to the article author
| Rights and permissions | |
 |
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License. |
