بخشی از مقاله
چکیده -
شبکه یک راه حل قوی جهت مطالعه تعامل اشیا در سیستم های پیچیده می باشد.گره های شبکه به اجتماع هایی تقسیم می گردند که در اغلب مواقع دارای یک ویژگی، نقش یا عملکرد مشترکی می باشند. اجتماع ممکن است همپوشانی داشته باشد و بعضی از گره ها متعلق به چندین اجتماع باشند.
ما به دنبال راهکاری سریع و باکیفیت جهت تشخیص اجتماع های همپوشان بر اساس معیارهایی می باشیم و می خواهیم این راهکار در بستر معماری کلان داده باشد تا امکان پردازش گراف های خیلی بزرگ با تعداد گره ها و یال های بسیار زیاد در زمان اندک را فراهم سازد.
ایده کلیدی ما استفاده از الگوریتم های محلی در بستر کلان داده می باشد.
.1 مقدمه
شبکه یک راه حل مناسب جهت نمایش سیستم های طبیعی می باشد. برخی از این شبکه ها از پیچیدگی های خاصی برخوردارند و شبکه های پیچیده نامیده می شوند. ابزار مناسب جهت مدلسازی شبکه ها گراف می باشد. الگوهای مشترکی در شبکه های پیچیده موجود است که آنها را ازشبکه های تصادفی مجزا می سازد. به عنوان مثال می توان به قوانینی همچون توزیع توانی درجه و پدیده جهان کوچک و وجود اجتماع اشاره کرد.
گراف، از گره ها و یال هایی تشکیل گردیده است و می توان آن را در قالب گروه هایی متصل و چگال تقسیم کرد که به عنوان "اجتماع"،"خوشه" یا "ماژول" شناخته می گردند.[1] اجتماع در واقع مجموعه ای از گره هاست که بین آنها یال های زیادی وجود دارد ولی بین این گره ها و سایر گره های شبکه یال های کمتری وجود دارد[2] و به گونه ای قابل جدا شدن از سایر اعضای شبکه هستند. هدف از ارائه این مقاله یافتن اجتماع های شبکه های کلان می باشد. این مسئله معادل خوشه بندی بوده و از نوع NP-Hard می باشد.
شبکه های کلان یا مقیاس بزرگ به شبکه هایی گفته می شود که حاوی میلیون ها و میلیاردها گره و یال می باشند و پردازش و ذخیره سازی آنها با امکانات امروزی بر روی یک سیستم کامپیوتری تکی مقدور نمی باشد و جهت ذخیره سازی یا پردازش آنها، نیاز به مجموعه یا خوشه ای از کامپیوترها می باشد. در حال حاضر ابزارها و چارچوب هایی جهت پردازش این نوع گراف های کلان به وجود آمده است که به عنوان مثال می توان به Graphx، Graphlab و Giraph اشاره کرد. در پیاده سازی الگوریتم های این مقاله تلاش گردیده تا از Graphx استفاده گردد.
شکل -1 مقایسه اجرای ابزارهای پردازش گراف برمجموعه داده
در این مقاله، ما با به کارگیری الگوریتم های محلی، و خواص ساختاری گراف تلاش می کنیم تا اجتماع های باکیفیتی را بیابیم. سپس از خواص شبکه های پیچیده برای انتخاب مجموعه گره دانه - - seed کمک می گیریم. با استفاده از خصوصیت جهان کوچک می توان تعدادی از گره های مهم با درجه بالا را انتخاب کرد که هر یک به احتمال زیاد نماینده یک اجتماع می باشند و همسایگان زیادی دارند.
مرحله بعد بسط پیرامون این گره ها جهت یافتن اجتماع می باشد. الگوریتمی که در این قسمت استفاده می شود [2]PageRank nibble می باشد که بردار Personalized PageRank را برای هر گره دانه محاسبه می کند و برپایه Random Walk می باشد. سپس بردار محاسبه شده برای گره ها مرتب سازی می گردد و تابع ارزیابی بر اساس معیارهای مختلف تشخیص اجتماع، تعداد گره های درون اجتماع را تخمین می زند، پس از این مرحله اجتماع مجدد مورد ارزیابی قرار می گیرد تا خصوصیات یک اجتماع خوب را داشته باشد.
روش ما در این مقاله به 3 مرحله تقسیم می شود. مرحله نخست تقسیم بندی گراف به افرازهایی است که هر یک را بتوان به صورت مجزا بر روی یک سیستم کامپیوتری پردازش کرد. این روش افرازبندی به دو صورت برش راس یا برش یال صورت می گیرد. مرحله دوم به صورت موازی است و به دنبال یافتن دانه های مهم است که نماینده اجتماع می باشند. مرحله سوم بسط پیرامون این دانه ها و ارزیابی اجتماع به دست آمده بر اساس معیارهایی است که در آینده معرفی می کنیم ودر نهایت اجتماع هایی را انتخاب می کنیم که خوب و باکیفیت باشند.
.2 ارزیابی اجتماع
فرض می کنیم مجموعه S شامل تعدادی گره در گراف می باشد. تابع f - S - تابع ارزیابی می باشد که نشان می دهد گره های موجود در S به چه نحوی به یکدیگر متصلند و معیارهای یک اجتماع را تا چه مقداری فراهم می سازند . گراف G - V, E - گرافی بی جهت است با n = |V| که معرف تعداد گره های گراف است و m = |E| که تعداد یال های گراف را نمایش می دهد.
ns تعداد گره های S را نشان می دهد = |S| ms تعداد یال های موجود در S را نشان می دهد
در این قسمت 2 تابع هزینه را معرفی می نماییم که هر یک کیفیت اجتماع S را نمایش می دهد.[3]
• نسبت مشارکت مثلث - Triangle Participation Ratio
• رسانش - :[4] - Conductance
هدف ما از تشخیص اجتماع - - community-like، پیدا کردن گروهی از گره هاست که این معیارها و توابع هزینه را حداکثر نماید .
بیشینه سازی دقیق این توابع مسئلهNP-Hard می باشد
معیارهای یک اجتماع خوب به غیر از معیارهایی که در بالا اشاره کردیم، معیارهایی هستند
که با انها می توانیم تشخیص بدهیم که یک اجتماع خوب - - good است . این معیارها از بررسی اجتماع های واقعی - ground-truth - به دست آمده اند. یک اجتماع خوب اجتماعی است که اعضای آن به خوبی متصل هستند و اجتماع فشرده است به نحوی که به خوبی از مابقی شبکه نیز جدا باشد. تفاوت بین توابع هزینه مطرح شده و معیار اجتماع خوب در این است که توابع هزینه مشخص می سازند که مجموعه نودهای مورد نظر، چقدر شبیه به یک اجتماع می باشند.
در صورتی که معیارهای خوبی به طور شفاف مشخص می سازند که یک اجتماع چه ویژگی های مطلوبی دارد. در مجموعه ای از نودها معیار خوبی زیاد لزوما نشان دهنده یک اجتماع نیست، اما یک مجموعه با امتیاز بالا از تابع ارزیابی، باید مقدار زیادی روی یک یا چند معیارخوب داشته باشد. به عبارت دیگر، معیار خوب بودن در انواع مختلف از ساختار اجتماع به وضوح دیده می شود - در بعضی مواقع ناسازگار هستند - با استفاده از ادبیات قسمت تابع ارزیابی این تابع را نیز به صورت g - s - برای مجموعه گره های S تعریف می کنیم.
• تفکیک پذیری - : - Separability از اجتماع های خوب مشهود است که از بقیه شبکه به خوبی مجزا هستند., [5] [4] به این معنی می باشد که تعداد یال های مجموعه S به بقیه شبکه تعداد کمی است. معیار تفکیک پذیری نرخی بین تعداد یال های داخلی و خارجی یال های S می باشد.
• تراکم : - Density - از مشاهده اجتماع های خوب در می یابیم که به خوبی متصل اند.[4] این معیار کسری از یال ها می باشد - تمام یال های ممکن - که بین گره های S نمایش داده می شوند.
چسبندگی - : - Cohesiveness ساختار داخلی اجتماع را مشخص می کند. به طور شهودی می یابیم که یک اجتماع خوب، باید به صورت عادلانه وبه خوبی ازدرون متصل باشد و همچنین به سختی بتواند به دو زیراجتماع تقسیم گردد. این را با رسانش برش داخلی نشان می دهیم و به صورت ریاضی داریم که عبارت است از رسانش S′ که زیرگرافی به دست آمده از S می باشد. به طور شهودی، رسانش، میزان نرخ یال هایی از S′ را نمایش می دهد که خارج مجموعه را به یال های داخل مجموعه S' متصل کرده اند. یک اجتماع خوب باید چسبندگی بالایی داشته باشد - رسانش داخلی بالا - و باید یال هایی را حذف کند که باعث می شوند اجتماع به دو مولفه مجزا تقسیم گردد.
• ضریب خوشه بندی - : - Clustering Coefficient اجتماع
های شبکه، توزیع ناهمگن محلی از یالها را نمایش می دهند، زیرا هر زوج گره با همسایه مشترک، علاقه بیشتری دارد تا به دیگری متصل گردد.
.3 رویکردهای افرازبندی گراف
جهت نمایش گراف در حالت توزیع شده و پردازش کلان داده، دو رویکرد افراز گراف وجود دارد تا گراف بر روی همه کامپیوترهای پردازشی توزیع گردد. رویکرد اول برش گره و و رویکرد دوم برش یال می باشد.[13]
شکل -2دورویکردافرازگراف:ازراست اول برش گره،دوم برش یال [14]
شکل -3 پیاده سازی رویکرد اول در یک سیستم توزیع شده[14]
.4 الگوریتم تشخیص اجتماع
روشی که به کار برده ایم از بسط و بهینه سازی محلی استفاده شده است. برخلاف روش های سراسری که الگوریتم بر کل گراف اعمال می گردد. از یک دانه شروع می کنیم، و آن را به صورت حریصانه بسط می دهیم تا زمانی که به یک نقطه بهینه محلی در هدف تشخیص اجتماع برسیم. از الگوریتم personalized Pagerank برای بسط محلی استفاده می کنیم.
فاز دانه یابی هدف یک راهبرد دانه یابی کارامد شناسایی گره های گوناگون است که در داخل خوشه ای با رسانش خوب قرار گرفته اند. این شناسایی نباید خیلی پرهزینه باشد.
این الگوریتم از یک منظر دیگری جهت دانه یابی استفاده می کند، هدف انتخاب یک مجموعه دانه است که به خوبی در گراف توزیع شده باشند. به طوری که، بعد از بسط این دانه ها، قسمت زیادی از گراف پوشش داده خواهد شد. ما به صورت حریصانه، یک مجموعه منحصربه فرد از k گره در گراف را به ترتیب کاهشی درجه انتخاب می نماییم. این ایده از آنجا الهام گرفته شده است، که فاصله بین یک گره و خوشه ، با اندازه درجه نسبت عکس دارد.
بنابراین انتظار داریم راس های با درجه بالا فاصله کمی با تعداد زیادی از راس ها داشته باشند. از اینجا علت اینکه روش را - مرکزگسترش - Spread Hubs می نامیم مشخص می شود. نتایجی که Gleich و [6]Shadhri به دست آورده اند نشان می دهد که اجتماع های خوبی در اطراف گره هایی با درجه بالا درگراف های پیچیده وجود دارد، که ویژگی power-low و ضریب خوشه بندی بالا دارند.
ما از یک مجموعه منحصربه فرد استفاده می کنیم تا از انتخاب دانه های کنار هم جلوگیری نماییم. رویه کامل در الگوریتم 1 نمایش داده شده است. همزمان با اینکه الگوریتم hub ها را در شبکه می یابد، اگر چند گره وجود داشته باشد که درجه یکسانی داشته باشند را نیز انتخاب می کنیم. این مرحله ممکن است تعداد دانه هایی بیشتر از k بازگرداند، اما تعداد نهایی دانه های بازگشتی که از ورودی k بیشتر باشند زیاد نیستند زیرا گره هایی با درجه بالا زیاد نیستند.
