• صفحه اصلی
  • ارائه الگوریتم موازی و کارا به‌منظور شناسایی انجمن‌های همپوشان در شبکه‌های اجتماعی

اشتراک گذاری

آدرس مقاله


کد مقاله : 1402051943556 بازدید : 338 صفحه: 245 - 258

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

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

محورهای موضوعی : مهندسی برق و کامپیوتر

مصطفی سبزه کار 1 * , شیما برادران نژاد 2 , مهدی خزاعی پور 3 , مهدی خرد 4

1 - گروه مهندسی کامپیوتر، دانشگاه صنعتی بیرجند
2 - گروه مهندسی کامپیوتر، دانشگاه آزاد اسلامی، واحد بیرجند، بیرجند، ایران
3 - گروه مهندسی کامپیوتر، دانشگاه آزاد اسلامی، واحد بیرجند، بیرجند، ایران
4 - دانشجوی دکتری، گروه مهندسی کامپیوتر، دانشکده فنی و مهندسی - دانشگاه قم - قم - ایران

تاریخ دریافت : 1402/05/19 تاریخ پذیرش : 1402/11/28 تاریخ انتشار : 1404/03/13

کلید واژه: شبکه‌های اجتماعی, موازی‌سازی, کشف انجمن, انجمن‌های هم‌پوشان.,

چکیده مقاله :

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

چکیده انگلیسی:

Social networks are not only tools for communication but also represent one of the key potentials in business and commerce. One of the most significant issues in this field is clustering nodes and extracting effective and useful patterns from them, known as community detection. A major challenge in community detection within social networks is the vast number of nodes, which makes any kind of analysis difficult. Another challenge is the overlap of cluster members, referred to as overlapping communities. In such networks, each node may belong to multiple groups. Considering overlaps between communities—especially in large-scale networks—poses significant challenges in accurately detecting and identifying communities. Therefore, many studies tend to overlook this issue. In this paper, an approach is proposed to address these challenges. The most time-consuming step in the proposed algorithm, identifying influential nodes, is performed in parallel. Moreover, overlaps between communities are taken into account and analyzed. The results of evaluating the proposed method, in comparison with other existing methods, indicate its superiority in terms of the uniformity of the detected communities.

منابع و مأخذ:

[1] [1] A. Reihanian, M. R. Feizi-Derakhshi, and H. S. Aghdasi, "An enhanced multi-objective biogeography-based optimization for overlapping community detection in social networks with node attributes," Information Sciences, vol. 622, pp. 903-929, Apr. 2023.
[2] S. K. Gupta and D. P. Singh, "Seed community identification framework for community detection over social media," Arab. J. Sci. Eng., vol. 48, no. 2, pp. 1829-1843, 2023.
[3] S. Mishra, S. S. Singh, S. Mishra, and B. Biswas, "Multi-objective based unbiased community identification in dynamic social networks," Comput. Commun., vol. 214, pp. 18-32, 15 Jan. 2024.
[4] M. Sabzekar, S. BaradaranNejad, and M. Khazaeipoor, "A node-centric approach for community detection in dynamic networks," J. Electr. Comput. Eng. Innov., vol. 12, no. 2, pp. 305-318, Jul. 2024.
[5] X. Li, Y. Xin, C. Zhao, Y. Yang, and Y. Chen, "Graph convolutional networks for privacy metrics in online social networks," Applied Sciences, vol. 10, no. 4, Article ID: 1327, 2020.
[6] Z. Ma and S. Nandy, "Community detection with contextual multilayer networks," IEEE Trans. Inf. Theory, vol. 69, no. 5, pp. 3203-3239, May 2023.
[7] M. Rostami, M. Oussalah, K. Berahmand, and V. Farrahi, "Community detection algorithms in healthcare applications: a systematic review," IEEE Access, vol. 11, pp. 30247-30272, 2023.
[8] F. S. Gharehchopogh, "An improved harris hawks optimization algorithm with multi-strategy for community detection in social network," J. Bionic Eng., vol. 20, pp. 1175-1197, 2023.
[9] D. Jin, et al., "A survey of community detection approaches: from statistical modeling to deep learning," IEEE Trans. Knowl. Data Eng., vol. 35, no. 2, pp. 1149-1170, Feb. 2023.
[10] M. Seifikar, S. Farzi, and M. Barati, "C-Blondel: an efficient louvain-based dynamic community detection algorithm," IEEE Trans. Comput. Soc. Syst., vol. 7, no. 2, pp. 308-318, Apr. 2020.
[11] S. Ahajjam, M. El Haddad, and H. Badir, "A new scalable leader-community detection approach for community detection in social networks," Soc. Networks, vol. 54, pp. 41-49, Jul. 2018.
[12] S. Bahadori, H. Zare, and P. Moradi, "PODCD: probabilistic overlapping dynamic community detection," Expert Syst. Appl., vol. 174, Article ID: 114650, 15 Jul. 2021.
[13] C. Bothorel, V. L. Dao, and P. Lenca, "Community structure: a comparative evaluation of community detection methods," Netw. Sci., vol. 8, no. 1, pp. 1-41, Mar. 2020.
[14] S. Fortunato, "Community detection in graphs," Phys. Rep., vol. 486, no. 3-5, pp. 75-174, Feb. 2010.
[15] M. E. J. Newman, "Modularity and community structure in networks," in Proc. Natl. Acad. Scivol. 103, no. 23, pp. 8577-8582, Jun. 2006.
[16] W. Li, X. Zhou, C. Yang, Y. Fan, Z. Wang, and Y. Liu, "Multi-objective optimization algorithm based on characteristics fusion of dynamic social networks for community discovery," Inf. Fusion, vol. 79, no. C, pp. 110-123, Mar. 2022.
[17] Q. Ni, J. Guo, W. Wu, and H. Wang, "Influence-based community partition with sandwich method for social networks," IEEE Trans. Comput. Soc. Syst., vol. 10, no. 2, pp. 819-830, Apr. 2023.
[18] H. Long, X. Li, X. Liu, and W. Wang, "BBTA: detecting communities incrementally from dynamic networks based on tracking of backbones and bridges," Appl. Intell., vol. 53, pp. 1084-1100, 2023.
[19] H. Safdari, M. Contisciani, and C. De Bacco, "Reciprocity, community detection, and link prediction in dynamic networks," J. Phys. Complex., vol. 3, no. 1, Article ID: 15010, 2022.
[20] S. Kumar, A. Mallik, and S. S. Sengar, "Community detection in complex networks using stacked autoencoders and crow search algorithm," J. Supercomput., vol. 79, no. 3, pp. 3329-3356, 2023.
[21] T. Ma, Q. Liu, J. Cao, Y. Tian, A. Al-Dhelaan, and M. Al-Rodhaan, "LGIEM: global and local node influence based community detection," Futur. Gener. Comput. Syst., vol. 105, pp. 533-546, Apr. 2020.
[22] T. Wang, S. Chen, X. Wang, and J. Wang, "Label propagation algorithm based on node importance," Phys. A Stat. Mech. its Appl., vol. 551, Article ID: 124137, Aug. 2020.
[23] C. Li, et al., "NANI: an efficient community detection algorithm based on nested aggregation of node influence," 2017.
[24] D. Zhuang, M. Chang, and M. Li, "DynaMo: dynamic community detection by incrementally maximizing modularity," IEEE Trans. Knowl. Data Eng., vol. 33, no. 5, pp 1934-1945, May 2021.
[25] S. A. Seyedi, A. Lotfi, P. Moradi, and N. N. Qader, "Dynamic graph-based label propagation for density peaks clustering," Expert Syst. Appl., vol. 115, pp. 314-328, Jan. 2019.
[26] F. Liu, J. Wu, C. Zhou, and J. Yang, "Evolutionary community detection in dynamic social networks," in Proc. Int. Joint Conf. on Neural Networks, 7 pp. , Budapest, Hungary, 14-19 Jul. 2019.
[27] X. Su, J. Cheng, H. Yang, M. Leng, W. Zhang, and X. Chen, "IncNSA: detecting communities incrementally from time-evolving networks based on node similarity," Int. J. Mod. Phys. C, vol. 31, no. 7, Article ID: 2050094, 2020.
[28] M. Cordeiro, R. P. Sarmento, and J. Gama, "Dynamic community detection in evolving networks using locality modularity optimization," Soc. Netw. Anal. Min., vol. 6, Article ID: 15, 2016.
[29] J. Leskovec, J. Kleinberg, and C. Faloutsos, "Graphs over time: densification laws, shrinking diameters and possible explanations," in Proc. of the 11th ACM SIGKDD Int. Conf. on Knowledge Discovery in Data Mining, pp. 177-187, Chicago, IL, USA, 21-24 Aug. 2005.
[30] A. Paranjape, A. R. Benson, and J. Leskovec, "Motifs in temporal networks," in Proc. of the 10th ACM Int. Conf. on Web Search and Data Mining, pp. 601-610, Cambridge, UK, 6-10 Dec. 2017.
[31] P. Panzarasa, T. Opsahl, and K. M. Carley, "Patterns and dynamics of users' behavior and interaction: network analysis of an online community," J. Am. Soc. Inf. Sci. Technol., vol. 60, no. 5, pp. 911-932, May 2009.
متن کامل:
معرفي يک روش جديد خوشه‌يابي خودکار

نشریه مهندسی برق و مهندسی کامپیوتر ایران، ب- مهندسی کامپیوتر، سال 22، شماره 4، زمستان 1403                  245

مقاله پژوهشی

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

مصطفی سبزه‌کار، شیما برادران‌نژاد، مهدی خزاعی‌پور و مهدی خرد

 

1 

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

 

کلیدواژه: شبکه‌های اجتماعی، موازی‌سازی، کشف انجمن، انجمن‌های هم‌پوشان.

1-       مقدمه

امروزه تقریباً می‌توان هر پدیده طبیعی را با تعریف مجموعه‌ای از موجودیت‌ها و در نظر گرفتن روابط بین آنها به‌صورت شبکه در نظر گرفت [‌1]‌. شبکه‌های اجتماعی نمونه‌ شناخته‌شده‌ای از یک شبکه هستند که عبارت است از ساختاری اجتماعی از مجموعه‌ای از گره‌ها به عنوان بازیگران اجتماعی که توسط یک یا چند نوع خاص از وابستگی متقابل به هم مرتبط هستند [‌2]‌. شبکه‌های اجتماعی شبکه‌های دنیای واقعی هستند که ماهیتی فراگیر دارند. برخی از نمونه‌های معمولی از شبکه‌های اجتماعی عبارتند از شبکه‌های همکاری گروهی تحقیقاتی، شبکه‌های ارتباطی شرکت، شبکه‌های دوستی آنلاین، شبکه‌های مبتنی بر رفتار حیوانات و غیره. استفاده از شبکه‌های اجتماعی به دلیل کاربرد گسترده آن در دنیای واقعی، توجه تحقیقاتی قابل توجهی را به خود معطوف کرده است. با گسترش خدمات مبتنی بر اینترنت و افزایش حجم داده‌ها، شبکه‌های اجتماعی نیز به طرز چشم‌گیری در حال افزایش حجم و اندازه هستند [3] و [4]‌. به علاوه این شبکه‌ها امروزه به علت کمک به برقراری ارتباط بین افراد، بی‌گمان به محبوب‌ترین ابزار مبتنی بر اینترنت تبدیل شده‌اند [‌5]‌.

از مهم‌ترین مشخصه‌های شبکه‌های اجتماعی، ساختار انجمن‌های درون آنهاست. شناسایی ساختار انجمن یکی از موضوعات مهم و چالش‌برانگیز در شبکه‌های اجتماعی می‌باشد که هدف از آن، یافتن زیرگراف‌هایی است که از نظر داخلی متراکم بوده، اما از نظر خارجی به‌طور پراکنده با هم در ارتباط هستند [‌6]‌. شناسایی انجمن‌ها اصولاً به عنوان مسائل خوشه‌بندی و گراف‌کاوی تعریف می‌شوند [‌7]‌. انجمن‌ها اغلب نشان‌دهنده گروه‌های سازمان‌یافته از افراد با ویژگی‌ها، علایق یا روابط شخصی مشابه هستند و در نتیجه، شناسایی ساختار انجمن‌ها در شبکه‌های اجتماعی بسیار ضروری است [8]‌.

