ارائه ی یک روش بهبود یافته مبتنی بر انتشار برچسب و رویکرد بهینه سازی ماژولاریتی برای تشخیص جوامع در شبکه های اجتماعی پویا
الموضوعات :
محمد ستاری
1
,
کارمران زمانی فر
2
1 - مرکز تحقیقات فناوری اطلاعات در امور سلامت، دانشگاه علوم پزشکی اصفهان، اصفهان، ایران
2 - گروه مهندسی نرم¬افزار، دانشکده مهندسی کامپيوتر، دانشگاه اصفهان، اصفهان، ايران
الکلمات المفتاحية: رتبه بندی برچسب مبتنی بر زمان حریصانه, رتبه بندی برچسب مبتنی بر زمان, رویکرد انتشار برچسب, تشخیص جوامع, شبکه ی اجتماعی پویا,
ملخص المقالة :
تشخیص جوامع در شبکههای اجتماعی پویا یکی از مهمترین موضوعات تحقیقاتی است که در سالیان اخیر مورد توجه قرار گرفته شده است. رویکردهای گوناگونی برای تشخیص جوامع در شبکههای اجتماعی در حالت پویا وجود دارد. از بین رویکردها، رویکرد انتشار برچسب به عنوان یک رویکرد ساده، کارا و تصادفی مطرح شده است. این رویکرد شامل روشهای بسیاری است که غالبا مبتنی بر حالت تصادفی این رویکرد هستند. از میان این روشها، روش رتبهبندی برچسب مبتنی بر زمان این رویکرد را از حالت تصادفی خارج کرده است و به آن قطعیت بخشیده است. البته مسلما این رویکرد هم با مشکلاتی مواجه است، یکی از مشکلات این است وقتی یک گره میخواهد به یک جامعه بپیوندد، ساختار درونی آن جامعه جهت پیوستن گره در نظر گرفته نمیشود. بنابراین برای حل این مشکل، یک رویکرد جدید به نام حریصانه به رویکرد انتشار برچسب اضافه شده است. رویکرد جدید ارائهشده به همراه روش رتبهبندی برچسب مبتنی بر زمان و نسخهی غیراشتراکی روش انتشار برچسب برجستهی گسترشیافته در مجموعههای دادهای مورد ارزیابی اعم از واقعی و ساختگی پیادهسازی شدهاند. نتایج نشان میدهد که روش پیشنهادی نسبت به دو روش دیگر از لحاظ میزان صحت براساس دو پارامتر ماژولاریتی و اطلاعات متقابل نرمال شده بهتر عمل کرده است.
[1] M. E. Newman, and M. Girvan, "Finding and evaluating community structure in networks", Physical review E, vol.69 , no.2, p.026113, 2004.
[2] S. Fortunato, “Community detection in graphs,” Physics Reports, pp. 75-174,2010. [3] N. P. Nguyen, T. N. Dinh, Y. Shen, and M. T. Thai, “Dynamic social community detection and its applications.”, PLoS One, vol. 9, no.4, p. e91431, 2014.
[4] V. D. Blondel, J. Guillaume, and E. Lefebvre, “Fast unfolding of communities in large networks,” Journal of Statistical Mechanics: Theory and Experiment, no. 10, pp. 1–12, 2008.
[5] S. Soundarajan, and J. E. Hopcroft, "Use of local group information to identify communities in networks". ACM Transactions on Knowledge Discovery from Data (TKDD), vol. 9, no.3, pp 1-35, 2015.
[6] U. N. Raghavan, R. Albert, and S. Kumara, Near linear time algorithm to detect community structures in large-scale networks, Physical review E, vol. 76, no.3, p.036106, 2007.
[7] M. Sattari, K. Zamanifar, “A spreading activation-based label propagation algorithm for overlapping community detection in dynamic social networks”, Data & Knowledge Engineering, vol. 113, pp.155-170, 2018.
[8] M. Sattari, K. Zamanifar. “A cascade information diffusion based label propagation algorithm for community detection in dynamic social networks”, Journal of Computational Science. vol. 25, pp. 122-33, 2018.
[9] X. Ma, D. Dong, “Evolutionary nonnegative matrix factorization algorithms for community detection in dynamic networks”. IEEE Transactions on Knowledge and Data Engineering, vol. 29, no. 5, pp. 1045-58, 2017.
[10] G. Rossetti, L. Pappalardo, Pedreschi D, Giannotti F. “Tiles: an online algorithm for community discovery in dynamic social networks”, Machine Learning. vol. 106, no. 8, pp. 1213-41, 2017.
[11] K. Kuzmin, S. Y. Shah, and B. K. Szymanski,"Parallel overlapping community detection with SLPA". In Social Computing (SocialCom), pp. 204-212, 2013.
[12] J. Xie, M. Chen, and B. Szymanski, “LabelrankT: Incremental community detection in dynamic networks via label propagation,” In Proceedings of the ACM Workshop on Dynamic Networks Management and Mining, ACM, pp. 25–32, 2013.
[13] J. Xie, and B. K. Szymanski, “LabelRank: A stabilized label propagation algorithm for community detection in Networks,” In Network Science Workshop (NSW), IEEE, pp. 138-143, 2013.#3 [14] M. Takaffoli, R. Rabbany, and O. R. Za, “Incremental local community identification in dynamic social networks.” In Proceedings of the IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, IEEE/ACM pp. 90-94, 2013.
[15] H. Alvari, A. Hajibagheri, and G. Sukthankar, “Community detection in dynamic social networks: A game-theoretic approach,” In Advances in Social Networks Analysis and Mining (ASONAM), IEEE/ACM , pp. 101–107, 2014.
[16] R. I. Lung, C. Chira, and A. Andreica, "Game theory and extremal optimization for community detection in complex dynamic networks". PloS one, vol.9, no.2, pp. 891-901, 2014.
[17] M. Takaffoli, R. Rabbany, and O. R. Za, “Incremental local community identification in dynamic social networks.” In Proceedings of the IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, IEEE/ACM pp. 90-94, 2013.
[18] J. He and D. Chen, “A fast algorithm for community detection in temporal network”, PhysicaA: Statistical Mechanics and its Applications, vol. 429, pp. 87–94, 2015.
[19] LXY.Leung, P.Hui, P.Liu , and J.Crowcroft, "Towards real-time community detection in large networks.", Physical Review E , vol. 79, no. 6, p.066107, 2009.
[20] K. Liu, J. Huang, H. un, M. Wan, Y. Qi, and H. Li, “Label propagation based evolutionary clustering for detecting overlapping and non-overlapping communities in dynamic networks,” Knowledge-Based Systems, vol. 89, pp. 487–496, 2015.
[21] S. H.L, H. J.B, T. Y.Q., Q.B., and L.Huai-Liang, “Detecting overlapping communities in networks via dominant label propagation,” Chinese Phys.B, vol. 24, no.1, p. 18703, 2015.
[22] X. Niu, W. Si, and C.Q. Wu, 2017. A label-based evolutionary computing approach to dynamic community detection. Computer Communications, vol. 108, pp.110-122, 2017.
[23] J. Han, W. Li, L. Zhao, Z. Su, Y. Zou, and W. Deng, "Community detection in dynamic networks via adaptive label propagation", PloS one, vol.12, no.11, p.e0188655,2017.
[24] M. Takaffoli, R. Rabbany, and O. R. Za, “Incremental local community identification in dynamic social networks.” In Proceedings of the IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, IEEE/ACM pp. 90-94, 2013.
[25] J. Gehrke, P. Ginsparg and J. Kleinberg, "Overview of the 2003 KDD Cup", ACM SIGKDD Explorations Newsletter, vol. 5, no. 2, pp.149-151, 2003.
[26] J. Leskovec, J. Kleinberg and C. Faloutsos. "Graphs over Time: Densification Laws, Shrinking Diameters and Possible Explanations.", ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), ACM, pp. 177-187, 2005
[27] A. Lancichinetti, S. Fortunato, "Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities", Phys. Rev. E, vol. 80, no.1, p. 016118, 2009.
[28] L. Danon, A. Diaz-Guilera, J. Duch, and A. Arenas. Comparing community structure identification. Journal of Statistical Mechanics: Theory and Experiment, 2005(09):P09008, 2005
[29] M. Newman, "modularity and community structure in networks". Proceedings of the National Academy of Sciences, vol. 103, no. 23, pp. 8577 –8582, 2002.
