مروری بر روش‌های مدل‌سازی همپوشانی در الگوریتم‌های انجمن یابی شبکه‌های اجتماعی

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

نویسندگان

1 دانشکده کامپیوتر، دانشگاه صنعتی شاهرود، شاهرود، ایران

2 استادیار و رییس دانشکده کامپیوتر دانشگاه صنعتی شاهرود

چکیده

شبکه اجتماعی شامل تعدادی از اشخاص است که به‌واسطه یک یا چند نوع از روابط یا اشتراکات، با یکدیگر ارتباط دارند. پیدایش و رشد این شبکه‌ها در فضای مجازی و استفاده روزافزون از آنها، باعث شده است تا تحلیل شبکه‌های اجتماعی به‌عنوان یک حوزه تحقیقاتی پرمخاطب و میان‌رشته‌ای مطرح باشد. هر انجمن شامل چند عضو شبکه اجتماعی است که با توجه به نحوه دسته‌بندی اعضای شبکه تعیین می‌شود. مطالعه انجمن‌ها، یک مبحث مهم و کلیدی در تحلیل شبکه‌های اجتماعی است که ویژگیها و الگوهای مشخص یا مخفی در لایه‌های یک شبکه را نمایان می‌سازد و موجبات درک بهتر ساختار و رفتار آن را فراهم می‌کند. در این مقاله، ابتدا الگوریتم‌های انجمن‌یابی بر اساس رویکرد آنها به شکل‌گیری انجمن و نیز مدل‌سازی مفهوم همپوشانی (امکان تعلق هم‌زمان اعضا به دو یا چند انجمن) در شش دسته شامل روش‌های طیفی و مرکزگرایی، تابع کیفیت (چگالی)، انتشار برچسب، ساختار، نزدیکی، و دسته‌بندی یال‌ها، طبقه‌‌بندی و بررسی‌شده‌اند. در ادامه، روش‌های‌ انجمن‌یابی روی چهار دادگان با ساختار متفاوت، پیاده‌سازی و مقایسه شده‌‌اند. نتایج حاصله از معیارهای ارزیابی کیفیت روی چهار دادگان انتخابی، حاکی از آن است که هر روش روی توپولوژی و ویژگی خاصی بهتر عمل می‌کند. بنابراین هیچ روشی نمی‌تواند به‌عنوان بهترین روش انجمن‌یابی برای تمام شبکه‌ها مطرح باشد.

کلیدواژه‌ها

موضوعات

عنوان مقاله [English]

Modelling of Overlapping by Community Detection Algorithms in Social Networks: A Review

نویسندگان [English]

  • Seyed Mohammad Mahdi Salehi 1
  • Ali Akbar Pouyan 2
1 Department of Computer Engineering and IT, Shahrood University of technology, Shahrood, Iran.
2 Department of Computer Engineering and IT, Shahrood University of Technology, Shahrood, Iran
چکیده [English]

A social network consists of some people who are related to each other through some similarities. The emergence and evolution of these networks and increasing rate of using them is the major cause for social network analysis to be a hot research topic. Using various algorithms, each network can be divided into some communities. So, each community includes some members of the social network. Community detection is one of the most important and fundamental tasks in network analysis. It is a step towards understanding the patterns and characteristics of the complex systems they represent. In this paper, the state of the art algorithms for community detection are categorized into six categories (spectral clustering and centrality, quality function, Label propagation, Structure, Closeness, link clustering) based on their definition of the community and modelling the concept of overlapping (existence of the nodes with membership in multiple communities). Next, these methods are implemented on various datasets and compared to each other. It is obvious from the results of performance measures, even in this small collection of data sets, no algorithm can be considered as the best community detection method for all kinds of networks.

کلیدواژه‌ها [English]

  • Social networks
  • Social Networks Analysis (SNA)
  • Community
  • Community Detection
  • Overlapping