تشخیص انجمن‌ها اگرچه مسئله جدیدی نبوده و به عنوان یک مسئله خوشه‌بندی تعریف می‌شود، اما با چالش‌های متعددی نیز همراه است که به شرح ذیل می‌باشد:

•        یکی از این چالش‌ها همپوشانی موجود بین انجمن‌هاست. بسیار طبیعی است که در دنیای واقعی هر گره از شبکه بتواند به چندین گروه تعلق پیدا کند. در نظر گرفتن این مسئله موجب تحمیل‌شدن حجم زیادی از محاسبات و پیچیده‌شدن راه‌حل‌های ارائه‌شده می‌گردد؛ به نحوی که در بسیاری از پژوهش‌ها از همپوشانی بین انجمن‌ها صرف نظر می‌شود [‌9]‌.

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

•        در شبکه‌های اجتماعی نظر افراد مختلف با یکدیگر یکسان نیست و این مسئله بایستی در تشخیص انجمن‌ها مد نظر قرار بگیرد. به طور مثال، چنانچه یک نظر توسط افراد مشهور یا بسیار نزدیک به فرد مورد نظر ارائه شده باشد، در تصمیم‌گیری در خصوص مسئله خاص تأثیر بیشتری می‌گذارد [‌11]‌. بنابراین در پژوهش‌های اخیر بر روی یافتن و شناسایی گره‌های تأثیرگذار و دخالت‌دادن آنها بر تشخیص انجمن‌ها تأکید گردیده است؛ اگرچه در پاسخ به این چالش، مطالعات چندانی صورت نگرفته است.

•        مسئله تشخیص انجمن در شبکه‌های بزرگ در زمره مسائل 
NP-hard قرار می‌گیرد. روش‌هایی برای شناسایی سریع انجمن‌ها پیشنهاد شده که اکثر آنها بر اساس بهینه‌سازی توابع هدف هستند. تاکنون روشی برای موازی‌سازی الگوریتم‌های پیشنهادی برای حل مشکل ارائه نگردیده است.

در این مقاله، روشی برای حل تمامی چالش‌های ذکرشده ارائه گردیده است. هدف از این مقاله، ارائه یک الگوریتم کشف انجمن پویاست که از تأثیر و نفوذ گره‌ها برای ایجاد انجمن استفاده می‌کند. الگوریتم پیشنهادی در مرحله اول، تأثیر گره‌ها در شبکه را محاسبه می‌کند و img0 گره بالاتر به‌عنوان گره مرکزی2 انتخاب شده و سپس انجمن‌ها بر اساس این گره‌های مرکزی انتخاب می‌شوند. گره‌هایی که یال مستقیم به یک گره مرکزی داشته باشند، به آن انجمن اختصاص می‌یابند. سایر گره‌ها که فاقد یال مستقیم به یکی از گره‌های مرکزی هستند، بر اساس میزان شباهت و همسایگان مشترک به انجمن‌ها ملحق می‌شوند. در صورتی که برای یک گره هیچ یک از همسایگی‌ها به انجمن خاصی تعلق نداشته باشند، خودشان تشکیل انجمن می‌دهند؛ بدین ترتیب تعداد انجمن می‌تواند بیش از img0 باشد. در مرحله بعد، انجمن‌ها بررسی شده و بر اساس یک معیار جدید، میزان همپوشانی انجمن‌ها محاسبه و در نهایت انجمن‌ها با هم ادغام می‌شوند. در ادامه فرایند کشف انجمن با دریافت یک بازه زمانی دیگر، بعد از شناسایی تغییرات در شبکه، انجمن‌ها به‌روز می‌شوند. فرایند به‌روزشدن انجمن‌ها بر اساس ایجاد انجمن جدید، حذف انجمن موجود و یا ادغام انجمن‌های موجود انجام می‌شود. پیش از این در [4]‌ روشی برای تشخیص انجمن در شبکه‌های اجتماعی با در نظر گرفتن تأثیر گره‌های مهم ارائه نمودیم و در این مقاله توسعه آن برای حالت موازی با در نظر گرفتن انجمن‌های همپوشان ارائه می‌گردد.

به طور خلاصه نوآوری‌ها و دستاوردهای این مقاله شامل موارد زیر هستند:

•        ارائه یک روش تشخیص انجمن در شبکه پویا بر اساس تأثیر 
گره‌ها بر اساس اطلاعات محلی و سراسری و توجه به امکان همپوشانی انجمن‌ها

•        ارائه روشی جهت شناسایی تغییرات در شبکه پویا و میزان تأثیرگذاری هر گره و اعمال این تغییرات در انجمن‌‌های موجود

•        مقایسه الگوریتم پیشنهادی با روش‌های پیشرفته اخیر در زمینه تشخیص انجمن در شبکه‌های پویا شامل Dynamic Louvain، DynaMo، IncNSA، ECD، DPC-DLP، DynCRep و 
CD-SACS بر روی سه مجموعه داده استاندارد Cit-Hep Ph، sx-mathoverflow و CollegeMsg با معیارهای ارزیابی مدولاریتی نیومن، مدولاریتی با جریمه تقسیم، مدولاریتی چگالی و زمان اجرا

•        مجهزکردن روش پیشنهادی به اجرای موازی برای یافتن انجمن‌ها در زمان کوتاه که این روش را برای شبکه‌های بزرگ بسیار کارا می‌نماید.

در ادامه این مقاله در بخش 2، مفاهیم پایه پژوهش بیان شده است. بخش 3 به پیشینه تحقیق با مقایسه کارهای انجام‌شده در حوزه حل مسئله کشف انجمن با استفاده از گره‌های تأثیرگذار پرداخته است. اجزا و فازهای روش پیشنهادی در بخش 4 و پیاده‌سازی و ارزیابی روش مذکور در بخش 5 ارائه شده است. نهایتاً خلاصه و نتیجه‌گیري رویکرد پیشنهادي در بخش 6 جمع‌بندي شده است.

2-       مفاهیم پایه

1-2 شبکه‌های اجتماعی

همان طور که در فصل پیش عنوان شد، در یک تعریف ساده، مجموعه‌ای از گره‌ها و ارتباط بین آنها را می‌توان شبکه نامید. شبکه، یک ساختار به‌هم‌پیوسته از گره‌هایی است که با هم ارتباطاتی را شکل می‌دهند. حال چنانچه این شبکه برای بیان تعاملات اجتماعی بین مجموعه‌ای از کاربران به کار رفته باشد، آن را شبکه اجتماعی می‌نامیم. اغلب برای نمایش شبکه‌های اجتماعی از ماتریس مجاورت استفاده می‌شود. در این ماتریس چنانچه img0 گره از کاربران را داشته باشیم، وجود رابطه بین هر زوج از کاربران را با یک و عدم وجود چنین ارتباطی را با صفر نمایش می‌دهیم. لذا ماتریس مجاورت یک شبکه، ماتریسی img0 متشکل از صفر و یک خواهد بود. بدیهی است ساختار چنین شبکه‌هایی کاملاً پویا بوده و با اضافه یا کم شدن کابران (رئوس گراف) و ایجاد یا حذف ارتباط بین کاربران (یال‌های گراف) در هر لحظه تصویر گراف با لحظه قبل متفاوت خواهد بود. در نتیجه، انجمن‌های موجود در شبکه نیز به‌صورت پویا در حال تغییر می‌باشند [‌12]‌.

2-2 تشخیص انجمن

در علم شبکه برای تشخیص انجمن که خوشه‌بندی گراف نیز نامیده می‌شود، تعریف مشخص، دقیق و مورد پذیرش توسط عامه‌ای وجود ندارد [‌13]‌. در [‌14]‌ انجمن به‌صورت گروهی از گره‌ها در یک گراف تعریف شده که یال‌هایی که آنها را به یکدیگر متصل می‌کند، بسیار بیشتر از یال‌هایی است که آن انجمن را به بقیه گراف متصل می‌نماید. نیومن نیز انجمن را مجموعه رئوس یک گراف در نظر می‌گیرد که تعداد یال‌های بین آنها بیشتر از میانگین می‌باشد [‌15]‌. لذا منظور از تشخیص انجمن، یافتن انجمن‌هایی (زیرگراف‌هایی) است که با تعریف فوق برای انجمن هم‌خوانی داشته باشند. چنانچه شبکه مورد نظر با زمان تغییر نکند، مسئله تشخیص انجمن به‌صورت خوشه‌بندی گراف تعریف شده که یک مسئله کاملاً مطالعه‌شده است.

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

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

3-       پیشینه تحقیق

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

در دسته‌ای از روش‌های ارائه‌شده، رویکرد اتخاذشده شامل یک استراتژی بهینه‌سازی چندهدفه است؛ مثلاً [‌16]‌ تکنیک ترکیب احتمالاتی را به کار می‌گیرد و از دو رویکرد متمایز، یعنی تنوع همسایه و جمعیت همسایه استفاده می‌کند. این رویکردها تشکیل سریع و دقیق اجتماعات مناسب را تسهیل می‌کنند. همچنین استفاده از یک معیار پیشرفت به نویسندگان اجازه می‌دهد تا شباهت‌های بین انجمن‌های تشکیل‌شده در دو تصویر لحظه‌ای متوالی را شناسایی کنند.

در [‌17]‌، روشی برای تشخیص انجمن در شبکه‌های پویا بر اساس نفوذ ارائه شده است. این روش، مسئله را به عنوان یک مسئله بهینه‌سازی ترکیبی فرموله می‌کند که هدف آن، پارتیشن‌بندی یک شبکه اجتماعی معین به img0 انجمن مجزاست. هدف، بیشینه‌کردن مجموع انتشار نفوذ در شبکه اجتماعی با بیشینه‌کردن آن درون هر انجمن می‌باشد.

در [‌18]‌، روشی برای شناسایی انجمن‌ها در شبکه‌های پویا ارائه شد که بر اساس ردیابی ستون‌ فقرات‌ها و پل‌ها عمل می‌کند. آنها از «ستون‌های فقرات» برای نشان‌دادن یال‌های حیاتی انجمن‌ها و از یال‌های «پل» برای توصیف ارتباطات کلیدی بین انجمن‌ها استفاده کردند.

محققان در [‌19]‌ به بررسی مدل جدیدی برای شبکه‌های پویا به نام DynCRep می‌پردازند که در کنار ساختار انجمن‌ها از متغیرهای پنهان مبنی بر متقارن‌بودن روابط نیز برای تولید شبکه استفاده می‌کند. این مدل بر اساس یک فرایند مارکوف بنا شده که در آن، احتمال وجود یال بین دو گره در زمان img0 وابسته به زمان قبلی img0 است. روش پیشنهادی برای تشخیص انجمن، مدل تولیدی احتمالی با متغیرهای پنهان است که به طور همزمان از تقارن و عضویت در انجمن به عنوان اطلاعات ساختاری شبکه استفاده می‌کند. این مدل فرض می‌کند که وجود یک لینک بین دو رأس به طور شرطی وابسته به عضویت آن دو رأس در انجمن‌ها و همچنین وجود لینک متقارن در قدم زمانی قبل است. این مدل بر روی داده‌های مصنوعی و واقعی آزمایش شد و نتایج نشان داد که درک بهتری از متقارن‌بودن روابط دارد و عملکرد بهتری در پیش‌بینی پیوندهای آینده شبکه دارد.

یک روش جدید تشخیص انجمن با استفاده از شبکه‌های عصبی خودرمزنگار عمیق و الگوریتم جستجوی کلاغ در [‌20]‌ با نام CD-SACS پیشنهاد شده است. در این روش، ابتدا یک ماتریس مدولاریته برای گراف ورودی تولید می‌شود؛ سپس از طریق یک سری خودرمزنگار‌های پشته‌ای، بعد ماتریس مدولاریته کاهش داده می‌شود. این کاهش بعد باعث می‌شود تا توپولوژی شبکه حفظ شده و همچنین زمان محاسباتی بهبود یابد. سپس ماتریس کاهش‌یافته به عنوان ورودی به الگوریتم خوشه‌بندی img0 تغییریافته با استفاده از الگوریتم بهینه‌سازی جستجوی کلاغ داده می‌شود. این الگوریتم به جای تولید تصادفی مراکز اولیه خوشه‌ها 
از جستجوی کلاغ استفاده می‌کند تا مراکز خوشه‌ها را به‌صورت بهینه تولید کند.

