ارائه ی یک روش بهبود یافته مبتنی بر انتشار برچسب و رویکرد بهینه سازی ماژولاریتی برای تشخیص جوامع در شبکه های اجتماعی پویا
محورهای موضوعی : عمومى
محمد ستاری
1
(مرکز تحقیقات فناوری اطلاعات در امور سلامت، دانشگاه علوم پزشکی اصفهان، اصفهان، ایران)
کارمران زمانی فر
2
(گروه مهندسی نرم¬افزار، دانشکده مهندسی کامپيوتر، دانشگاه اصفهان، اصفهان، ايران )
کلید واژه: رتبه بندی برچسب مبتنی بر زمان حریصانه, رتبه بندی برچسب مبتنی بر زمان, رویکرد انتشار برچسب, تشخیص جوامع, شبکه ی اجتماعی پویا,
چکیده مقاله :
تشخیص جوامع در شبکههای اجتماعی پویا یکی از مهمترین موضوعات تحقیقاتی است که در سالیان اخیر مورد توجه قرار گرفته شده است. رویکردهای گوناگونی برای تشخیص جوامع در شبکههای اجتماعی در حالت پویا وجود دارد. از بین رویکردها، رویکرد انتشار برچسب به عنوان یک رویکرد ساده، کارا و تصادفی مطرح شده است. این رویکرد شامل روشهای بسیاری است که غالبا مبتنی بر حالت تصادفی این رویکرد هستند. از میان این روشها، روش رتبهبندی برچسب مبتنی بر زمان این رویکرد را از حالت تصادفی خارج کرده است و به آن قطعیت بخشیده است. البته مسلما این رویکرد هم با مشکلاتی مواجه است، یکی از مشکلات این است وقتی یک گره میخواهد به یک جامعه بپیوندد، ساختار درونی آن جامعه جهت پیوستن گره در نظر گرفته نمیشود. بنابراین برای حل این مشکل، یک رویکرد جدید به نام حریصانه به رویکرد انتشار برچسب اضافه شده است. رویکرد جدید ارائهشده به همراه روش رتبهبندی برچسب مبتنی بر زمان و نسخهی غیراشتراکی روش انتشار برچسب برجستهی گسترشیافته در مجموعههای دادهای مورد ارزیابی اعم از واقعی و ساختگی پیادهسازی شدهاند. نتایج نشان میدهد که روش پیشنهادی نسبت به دو روش دیگر از لحاظ میزان صحت براساس دو پارامتر ماژولاریتی و اطلاعات متقابل نرمال شده بهتر عمل کرده است.
Community detection in temporal social networks is one of the most important topics of research which attract many researchers around the world. There are variety of approaches in detecting communities in dynamic social network among which label propagation approach is simple and fast approach. This approach consists of many methods such as LabelRankT is one with high speed and less complexity. Similar to most methods for detecting communities in dynamic social networks, this one is not trouble free. That is, it is not considered the internal connection of communities, when it expands communities of the previous snapshots in the current snapshot. This drawback decreases the accuracy of community detection in dynamic social networks. For solving the drawback, a greedy approach based on local modularity optimization is added to LabelRankT method. Here, the newly proposed GreedyLabelRankT, LabelRankT and non-overlapping version of Dominant Label Propagation Algorithm Evolutionary (DLPAE-Non Overlapping) on real and synthetic datasets are implemented. Experimental results on both real and synthetic network show that the proposed method detect communities more accurately compared to the benchmark methods. Moreover, the finding here show that running time of the proposed method is close to LabelRankT. Therefore, the proposed method increase the accuracy of community detection in dynamic social networks with no noticeable change in the running time of that.
[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.