خوشه بندی نمودار با استفاده از اقدامات آگاه مثلث در شبکه های بزرگ

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

معرفی

تشخیص جامعه یک مشکل اساسی در تجزیه و تحلیل شبکه است [38] ، و مقدار زیادی از کار در ریاضیات کاربردی ، علوم کامپیوتر و فیزیک آماری برای انتزاع جوامع در شبکه های پیچیده انجام شده است. یک جامعه به طور معمول به عنوان مجموعه ای از راس های متراکم متصل در یک شبکه تعریف می شود [6] ، [8] ، [11] ، [15] ، [23] ، [27] ، [30] ، [33] ، [34]، جایی که رئوس ها در همان جامعه همیشه دارای خواص مشترک هستند [31]. و تشخیص جامعه با هدف شناسایی همه جوامع موجود در یک شبکه انجام می شود.

اگرچه مشکل تشخیص جامعه به طور گسترده مورد مطالعه قرار گرفته است ، اما بیشتر روش ها فقط به الگوهای اتصال مرتبه پایین در سطح لبه های اصلی توجه می کنند در حالی که اتصال مرتبه بالاتر نقش اساسی در درک ساختار شبکه های پیچیده دارد [3]، [23]. برای گرفتن اطلاعات مرتبه بالاتر از شبکه ها ، برخی از روش های مبتنی بر نقوش اخیراً ارائه شده است [3] ، [23] ، [34]. این روشها به طور معمول با ساختن یک ابرگرفتگی آگاه از نقوش شروع می شوند که در صورت وجود یک نقوش حاوی هر دو آنها ، دو راس دارای یک لبه مرتبه بالاتر هستند و سپس یک الگوریتم تشخیص جامعه سنتی را بر روی هایپرگراف انجام می دهند. ثابت شده است که این روش جدید در بهبود صحت تشخیص جامعه مؤثر است. با این حال ، هایپرگراف بازسازی شده همیشه تکه تکه شده است و حاوی تعداد زیادی از راس های جدا شده است که نمی توانند به هیچ جوامع اختصاص داده شوند و از ساختار جامعه انتزاعی قرار بگیرند. Hypergraph همچنین می تواند حاوی تعداد زیادی از مؤلفه های کوچک باشد ، که در آن رئوس موجود در اجزای مختلف نمی تواند به همان جامعه اختصاص یابد ، با وجود این که ممکن است در شبکه اصلی به خوبی متصل شوند. بنابراین ، بیشتر روشهای تشخیص جامعه مرتبه بالا از مشکل تکه تکه شدن رنج می برند. به عنوان مثال ، اگر یک روش خوشه بندی مبتنی بر پیاده روی بر روی ابرگراف اعمال شود ، راس های جدا شده و راس های موجود در اجزای کوچک گره های مرده خواهند بود ، یک واکر هرگز نمی تواند از یک جزء کوچک در ابرگراف پرش کند. شکل 1 ساختار شبکه CORA و هایپراگراف مبتنی بر نقوش مربوطه را نشان می دهد ، جایی که مؤلفه بزرگ متصل شبکه اصلی به تعداد زیادی از زیرگرافهای کوچک و راس های جدا شده تقسیم می شود. رئوس های جدا شده را نمی توان با اطلاعات اتصال ارائه شده توسط Hypergraph به هیچ جامعه ای اختصاص داد ، و راس های موجود در اجزای کوچک احتمالاً به دلیل عدم ارتباط با بقیه هایپرگراف نمی توانند برخی از وابستگی های جامعه خود را بدست آورند.

• 1. ما دو اقدامات خوشه ای آگاه مثلث را پیشنهاد می کنیم که اطلاعات مرتبه بالاتر و مرتبه پایین یک شبکه را ادغام می کنند.
• 2. ما یک روش تشخیص جامعه محلی چند مرتبه را پیشنهاد می کنیم و از نظر تئوریک ثابت می کنیم که جوامع شناسایی شده به هم وصل شده و حاوی دانه های مربوطه هستند.
• 3. ما یک مدل تقریبی را طراحی می کنیم که الگوریتم را در حدود 10 برابر در شبکه های در مقیاس بزرگ با تأثیر کمی در دقت سرعت می بخشد.