نویسندگان در [‌21]‌ ابتدا گره‌های تأثیرگذار سراسری و محلی در شبکه را شناسایی کرده‌اند و سپس سعی نموده‌اند تا از بین گره‌های تأثیرگذار موجود، گره‌هایی را که فاقد همپوشانی هستند، شناسایی نموده و اقدام به شکل‌دادن انجمن‌ها نمایند.

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

محققان در [23]‌ مسئله تشخیص انجمن را از زاویه انتشار اطلاعات پویا بررسی نموده‌اند. این روش از یک مدل جدید به نام نفوذ گره3 برای ارزیابی تأثیر بین گره‌ها و انجمن‌ها میانی پیشنهاد نموده است. همچنین یک الگوریتم جدید به نام تجمع تودرتو از تأثیرات گره برای ادغام گره‌ها یا انجمن‌های میانی در مسیر صعودی پیشنهاد شده است. این روش از چهار معیار برای تعیین تأثیر گره و شش معیار شباهت برای دستیابی به معیار تأثیرپذیری استفاده‌ نموده است.

در ادامه به بررسی پژوهش‌های ارائه‌شده برای کشف انجمن در شبکه‌های پویا می‌پردازیم. در اغلب مطالعات، جهت کشف انجمن پویا از همان الگوریتم‌های ایستا استفاده می‌شود؛ در حالی که در هر بازه زمانی معین، یک تصویر لحظه‌ای از شبکه گرفته شده و الگوریتم ایستا روی آن اعمال می‌شود. در [24]‌ الگوریتمی به‌منظور تشخیص انجمن پویا مبتنی بر ماژولاریته با هدف شناسایی انجمن در شبکه‌های پویا توسط استفاده مکرر از الگوریتم‌های استاتیک، اما به روشی کارآمدتر ارائه شده است. این روش یک الگوریتم تطبیقی و افزایشی است که برای به حداکثر رساندن افزایشی ماژولاریته در حین به‌روزرسانی ساختار انجمن شبکه‌های پویا طراحی شده است. در این مقاله برای به‌روزرسانی ساختارهای انجمن، شبکه پویا به‌عنوان دنباله‌ای از تغییرات تدریجی شبکه مدل شده و برای هر تغییر تدریجی شبکه، عملیاتی برای به حداکثر رساندن ماژولاریتی طراحی شده است.

یک روش تشخیص انجمن همپوشانی احتمالی در [12]‌ ارائه شده است. این روش، وظیفه تشخیص انجمن را به‌عنوان یک مسئله فاکتورسازی ماتریس غیرمنفی در نظر می‌گیرد. روش پیشنهادی از یک مدل احتمالی برای کنترل پویایی ساختار انجمن و از روش مختصات بلوکی برای حل تابع هدف مدل فاکتورسازی ماتریس استفاده می‌نماید. این راهکار، عامل نهفته غیرمنفی را برای سرعت‌بخشیدن به محاسبه گرادیان‌ها تخمین می‌زند. نتایج به‌دست‌آمده نشان می‌دهند که روش پیشنهادی از نظر معیارهای ارزیابی شناخته‌شده از الگوریتم‌های قبلی در شبکه‌های در حال تکامل بهتر عمل می‌کند.

محققین در [25]‌ روشی را به نام DPC-DLP ارائه نمودند که از خوشه‌بندی قله تراکم برای یافتن مراکز انجمن و از انتشار برچسب برای تخصیص‌دادن برچسب‌ها به گره‌ها و تشکیل انجمن‌های نهایی استفاده نموده و قادر است به‌طور مؤثرتری برچسب‌های واقعی را به نمونه‌های داده‌ای که در مناطق مرزی و همپوشانی قرار دارند، اختصاص دهد. نتایج حاصل از آزمایش این روش، نشان از مناسب‌بودن عملکرد آن نسبت به سایر روش‌ها دارد.

یک روش جدید برای تشخیص انجمن با استفاده از الگوریتم ژنتیک در [26]‌ پیشنهاد شده و در آن در کنار عملگرهای ژنتیکی کلاسیک و سنتی، یک عملگر ژنتیکی مهاجرتی جدید ارائه شده است. این عملگر بر یک چارچوب تجزیه تکیه دارد و سعی می‌کند تا تشخیص انجمن تکاملی را به‌عنوان یک مسئله بهینه‌سازی چندهدفه فرموله کند. همچنین روشی سریع برای محاسبه معیار ماژولاریتی پیشنهاد شده که منجر به جستجوی سریع‌تر فضای مسئله به‌منظور یافتن راه‌حل بهینه می‌شود.

پژوهشگران در [27]‌، یک روش تشخیص انجمن تکاملی را پیشنهاد نموده‌اند که می‌تواند ساختارهای اجتماعی با کیفیت بالا را از شبکه‌های در حال تکامل در بازه‌های زمانی مختلف تشخیص دهد. هنگامی که شبکه تکامل می‌یابد، روش پیشنهادی فقط وابستگی‌های اجتماعی گره‌های جزئی را به‌طور مؤثر در نظر می‌گیرد که یا گره‌های تازه متولدشده 
یا برخی گره‌های فعال در زمان قبل هستند. سپس زیرگراف‌هایی برای این گره‌ها ساخته می‌شوند تا انجمن‌های اولیه به دست آیند. در نهایت نتیجه نهایی از تشخیص انجمن از طریق بهینه‌سازی انجمن‌های اولیه به دست می‌آید.

نویسندگان در [28]‌ یک روش بهینه‌سازی مدولاریتی محلی را فراهم می‌کنند که طی آن، تنها انجمن‌هایی که دچار تغییر شدند بررسی شده و سایر انجمن‌ها دست‌نخورده باقی می‌مانند. طبق ادعای مقاله، الگوریتم دارای اثربخشی مناسب‌تری نسبت به سایر الگوریتم‌های مشابه است.

با مرور مطالعات انجام‌شده می‌توان مسائل باز پژوهشی بسیاری را تعریف نمود. شناسایی انجمن یک مسئله NP-hard است. ذات پویابودن شبکه و وجود تصاویر مختلف از شبکه، نیازمند انجام محاسبات مجدد برای به‌روزکردن و یا ایجاد انجمن‌هاست؛ بنابراین به روش‌هایی نیاز است که تا حد امکان کم‌هزینه و سریع و به لحاظ محاسباتی ساده باشد. همچنین برای کشف انجمن در شبکه‌های پویا لازم است دو تصویر لحظه‌ای قبلی و فعلی با هم مورد مقایسه قرار گیرند. این مقایسه، اغلب زمان‌بر بوده و نیاز به محاسبات متوسط تا بالایی دارد. داشتن قوانین و یا روش‌هایی جهت تسریع این فرایند می‌تواند کلید موفقیت در کاهش سرعت الگوریتم‌های کشف انجمن در شبکه‌های پویا باشد. یکی از راهکارهای مناسب برای حل این مسئله موازی‌سازی است. موازی‌کردن محاسبات سبب افزایش سرعت الگوریتم می‌شود. به‌علاوه، اهمیت‌دادن به گره‌های رهبر و یا به عبارتی تأثیرگذار می‌تواند بستر تولید بسیاری از انجمن‌ها باشد. این موضوع در بسیاری از تحقیقات نادیده گرفته شده است. نهایتاً اغلب تحقیقات، موضوع همپوشانی انجمن‌ها را نادیده گرفته‌اند؛ بنابراین روش کارا برای حل مسئله بایستی به تمامی جوانب مسئله توجه نماید. در فصل آینده روشی کارا برای حل مسئله ارائه خواهد شد که به تمامی چالش‌های ذکرشده پاسخ خواهد داد.

4-       روش پیشنهادی

روش پیشنهادی دارای شش فاز اصلی می‌باشد که در ادامه هر فاز را شرح می‌دهیم.

1-4 دریافت تصویر لحظه‌ای از شبکه

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

مجموعه گره‌های موجود در تصویر جاری از شبکه در آرایه Current_Nodes ذخیره می‌شوند. برای ذخیره‌سازی یال‌ها نیز یک ماتریس img0 به نام Current_Edges خواهیم داشت که img0 برابر با تعداد یال‌ها و هر سطر شامل شناسه گره‌های تشکیل‌دهنده یال است.

2-4 انتخاب گره‌های تأثیرگذار بر اساس اطلاعات محلی و سراسری

در این مرحله در سه گام، بر اساس اطلاعات محلی و سراسری هر گره، اقدام به یافتن گره‌های تأثیرگذار می‌شود. در گام نخست به‌منظور شناسایی اطلاعات سراسری گره، ابتدا از الگوریتم تجزیه شبکه img0 استفاده می‌شود. به‌منظور محاسبه اهمیت گره‌ها در شبکه، معیارهای مختلفی وجود دارد، اما فقط درجه و ضریب خوشه‌بندی گره‌ها می‌تواند اطلاعات محلی شبکه‌ها را مشخص کند. img0 یک زیرگراف متصل حداکثر از گراف img0 است که در آن درجه هر رأس حداقل برابر با img0 است. مقدار img0 برای گره img0 که با img0 نشان داده می‌شود، نشان می‌دهد که گره img0 به پوسته img0 تعلق دارد اما به هیچ img0 پوسته دیگر تعلق ندارد. روش تجزیه img0، اغلب برای شناسایی گره هسته و گره‌های حاشیه‌ای شبکه استفاده می‌شود. این روش با حذف تمام گره‌هایی که تنها یک پیوند دارند، شروع می‌شود تا زمانی که هیچ گرهی باقی نماند و آن‌ها را به پوسته 1 اختصاص می‌دهد. به همین ترتیب به‌صورت بازگشتی تمام گره‌های با درجه ۲ (کمتر) را حذف می‌کند و پوسته ۲ را ایجاد می‌کند. این روند تا زمانی که تمام گره‌های شبکه 
به یک پوسته اختصاص داده شوند، ادامه پیدا می‌کند. پوسته‌هایی با شاخص‌های بالاتر در هسته یا مرکز شبکه قرار دارند. روش تجزیه img0 را می‌توان به‌طور مؤثر با پیچیدگی زمانی خطی img0 که در آن img0 تعداد یال‌ها در شبکه است، پیاده‌سازی‌کرد.

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

img0        (1)

پس از به دست آوردن اطلاعات سراسری گره‌ها، اقدام به اندازه‌گیری اطلاعات محلی می‌شود. برای اندازه‌گیری اطلاعات محلی نیز از تعداد همسایگی‌های هر گره استفاده می‌شود؛ بنابراین بر اساس (1) مقدار img0 که به معنای اطلاعات محلی گره img0ام می‌باشد، به دست می‌آید

img0 

شکل 1:  محاسبه تأثیر گره‌ها.

 

img0        (2)

در گام نهایی به‌منظور محاسبه نفوذ گره در شبکه، اطلاعات سراسری و محلی گره مطابق با (3) با هم ادغام می‌شود. در این رابطه img0 و img0 ضریب اطلاعات سراسری و اطلاعات محلی است

img0        (3)

گره‌هایی که میزان تأثیرگذاری بیشتری دارند، به‌عنوان مرکز انجمن در نظر گرفته می‌شوند. شبه‌کد مربوط به الگوریتم این فاز در شکل 1 آمده است.

3-4 راه‌اندازی انجمن‌های اولیه

با توجه به فاز دوم، فهرست تأثیر گره‌‌ها به‌دست‌آمده و گره‌‌های موجود در لیست رتبه‌‌بندی به ترتیب نزولی مرتب می‌‌شوند. در گام بعد، img0 گره‌‌ دارای نفوذ بالاتر به‌‌عنوان مراکز انجمن‌‌ها در نظر گرفته می‌‌شوند. از بین گره‌‌های باقی‌مانده در شبکه، گره‌‌هایی که یک لینک مستقیم به گره‌‌های مرکز خوشه دارند، انجمن را تشکیل می‌‌دهند. در صورتی که دو مرکز انجمن دارای یال مستقیم به هم باشند، از این یال صرف نظر می‌‌شود و این دو در انجمن‌‌های یکدیگری قرار نمی‌‌گیرند.

