تشخیص انجمن‌ها در شبکه‌های اجتماعی بر اساس نظریه‌بازی با ائتلاف پایدار

نوع مقاله : مقاله ترویجی

نویسندگان

دانشکده علوم ریاضی، دانشگاه یزد، یزد، ایران

چکیده

با توجه به در دسترس بودن بیشتر داده‌ها و افزایش فعالیت‌های تعاملی در رسانه‌های اجتماعی، شناسایی همپوشانی انجمن‌ها مورد توجه قرار گرفته است. در این مقاله، یک رویکرد مبتنی بر نظریه بازی برای شناسایی همپوشانی انجمن‌ها ‏بررسی شده است.

در این روش، تشخیص انجمن‌ها را به‌عنوان یک بازی تشکیل ائتلاف مدل‌سازی می‌کنند. در این بازی، افراد در یک شبکه اجتماعی به‌عنوان بازیگران منطقی، مدل‌سازی می‌شوند که هدفشان بهبود مطلوبیت گروه است که از طریق همکاری با سایر بازیکنان و تشکیل ائتلاف‌ها دست‌یابی به این هدف را ممکن می‌سازد. هر بازیکن می‌تواند به چندین ائتلاف بپیوندد و ائتلاف‌هایی که بازیکنان کمتری دارند، می‌توانند تا زمانی که عملیات پیوستن برای اهداف ائتلاف بهبود بخش باشد، در یک ائتلاف بزرگتر با یکدیگر ادغام شوند. بنابراین، همپوشانی انجمن‌ها می‌توانند به‌طور همزمان شناسایی شوند.

در این مقاله، به دو نوع روش مبتنی بر نظریه بازی همکارانه و غیرهمکارانه پرداخته شده است. گزارش نتایج براساس مقایسه روش‌های انجمن‌یابی

به‌صورت نمودار مورد بررسی قرار می‌گیرد. مشاهده می‌شود که بازی‌گروهی و روش ‎COFOGA‎ بهتر انجمن‌یابی می‌کنند.

کلیدواژه‌ها


[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.