بقیه مقاله به شرح زیر سازماندهی شده است. بخش 2 کارهای مرتبط در مورد تشخیص جامعه را معرفی می کند. بخش 3 مشکلات جستجوی جامعه و تشخیص جامعه محلی را تعریف می کند و سپس دو اقدامات خوشه ای آگاه مثلث را ارائه می دهد. بخش 4 روش بذر را ارائه می دهد و بخش 5 روش انبساط بذر را ارائه می دهد. بخش 6 این مدل را برای تقریبی اقدامات مثلث آگاه ارائه می دهد. در بخش 7 ، ما پیچیدگی زمان روش پیشنهادی را تجزیه و تحلیل می کنیم. در بخش 8 ، ما آزمایش های گسترده ای را در هر دو شبکه واقعی و مصنوعی انجام می دهیم و بخش 9 این کار را نتیجه می گیرد.

قطعه قطعه

کار مرتبط

در این بخش ، ما به طور خلاصه برخی از کارهای پیشرفته در مورد تشخیص جامعه از جمله روش های استاندارد تشخیص جامعه (CD) و روش های جستجوی جامعه (CS) را معرفی می کنیم.

مقدمات

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

بذر با چگالی تقویت مثلث

دانه های اولیه به عنوان یک مؤلفه اصلی برای روش های LCD عمل می کنند. به طور شهودی ، زیرگراف ناشی از یک بذر باید از چگالی لبه داخلی بالایی برخوردار باشد زیرا قسمت مرکزی یک جامعه معمولاً متراکم است. از طرف دیگر ، یک بذر برای اتصال کل جامعه باید درجه کل داشته باشد. در اینجا ، ما چگالی تقویت مثلث پیشنهادی δ - (ها) را به جای چگالی استاندارد برای گرفتن اطلاعات مرتبه بالاتر یک شبکه اعمال می کنیم. علاوه بر این ، بذر بزرگتر باید در اختیار داشته باشد

گسترش بذر توسط هدایت مثلث آگاه

شخصی PageRank (PPR) [2] ، [20] ، [32] نسخه شخصی شده از PageRank استاندارد [20] ، [24] است ، به یکی از موفق ترین تکنیک های تشخیص جامعه محلی تبدیل شده است. با توجه به مجموعه ای از راس ها ، PPR با شروع انتشار از توزیع یکنواخت بر روی راس های موجود در مجموعه ، نمره نزدیکی را به هر راس در ساختار محلی اختصاص می دهد. به طور رسمی ، بگذارید P ماتریس مجاور یک شبکه را به عنوان مثال ، به عنوان مثال ، ∀ I ∈ [1 ، n] ، ∑ j p ij = 1 نشان دهد ، جایی که n تعداد رئوس ها در آن است

استراتژی سرعت

واضح است که پیچیدگی کل الگوریتم با عملکرد شمارش انواع مختلف مثلث محدود می شود. ما با برآورد تعداد مثلث ها ، یک مدل را برای تقریب دو معیار آگاه مثلث می سازیم. طرح ساده در شکل 4 نشان داده شده است. با توجه به یک جامعه C و یک راس X ، ما آمار زیر را اعمال می کنیم: (1) چگالی لبه داخلی جامعه Δ = Δ (c).(2) اندازه جامعه σ = |ج |(3) ضریب خوشه بندی ϑ (x) هر راس در شبکه.(4)

پیچیدگی زمانی

با توجه به شبکه G ، اجازه دهید n تعداد راس ها باشد. در مرحله بذر ، پیچیدگی عملکرد مرتب سازی O (n log n) است. در الگوریتم ساده لوح ، پیچیدگی دقیقاً محاسبه چگالی تقویت مثلث هر محله با عملکرد شمارش مثلث ها محدود می شود ، که با توزیع درجه شبکه تعیین می شود. پیچیدگی برای بیان فشرده پیچیده است. با این حال ، ما می دانیم که محاسبات بخش زیادی از هزینه زمان بذر را می گیرد. در btlcd ،

آزمایش

برای ارزیابی اثربخشی و کارآیی روش پیشنهادی ، آزمایش های گسترده ای در چهار شبکه در مقیاس بزرگ در مقیاس بزرگ و تعداد قابل توجهی از شبکه های مصنوعی انجام می شود. ما تمام آزمایشات را بر روی رایانه شخصی با حافظه 16G و یک پردازنده هسته اینتل در 3. 3 گیگاهرتز انجام می دهیم.

نتیجه

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

اعلام علاقه رقیب

نویسندگان اعلام می كنند كه آنها هیچ منافع مالی رقیب یا روابط شخصی را كه به نظر می رسد بر اثر گزارش شده در این مقاله تأثیر می گذارد ، ندارند.

تصدیق

این کار توسط برنامه ملی تحقیق و توسعه کلیدی چین پشتیبانی شده است [کمک هزینه شماره 2020YFB1406902].