4-4 توسعه انجمن‌‌ها

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

img0        (4)

که img0 تعداد همسایگان گره img0 برای خوشه img0ام را نشان می‌‌دهد. در صورتی که گره حاوی همسایگانی باشد که هنوز خوشه به آنها اختصاص داده نشده باشد، آن همسایگان در رابطه فوق نادیده گرفته می‌‌شوند. شکل 2 مراحل مربوط به ایجاد و توسعه انجمن‌‌ها را بیان می‌‌نماید. در خط 1 از شکل 2، گره‌‌ها بر اساس میزان نفوذشان مرتب می‌‌شوند. در خط 2، img0 گره که دارای نفوذ بیشتر است به‌عنوان سرخوشه انتخاب و در یک لیست به نام ClusterHead که وظیفه نگهداری مراکز انجمن را دارد، ذخیره می‌‌شوند. در خط 3 به‌‌منظور مدیریت بهتر گره‌‌ها برای توسعه انجمن، یک لیست به نام Candidate ایجاد می‌‌شود. این لیست وظیفه نگهداری گره‌‌هایی را بر عهده دارد که حداقل یکی از همسایگی‌‌های آن دارای انجمن باشد. بدین ترتیب مطمئن می‌‌شویم  که  گره‌‌هایی  برای  تعمیم  انجمن ‌‌ انتخاب  می‌‌شود  که  حتماً  دارای 

img0 

شکل 2:  الگوریتم ایجاد و توسعه انجمن.

 

یک همسایگی دارای خوشه باشند و در غیر این صورت گره به هیچ انجمنی تعلق نخواهد داشت. لذا در خط 3، همه همسایگان مراکز خوشه به Candidate ملحق می‌‌شوند. سپس یک لیست دیگر نیز با نام assign_Nodes تشکیل شده که وظیفه آن نگهداری گره‌‌هایی است که به عضویت حداقل یک انجمن درآمده باشند (خط 4). در ادامه، تمام نقاطی که به‌عنوان سرخوشه انتخاب شدند، به این اضافه می‌‌شوند تا دوباره در فرایند خوشه‌‌بندی ظاهر نشوند. در خط 5 به ترتیب قرارگیری گره‌‌ها، اولین گره مانند img0 انتخاب می‌‌شود. در خط 6 یک متغیر به نام flag مقداردهی می‌‌شود تا در صورتی که گره، همسایه یکی از مراکز انجمن باشد، شناسایی شود. در خط 7 برای هر مرکز انجمن، چک می‌‌شود که آیا گره img0 همسایگی آن است یا خیر. در صورتی که گره img0 همسایه آن مرکز انجمن باشد، گره img0 به آن انجمن ملحق می‌‌شود و مقدار flag نیز true می‌‌شود (خط 7 تا 12). در صورتی که گره img0 همسایه هیچ یک از مراکز انجمن نباشد، با استفاده از (4)، مقدار وابستگی به انجمن محاسبه شده و نهایتاً به انجمن‌‌های ممکن ملحق می‌‌شود 
(خط 13 تا 18). سپس تمام همسایگی‌‌های گره img0 در صورتی که فاقد انجمن باشند، به لیست Candidate اضافه می‌‌شوند و گره img0 نیز به assign_Nodes اضافه می‌‌شود تا دیگر در فرایند ایجاد انجمن ظاهر نگردد (خط 19 تا 24). نهایتاً این روند تا زمانی که لیست Candidate دارای  یک  عضو  باشد  ادامه  می‌‌یابد.  در  خط  26  تا  30  نیز  وجود  پراکندگی 

img0 

شکل 3:  گراف مثال.

 

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

5-4 ارزیابی و ادغام انجمن‌ها

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

img0        (5)

هرچه img0 بزرگ‌‌تر باشد، گره‌‌های بیشتری در بین انجمن‌‌های دارای همپوشانی دارند و در نتیجه دو انجمن مستعد ادغام‌شدن هستند. با این حال در دنیای واقعی این امکان وجود دارد که دو انجمن، دارای همپوشانی بالا باشند؛ اما به دلایلی همچون موضوع انجمن، امکان ادغام آن دو موجود نداشته باشد؛ بنابراین در این مقاله علاوه بر معیار فوق از معیار دیگری به نام برازندگی انجمن نیز استفاده می‌‌شود. معیار برازندگی انجمن به اهمیت انجمن در شبکه اشاره دارد و طبق (6) محاسبه می‌‌شود

img0        (6)

img0        (7)

img0        (8)

که img0 تراکم انجمن را مشخص می‌کند و بر اساس نسبت اعضای انجمن به کل گره‌های موجود در شبکه محاسبه می‌شود. totalNodes نشان‌دهنده تمام گره‌های موجود در شبکه است و همچنین img0 نسبت گره‌هایی است که تنها در انجمن img0 وجود دارند (در انجمن‌های دیگر عضو نیستند) به کل گره‌های موجود در انجمن img0. بدین ترتیب انجمن‌هایی که بتوانند مقدار برازندگی بیش از حد آستانه را کسب کنند، ماندگار می‌شوند؛ در غیر این صورت با انجمن دیگر ادغام می‌شود. به عبارت  بهتر  در  مورد  معیار  برازندگی،  هرچه  این  مقدار  کمتر  باشد،  احتمال 

جدول 1: نمایش میزان img0 برای هر لایه.

 

گره

Shell

لیست همسایگان

اطلاعات سراسری

اطلاعات محلی

1

2

2 و 3

67/1

2

2

2

1، 3 و 8

2

3

3

3

1، 2، 4، 5، 6 و 7

5

6

4

3

3، 6 و 7

3

3

5

2

3 و 6

2

2

6

3

3، 4، 5، 7 و 9

3333/5

5

7

3

3، 4، 6 و 9

7

4

8

1

2

67/0

1

9

2

6 و 7

2

2

 

ادغام‌شدن خوشه بیشتر است. به‌منظور ادغام دو خوشه، گرهی که میزان نفوذ بیشتری داشته به‌عنوان سرخوشه انتخاب شده و تمام اعضای هر دو خوشه به همراه مرکز خوشه دیگر به‌عنوان اعضای آن شناخته می‌شوند.

6-4 به‌روزرسانی انجمن‌ها

این فاز خود شامل چهار گام است که عبارتند از دریافت تصویر جدید و شناسایی تغییرات، تغییرات در انجمن‌‌ها، بررسی انجمن‌‌ها، تعیین انجمن برای گره‌‌های فاقد انجمن و ارزیابی و ادغام انجمن‌‌ها. در ادامه هر یک از گام‌‌ها تشریح می‌‌شوند.

در گام اول، یک تصویر لحظه‌‌ای دیگر از شبکه دریافت می‌‌شود و بر اساس انجمن‌‌های موجود اقدام به به‌‌روزکردن انجمن‌‌ها می‌‌شود. برای به‌روز‌‌رسانی انجمن‌‌ها با در نظر گرفتن اینکه img0 زمان جاری شبکه باشد، باید تغییرات صورت‌گرفته در شبکه در زمان img0 نسبت به زمان img0 (شبکه قبلی) را مشخص کرد. تغییرات شبکه می‌‌تواند شامل اضافه‌‌شدن یا حذف یک گره به/ از شبکه و یا اضافه/ حذف شدن یال به/ از شبکه باشد. فرض کنید گره‌‌های تعیین‌شده در شبکه قبل در لیست Current_Node و لبه‌های مربوط به آن در لیست current_Edge قرار گرفته باشد.

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

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

در گام پایانی نیز عملیات ارزیابی میزان همپوشانی و برازندگی گره‌‌ها تعیین و مشخص می‌‌شود و در صورت نیاز انجمن‌‌ها با هم ادغام می‌‌گردند. در فصل آینده در خصوص کارایی روش پیشنهادی به‌صورت مفصل بحث خواهیم نمود.

7-4 مثال از روش پیشنهادی

برای درک روش پیشنهادی مثال ساده‌‌ای ارائه می‌‌نماییم. گراف موجود در  شکل  3  را  در  نظر  بگیرید.  در  جدول  1  با  توجه  به  روابط  ذکرشده  در 

img0 

(الف)

img0 

(ب)

شکل 4:  محاسبات انجام‌شده برای تعیین اطلاعات سراسری برای گره‌های (الف) 1 و (ب) 2 گراف مثال شکل 3. (در متن ارجاع ندارد)

 

جدول 2: نمایش میزان نفوذ برای گره‌های گراف مثال شکل 4.

 

نام گره

میزان نفوذ

3

5/5

7

5/5

6

1665/5

4

3

2

5/2

5

2

9

2

1

835/1

8

835/0

 

بخش 4-2، اطلاعات سراسری و محلی هر گره و در نتیجه میزان نفوذ گره مشخص می‌‌شود.

در شکل 5 محاسبات مربوط به img0 برای گره‌های 1 و 2 آمده و برای سایر گره‌ها نیز به همین صورت محاسبه انجام گرفته است. همان طور که بیان شد، اطلاعات محلی img0 نیز برابر با تعداد همسایگان گره img0 است. در ادامه، میزان نفوذ هر یک از گره‌ها با توجه به اطلاعات موجود در جدول 2 و (4) با مقدار img0 محاسبه می‌شود. بعد از مرتب‌سازی گره‌ها بر اساس میزان نفوذ با فرض اینکه مقدار img0 باشد، گره‌های 7 و 3 به عنوان مرکز خوشه انتخاب می‌شوند. جدول 2 ترتیب گره‌ها بر اساس میزان نفوذ را نشان می‌دهد.

شکل 5، انجمن‌های متشکل از این مراکز خوشه را نشان می‌دهد. در این شکل گره‌های 1، 2 و 5 به خوشه حاصل از گره 3 و گره 9 به مرکز خوشه 7 تعلق دارد. دو گره 4 و 6 هم به هر دو خوشه تعلق دارند. تنها گرهی که هنوز بدون خوشه است، گره 8 است. تنها همسایه گره 8، گره 2 است که قبلاً به خوشه حاصل از گره 3 ملحق شده است؛ لذا گره 8 نیز به این خوشه ملحق می‌شود. شکل 6 انجمن‌های نهایی برای گراف مثال را نشان می‌دهد.

img0 

شکل 5:  انجمن‌های اولیه برای گراف مثال شکل 3.

 

img0 

شکل 6:  انجمن‌های نهایی برای گراف مثال شکل 3.

 

با توجه به گراف مثال و انجمن‌های تولیدشده، میزان نرخ همپوشانی img0 برای دو انجمن با توجه به (5) برابر خواهد بود با

img0        (9)

بر اساس (6) تا (8) مقدار معیار برازندگی برای دو انجمن به‌صورت زیر محاسبه شده است

img0        (10)

برای خوشه حاصل از گره 3

img0        (11)

img0        (12)

برای خوشه حاصل از گره 7

img0        (13)

img0        (14)

img0        (15)

با توجه به این نتایج، میزان همپوشانی برای دو خوشه 5/0 به دست آمده که با در نظر گرفتن مقدار آستانه 75/0 برآورده نمی‌شود. اگر مقدار به‌دست‌آمده، بیشتر از آستانه بود، دو خوشه می‌توانستند با هم ادغام گردند. علاوه بر این، مقدار برازندگی برای خوشه حاصل از گره 3، 75/0 و برای 

[1] این مقاله در تاریخ 19 مرداد ماه 1403 دریافت و در تاریخ 28 بهمن ماه 1402 بازنگری شد.

مصطفي سبزه‌کار (نویسنده مسئول)، گروه مهندسی کامپیوتر، دانشگاه صنعتی بیرجند، بیرجند، ایران، (email: sabzekar@birjandut.ac.ir).

شیما برادران‌نژاد، گروه مهندسی کامپیوتر، دانشگاه آزاد اسلامی، واحد بیرجند، بیرجند،  ایران، (email: shima.baradaran2005@gmail.com).

