مقایسه دو الگوریتم تقریبی MC و NBRW برای محاسبه ضریب خوشه بندی در شبکه های اجتماعی بزرگ
- سال انتشار: 1397
- محل انتشار: پنجمین کنفرانس مهندسی دانش بنیان و نوآوری
- کد COI اختصاصی: KBEI05_007
- زبان مقاله: فارسی
- تعداد مشاهده: 534
نویسندگان
دانشکده فنی و مهندسی گلپایگان، اصفهان، ایران
چکیده
محاسبه ضریب خوشه بندی یکی از کارهای مهم در تحلیل شبکه های دنیای واقعی است. یافتن ضریب خوشه بندی در شبکه های اجتماعی بزرگ با استفاده از الگوریتم های متعارف بسیار زمان بر و گاهی غیرممکن است. پس برای شبکه های بسیار بزرگ این پارامتر پراهمیت می تواند با استفاده از تکنیک های نمونه برداری و با روش های احتمالی تقریب زده شود. در این راستا در این مقاله، دو الگوریتم تقریبی یکی مبتنی بر مونت کارلو (MC) و دیگری مبتنی بر گام های تصادفی (NBRW)، معرفی و برای چند مجموعه داده بزرگ با یکدیگر ارزیابی و مقایسه می شوند. این دو الگئریتم تقریبی برای چهار مجموعه داده DBLP, Amazon, Facebook و Orkut پیاده سازی شده اند و مقادیر تقریبی ضریب خوشه بندی های آنها محاسبه شده است. نتایج نشان می دهد دقت درستی نتایج NBRW بیشتر از MC است و مقادیر تقریب زده شده اختلاف کمتری با مقادیر ثبت شده برای میانگین ضرایب این شبکه ها دارند. هرچند از نظر پیچیدگی زمانی الگوریتم MC بهینه تر است چون در زمان ثابت مراحل الگوریتم انجام می شود. ولی در NBRW برای رسیدن به کمترین خطای محاسباتی نیاز به تکرار گام های تصادفی داریم که سبب افزایش زمان کل الگوریتم می شود.کلیدواژه ها
شبکه های اجتماعی، ضریب خوشه بندی، روش های تقریبی، الگوریتم مونت کارلو، گام تصادفیمقالات مرتبط جدید
- تحلیل انطباقی کیفیت و میزان محبوبیت خدمات ابری با بررسی و مقایسه رتبه بندی Tranco و رتبه بندی عملکردی شرکت های ابری
- طبقه بندی سیگنال های EEG ثبت شده از قشر پیش پیشانی به منظور کشف اثر موسیقی در شدت احساسات با استفاده از شبکه عصبی مصنوعی و پرسشنامه
- ارائه رویکردی برای مدیریت ریسک در پروژه های نرمافزاری با استفاده از خوشه بندی تجمعی
- تحلیل احتمالنقض ترتیب علیتی پیام ها در یک الگوریتم پخش علیتی در سیستمهای توزیع شده
- بهینه سازی به سبک گربه های شنی: الگوریتمی برای جستجوی کارآمد و مدیریت ازدحام
اطلاعات بیشتر در مورد COI
COI مخفف عبارت CIVILICA Object Identifier به معنی شناسه سیویلیکا برای اسناد است. COI کدی است که مطابق محل انتشار، به مقالات کنفرانسها و ژورنالهای داخل کشور به هنگام نمایه سازی بر روی پایگاه استنادی سیویلیکا اختصاص می یابد.
کد COI به مفهوم کد ملی اسناد نمایه شده در سیویلیکا است و کدی یکتا و ثابت است و به همین دلیل همواره قابلیت استناد و پیگیری دارد.