روش توزیعی تشخیص انجمن در شبکه‌های اجتماعی بزرگ بر اساس انتشار برچسب

نوع مقاله : مقاله پژوهشی

نویسندگان

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

2 هیات علمی دانشکده فنی مهندسی دانشگاه شاهد

چکیده

تشخیص انجمن­های هم­پوشان در شبکه­های اجتماعی بسیار بزرگ با عامل­های هوشمند یک مساله سخت و مهم است که قدرت تشخیص و تحلیل آن شبکه­ها را از حالت بی­درنگِ برخط خارج می­کند. همپوشانی انجمن­ها در کنار افزایش ابعاد و ارتباطات این شبکه­ها به ­چالش­های پیچیدگی زمان زیاد جستجوی انجمن­ها و افزایش طاقت­فرسای حافظه مصرفی منجر می­شود که از قابلیت کنترل سریع آن‌ها می­کاهد. ارائه روش­های توزیعی مقیاس­پذیر تصادفی و عامل­گرا، بر اساس انتشار برچسب در شبکه­های بسیار بزرگ و پیچیده به کاهش زمان جستجو و تسریع تشخیص کمک می­کند. این مقاله روش توزیعی نوین مقیاس­پذیر عامل­گرا برای تشخیص انجمن‌های هم­پوشان بر اساس انتشار برچسب توانسته با محدودسازی انتشار پیام و استفاده از معیارهای جدید بر روی معماری چندهسته‌ای، به پیچیدگی خطی زمان اجرا و حافظه مصرفی دست یابد. روش پیشنهادی با آزمون بر روی مجموعه داده‌های بسیار بزرگ شبکه­های اجتماعی، از نظر زمان اجرا در شبکه‌های بزرگ تا 9 برابر تسریع و از نظر پیمانه‌ای از %3 تا %100 بهبود دارد و در یافتن انجمن­های هم­پوشان بسیار دقیق و سریع عمل می­کند.

کلیدواژه‌ها


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

A Distributed Approach to Community Detection in Large Social Networks Based on Label Propagation

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

  • M. Huseini 1
  • Aminollah Mahabadi 2
1 shahed university
2 Computer Engineering Department, Shahed University, Tehran, Iran. Acoustic Research Center , Shahed University, Tehran, Iran.
چکیده [English]

Detection of overlapping communities in large complex social networks with intelligent agents, is an NP problem with great time complexity and large memory usage and no simultaneous online solution.           Proposing a novel distributed label propagation approach can help to decrease the searching time and reduce the memory space usage. This paper presents a scalable distributed overlapping community         detection approach based on the label propagation method by proposing a novel algorithm and three new metrics to expand scalability and improve modularity through agent-based implementation and good memory allocation in a multi-core architecture. The experimental results of large real datasets over the state-of-the-art SLPA approach show that the execution time speeds up by 900% and the modularity improves by 3% to 100% thus producing fast and accurate detection of overlapped communities.
 

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

  • Social Networks
  • Distributed Processing
  • Overlapping Community Detection
  • Label Propagation Algorithm