مهدی خزاعی‌پور، گروه مهندسی کامپیوتر، دانشگاه آزاد اسلامی، واحد بیرجند، بیرجند، ایران، (email: mkhazaeipoor@iaubir.ac.ir).

مهدی خرد، گروه مهندسی کامپیوتر، دانشگاه قم، قم، ایران،
(email: m.kherad@stu.qom.ac.ir).

[2] . Seed

[3] . Node Influence

جدول 3: مجموعه داده مورد استفاده در پیاده‌سازی.

 

نام مجموعه داده

تعداد رئوس

تعداد یال‌ها

نوع روابط

تعداد تصاویر لحظه‌ای

Cit-Hep Ph [‌29]

34546

421578

ارجاع به هم

11

sx-mathoverflow [30]‌

24818

506550

نظردادن روی سؤال و روی پاسخ

8

CollegeMsg [31]‌

1899

59835

ارسال پیام خصوصی به هم

7

 

 

خوشه حاصل از گره 7، مقدار 45/0 بوده است. اگر مقدار آستانه را 5/0 در نظر بگیریم، خوشه حاصل از گره 7 مقدار برازندگی کمتر از 5/0 را به دست آورده است؛ پس امکان ادغام دو خوشه با هم وجود دارد. اما با توجه به اینکه میزان همپوشانی نتوانسته است آستانه 75/0 را برآورده کند، فرایند ادغام منتفی می‌شود.

8-4 قابلیت موازی‌سازی

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

•        موازی‌سازی مرحله حذف گره: در این روش، گره‌ها به طور همزمان در چندین پردازنده حذف می‌شوند. این روش می‌تواند به طور قابل توجهی زمان اجرای الگوریتم را برای شبکه‌های بزرگ کاهش دهد.

•        موازی‌سازی محاسبه درجه گره: در این روش، درجه گره‌ها به طور همزمان در چندین پردازنده محاسبه می‌شود.

•        موازی‌سازی مراحل تکرار: در این روش، مراحل تکرار الگوریتم img0 به طور همزمان در چندین پردازنده اجرا می‌شوند.

5-       پیاده‌سازی و ارزیابی‌

در این بخش به پیاده‌سازی و ارزیابی الگوریتم پیشنهادی پرداخته شده و برای پیاده‌سازی از زبان برنامه‌نویسی پایتون استفاده گردیده است. برای ارزیابی عملکرد الگوریتم پیشنهادی، آن را با پنج روش اخیراً ارائه‌شده در [28]، [27]، [25]، [19] و [20] مقایسه نموده‌ایم. در ادامه، مجموعه‌ داده‌های استفاده‌شده بررسی می‌‌گردد و سپس معیارهای ارزیابی معرفی شده و نتایج حاصل از این معیارها برای روش پیشنهادی و الگوریتم‌های مورد مقایسه بر روی مجموعه داده‌های معرفی‌شده ارائه می‌شود.

1-5 معرفی مجموعه داده‌ها

جهت اجرا، ابتدا مجموعه داده‌های مرتبط فراخوانی می‌شوند. مجموعه داده‌های مورد استفاده در این مقاله در جدول 3 آمده است.

مجموعه داده Cit-Hep Ph دارای 30501 رأس و 346742 یال است. در این مقاله بر اساس سال، تصاویر لحظه‌ای استخراج شدند و از این رو 11 تصویر لحظه‌ای استخراج شده است. هر تصویر لحظه‌ای شامل گره‌های همان سال به همراه گره‌های مربوط به سال قبل از آن است. مثلاً برای سال 1999، گره‌ها و یال‌های مربوط به سال 1999 و 1998 استخراج و استفاده می‌شوند. بدین ترتیب هم حذف و هم اضافه شده یال‌ها مورد بررسی قرار می‌گیرد.

مجموعه داده sx-mathoverflow شامل شبکه‌ای موقتی از تعاملات در وب‌سایت تبادل اطلاعات MathOverflow است. سه نوع مختلف از تعاملات شامل پاسخ‌دادن، نظردادن روی سؤال و نظردادن روی پاسخ وجود دارد. این مجموعه داده 24818 گره و 506550 یال دارد که طی 2350 روز جمع‌آوری شده است. در این پژوهش، این مجموعه داده بر اساس سال از هم جدا شده و نهایتاً شامل 8 بازه زمانی مختلف است که در هر بازه زمانی، اطلاعات مربوط به سال جاری و سال قبل آمده است.

مجموعه CollegeMsg شامل پیام‌های خصوصی ارسال‌شده در یک شبکه اجتماعی آنلاین در دانشگاه کالیفرنیا است و 1899 گره و 59835 یال دارد. در این مقاله، سال به عنوان جداکننده در نظر گرفته شده و بدین ترتیب 7 بازه زمانی مختلف مشخص شده است.

2-5 معیارهای ارزیابی

معیارهای ارزیابی مورد استفاده در این مقاله عبارتند از مدولاریتی نیومن1، مدولاریتی با جریمه تقسیم2 و مدولاریتی چگالی3. مدولاریتی نیومن برای شبکه‌های بدون وزن و بدون جهت، این نوع مدولاریتی به‌عنوان نسبت تفاوت بین تعداد واقعی و مورد انتظار یال‌ها در انجمن‌ تعریف می‌شود که در (16) نشان داده شده است

img0        (16)

در این رابطه img0 مجموعه همه انجمن‌ها، img0 انجمن img0ام، img0 تعداد یال‌های درون انجمن، img0 تعداد یال‌های خارج از انجمن و img0 نیز نشان‌دهنده کل یال‌های موجود در شبکه است. هرچه مقدار این معیار بیشتر باشد، به معنای مناسب‌بودن انجمن‌هاست. بایستی توجه داشت که در شبکه‌های اجتماعی به دلیل پیچیده‌بودن ارتباطات و امکان وجود ارتباط بین هر دو یال، مقدار مناسب مدولاریتی حدود 5/0 در نظر گرفته می‌شود. یعنی در صورتی که مقدار این معیار حدود 5/0 باشد، به معنای مناسب‌بودن وضعیت انجمن‌ها در شبکه اجتماعی است.

معیار مدولاریتی با جریمه‌ تقسیم، یکی دیگر از معیارهای ارزیابی انجمن است و برای بررسی کیفیت ساختار انجمن‌ استفاده می‌شود. مدولاریتی با جریمه تقسیم img0 بر اساس (17) به دست می‌آید. در این رابطه، img0 میزان مدولاریتی و img0 تعداد لبه‌های مشترک بین انجمن‌ها است و بر اساس (18) محاسبه می‌گردد

img0        (17)

img0        (18)

که در (16)، img0 تعداد لبه‌هایی است که از انجمن img0 به img0 امتداد یافتند. در این معیار نیز هرچه مقدار به‌دست‌آمده بیشتر باشد، نشان‌دهنده مناسب‌تربودن ساختار انجمن‌هاست.

 

[1] . Newman's Modularity

[2] . Modularity with Split Penalty

[3] . Modularity Density

جدول 4: مقایسه نتایج به‌دست‌آمده با معیار مدولاریتی نیومن برای مجموعه داده cit-Hep Ph.

 

روش پیشنهادی

CD-SACS

DynCRep

louvain

IncNSA

DPC-DLP

برچسب زمانی

6550/0

5926/0

6058/0

6289/0

5389/0

5777/0

1

0882/0

0712/0

0819/0

0839/0

0870/0

0590/0

2

0404/0

0681/0

0480/0

0366/0

0340/0

0619/0

3

0229/0

0192/0

0148/0

0173/0

0155/0

0168/0

4

0124/0

0136/0

0119/0

0058/0

0108/0

0153/0

5

0118/0

0122/0

0108/0

0051/0

0115/0

0107/0

6

1994/0

1742/0

1475/0

1115/0

1231/0

1181/0

7

2185/0

2172/0

2048/0

2015/0

2115/0

2091/0

8

3748/0

3271/0

2843/0

2236/0

2380/0

2925/0

9

4059/0

3782/0

2942/0

1037/0

3653/0

3519/0

10

4121/0

3250/0

2791/0

2255/0

3035/0

2523/0

11

2219/0

1999/0

1803/0

1494/0

1762/0

1785/0

میانگین

 

جدول 5: مقایسه نتایج به‌دست‌آمده با معیار مدولاریتی نیومن برای مجموعه داده CollegeMsg.

 

روش پیشنهادی

CD-SACS

DynCRep

louvain

IncNSA

DPC-DLP

برچسب زمانی

۳۸۰۵/0

۳۳۷۵/0

۳۴۴۶/0

۳۲۹۸/0

۲۷۸۶/0

۳۵۴۰/0

1

۱۴۶۲/0

۱۳۹۰/0

۱۲۵۵/0

۱۴۹۰/0

۱۲۹۲/0

۱۰۸۶/0

2

۴۹۴۷/0

۴۸۱۲/0

۴۵۷۶/0

۴۷۷۴/0

۳۷۸۵/0

۳۵۹۰/0

3

۲۵۳۳/0

۲۴۸۱/0

۲۳۹۷/0

۲۴۴۹/0

۲۴۵۳/0

۲۱۰۳/0

4

۱۳۷۹/0

۱۲۰۸/0

۱۱۹۲/0

۱۱۷۹/0

۱۰۴۴/0

۱۰۸۱/0

5

۱۶۷۵/0

۱۵۱۹/0

۱۵۰۲/0

۱۵۰۵/0

۱۷۱۲/0

۱۵۴۹/0

6

۲۸۸۶/0

۲۷۵۴/0

۲۲۴۸/0

۲۰۶۶/0

۲۳۸۷/0

۲۳۹۰/0

7

۲۶۷۰/0

۲۵۰۶/0

۲۳۷۴/0

۲۳۹۴/0

۲۲۰۸/0

۲۱۹۱/0

میانگین

 

جدول 6: مقایسه نتایج به‌دست‌آمده با معیار مدولاریتی نیومن برای مجموعه داده sx-mathoverflow.

 

روش پیشنهادی

CD-SACS

DynCRep

louvain

IncNSA

DPC-DLP

برچسب زمانی

۲۴۲۷/0

۲۲۱۲/0

۲۰۱۹/0

۲۱۴۳/0

۲۰۹۰/0

۱۵۱۲/0

1

۰۰۰۲/0

۰۱۵۷/0

۰۰۸۴/0

۰۶۸۴/0

۰۰۱۰/0

۰۵۷۲/0

2

۰۰۰۵/0

۱۷۴۱/0

۱۸۹۲/0

۲۱۸۱/0

۲۱۳۵/0

۱۶۰۱/0

3

۰۰۱۸/0

۰۱۶۲/0

۱۲۸۶/0

۰۰۴۴/0

۰۸۴۹/0

۱۱۴۴/0

4

۱۰۰۱/0

۰۸۴۶/0

۰۶۲۷/0

۰۵۴۱/0

۰۴۹۳/0

۰۶۲۱/0

5

۱۱۸۱/0

۱۰۱۲/0

۰۹۷۵/0

۰۹۶۰/0

۱۰۶۶/0

۱۰۴۲/0

6

۱۲۴۹/0

۱۱۰۸/0

۰۹۱۶/0

۰۷۱۷/0

۱۱۱۶/0

۰۶۱۹/0

7

۱۱۰۹/0

۰۹۴۲/0

۰۸۹۱/0

۰۱۶۴/0

۱۰۸۳/0

۱۰۲۰/0

8

۰۸۷۴/0

۱۰۲۳/0

۱۰۸۶/0

۰۹۲۹/0

۱۱۰۵/0

۱۰۱۶/0

میانگین

 

 

هم مدولاریت نیومن img0 و هم مدولاریت با جریمه تقسیم img0 مستقل از تعداد گره‌ها در انجمن‌ها هستند. مدولاریتی چگالی، گره‌ها و تراکم آنها در انجمن‌ها را نیز مورد بررسی قرار می‌دهد. برای شبکه‌های بدون جهت، چگالی مدولاریته img0 به‌صورت (19) تعریف می‌شود

img0        (19)

که img0 تراکم داخلی خوشه img0 و img0 تراکم بین دو انجمن img0 و img0 بوده و با استفاده از (20) محاسبه می‌شود

img0        (20)

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

3-5 نتایج آزمایش‌ها

