کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
7376126 1480077 2018 15 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Overlapping communities from dense disjoint and high total degree clusters
ترجمه فارسی عنوان
جوامع با هم تداخل دارند از خوشه های غیر متراکم و جامع درجه بالا
کلمات کلیدی
تشخیص جامعه همپوشانی، روش کاشت بر اساس تراکم، گسترش بذر، بهینه سازی هدایت،
ترجمه چکیده
جامعه نقش مهمی در زمینه جامعه شناسی، زیست شناسی و به ویژه در زمینه علوم رایانه ای دارد که سیستم ها اغلب به عنوان شبکه ها نمایان می شوند. و تشخیص جامعه در حوزه ها بسیار مهم است. جامعه یک زیرگراف چگالی کل گراف است با پیوندهای بیشتر بین اعضای آن نسبت به اعضای آن به گره های خارجی و گره ها در همان جامعه احتمالا به اشتراک گذاری خواص مشترک و یا نقش مشابه در گراف بازی می کنند. جوامع همپوشانی زمانی که گره ها در یک گراف متعلق به جوامع مختلف هستند. طیف گسترده ای از روش های همپوشانی تشخیص جامعه در ادبیات ارائه شده است و روش توسعه محلی یکی از موفق ترین تکنیک های برخورد با شبکه های بزرگ است. این مقاله یک روش کاشت بذر مبتنی بر تراکم را ارائه می دهد که در آن خوشه های محلی غیر متضاد خوشه ای جستجو می شوند و به عنوان دانه ها انتخاب می شوند. روش پیشنهادی بذر را با کل درجه و چگالی خوشه های محلی، با استفاده از ساختارهای محلی شبکه، انتخاب می کند. علاوه بر این، در این مقاله فاز تصفیه جامعه جدید را از طریق به حداقل رساندن هدایت هر جامعه پیشنهاد می کند، که از طریق آن کیفیت در جوامع شناخته شده به طور عمده در زمان خطی بهبود می یابد. نتایج تجربی در شبکه های مصنوعی نشان می دهد که روش کاشت پیشنهاد شده از سایر روش های بذر در حالت هنر برتر است و روش پالایش پیشنهاد شده به طور عمده کیفیت جوامع شناخته شده را افزایش می دهد. نتایج تجربی در نمودارهای واقعی با جوامع زمین واقعی نشان می دهد که رویکرد پیشنهادی از الگوریتم های تشخیص جامعه همپوشانی دیگر با پیشرفت های متفاوت را تجربه می کند، به ویژه، آن بیش از دو برابر سریع تر از الگوریتم های جهانی موجود با کیفیت بالاتر است و بدست می آید ساختار جامعه دقیق تر از الگوریتم های فعلی محلی بدون هیچ گونه اطلاعات پیشینی است.
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات فیزیک ریاضی
پیش نمایش مقاله
جوامع با هم تداخل دارند از خوشه های غیر متراکم و جامع درجه بالا
چکیده انگلیسی
Community plays an important role in the field of sociology, biology and especially in domains of computer science, where systems are often represented as networks. And community detection is of great importance in the domains. A community is a dense subgraph of the whole graph with more links between its members than between its members to the outside nodes, and nodes in the same community probably share common properties or play similar roles in the graph. Communities overlap when nodes in a graph belong to multiple communities. A vast variety of overlapping community detection methods have been proposed in the literature, and the local expansion method is one of the most successful techniques dealing with large networks. The paper presents a density-based seeding method, in which dense disjoint local clusters are searched and selected as seeds. The proposed method selects a seed by the total degree and density of local clusters utilizing merely local structures of the network. Furthermore, this paper proposes a novel community refining phase via minimizing the conductance of each community, through which the quality of identified communities is largely improved in linear time. Experimental results in synthetic networks show that the proposed seeding method outperforms other seeding methods in the state of the art and the proposed refining method largely enhances the quality of the identified communities. Experimental results in real graphs with ground-truth communities show that the proposed approach outperforms other state of the art overlapping community detection algorithms, in particular, it is more than two orders of magnitude faster than the existing global algorithms with higher quality, and it obtains much more accurate community structure than the current local algorithms without any priori information.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Physica A: Statistical Mechanics and its Applications - Volume 496, 15 April 2018, Pages 286-298
نویسندگان
, , ,