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

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

A Label Propagation Based Algorithm for Community Detection in Social Networks

Social network analysis with large volumes of data and complex communication structures is so difficult and time-consuming. Community detection is one of the major challenges in network analysis. A community is a set of individuals or organizations whose communication density is more than other network entities. Community detection or clustering can reveal the structure of groups in social networks, or relationships between entities. The label propagation algorithms with neighbor node influence have less complexity than traditional algorithms, such as clustering, to recognize communities. Also, the algorithms can identify overlapping communities. In our label propagation algorithm, which is based on the neighbor node influence, important nodes are more likely to publish their labels, while less important nodes have a small chance of spreading the label. The degree of similarity of nodes and the effect of nodes in a social network depends on the parameter of path length between nodes. In the proposed method, increasing this parameter leads to more accurate identification of overlapping and stable communities. The proposed algorithm detects overlapping communities with the same accuracy as the previous algorithms with fewer iterations, in less time. The algorithm is implemented on real and artificial social networks with weightless graphs and weighted graphs with weighting by Jacquard similarity criterion, in all of which the execution time is improved.