جداول 4 تا 6 نشان‌دهنده نتایج حاصل از معیار مدولاریتی نیومن برای روش‌های مورد مقایسه روی مجموعه داده‌های مختلف می‌باشد.

طبق نتایج جدول 4، روش پیشنهادی در مجموعه داده cit-Hep Ph، در 8 بازه زمانی از 11 بازه زمانی و همچنین به طور میانگین بهترین مقدار معیار مدولاریتی نیومن را نسبت به بقیه روش‌ها دارد و فقط در بازه‌های زمانی 3، 5 و 6 دو روش CD-SACS و DPC-DLP بهترین مقدار را 

جدول 7: مقایسه نتایج به‌دست‌آمده با معیار مدولاریتی با جریمه تقسیم برای مجموعه داده cit-Hep Ph.

 

روش پیشنهادی

CD-SACS

DynCRep

louvain

IncNSA

DPC-DLP

برچسب زمانی

1962/0

1452/0

1309/0

1207/0

1952/0

1305/0

1

4335/0

4419/0

4227/0

4373/0

4124/0

4565/0

2

4663/0

4726/0

4542/0

4695/0

4260/0

4277/0

3

4882/0

4591/0

4029/0

4859/0

3847/0

3837/0

4

4896/0

4783/0

4669/0

4951/0

3882/0

4749/0

5

4900/0

4805/0

4572/0

4856/0

4500/0

4621/0

6

1438/0

1511/0

1484/0

1048/0

1016/0

1341/0

7

4929/0

4891/0

5008/0

4987/0

4227/0

3953/0

8

4911/0

4758/0

4662/0

4868/0

4462/0

4657/0

9

4911/0

4749/0

4671/0

4867/0

4469/0

3982/0

10

1537/0

1732/0

1412/0

0156/0

1314/0

0962/0

11

3942/0

3856/0

3690/0

3715/0

3459/0

3477/0

میانگین

 

جدول 8: مقایسه نتایج به‌دست‌آمده با معیار مدولاریتی با جریمه تقسیم برای مجموعه داده CollegeMsg.

 

روش پیشنهادی

CD-SACS

DynCRep

louvain

IncNSA

DPC-DLP

برچسب زمانی

۴۹۹۲/0

۴۷۷۲/0

۴۵۲۹/0

۴۹۱۸/0

۳۹۹۵/0

۳۹۹۵/0

1

۵۰۱۰/0

۴۹۳۱/0

۴۶۹۷/0

۵۰۰۷/0

۴۹۰۴/0

۴۱۵۸/0

2

۴۹۹۸/0

۴۸۱۶/0

۴۶۵۳/0

۳۹۹۲/0

۴۳۰۷/0

۴۸۴۵/0

3

۴۹۸۸/0

۵۰۴۲/0

۴۷۶۸/0

۴۹۹۳/0

۳۲۴۵/0

۴۲۴۵/0

4

۰۴۰۸/0

۰۴۱۱/0

۰۳۵۹/0

۰۴۸۵/0

۰۳۴۴/0

۰۱۱۷/0

5

۰۷۴۶/0

۰۵۸۲/0

۰۴۵۳/0

۰۵۴۴/0

۰۳۳۹/0

۰۳۸۱/0

6

۰۶۸۶/0

۰۵۹۱/0

۰۵۰۴/0

۰۵۸۸/0

۱۳۶۳/0

۱۳۲۱/0

7

۳۱۱۸/0

۳۰۲۱/0

۲۸۵۲/0

۲۹۳۲/0

۲۶۴۲/0

۲۷۲۳/0

میانگین

 

جدول 9: مقایسه نتایج به‌دست‌آمده با معیار مدولاریتی با جریمه تقسیم برای مجموعه داده sx-mathoverflow.

 

روش پیشنهادی

CD-SACS

DynCRep

louvain

IncNSA

DPC-DLP

برچسب زمانی

۵۶۶۱/0

۴۵۹۳/0

۳۳۴۶/0

۱۸۲۹/0

۲۷۲۲/0

۳۲۶۸/0

1

۰۰۰۲/0

۱۲۸۸/0

۰۵۷۳/0

۰۰۰۲/0

۰۴۱۷/0

۱۲۱۲/0

2

۰۰۰۵/0

۰۰۰۵/0

۰۰۰۳/0

۰۰۰۸/0

۰۰۰۴/0

۰۰۰۵/0

3

۰۰۱۸/0

۰۰۲۵/0

۰۰۴۷/0

۰۰۳۱/0

۰۰۱۳/0

۰۰۱۲/0

4

۱۷۵۰/0

۱۶۶۸/0

۱۵۴۸/0

۱۳۲۱/0

۱۵۹۰/0

۱۶۰۰/0

5

۲۰۸۰/0

۱۹۰۶/0

۱۶۱۲/0

۰۱۰۱/0

۱۷۴۷/0

۱۰۹۰/0

6

۱۵۷۷/0

۱۳۶۲/0

۱۵۴۹/0

۰۱۴۶/0

۱۳۹۳/0

۰۱۸۸/0

7

۰۱۰۹/0

۰۱۰۵/0

۰۰۹۴/0

۰۱۰۴/0

۰۰۲۳/0

۰۱۰۴/0

8

۱۴۰۰/0

۱۳۶۹/0

۱۰۹۷/0

۰۴۴۳/0

۰۹۸۹/0

۰۹۳۵/0

میانگین

 

 

دارند که به دلیل تعداد تغییرات متفاوت (حذف و اضافه شدن یال‌ها و نودها) در بازه‌های زمانی مختلف است. به طور میانگین بعد از روش پیشنهادی، روش‌های CD-SACS و DynCRep بهترین مقدار معیار مدولاریتی نیومن در مجموعه داده cit-Hep Ph را به دست آورده‌اند. بر اساس نتایج جدول 5، روش پیشنهادی در مجموعه داده CollegeMsg در شش بازه زمانی و به طور میانگین بهترین مقدار معیار مدولاریتی نیومن را نسبت به بقیه روش‌ها دارد و فقط در بازه‌ زمانی دو، روش louvain بهترین مقدار را دارد که اختلاف آن با روش پیشنهادی خیلی اندک و قابل قبول است. به طور میانگین بعد از روش پیشنهادی، روش‌های CD-SACS و louvain بهترین مقدار معیار مدولاریتی نیومن در مجموعه داده CollegeMsg را به دست آورده‌اند. بر اساس نتایج جدول 6، روش پیشنهادی در مجموعه داده sx-mathoverflow در 5 بازه زمانی از هشت بازه بهترین مقدار معیار مدولاریتی نیومن را نسبت به بقیه روش‌ها دارد و در سه بازه‌ زمانی 2، 3 و 4 روش‌های Louvain و DynCRep بهترین مقدار را دارند که به دلیل تعداد کم تغییرات یال‌ها و نودها در این بازه‌های زمانی است. به طور میانگین، روش‌های IncNSA، DynCRep و CD-SACS بهترین مقدار معیار مدولاریتی نیومن در مجموعه داده sx-mathoverflow را به دست آورده‌اند. همان طور که مشاهده می‌شود، طبق نتایج به‌دست‌آمده از جداول 4 تا 6، روش پیشنهادی در اکثر بازه‌های زمانی هر مجموعه داده‌،‌ عملکرد بهتری نسبت به سایر روش‌ها‌ی مورد مقایسه داشته است.

نتایج به‌دست‌آمده برای معیار مدولاریتی با جریمه تقسیم به تفکیک مجموعه داده در جداول 7 تا 9 آمده است.

طبق نتایج جدول 7، روش پیشنهادی در مجموعه داده cit-Hep Ph، در 5 بازه زمانی و همچنین به طور میانگین بهترین مقدار معیار مدولاریتی با جریمه تقسیم را نسبت به بقیه روش‌ها دارد. به طور میانگین بعد از 

جدول 10: مقایسه نتایج به‌دست‌آمده با معیار مدولاریتی چگالی برای مجموعه داده cit-Hep Ph.

 

روش پیشنهادی

CD-SACS

DynCRep

louvain

IncNSA

DPC-DLP

برچسب زمانی

۵۱۳۵/0

۴۶۷۹/0

۴۶۳۱/0

۴۷۴۰/0

۴۷۹۶/0

۴۷۲۴/0

1

۰۷۰۸/0

۰۷۹۲/0

۰۷۲۱/0

۰۶۴۷/0

۱۴۰۳/0

۱۹۷۲/0

2

۰۹۵۱/0

۱۳۱۷/0

۱۰۲۱/0

۰۳۰۸/0

۰۶۰۹/0

۱۲۸۴/0

3

۱۲۱۰/0

۱۱۶۵/0

۰۸۵۹/0

۰۱۵۳/0

۱۰۸۶/0

۱۱۸۳/0

4

۱۱۱۸/0

۱۲۴۲/0

۱۰۷۸/0

۰۰۵۱/0

۰۵۹۰/0

۰۶۳۲/0

5

۱۲۸۱/0

۱۱۴۶/0

۰۷۶۳/0

۰۰۱۰/0

۱۲۶۱/0

۰۵۸۶/0

6

۲۵۷۷/0

۲۲۵۹/0

۱۹۴۶/0

۱۸۱۳/0

۱۵۰۵/0

۲۳۹۴/0

7

۱۶۷۹/0

۱۵۳۷/0

۱۴۱۹/0

۱۰۰۹/0

۱۴۱۲/0

۱۴۶۶/0

8

۲۰۸۲/0

۱۹۳۷/0

۱۴۵۳/0

۱۰۱۲/0

۰۴۳۳/0

۰۷۰۶/0

9

۲۱۰۰/0

۱۷۶۲/0

۱۴۶۷/0

۱۰۳۲/0

۱۰۰۱/0

۱۳۱۷/0

10

۲۲۳۳/0

۲۰۵۹/0

۱۸۴۸/0

۱۳۳۴/0

۲۱۶۵/0

۱۶۹۰/0

11

۱۹۱۶/0

۱۸۰۹/0

۱۵۶۴/0

۱۱۰۱/0

۱۴۷۸/0

۱۶۳۲/0

میانگین

 

جدول 11: مقایسه نتایج به‌دست‌آمده با معیار مدولاریتی چگالی برای مجموعه داده CollegeMsg.

 

روش پیشنهادی

CD-SACS

DynCRep

louvain

IncNSA

DPC-DLP

برچسب زمانی

۲۰۰۲/0

۱۹۸۳/0

۱۸۲۰/0

۲۱۹۵/0

۱۸۶۸/0

۱۷۰۶/0

1

۰۰۳۰/0

۰۰۱۹/0

۰۰۱۷/0

۰۰۰۷/0

۰۰۰۸/0

۰۰۰۲/0

2

۰۰۲۱/0

۰۰۱۵/0

۰۰۱۴/0

۰۰۰۵/0

۰۰۰۵/0

۰۰۰۱/0

3

۰۰۰۸/0

۰۰۰۵/0

۰۰۰۵/0

۰۰۰۲/0

۰۰۰۲/0

۰۰۰۵/0

4

۳۳۹۳/0

۳۶۷۲/0

۳۵۱۳/0

۳۷۳۸/0

۱۹۰۸/0

۲۴۳۵/0

5

۲۰۸۱/0

۱۸۷۵/0

۱۵۴۶/0

۱۲۹۵/0

۱۲۰۱/0

۱۲۵۸/0

6

۲۸۶۹/0

۲۵۶۱/0

۲۲۲۷/0

۲۰۶۲/0

۲۰۴۰/0

۱۶۲۶/0

7

۱۴۸۶/0

۱۴۴۷/0

۱۳۰۶/0

۱۳۲۹/0

۱۰۰۵/0

۱۰۰۵/0

میانگین

 

جدول 12: مقایسه نتایج به‌دست‌آمده با معیار مدولاریتی چگالی برای مجموعه داده sx-mathoverflow.

 

روش پیشنهادی

CD-SACS

DynCRep

louvain

IncNSA

DPC-DLP

برچسب زمانی

۵۶۶۱/0

۴۴۲۷/۰

۳۴۱۹/0

۱۸۲۹/0

۲۷۲۲/0

۳۲۶۸/0

1

۰۰۰۲/0

