Identification of communities in social networks based on game theory with stable coalitions

Document Type : Promotional Paper

Authors

Department of Mathematical Sciences, Yazd University, 89195-741, Yazd, Iran

Abstract

Due to the availability of more data and the increase of interactive activities in social media, the identification of overlapping associations has been considered. In this paper, a game theory-based approach to identify overlapping associations is proposed. In this method, association detection is modeled as a coalition formation game. In this game, individuals in a social network are modeled as rational actors whose goal is to improve the group's utility, which is achieved by cooperating with other players and forming coalitions. Each player can join multiple alliances, and alliances with fewer players can merge into a larger alliance as long as the joining operation is conducive to the alliance's goals. Therefore, overlapping associations can be identified simultaneously. In this article, two types of methods based on cooperative and non-cooperative game theory have been discussed. The results report is analyzed based on the comparison of association methods in the form of a diagram. It can be seen that the game group and the COFOGA method perform better association.

Keywords

References

[1] Y. Y. Ahn, J. P. Bagrow and S. Lehmann, Link communities reveal multiscale complexity in networks, Nature, 466 (2010) 761–764.
[2] H. Alvari, S. Hashemi and A. Hamzeh, Detecting overlapping communities in social networks by game theory and structural equivalence concept, In: International Conference on Artificial Intelligence and Computational Intelligence, Springer, Berlin, Heidelberg, (2011) 620–630.
[3] B. Ball, B. Karrer and M. E. Newman, Efficient and principled method for detecting communities in networks, Phys. Rev. E, 84 no. 3 (2011) 036103.
[4] O. Chatain, Cooperative and non-cooperative game theory, In book: The Palgrave Encyclopedia of Strategic Management, University of Pennsylvania, 2016 pp. 1–3.
[5] W. Chen, Z. Liu, X. Sun and Y. Wang, A game-theoretic framework to identify overlapping communities in social networks, Data Min. Knowl. Discov., 21 no. 2 (2010) 224–240.
[6] PO. Fjällström, Algorithms for graph partitioning: a survey, Linköping electronic articles in computer and information science, 3 (1998) pp. 34. http://www.ep.liu.se/ea/cis/1998/010/.
[7] M. Girvan and M. E. Newman, Community structure in social and biological networks, Proc. Natl. Acad. Sci. USA, 99 no. 12 (2002) 7821–7826.
[8] A. Hajibagheri, H. Alvari, A. Hamzeh and S. Hashemi, Social networks community detection using the shapley value, In: The 16th CSI International Symposium on Artificial Intelligence and Signal Processing (AISP 2012), Shiraz, Iran, (2012) 222–227.
[9] A. Lancichinetti, S. Fortunato and J. Kertesz, Detecting the overlapping and hierarchical community structure in complex networks, New J. Phys., 11 (2009) 122–128.
[10] A. Lancichinetti, S. Fortunato, and F. Radicchi, Benchmark graphs for testing community detection algorithms on directed and weighted graphs with overlapping communities. Phys. Rev. E 80 no.1 (2009) pp. 9.
[11] R. I. Lung, A. Gog and C. Chira, A game theoretic approach to community detection in social networks, Chapter In: Nature Inspired Cooperative Strategies for Optimization (NICSO 2011), Berlin, Heidelberg: Springer Berlin Heidelberg, (2011) 121–131.
[12] M. Molloy and B. Reed, A critical point for random graphs with a given degree sequence, Random Struct Algorithms, 6 no. 2-3 (1995) 161–180.
[13] V. Moscato, A. Picariello and G. Sperlí, Community detection based on Game Theory, Eng. Appl. Artif. Intell., 85 (2019) 773–782.
[14] M. E. J. Newman, Modularity and community structure in networks, Proc. Natl. Acad. Sci., 103 no. 23 (2006) 8577–8582.
[15] M. E. J. Newman and M. Girvan, Finding and evaluating community structure in networks, Phys. Rev. E, 69 (2004) 231–238.
[16] G. Palla, I. Derényi, I. Farkas and T. Vicsek, Uncovering the overlapping community structure of complex networks in nature and society, Nature, 435 (2005) 814–818.
[17] A. Roth, The Shapley Value: Essays in Honor of Lloyd S. Shapley, Cambridge: Cambridge University Press, 1988.
[18] H. C. White, S. A. Boorman and R. L. Breiger, Social structure from multiple networks. I. blockmodels of roles and positions, Am. J. Soc., 81 no. 4 (1976) 730–780.
[19] W. W. Zachary, An information flow model for conflict and fission in small groups, Journal of Anthropological Research, 33 no. 4 (1977) 452–473.
[20] G. L.Zacharias, J. E. Macmillan and S. B. Van Hemel, Behavioral modeling and simulation: From individuals to societies, National Academies Press, 2008.
[21] L. Zhou, C. Cheng, K. Lü and H. Chen, Using coalitional games to detect communities in social networks, In: International Conference on Web-Age Information Management, Springer, Berlin, Heidelberg, (2013) 326–331.
[22] L. Zhou and K. Lü, Detecting communities with different sizes for social network analysis, The Computer Journal, 58 no. 9 (2015) 1894–1908.
[23] L. Zhou, K. Lü, P. Yang, L. Wang and B. Kong, An approach for overlapping and hierarchical community detection in social networks based on coalition formation game theory, Expert Syst. Appl., 42 no. 24 (2015) 9634–9646.
[24] L. Zhou, P. Yang, K. Lü, L. Wang and H. Chen, A fast approach for detecting overlapping communities in social networks based on game theory, In: British International Conference on Databases, Springer, Cham, (2015) 62–73.

Files

History

  • Receive Date: 10 March 2024
  • Revise Date: 10 August 2024
  • Accept Date: 11 August 2024
  • Publish Date: 21 April 2025

Share

How to cite

Statistics