مراجع

 
[1] Huang, F., Li, X., Zhang, S., Zhang, J. (2017). Overlapping Community Detection for Multimedia Social Networks, IEEE Transactions on Multimedia, Vol. 92, pp. 1-3.
[2] Barabási, A. L., Albert, R. (1999). Emergence of scaling in random networks, Science, Vol. 286, pp. 509-512.
[3] Barabási, A. L., Bonabeau, E. (2003). Scale-free Networks, Scientific American, Vol. 288, pp. 50-59.
[4] Plantié, M., Crampes, M. (2013). Survey on social community detection, Social media retrieval (Springer), pp. 65-85.
[5] Yang, S., Yang, X., Zhang, C., Spyrou, E. (2010). Using social network theory for modeling human mobility, IEEE network, Vol. 24, pp. 6-13.
[6] Fortunato, S. (2010). Community detection in graphs, Physics reports, Vol. 486, pp. 75-174.
[7] Harenberg, S., Bello, G., Gjeltema, L., Ranshous, S., Harlalka, J., Seay, R. (2014). Community detection in large-scale networks: a survey and empirical evaluation, Wiley Interdisciplinary Reviews: Computational Statistics, Vol. 6, pp. 426-439.
[8] Coscia, M., Giannotti, F., Pedreschi, D. (2011). A classification for community discovery methods in complex networks, Statistical Analysis and Data Mining, Vol. 4, pp. 512-546.
[9] Psorakis, I., Roberts, S., Ebden, M., Sheldon, B. (2011). Overlapping community detection using Bayesian non-negative matrix factorization, Physical Review E, Vol. 83(6), p. 066114.
[10] Yang, J., Leskovec, J. (2013). Overlapping community detection at scale: a nonnegative matrix factorization approach, in Proceedings of the sixth ACM international conference on Web search and data mining, pp. 587-596.
[11] Girvan, M., Newman, M. E. (2002). Community structure in social and biological networks, Proceedings of the national academy of sciences, Vol. 99, pp. 7821-7826.
[12] Gregory, S. (2007). An algorithm to find overlapping community structure in networks, in Proceedings of the European Conference on Principles of Data Mining and Knowledge Discovery, pp. 91-102.
[13] Rhouma, D., Romdhane, L. (2014). An efficient algorithm for community mining with overlap in social networks, Expert Systems with Applications, Vol. 41, pp. 4309-4321.
[14] Zhi-Xiao, W., Ze-chao, L., Xiao-fang, Jin-hui, T. (2016). Overlapping community detection based on node location analysis, Knowledge-Based Systems, Vol. 105, pp. 225-235.
[15] Clauset, A., Newman, M. E., Moore, C. (2004). Finding community structure in very large networks, Physical review E, Vol. 70, p. 066111.
[16] Blondel, V. D., Guillaume, J., Lambiotte, R., Lefebvre, E. (2008). Fast unfolding of communities in large networks, Journal of statistical mechanics: theory and experiment, p. 10008.
[17] Chen, M., Kuzmin, K., Szymanski, B. K. (2014). Extension of Modularity Density for overlapping community structure, in Proceedings of the IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM), pp. 856-863.
[18] Kelley, S. (2009). The existence and discovery of overlapping communities in large-scale networks, PhD Thesis, Rensselaer Polytechnic Institute, NY.
[19] Lancichinetti, A., Fortunato, S. (2009). Community detection algorithms: a comparative analysis, Physical review E, Vol. 80, p. 056117.
[20] Lancichinetti, A., Radicchi, F., Ramasco, J. J., Fortunato, S. (2011). Finding statistically significant communities in networks, PloS one, Vol. 6, p. e18961.
[21] Bandyopadhyay, S., Chowdhary, G., Sengupta, D. (2015). FOCS: Fast Overlapped Community Search, IEEE Transactions on Knowledge and Data Engineering, Vol. 27, pp. 2974-2985.
]22[ شریف‌زاده، ح.، امجدی، ن.، (1393)، مروری بر انواع الگوریتم‌های فراکاوشی در بهینه‌سازی، مجله مدل‌سازی در مهندسی، دانشگاه سمنان، دوره 12، شماره 38.
[23] Pizzuti, C. (2008). GA-Net: A Genetic Algorithm for Community Detection in Social Networks, PPSN (Springer), pp. 1081-1090.
[24] Pizzuti, C. (2012). A Multiobjective Genetic Algorithm to Find Communities in Complex Networks, IEEE Transactions on Evolutionary Computation, Vol. 16, pp. 418-430.
]25[ نعیمی‌صدیق، ع.، چهارسوقی، س.ک.، شیخ‌محمدی، م.، (1391)، طراحی مدل هماهنگی در زنجیره تأمین رقابتی با استفاده از رویکرد نظریه بازی با همکاری و بدون همکاری، مجله مدل‌سازی در مهندسی، دانشگاه سمنان، دوره 10، شماره 29.
[26] Chen,W., Liu, Z., Sun, X., Wang, Y. (2010). A game-theoretic framework to identify overlapping communities in social networks, Data Mining and Knowledge Discovery, Vol. 21, pp. 224-240.
]27[ گلکار، ا.، کائدی، م.، (1394)، ارائه مدلی برای تخمین میزان برون‌گرایی اعضای شبکه اجتماعی با استفاده از اطلاعات ساختار گراف، مجله مدل‌سازی در مهندسی، دانشگاه سمنان، دوره 13، شماره 43.
]28[ احمدی، ر.، شیخ احمدی، س.، (1395)، پیش بینی افراد خبره در شبکه های اجتماعی آنلاین، هشتمین کنفرانس بین‌المللی فناوری اطلاعات و دانش، دانشگاه بوعلی سینا، همدان.
]29[ طالعی‌زاده، ع.ا.، چراغی، ز.، (1394)، قیمت‌گذاری و بازاریابی در یک زنجیره تامین دوسطحی تحت چهار رویکرد نظریه بازی‌ها، مجله مدل‌سازی در مهندسی، دانشگاه سمنان، دوره 13، شماره 42.
[30] Raghavan, U. N., Albert, R., Kumara, S. (2007). Near linear time algorithm to detect community structures in large-scale networks, Physical review E, Vol. 76, p. 036106.
[31] Gregory, S. (2010). Finding overlapping communities in networks by label propagation, New Journal of Physics, Vol. 12, p. 103018.
[32] Xie, J., Szymanski, B. K. (2012). Towards linear time overlapping community detection in social networks, in Proceedings of the Pacific-Asia Conference on Knowledge Discovery and Data Mining, pp. 25-36.
[33] Coscia,M., Rossetti, G., Giannotti, F., Pedreschi, D. (2012). Demon: a local-first discovery method for overlapping communities, in Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 615-623.
[34] Airoldi, E., Blei, D., Fienberg, S., Xing, E. (2008). Mixed membership stochastic blockmodels, Journal of Machine Learning Research, Vol. 9, pp. 1981-2014.
[35] McDaid, A., Hurley, N. (2010). Detecting highly overlapping communities with model-based overlapping seed expansion, in Proceedings of the IEEE/ACM International Conference on Social Networks Analysis and Mining (ASONAM), pp. 112-119.
[36] Whang, J., Gleich, D., Dhillon, I. (2016). Overlapping Community Detection Using Neighborhood-Inflated Seed Expansion, IEEE Transactions on Knowledge and Data Engineering, Vol. 28, pp. 1272-1284.
[37] Palla, G., Derényi, I., Farkas, I., Vicsek, T. (2005). Uncovering the overlapping community structure of complex networks in nature and society, Nature, Vol. 435, pp. 814-818.
[38] Shen, H., Cheng, X., Cai, K., Hu, M. (2010). Detect overlapping and hierarchical community structure in networks, Physica A: Statistical Mechanics and its Applications, Vol. 388, pp. 1706-1712.
[39] Lee, C., Reid, F., McDaid, A., Hurley, N. (2010). Detecting highly overlapping community structure by greedy clique expansion, arXiv preprint:1002.1827.
[40] Pons, P., Latapy, M. (2005). Computing communities in large networks using random walks, International Symposium on Computer and Information Sciences, pp. 284-293.
[41] Rosvall, M., Bergstrom, C. (2008). Maps of random walks on complex networks reveal community structure, Proceedings of the National Academy of Sciences, Vol. 105, pp. 1118-1123.
[42] Jin, D., Yang, B., Baquero, C., Liu, D., He, D., Liu, J. (2011). A Markov random walk under constraint for discovering overlapping communities in complex networks, Journal of Statistical Mechanics: Theory and Experiment, p. P05031.
[43] Evans, T., Lambiotte, R. (2009). Line graphs, link partitions, and overlapping communities, Physical Review E, Vol. 80, p. 016105.
[44] Ahn, Y. Y., Bagrow, J. P., Lehmann, S. (2010). Link communities reveal multiscale complexity in networks, Nature, Vol. 466. pp. 761-764.
[45] Palla, G., Farkas, I., Pollner, P., Derenyi, I., Vicsek, T. (2007). Directed network modules, New Journal of Physics, Vol. 9, p. 186.
[46] Farkas, I., Ábel, D., Palla, G., Vicsek, T. (2007). Weighted network modules, New Journal of Physics, Vol. 9, p. 180.
[47] Kunegis, J. (2013). Konect: the koblenz network collection, 22nd International Conference on World Wide Web, pp. 1343-1350.
[48] Leskovec, J., Sosič, R. (2016). SNAP: A general-purpose network analysis and graph-mining library, ACM Transactions on Intelligent Systems and Technology, Vol. 8, pp. 1-20.
[49] Bastian, M., Heymann, S., Jacomy, M. (2009). Gephi: open source software for exploring and manipulating networks, in Proceedings of the International Conference on Weblogs and Social Media, Vol. 8, pp. 361-362.
[50] Leskovec, J., Lang, K., Mahoney, M. (2010). Empirical comparison of algorithms for network community detection, in Proceedings of the 19th international conference on World Wide Web, pp. 631-640.
 
 
مدل سازی در مهندسی
دوره 17، شماره 56
بهار 1398
صفحه 247-265

فایل ها

اشتراک گذاری

ارجاع به این مقاله

آمار