۱۶۱۲/0

۰۵۲۷/0

۰۰۰۲/0

۰۴۱۷/0

۱۲۱۲/0

2

۰۰۰۵/0

۰۰۰۵/0

۰۰۰۴/0

0008/0

۰۰۰۴/0

۰۰۰۴/0

3

۰۰۱۸/0

۰۰۱۹/0

۰۰۱۶/0

۰۰۳۱/0

۰۰۱۰/0

۰۰۱۱/0

4

۰۷۵۰/0

۱۲۸۶/0

۱۳۴۹/0

۱۳۲۱/0

۰۵۹۰/0

۰۶۰۰/0

5

۲۰۸۰/0

۱۸۷۲/0

۱۵۶۳/0

۰۰۰۱/0

۰۷۴۷/0

۰۰۹۰/0

6

۱۵۷۷/0

۱۴۰۵/0

۱۱۷۹/0

۰۱۴۶/0

۱۰۹۳/0

۰۱۸۸/0

7

۰۱۰۹/0

۰۱۲۳/0

۰۱۰۲/0

۰۱۶۴/0

۰۰۳۸/0

۰۰۴۹/0

8

۱۲۷۵/0

۱۳۴۴/0

۱۰۲۰/0

۰۴۳۸/0

۰۷۰۳/0

۰۶۷۸/0

میانگین

 

 

روش پیشنهادی، روش‌های CD-SACS و louvain بهترین مقدار معیار مدولاریتی با جریمه تقسیم در مجموعه داده cit-Hep Ph را به دست آورده‌اند. بر اساس نتایج جدول 8، روش پیشنهادی در مجموعه داده CollegeMsg در 5 بازه زمانی و به طور میانگین بهترین مقدار معیار مدولاریتی با جریمه تقسیم را نسبت به بقیه روش‌ها دارد و فقط در بازه‌های‌ زمانی 4 و 5، روش‌های CD-SACS و louvain بهترین مقدار را دارند که اختلاف آنها با روش پیشنهادی خیلی اندک و قابل قبول است. به طور میانگین بعد از روش پیشنهادی، روش‌های CD-SACS و louvain بهترین مقدار معیار مدولاریتی با جریمه تقسیم در مجموعه داده CollegeMsg را به دست آورده‌اند. بر اساس نتایج جدول 9، روش پیشنهادی در مجموعه داده sx-mathoverflow در 5 بازه زمانی از 8 بازه بهترین مقدار معیار مدولاریتی با جریمه تقسیم را نسبت به بقیه روش‌ها دارد و در سه بازه‌ زمانی 2، 3 و 4 روش‌های CD-SACS، Louvain و DynCRep بهترین مقدار را دارند که به دلیل تعداد کم تغییرات یال‌ها و نودها در این بازه‌های زمانی است. به طور میانگین، روش‌های IncNSA و CD-SACS بهترین مقدار معیار مدولاریتی با جریمه تقسیم در مجموعه داده sx-mathoverflow را به دست آورده‌اند. طبق نتایج به‌دست‌آمده از جداول 7 تا 9 برای اکثر مجموعه داده‌ها و بازه‌های زمانی، روش ارائه‌شده بر اساس معیار مدولاریتی با جریمه تقسیم بهتر عمل نموده است.

نتایج به‌دست‌آمده برای معیار مدولاریتی چگالی نیز به تفکیک مجموعه داده در جدول‌های 10 تا 12 آمده است.

طبق نتایج جدول 10، روش پیشنهادی در مجموعه داده cit-Hep Ph در 8 بازه زمانی و همچنین به طور میانگین بهترین مقدار معیار مدولاریتی چگالی را نسبت به بقیه روش‌ها دارد و فقط در بازه‌های زمانی 2، 3 و 5 روش‌های CD-SACS،DPC-DLP بهترین مقدار را دارند. به طور 

جدول 13: نتایج به‌دست‌آمده برای زمان برای مجموعه داده cit-Hep Ph.

 

روش پیشنهادی

CD-SACS

DynCRep

louvain

IncNSA

DPC-DLP

برچسب زمانی

۰۷۸/0

۱۲۷/5

۷۶۹/2

۰۷۹/0

۴۸۶/2

۲۲۳/3

1

۶۷۵/3

۴۴۱/9

۵۲۷/5

۴۵۱/4

۳۶۱/8

۲۴۲/6

2

۱۳۰/17

۴۲۱/69

۰۰۲/63

۸۴۵/59

۱۳۶/63

۸۹۳/64

3

۸۶۵/51

۱۴۲/108

۱۲۸/95

۶۳۷/91

۵۳۷/93

۱۸۲/94

4

۶۶۲/95

۰۱۸/141

۹۳۸/129

۵۳۸/126

۵۸۰/128

۰۶۱/129

5

۶۶۱/146

۶۲۸/195

۳۶۷/185

۶۳۷/182

۰۵۷/187

۹۰۳/185

6

۲۴۰/250

۳۵۷/261

۱۸۶/249

۵۷۵/246

۷۱۷/250

۰۷۸/248

7

۶۵۸/145

۹۱۴/201

۳۵۲/182

۵۳۴/181

۴۲۶/184

۵۴۳/183

8

۰۱۵/182

۰۶۵/217

۴۲۹/193

۵۲۷/191

۲۸۶/196

۶۸۶/194

9

۹۱۱/172

۱۲۸/309

۳۷۵/288

۵۱۳/281

۵۲۶/286

۸۰۷/282

10

۸۷۶/93

۱۷۵/142

۹۵۲/125

۵۷۴/124

۸۵۸/127

۱۱۹/127

11

۵۲۵/114

۹۴۷/150

۲۷۵/138

۵۳۷/135

۹۹۷/138

۱۵۸/138

میانگین

 

جدول 14: نتایج به‌دست‌آمده برای زمان برای مجموعه داده CollegeMsg.

 

روش پیشنهادی

CD-SACS

DynCRep

louvain

IncNSA

DPC-DLP

برچسب زمانی

۷۶۵۶/0

۷۶۲۸/2

۵۸۲۷/0

۳۳۴۴/0

۳۳۴۸/1

۶۵۲۵/1

1

۳۲۷۸/18

۱۶۷۳/29

۱۲۷۵/21

65/19

۹۷۴۹/20

۰۹۸۱/11

2

۶۵۵۶/37

۳۶۷۴/47

۵۲۸۱/41

913/40

۰۸۲۴/42

۵۸۳۲/41

3

۵۶۷۳/13

۲۴۷۵/21

۰۷۵۳/15

۴۱۶۳/14

۷۹۰۰/14

۳۸۳۹/18

4

۲۸۷۵/3

۱۳۴۷/7

۱۱۴۲/5

۱۰۸۵/3

۶۳۷۷/3

۸۰۵۶/4

5

۴۲۶۸/1

۱۷۶۴/3

۸۹۹۱/1

۰۶۱۷/1

۷۴۶۷/1

۶۰۴۲/2

6

۶۹۷۴/0

۲۰۴۶/3

۴۶۵۵/1

۲۵۹۴/0

۶۶۳۰/0

۵۳۰۲/1

7

۸۱۸۲۹/10

۲۹۴۳/16

۳۹۸۹۱/12

۳۹۱۹/11

۱۷۵۶۴/12

۶۶۵۳۹/11

میانگین

 

جدول 15: نتایج به‌دست‌آمده برای زمان برای مجموعه داده sx-mathoverflow.

 

روش پیشنهادی

CD-SACS

DynCRep

louvain

IncNSA

DPC-DLP

برچسب زمانی

۳۸/14

۱۴/31

۱۱/25

۹۶/21

۰۰/23

۴۳/23

1

۸۹/300

۱۷/592

۸۷/495

۵۰/460

۹۰/519

۸۹/491

2

۶۸/997

۰۱/1912

۹۴/۱۵۰۱

۳۵/۱۵۱۵

۳۱/۱۳۷۱

۸۶/۱۸۷۱

3

۷۰/۱۱۹۸

۸۳/2053

۴۴/1642

۸۳/1804

۱۴/1425

۸۹/۱۴۰۹

4

۲۱/۱۰۴۸

۶۲/2063

21/۱۴۱۲

۹۷/۱۵۷۳

۰۲/۱۵۷۵

۸۹/۱۶۱۲

5

۱۳/۱۰۰۲

۴۲/۱۹۲۷

۱۰/۱۵۸۶

۹۲/۱۵۰۳

۸۳/۱۵۰۴

۳۸/۱۵۰۵

6

۰۳/۹۸۶

۴۳/۱۷۵۳

۰۷/۱۵۰۷

۴۰/۱۴۷۹

۲۱/۱۴۸۰

۹۶/۱۴۸۰

7

۳۸/14

۰۲/۱۳۷۹

۱۳/۱۰۹۲

۱۳/۱۱۸۴

۵۹/۱۰۱۲

۱۴/۸۱۱

8

۸۹/۳۰۰

۰۸/۱۴۶۴

۸۶/۱۱۵۷

۰۱/۱۱۹۳

۰۰/۱۱۱۴

۹۳/۱۱۵۰

میانگین

 

 

میانگین بعد از روش پیشنهادی، روش‌های CD-SACS و DPC-DLP بهترین مقدار معیار مدولاریتی چگالی در مجموعه داده cit-Hep Ph را به دست آورده‌اند. بر اساس نتایج جدول 11، روش پیشنهادی در مجموعه داده CollegeMsg در 5 بازه زمانی و به طور میانگین بهترین مقدار معیار مدولاریتی چگالی را نسبت به بقیه روش‌ها دارد و فقط در بازه‌های‌ زمانی 1 و 5، روش ‌louvain بهترین مقدار را دارند که اختلاف آنها با روش پیشنهادی خیلی اندک و قابل قبول است. به طور میانگین بعد از روش پیشنهادی، روش‌های CD-SACS و louvain بهترین مقدار معیار مدولاریتی چگالی در مجموعه داده CollegeMsg را به دست آورده‌اند. مطابق با نتیجه‌های جدول 12، روش پیشنهادی در مجموعه داده 
sx-mathoverflow در 3 بازه زمانی بهترین مقدار معیار مدولاریتی چگالی را نسبت به بقیه روش‌ها دارد و در بقیه بازه‌‌های زمانی، روش‌های CD-SACS، Louvain و DynCRep بهترین مقدار را دارند.

نتایج به‌دست‌آمده برای معیار زمان برحسب ثانیه نیز به تفکیک مجموعه داده در جدول‌های 13 تا 15 آمده است. با در نظر گرفتن نتایج به‌دست‌آمده ملاحظه می‌شود که روش پیشنهادی عملکرد مناسب‌تری را در قیاس با روش‌های مورد مقایسه روی مجموعه داده‌های معرفی‌شده و با معیار‌های ارزیابی مختلف گزارش نموده است.

4-5 تأثیر هم‌پوشانی در روش پیشنهادی

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

جدول 16: نتایج به‌دست‌آمده برای روش پیشنهادی با در نظر گرفتن همپوشانی نسبت به در نظر نگرفتن همپوشانی.

 

مجموعه داده

Cit-Hep Ph

sx-mathoverflow

CollegeMsg

مدولاریتی

نیومن

جریمه تقسیم

چگالی

نیومن

جریمه تقسیم

چگالی

نیومن

جریمه تقسیم

چگالی

با همپوشانی

۲۲۱۹/0

۳۹۴۲/0

۱۹۱۶/0

۰۸۷۴/0

۱۴۰۰/0

۱۲۷۵/0

۲۶۷۰/0

۳۱۱۸/0

۱۴۸۶/0

بدون همپوشانی

۱۶۴۷/0

۳۱۴۰/0

۱۴۴۲/0

۰۷۱۱/0

۱۱۹۳/0

۰۹۸۵/0

۲۳۳۲/0

۲۷۷۴/0

۱۱۹۷/0

 

 

جدول 17: نمایش زمان اجرای روش پیشنهادی بدون موازی‌سازی 
نسبت به نسخه موازی‌سازی‌شده.

 

مجموعه داده

Cit-Hep Ph

sx-mathoverflow

CollegeMsg

بدون موازی‌سازی

۵۲۵/114

۱۸۵۴/792

۸۱۸۲۹/10