[1]     T. Aynaud and J. L. Guillaume, “Multi-step community detection and hierarchical time segmentation in evolving networks,” Proceedings of the 5th SNA-KDD workshop, 2011.##
[2]     W. M. Campbell, C. K. Dagli, and C. J. Weinstein, “Social Network Analysis with Content and Graphs,” Lincoln Laboratory Journal, vol. 20, no. 1, 2013.##
[3]     Y.-Y. Ahn, J. P. Bagrow, and S. J. n. Lehmann, “Link communities reveal multiscale complexity in networks,” vol. 466, no. 7307, p. 761, 2010.##
[4]     L. Tang and H. Liu, “Community detection and mining in social media,” Synthesis Lectures on Data Mining and Knowledge Discovery, vol. 2, no. 1, pp. 130-137, 2010.##
[5]     [5] Y. Cohen, D. Hendler, and A. Rubin, “Node-centric detection of overlapping communities in social networks,” International Conference and School on Network Science, pp. 1-10, 2017.##
[6]     [6] M. Brutz and F. G. Meyer, “A Modular Multiscale Approach to Overlapping Community Detection,” arXiv preprint arXiv: 1501.05623, 2015.##
[7]     [7] U. N. Raghavan, R. Albert, and S. J. P. E. Kumara, “Near linear time algorithm to detect community structures in large-scale networks,” Phys. Rev. E., vol. 76, no. 3, p. 036106, Sep 2007.##
[8]     [8] M. J. Barber and J. W. J. P. R. E. Clark, “Detecting network communities by propagating labels under constraints,” Phys. Rev. E., vol. 80, no. 2, p. 026129, Aug. 2009.##
[9]     [9] X. Liu, T. J. P. A. S. M. Murata, and I. Applications, “Advanced modularity-specialized label propagation algorithm for detecting communities in networks,” Physica A: Statistical Mechanics and its Applications, vol. 389, no. 7, pp. 1493-1500, 2010.##
[10]  C. L. Staudt and H. Meyerhenke, “Engineering parallel algorithms for community detection in massive networks,” IEEE Transactions on Parallel and Distributed Systems, vol. 27, no. 1, pp. 171-184, 2016.##
[11]  S. Moon, J.-G. Lee, M. Kang, M. Choy, and J. w. Lee, “Parallel community detection on large graphs with MapReduce and GraphChi,” Data & Knowledge Engineering, vol. 104, pp. 17-34, 2016.##
[12]  C. Li, Y. Tang, H. Lin, C. Yuan, and H. Mai, “Parallel overlapping community detection algorithm in complex networks based on label propagation,” SCIENTIA SINICA Informationis, vol. 46, no. 2, pp. 212-227, 2016.##
[13]  K. Kuzmin, S. Y. Shah, and B. K. Szymanski, “Parallel overlapping community detection with SLPA,” International Conference on Social Computing. IEEE, pp. 204-212, 2013.##
[14]  Q. Yuchen, W. Haixia, and W. Dongsheng, “Parallelizing and optimizing overlapping community detection with speaker-listener Label Propagation Algorithm on multi-core architecture,” IEEE 2nd International Conference on Cloud Computing and Big Data Analysis (ICCCBDA), pp. 439-443, 2017.##
[15]  A. Kukanov and M. J. J. I. T. J. Voss, “The Foundations for Scalable Multi-Core Software in Intel Threading Building Blocks,” Intel Technology Journal, vol. 11, no. 4, 2007.##
[16]  S. Kim, “Community Detection in Directed Networks and its Application to Analysis of Social Networks,” Dissertation, The Ohio State University, 2014.##
[17]  S. Fortunato, “Community detection in graphs,” Physics Reports, vol. 486, no. 3-5, pp. 75-174, 2010.##
[18]  J. Su and T. C. Havens, “Fuzzy community detection in social networks using a genetic algortihm,” International Conference on Fuzzy Systems IEEE, pp. 2039-2046, 2014.##
[19]  B. Adamcsek, G. Palla, I. J. Farkas, I. Derenyi, and T. Vicsek, “CFinder: locating cliques and overlapping modules in biological networks,” Bioinformatics, vol. 22, no. 8, pp. 1021-1023, 2006.##
[20]  S. Gregory,“ Finding overlapping communities in networks by label propagation,” New Journal of Physics, vol. 12, no. 10, p. 103018, 2010.##
[21]  S. Gregory, “An algorithm to find overlapping community structure in networks,” European Conference on Principles of Data Mining and Knowledge Discovery, pp. 91-102, Springer 2007.##
[22]  H. Shen, X. Cheng, K. Cai, and M. B. Hu,“ Detect overlapping and hierarchical community structure in networks,” Physica A: Statistical Mechanics and its Applications, vol. 388, no. 8, pp. 1706-1712, 2009.##
[23]  J. Yang and J. Leskovec, “Defining and evaluating network communities based on ground-truth,” Knowledge and Information Systems, vol. 42, no. 1, pp. 181-213, 2013.##
[24]  W. Liu, X. Jiang, M. Pellegrini, and X. J. S. r. Wang, “Discovering communities in complex networks by edge label propagation,” Scientific Reports 6.1, vol. 6, no. 1, pp. 1-10, 2016.##
[25]  J. J. Whang, D. F. Gleich, and I. S. Dhillon, “Overlapping community detection using neighborhood-inflated seed expansion,” IEEE Transactions on Knowledge and Data Engineering, vol. 28, no. 5, pp. 1272-1284, 2016.##
[26]  V. D. Blondel, J.-L. Guillaume, R. Lambiotte, and E. Lefebvre, “Fast unfolding of communities in large networks,” Journal of Statistical Mechanics: Theory and Experiment, vol. 2008, no. 10, p. P10008, 2008.##