Abstract
Network communities represent basic structures for understanding the organization of real-world networks. A community (also referred to as a module or a cluster) is typically thought of as a group of nodes with more connections amongst its members than between its members and the remainder of the network. Communities in networks also overlap as nodes belong to multiple clusters at once. Due to the difficulties in evaluating the detected communities and the lack of scalable algorithms, the task of overlapping community detection in large networks largely remains an open problem. In this paper we present BIGCLAM (Cluster Affiliation Model for Big Networks), an overlapping community detection method that scales to large networks of millions of nodes and edges. We build on a novel observation that overlaps between communities are densely connected. This is in sharp contrast with present com-munity detection methods which implicitly assume that overlaps between communities are sparsely connected and thus cannot properly extract overlapping communities in networks. In this paper, we develop a model-based community detection algorithm that can detect densely overlapping, hierarchically nested as well as non-overlapping communities in massive networks. We evaluate our algorithm on 6 large social, collaboration and information networks with ground-truth community information. Experiments show state of the art performance both in terms of the quality of detected com-munities as well as in speed and scalability of our algorithm
چکیده
جوامع شبکه ای نشان دهنده ساختارهای اصلی برای درک سازمان دهی شبکه های دنیای واقعی هستند. یک جامعه (که یک ماژول یا یک گروه نیز نامیده می شود) به طور معمول به عنوان گروهی از گره ها (ند ها)تلقی می شود که ارتباط میان اعضایش نسبت به ارتباط بین اعضای آن و باقی مانده ی شبکه بیشتر است. هم چنین جوامع موجود در شبکه ها با هم همپوشانی دارند به طوری که گره ها بطور همزمان متعلق به چندین خوشه (گروه) هستند. با توجه به دشواری ارزیابی تشخیص جوامع وفقدان الگوریتم های مقیاس پذیر، هنوز هم کار تشخیص جامعه ی هم پوشان در شبکه های بزرگ تا حد زیادی به عنوان یک مساله بزرگ باقی مانده است. در این مقاله ما یک BIGCLAM ارائه می کنیم(مدل وابستگی گروهی برای شبکه های بزرگ)، که یک روش تشخیص جامعه همپوشان است که شبکه های بزرگی از میلیون ها گره و لبه را مقیاس گذاری می کند. ما با یک مشاهده جدید مواجه می شویم و آن این که بین جوامعی که بطور متراکمی به هم متصل هستند هم پوشانی بوجود می آید. این مساله کاملا در تضاد با روش های تشخیص جامعه موجود است که در آن ها به طور ضمنی فرض می شود که همپوشانی بین جوامعی رخ می دهد که بطور پراکنده در ارتباطند و در نتیجه به درستی نمی توانند جوامع همپوشان موجود در شبکه ها را استخراج نمایند. در این مقاله، ما یک الگوریتم شناسایی جامعه ی مبتنی بر مدل را توسعه می دهیم که می تواند جوامع همپوشان متراکم، جوامع آشیانه ای(تو در تو) سلسله مراتبی و نیز جوامع غیر همپوشان موجود در شبکه های بزرگ را شناسایی کند. ما الگوریتم مان را بر روی 6 شبکه اجتماعی، شبکه همکاری و شبکه اطلاعاتی بزرگ بوسیله ی اطلاعات جامعه ی حقیقت مبنا(جامعه حقیقت مبنا جامعه ای است که بر اساس یافته های عینی و واقعی استوار است)، ارزیابی می کنیم. آزمایش ها نشان دهنده عملکرد جدیدترین تکنولوژی هم برحسب کیفیت جوامع شناسایی شده و هم در سرعت و مقیاس پذیری الگوریتم ما است.
1-مقدمه
بخش بزرگی از فعالیت ها در علوم کامپیوتر، آمار، ریاضیات کاربردی و فیزیک آماری به شناسایی ساختار جامعه در شبکه های پیچیده اختصاص یافته است( ارزیابی رفرنس های [8، 28، 32] را ملاحظه کنید). یک جامعه (که یک ماژول یا یک گروه نیز نامیده می شود) به عنوان گروهی از گره ها تلقی می شود که از تعاملات بیشتری در میان اعضای آن نسبت به تعاملات بین اعضای آن و باقی مانده شبکه برخوردار است [10]. چنین گروه هایی از گره ها (یعنی، جوامع) اغلب به عنوان واحدهای سازمان یافته در شبکه های اجتماعی [7، 29]، واحدهای عملیاتی در شبکه های بیوشیمی [17]، زیست خوان های اکولوژیکی در شبکه های غذایی [10]، و یا رشته های علمی در شبکه های استنادی و همکاری [3] تفسیر شده اند....