مقایسه دو الگوریتم تقریبی MC و NBRW برای محاسبه ضریب خوشه بندی در شبکه های اجتماعی بزرگ

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

Keywords:

شبکه های اجتماعی , ضریب خوشه بندی , روش های تقریبی , الگوریتم مونت کارلو , گام تصادفی