Abstract
Community detection is an important work for discovering the structure and features of complex networks. Many existing methods are sensitive to critical user-dependent parameters or time-consuming in practice. In this paper, we propose a novel label propagation algorithm, called CenLP (Centrality-based Label Propagation). The algorithm introduces a new function to measure the centrality of nodes quantitatively without any user interaction by calculating the local density and the similarity with higher density neighbors for each node. Based on the centrality of nodes, we present a new label propagation algorithm with specific update order and node preference to uncover communities in large-scale networks automatically without imposing any prior restriction. Experiments on both real-world and synthetic networks manifest our algorithm retains the simplicity, effectiveness, and scalability of the original label propagation algorithm and becomes more robust and accurate. Extensive experiments demonstrate the superior performance of our algorithm over the baseline methods. Moreover, our detailed experimental evaluation on real-world networks indicates that our algorithm can effectively measure the centrality of nodes in social networks
چکیده
شناسایی اجتماع کار مهمی برای کشف ساختار و ویژگیهای شبکه های پیچیده است. بسیاری از روشهای موجود در عمل به پارامترهای وابسته به کاربر بحرانی یا زمان بر حساس هستند. در این مقاله، ما یک الگوریتم انتشار برچسب جدید را، با نام CenLP (انتشار برچسب برمنبای مرکزیت) پیشنهاد میکنیم. این الگوریتم یک تابع جدید را برای اندازه گیری مرکزیت گره ها بطورکمی بدون هیچ گونه تعامل با کاربر بوسیله محاسبه تراکم محلی و شباهت با همسایه های با تراکم بالا برای هر گره معرفی می کند. براساس مرکزیت گره ها، ما یک الگوریتم انتشار برچسب جدید را با ترتیب به روز رسانی خاص و اولویت گره برای کشف کردن اجتماعات در شبکه های مقیاس بزرگ بطوراتوماتیک بدون تحمیل کردن هیچ محدودیت از پیش، ارائه می کنیم. تجربیات در مورد شبکه های دنیای واقعی و ترکیبی آشکار میکند الگوریتم ما سادگی، تاثیرگذاری، و مقیاس پذیری الگوریتم انتشار برچسب اصلی را حفظ میکند و قویتر و دقیق تر میشود. تجربیات گسترده عملکرد برتر الگوریتم ما در روشهای خط مبنا را ثابت می کند. علاوه براین، ارزیابی تجربی به تفصیل ما در مورد شبکه های دنیای واقعی نشان می دهدکه الگوریتم ما می تواند بطورموثر مرکزیت گره ها را در شبکه های اجتماعی اندازه گیری کند.
1-مقدمه
امروزه، تحقیقات در مورد شبکه های توجه وسیعی را به خود جلب کرده اند. یک شبکه بطور نمونه بصورت نموداری مدلسازی می شود که راس ها و لبه ها به ترتیب موجود ها و روابط بین موجود را نشان می دهند. ساختار اجتماع ذاتی {1،2} در بسیاری از شبکه های دنیای واقعی مانند شبکه وب جهانی، شبکه اجتماعی، و شبکه بیولوژیکی، وجود دارد. یک اجتماع در یک شبکه همیشه بعنوان یک گروه از گره ها با ارتباطات متراکم درون گروهها و ارتباطات پراکنده با دیگر گروه ها بیان می شود. اجتماعات نقش مهمی را در درک شبکه و شناسایی اجتماع در شبکه ها کاربردهای بسیاری در زمینه های مختلف، مانند تحلیل شبکه اجتماعی، شبکه های تعامل پروتئین، تقسیم تصویر و مسئله طرح بندی مدار دارد...