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

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

نویسندگان

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

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

3 استادیار دانشگاه شهید بهشتی، دانشکده علوم و مهندسی کامپیوتر

چکیده

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

کلیدواژه‌ها


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

Dynamic Community in static social networks using the gray wolf optimizer algorithm

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

  • Fatemeh Besharatnia 1
  • Alireza Talebpur 2
  • Sadegh Aliakbari 3
چکیده [English]

Identifying communities in complex networks is an important issues in social network analysis, and it helps researchers understand the function and display of network structures. Clustering or recognizing communities will reveal the structure of groups in social networks and hidden communication between its components. A community is a collection of nodes whose density of communication is more than the other network entities.In this paper, a new algorithm for recognizing communities in static networks has been presented which utilizes Gray Wolf Optimizer algorithm, which has the ability to scale according to the selected criteria.  It has been shown that one of the most important characteristics of meta-algorithms is the lack of trapping at the local minimum. Gray Wolf Optimizer algorithm is less likely to be trapped than other optimization algorithms such as the genetic algorithm and the particle swarm algorithm. Finally, the results of the experiments showed that the algorithm is better than other algorithms on average.

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

  • Social Networks
  • Community Detection
  • Meta-Algorithms
  • Gray Wolf Optimizer Algorithm

مراجع

[1]  Xu, T., et al., Generative models for evolutionary clustering. ACM Transactions on Knowledge Discovery from Data    (TKDD), 2012. 6(2): p. 7.

[2] Barber, M.J., Modularity and community detection in bipartite networks. Physical Review E, 2007. 76(6): p. 066102.

[3] Pantié, M. and M. Crampes, Survey on social community detection, in Social media retrieval. 2013, Springer. p. 65-85.

[4] Newman, Mark EJ, and Michelle Girvan. "Finding and evaluating community structure in networks." Physical review E 69.2 (2004): 026113.

[5] Newman, Mark EJ. "Fast algorithm for detecting community structure in networks." Physical review E 69.6 (2004): 066133.

[6] Clauset, Aaron, Mark EJ Newman, and Cristopher Moore. "Finding community structure in very large networks." Physical review E 70.6 (2004): 066111.

[7] Shang, Ronghua, et al. "Community detection based on modularity and an improved genetic algorithm." Physica A:Statistical Mechanics and its Applications 392.5 (2013):1215-1231.

[8] Tasgin, M., A. Herdagdelen, and H. Bingol, Community detection in complex networks using genetic algorithms. arXiv preprint arXiv:0711.0491, 2007.

[9] Pizzuti, Clara. "A multiobjective genetic algorithm to find communities in complex networks." Evolutionary Computation, IEEE Transactions on 16.3 (2012): 418-430.

[10] Gong, Maoguo, et al. "Community detection in networks by using multiobjective evolutionary algorithm with decomposition." Physica A: Statistical Mechanics and its Applications 391.15 (2012): 4050-4060.

[11] Zhao, Yuxin, et al. "A cellular learning automata based algorithm for detecting community structure in complex networks." Neurocomputing 151 (2015): 1216-1226.

[12] Newman, M.E., Fast algorithm for detecting community structure in networks. Physical review E, 2004. 69(6): p. 066133.

[13] Lin, Z., et al., CK-LPA: Efficient community detection algorithm based on label propagation with community kernel. Physica A: Statistical Mechanics and its Applications, 2014. 416: p. 386-399.

[14] Papadopoulos, S., et al., Community detection in social media. Data Mining and Knowledge Discovery, 2012. 24(3): p. 515-554.

[15] Mirjalili, S., S.M. Mirjalili, and A. Lewis, Grey wolf optimizer. Advances in Engineering Software, 2014. 69: p. 46-61.

[16] Newman, M.E. and M. Girvan, Finding and evaluating community structure in networks. Physical review E, 2004. 69(2): p. 026113.

[17] Good, B.H., Y.-A. de Montjoye, and A. Clauset, Performance of modularity maximization in practical contexts. Physical Review E, 2010. 81(4): p. 046106.

[18] http://konect.uni-koblenz.de/networks/

CAPTCHA Image