با موازی‌سازی

۵۸۷۴/89

۱۴۷۵/482

۸۴۶۳/12

 

جریمه تقسیم و مدولاریتی چگالی روش پیشنهادی با در نظر گرفتن همپوشانی نسبت به در نظر نگرفتن همپوشانی در بازه‌های زمانی مجموعه داده‌ها Cit-Hep Ph، sx-mathoverflow و CollegeMsg نشان داده شده است.

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

5-5 تأثیر موازی‌سازی روش پیشنهادی

یکی از چالش‌های اصلی در ارتباط با روش‌های کشف انجمن، قابلیت موازی‌سازی است. از آنجا که این الگوریتم‌ها معمولاً روی گراف‌هایی با تعداد گره‌ها و یال‌های بسیار بالا اجرا می‌گردد، لازم است الگوریتم‌ها قابلیت موازی‌سازی داشته باشند. در جدول 17 میانگین زمان اجرای روش پیشنهادی بدون موازی‌سازی نسبت به نسخه موازی‌سازی‌شده در بازه‌های زمانی مجموعه داده‌ها Cit-Hep Ph، sx-mathoverflow و CollegeMsg نشان داده شده است.

همان طور که در جدول 17 مشاهده می‌شود، نسخه موازی‌سازی‌شده روش پیشنهادی بر روی مجموعه‌های داده Cit-Hep Ph و 
sx-mathoverflow که بزرگ‌تر از CollegeMsg هستند، میانگین زمان اجرای کمتری نسبت به روش پیشنهادی بدون موازی‌سازی ارائه می‌دهد؛ اما در شبکه کوچک CollegeMsg زمان اجرا به دلیل سربار موازی‌سازی بیشتر هم می‌شود. میزان کاهش زمان اجرای روش پیشنهادی برای 
sx-mathoverflow بیش از 39% و برای Cit-Hep Ph نزدیک به 22% بهبود گزارش نمود. در حالی که برای CollegeMsg به دلیل اینکه کوچک‌بودن و افزایش سربار ناشی از موازی‌سازی افزایش زمان اجرا را شاهد بودیم.

6-       نتیجه‌گیری‌

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

مراجع

[1]       A. Reihanian, M. R. Feizi-Derakhshi, and H. S. Aghdasi, "An enhanced multi-objective biogeography-based optimization for overlapping community detection in social networks with node attributes," Information Sciences, vol. 622, pp. 903-929, Apr. 2023.

[2]       S. K. Gupta and D. P. Singh, "Seed community identification framework for community detection over social media," Arab. J. Sci. Eng., vol. 48, no. 2, pp. 1829-1843, 2023.

[3]       S. Mishra, S. S. Singh, S. Mishra, and B. Biswas, "Multi-objective based unbiased community identification in dynamic social networks," Comput. Commun., vol. 214, pp. 18-32, 15 Jan. 2024.

[4]       M. Sabzekar, S. BaradaranNejad, and M. Khazaeipoor, "A node-centric approach for community detection in dynamic networks," J. Electr. Comput. Eng. Innov., vol. 12, no. 2, pp. 305-318, Jul. 2024.

[5]       X. Li, Y. Xin, C. Zhao, Y. Yang, and Y. Chen, "Graph convolutional networks for privacy metrics in online social networks," Applied Sciences, vol. 10, no. 4, Article ID: 1327, 2020.

[6]       Z. Ma and S. Nandy, "Community detection with contextual multilayer networks," IEEE Trans. Inf. Theory, vol. 69, no. 5, pp. 3203-3239, May 2023.

[7]       M. Rostami, M. Oussalah, K. Berahmand, and V. Farrahi, "Community detection algorithms in healthcare applications: a systematic review," IEEE Access, vol. 11, pp. 30247-30272, 2023.

[8]       F. S. Gharehchopogh, "An improved harris hawks optimization algorithm with multi-strategy for community detection in social network," J. Bionic Eng., vol. 20, pp. 1175-1197, 2023.

[9]       D. Jin, et al., "A survey of community detection approaches: from statistical modeling to deep learning," IEEE Trans. Knowl. Data Eng., vol. 35, no. 2, pp. 1149-1170, Feb. 2023.

[10]       M. Seifikar, S. Farzi, and M. Barati, "C-Blondel: an efficient louvain-based dynamic community detection algorithm," IEEE Trans. Comput. Soc. Syst., vol. 7, no. 2, pp. 308-318, Apr. 2020.

[11]       S. Ahajjam, M. El Haddad, and H. Badir, "A new scalable leader-community detection approach for community detection in social networks," Soc. Networks, vol. 54, pp. 41-49, Jul. 2018.

[12]       S. Bahadori, H. Zare, and P. Moradi, "PODCD: probabilistic overlapping dynamic community detection," Expert Syst. Appl., vol. 174, Article ID: 114650, 15 Jul. 2021.

[13]       C. Bothorel, V. L. Dao, and P. Lenca, "Community structure: a comparative evaluation of community detection methods," Netw. Sci., vol. 8, no. 1, pp. 1-41, Mar. 2020.

[14]       S. Fortunato, "Community detection in graphs," Phys. Rep., vol. 486, no. 3-5, pp. 75-174, Feb. 2010.

[15]       M. E. J. Newman, "Modularity and community structure in networks," in Proc. Natl. Acad. Scivol. 103, no. 23, pp. 8577-8582, Jun. 2006.

[16]       W. Li, X. Zhou, C. Yang, Y. Fan, Z. Wang, and Y. Liu, "Multi-objective optimization algorithm based on characteristics fusion
of dynamic social networks for community discovery," Inf. Fusion, vol. 79, no. C, pp. 110-123, Mar. 2022.

[17]       Q. Ni, J. Guo, W. Wu, and H. Wang, "Influence-based community partition with sandwich method for social networks," IEEE Trans. Comput. Soc. Syst., vol. 10, no. 2, pp. 819-830, Apr. 2023.

[18]       H. Long, X. Li, X. Liu, and W. Wang, "BBTA: detecting communities incrementally from dynamic networks based on tracking of backbones and bridges," Appl. Intell., vol. 53, pp. 1084-1100, 2023.

[19]       H. Safdari, M. Contisciani, and C. De Bacco, "Reciprocity, community detection, and link prediction in dynamic networks," J. Phys. Complex., vol. 3, no. 1, Article ID: 15010, 2022.

[20]       S. Kumar, A. Mallik, and S. S. Sengar, "Community detection in complex networks using stacked autoencoders and crow search algorithm," J. Supercomput., vol. 79, no. 3, pp. 3329-3356, 2023.

[21]       T. Ma, Q. Liu, J. Cao, Y. Tian, A. Al-Dhelaan, and M. Al-Rodhaan, "LGIEM: global and local node influence based community detection," Futur. Gener. Comput. Syst., vol. 105, pp. 533-546, Apr. 2020.

[22]       T. Wang, S. Chen, X. Wang, and J. Wang, "Label propagation algorithm based on node importance," Phys. A Stat. Mech. its Appl., vol. 551, Article ID: 124137, Aug. 2020.

[23]       C. Li, et al., "NANI: an efficient community detection algorithm based on nested aggregation of node influence," 2017.

[24]       D. Zhuang, M. Chang, and M. Li, "DynaMo: dynamic community detection by incrementally maximizing modularity," IEEE Trans. Knowl. Data Eng., vol. 33, no. 5, pp 1934-1945, May 2021.

[25]       S. A. Seyedi, A. Lotfi, P. Moradi, and N. N. Qader, "Dynamic graph-based label propagation for density peaks clustering," Expert Syst. Appl., vol. 115, pp. 314-328, Jan. 2019.

[26]       F. Liu, J. Wu, C. Zhou, and J. Yang, "Evolutionary community detection in dynamic social networks," in Proc. Int. Joint Conf. on Neural Networks, 7 pp. , Budapest, Hungary, 14-19 Jul. 2019.

[27]       X. Su, J. Cheng, H. Yang, M. Leng, W. Zhang, and X. Chen, "IncNSA: detecting communities incrementally from time-evolving networks based on node similarity," Int. J. Mod. Phys. C, vol. 31, no. 7, Article ID: 2050094, 2020.

[28]       M. Cordeiro, R. P. Sarmento, and J. Gama, "Dynamic community detection in evolving networks using locality modularity optimization," Soc. Netw. Anal. Min., vol. 6, Article ID: 15, 2016.

[29]       J. Leskovec, J. Kleinberg, and C. Faloutsos, "Graphs over time: densification laws, shrinking diameters and possible explanations," in Proc. of the 11th ACM SIGKDD Int. Conf. on Knowledge Discovery in Data Mining, pp. 177-187, Chicago, IL, USA, 21-24 Aug. 2005.

[30]       A. Paranjape, A. R. Benson, and J. Leskovec, "Motifs in temporal networks," in Proc. of the 10th ACM Int. Conf. on Web Search and Data Mining, pp. 601-610, Cambridge, UK, 6-10 Dec. 2017.

[31]       P. Panzarasa, T. Opsahl, and K. M. Carley, "Patterns and dynamics of users' behavior and interaction: network analysis of an online community," J. Am. Soc. Inf. Sci. Technol., vol. 60, no. 5, pp. 911-932, May 2009.

 

مصطفی سبزه‌کار تحصيلات خود را در رشته مهندسی کامپیوتر در مقطع كارشناسي در سال 1386 در دانشگاه خوارزمی و مقاطع كارشناسي ارشد و دکتری مهندسی کامپیوتر را در دانشگاه فردوسی مشهد و به ترتیب در سال‌های 1389 و 1396 در دانشگاه فردوسی مشهد به پایان رساند. او هم‌اکنون استادیار گروه مهندسی کامپیوتر دانشگاه صنعتی بیرجند می‌باشد. زمينه‎هاي تحقيقاتي مورد علاقه ايشان عبارتند از: یادگیری ماشین، بیوانفورماتیک و شبکه‌های اجتماعی.

 

شیما برادران‌نژاد مدرک کارشناسی مهندسی کامپیوتر را از دانشگاه بیرجند در سال ۱۳۸۶ دریافت کرده است. همچنین، مدرک کارشناسی‌ارشد مهندسی کامپیوتر با گرایش نرم‌افزار را از دانشگاه آزاد اسلامی واحد بیرجند در سال ۱۴۰۱ دریافت نمود. زمینه‌های پژوهشی مورد علاقه وی شامل شناسایی الگو و الگوریتم‌های فراابتکاری است.

 

مهدی خزاعی‌پور مدرک کارشناسی مهندسی کامپیوتر را در سال 1382 از دانشگاه آزاد اسلامی واحد مشهد، مدرک کارشناسی‌ارشد مهندسی کامپیوتر را از دانشگاه آزاد اسلامی واحد علوم و تحقیقات تهران در سال ۱۳۸۷ دریافت کرده است. همچنین، وی دارای مدرک دکترای مهندسی کامپیوتر با گرایش توسعه سیستم‌های نرم‌افزاری از دانشگاه آزاد اسلامی واحد کرمان، کرمان، می‌باشد. وی در حال حاضر استادیار گروه کامپیوتر دانشگاه آزاد اسلامی واحد بیرجند است. زمینه‌های پژوهشی مورد علاقه وی شامل داده‌کاوی، برآورد تلاش نرم‌افزار، و الگوریتم‌های تکاملی می‌باشد.

 

مهدی خرد تحصيلات خود را در رشته مهندسی کامپیوتر در مقطع كارشناسي در سال ۱۳۸۹ و كارشناسي ارشد فناوری اطلاعات در سال ۱۳۹۴  در دانشگاه بیرجند گذراند. وی اکنون دانشجوی دکتری فناوری اطلاعات در دانشگاه قم است. زمينه‎هاي تحقيقاتي مورد علاقه ايشان عبارتند از: یادگیری ماشین، داده کاوی، الگوریتم‌های فراابتکاری و دینامیک محاسباتی.

 

 

 

 


مقالات مرتبط

حقوق این وب‌سایت متعلق به سامانه مدیریت نشریات رایمگ است.
حق نشر © 1404-1396

صفحه اصلی| عضویت/ ورود| درباره رایمگ| تماس با ما|
[English] [العربية] [en] [ar]