افزایش دقت شناسایی جوامع همپوشان با استفاده از وزن‌دهی یال‌ها

سامانه‌های پردازشی و ارتباطی چندرسانه‌ای هوشمند

دوره 1، شماره 1، مهر 1399، صفحه 9-20   

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

نویسندگان

ایرج تیموری¹؛ مهدی افضلی^{* 2}

¹دانشگاه فرهنگیان، پردیس شهید بهشتی، زنجان، ایران

²هیات علمی دانشگاه آزاد واحد زنجان

چکیده

یکی از مهمترین ویژگی‌های شبکه‌های پیچیده وجود ساختارهای اجتماعی می‌باشد. بطور مشخص شناسایی این ساختارها در شبکه‌های پیچیده به تحلیل ویژگی‌های ساختاری شبکه کمک می‌کند. در سال های اخیر الگوریتم‌های متعددی برای کشف اجتماعات در شبکه‌های پیچیده پیشنهاد شده است. با توجه به ویژگی‌های این اجتماعات، یکی از روش‌های موجود برای شناسایی اجتماعات ارائه الگوریتم‌هایی برای وزن‌دهی یال‌های شبکه است به طوری‌که وزن یال‌های درون اجتماعات افزایش و بطور هم‌زمان وزن یال‌های مابین اجتماعات کاهش یابد تا تمایز میان اجتماعات به سادگی قابل شناسایی باشند.
در روش پیشنهادی با استفاده از فرآیند وزن‌دهی به یال‌ها، بین گره‌های که مشابهت بیشتری دارند و گره‌هایی که مشابهت اندکی با هم دارند تمایز قایل می‌شویم. یعنی با اختصاص وزن با استفاده از معیارهای پیشنهادی در برخی الگوریتم‌ها ، یال‌هایی که وزن بیشتری دارند نقش بیشتری در تعیین جمعیت خواهند داشت.
با توجه به اینکه یک همبستگی مثبت بین ساختارهای جامعه و معیارهای شباهت وجود دارد، نتایج آزمون‌های انجام شده نشان می-دهد که استفاده از معیارهای مشابهت محلی به عنوان وزن یال‌ها برای برخی از الگوریتم‌ها باعث افزایش دقت تشخیص جوامع می-شود. این الگوریتم‌ها از درجه گره‌ها به عنوان یکی از ویژگی‌های شبکه برای محاسبه قدرت جذب هسته‌ها برای تشکیل جوامع استفاده می‌کنند. به عنوان نمونه در مورد شبکه‌های واقعی، اجرای الگوریتم WHD-EM روی شبکه High school network، جوامع را با دقت NMI=0.6652 و معیار خلوص purity=0.9845 کشف می‌کند که از بعضی از الگوریتم‌ها مانند CPM، NMF ، GAME ، GCE، OSLOM و LINK از نظر معیار NMI بهتر است.

کلیدواژه‌ها

شبکه‌های پیچیده؛ شبکه‌های اجتماعی؛ شناسایی جوامع؛ وزن‌دهی یال‌ها

مراجع

[1]Gros, C. Complex and adaptive dynamical systems : a primer, with 98 figures and 10 tables. Berlin: Springer, 2008.

[2]Hakami Zanjani, A., & Darooneh, A. “Finding communities in linear time by developing the seeds”. Physical Review E, 84(3), 2011: 036109.

[3]Fortunato, S. “Community detection in graphs”. Physics Reports, 486(3–5), 2010: 75-174.

[4]Palla, G., Derenyi, I., Farkas, I., & Vicsek, T. “Uncovering the overlapping community structure of complex networks in nature and society”. Nature, 435(7043), 2005: 814-818.

[5]Rives, A. W., & Galitski, T. “Modular organization of cellular networks”. Proc Natl Acad Sci U S A, 100(3), 2003: 1128-1133.

[6]Chen, J., & Yuan, B. “Detecting functional modules in the yeast protein-protein interaction network”. Bioinformatics, 22(18), 2006: 2283-2290.

[7]Caldarelli, G., & Vespignani, A. Large scale structure and dynamics of complex networks : from information technology to finance and natural science. Singapore ; Hackensack, NJ: World Scientific, 2007.

[8]Guimera, R., & Nunes Amaral, L. A. “ Functional cartography of complex metabolic networks”. Nature, 433(7028), 2005: 895-900.

[9]Krause, A. E., Frank, K. A., Mason, D. M., Ulanowicz, R. E., & Taylor, W. W. “Compartments revealed in food-web structure”. Nature, 426(6964), 2003: 282-285.

[10]Reichardt, J. Structure in complex networks. Berlin: Springer. 2009.

[11]Xiang, J., Hu, K., & Tang, Y. “A class of improved algorithms for detecting communities in complex networks”. Physica A: Statistical Mechanics and its Applications, 387(13), 2008: 3327-3334.

[12]Ju, X., et. Al. “Enhancing community detection by using local structural information. Journal of Statistical Mechanics: Theory and Experiment, 2016(3), 20016: 033405.

 [13]Kernighan, B. W., & Lin, S. “An efficient heuristic procedure for partitioning graphs. Bell System Technical Journal, 49(2), 1970: 291 - 307.

[14]Girvan, M., & Newman, M. E. “Community structure in social and biological networks”. Proc Natl Acad Sci U S A, 99(12), 2002: 7821-7826.

[15]Newman, M. E. J., & Girvan, M. “Finding and evaluating community structure in networks”. Phys. Rev. E, 69(2). 2004.

[16]Newman, M. E. J. “Fast algorithm for detecting community structure in networks. Phys. Rev, 69(6), 2004:

[17]Boettcher, S., & Percus, A. G. “Optimization with Extremal Dynamics”. Physical Review Letters, 86(23), 2001: 5211-5214.

[18]Zachary, W. W. “An Information Flow Model for Conflict and Fission in Small Groups”. Journal of Anthropological Research, 33(4), 1977: 452-473.

[19]Papadopoulos, S., Kompatsiaris, Y., Vakali, A., & Spyridonos, P. “Community detection in Social Media. Data Mining and Knowledge Discovery, 24(3), 2012: 515-554.

[20]Yang, J., McAuley, J., & Leskovec, J. “Community Detection in Networks with Node Attributes”. Paper presented at the 2013 IEEE 13th International Conference on Data Mining.