افزایش دقت شناسایی جوامع همپوشان با استفاده از وزن‌دهی یال‌ها
محورهای موضوعی : پردازش چند رسانه ای، سیستمهای ارتباطی، سیستمهای هوشمند
ایرج تیموری
1
(دانشگاه فرهنگیان، پردیس شهید بهشتی، زنجان، ایران)
مهدی افضلی
2
(هیات علمی دانشگاه آزاد واحد زنجان)
کلید واژه: شبکه‌های اجتماعی, شبکه‌های پیچیده, وزن‌دهی یال‌ها, شناسایی جوامع,
چکیده مقاله :
یکی از مهمترین ویژگی‌های شبکه‌های پیچیده وجود ساختارهای اجتماعی می‌باشد. بطور مشخص شناسایی این ساختارها در شبکه‌های پیچیده به تحلیل ویژگی‌های ساختاری شبکه کمک می‌کند. در سال های اخیر الگوریتم‌های متعددی برای کشف اجتماعات در شبکه‌های پیچیده پیشنهاد شده است. با توجه به ویژگی‌های این اجتماعات، یکی از روش‌های موجود برای شناسایی اجتماعات ارائه الگوریتم‌هایی برای وزن‌دهی یال‌های شبکه است به طوری‌که وزن یال‌های درون اجتماعات افزایش و بطور هم‌زمان وزن یال‌های مابین اجتماعات کاهش یابد تا تمایز میان اجتماعات به سادگی قابل شناسایی باشند.در روش پیشنهادی با استفاده از فرآیند وزن‌دهی به یال‌ها، بین گره‌های که مشابهت بیشتری دارند و گره‌هایی که مشابهت اندکی با هم دارند تمایز قایل می‌شویم. یعنی با اختصاص وزن با استفاده از معیارهای پیشنهادی در برخی الگوریتم‌ها ، یال‌هایی که وزن بیشتری دارند نقش بیشتری در تعیین جمعیت خواهند داشت.با توجه به اینکه یک همبستگی مثبت بین ساختارهای جامعه و معیارهای شباهت وجود دارد، نتایج آزمون‌های انجام شده نشان می-دهد که استفاده از معیارهای مشابهت محلی به عنوان وزن یال‌ها برای برخی از الگوریتم‌ها باعث افزایش دقت تشخیص جوامع می-شود. این الگوریتم‌ها از درجه گره‌ها به عنوان یکی از ویژگی‌های شبکه برای محاسبه قدرت جذب هسته‌ها برای تشکیل جوامع استفاده می‌کنند. به عنوان نمونه در مورد شبکه‌های واقعی، اجرای الگوریتم WHD-EM روی شبکه High school network، جوامع را با دقت NMI=0.6652 و معیار خلوص purity=0.9845 کشف می‌کند که از بعضی از الگوریتم‌ها مانند CPM، NMF ، GAME ، GCE، OSLOM و LINK از نظر معیار NMI بهتر است.
In recent years, several algorithms have been proposed for detection in complex networks. It should be noted that wuth regarding the features of these communities, one of the existing methods for identifying communities, is providing an algorithms for weighting the edges of the network as the weight of the edges of the communities are incresed and at the same time the weight of the edges between communities are reduced. Therefore the distinction between communities could be identified simply. In the proposed method with useing the process of weighting the edges, we distinguish between the nodes that are more similar to each other and the nodes that have slight similarity. i.e. by assigning the weight with using the proposed criteria in some algorithms, the edges with more weight will have a greater role in determining the population.According that there is a positive correlation between similarity measures and community structures, the results of the tests shows that using local similarity measures as the weight of edges for some algorithms, causes an increase in the accuracy of communities recognition. These algorithms use the degree of the nodes as one of the network characteristics for computing the cores absorbing ability for communities formation. For example, in the case of Real Networks, running WHD-EM algorithm on the High school network, discovers the communities with the NMI=0.6652 and the purity criteria equal to 0.9845. Also it should be noted that some algorithms such as CPM, OSLOM and LINK in terms of NMI criteria, are better.
[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.
_||_