شناسائی جامعه در شبکه¬های پیچیده با استفاده از درخت پوشای مینیمم و بیشینه¬سازی ماژولاریتی
محورهای موضوعی : electrical and computer engineeringسندس بهادری 1 * , مریم نورائی 2
1 - گروه مهندسی کامپیوتر، دانشگاه آزاد اسلامي واحد آبادان، ایران
2 - گروه مهندسي كامپيوتر، دانشگاه آزاد اسلامي واحد آبادان، ایران
کلید واژه: شبکه‌های پیچیده, جامعه, درخت پوشای مینیمم, افزایش ماژولاریتی,
چکیده مقاله :
چکیده: ماژولاریتی، یکی از ویژگی های برجسته شبکه های پیچیده است که ساختار این شبکه ها را به صورت گروه های جامعه ای تقسیم می کند. تاکنون، روش های زیادی برای شناسایی جوامع در شبکه های پیچیده به کار گرفته شده است، اما برخی از این روش ها بهینه سازی های محلی دارند که به ترتیب پردازش نودها، جواب نهایی را تحت تاثیر قرار می دهند. در این مقاله، یک روش جدید برای یافتن جوامع در شبکه های پیچیده با استفاده از تقسیم و ادغام پیشنهاد شده است. در این روش، از درخت پوشای کمینه به عنوان یک ابزار برای تشخیص عدم تشابه بین نودها استفاده می شود. در فرایند تقسیم، یال هایی که بیشترین عدم تشابه را نشان می دهند، در درخت پوشای کمینه حذف می شوند تا گروه های کوچکتری از نودهای یک جامعه ایجاد شوند. در فرایند ادغام، هر گروه با گروه همسایه ادغام می شود که ترکیب آنها بیشترین افزایش ماژولاریتی را نسبت به گروه های همسایه دیگر داشته باشند. نتایج آزمایش های انجام شده بر روی شبکه های واقعی و شبکه های ساختگی نشان می دهد که روش پیشنهادی در این مقاله، دقت بهتری برای شناسایی جوامع در شبکه های پیچیده دارد.
Modularity is one of the prominent features of complex networks that divides the structure of these networks into community groups. So far, many methods have been used to identify communities in complex networks, but some of these methods have local optimizations that affect the order of processing nodes and the final solution. In this paper, a new method for finding communities in complex networks using split and merge is proposed. In this method, minimum spanning tree is used as a tool to detect dissimilarity between nodes. In the partitioning process, the edges that show the most dissimilarity are removed in the minimum spanning tree to create smaller groups of nodes in a community. In the merging process, each group is merged with the neighboring group whose combination has the highest increase in modularity compared to other neighboring groups. The results of experiments conducted on real networks and artificial networks show that the method proposed in this article has a good accuracy for identifying communities in complex networks.