بخشی از مقاله
چکیده:
این روزها شبکههای اجتماعی با استقبال فراوانی مواجه شدهاند و توجهات زیادی را به خود جلب کردهاند. شبکههای اجتماعی یک راه رایج برای مدلسازی تعاملات بین افراد در یک گروه یا کمیته هستند. میتوان آنها را به صورت گراف، نمایش داد. شبکههای اجتماعی خیلی پویا هستند، چون در طی زمان یالها وگرههای جدید به گراف اضافه میشوند. درک پویاییهای که از رشد شبکههای اجتماعی نشأت می گیرند بهعلت وجود تعداد زیادی پارامتر متغیر یک مسأله پیچیده است. اما، یک مسأله نسبتاً سادهتر درک ارتباط بین گرههای خاص است. یک نمونه از یک مسأله خاص که در این مقاله به آن اشاره میکنیم پیش بینی احتمال ارتباط آینده بین دو گره است، با دانستن اینکه هیچ ارتباطی بین گره های در حالت فعلی گراف نیست. این مشکل به پیشبینی پیوند معروف است. در این مقاله یک روش پیش بینی پیوند بر اساس الگوریتم هارمونی ارائه می شود. در روش پیشنهادی از الگوریتم هارمونی به منظور پیدا کردن مسیر بهینه حرکت مورچگان استفاده میکنیم بهطوریکه مسیر حرکت هر مورچه بهعنوان نوازنده و گرهها بهعنوان یک هارمونی در نظر گرفته میشود. نتایج شبیهسازی روی تعدادی از شبکههای واقعی نشان میدهد که الگوریتم صحت پیشبینی را بهبود میدهد.
کلید واژه: الگوریتم هارمونی، پیشبینی پیوند، سیستمهای پیشنهاد دهنده
-1 مقدمه
امروزه شبکههای اجتماعی برخط، به دلیل امکان ایجاد ارتباط بین افراد مختلف در سرتاسر دنیا محبوبیت زیادی دارند. یکی از تحلیلهایی که در شبکههای اجتماعی صورت میگیرد، پیشبینی پیوند میباشد. در موضوع پیشبینی پیوند، نمایی از یک شبکه به ما داده میشود و ما مایل هستیم که بدانیم در آینده نزدیک، احتمالاً چه تراکنشهایی میان اعضای فعلی شبکه روی میدهد و یا اینکه کدام یک از تراکنشهای موجود را از دست میدهیم. هر چند این مسأله به صورت گستردهای مورد مطالعه و بررسی قرار گرفته است؛ با این حال، مشکل چگونگی ترکیب بهینه و مؤثر اطلاعات حاصل از ساختار شبکه با دادههای توصیفی فراوان مربوط به گره و یال، تا حد زیادی پابرجا میماند. بسیاری از راهحلهای موجود،خصوصاً روش-هایی که کل گراف را پیمایش میکنند مدیریت مکانیسمهای استنتاج را دچار مشکل میکنند. با توجه به این مسأله، شناخت و انتخاب ویژگیها و نیز انتخاب روشی که بتواند در بهبود پیشبینیها مؤثر باشد و با هزینه کمتر، پاسخ بهتری را در پیشبینیها ارائه کند بسیار با اهمیت جلوه میکند.
هوش جمعی رویکردنسبتاً جدیدی در حل مسائل بهینهسازی است که از رفتار اجتماعی حشرات و حیوانات دیگر الهام میگیرد. از جمله مورچهها که برای متدها و تکنیکهای زیادی مورد الهام قرار گرفتهاند و بیشترین موفقیت را در تکنیک بهینهسازی که به عنوان بهینهسازی کلونی مورچه - ACO - شناخته شده است [1]، بهدست آوردهاند. ACO از رفتار جستجوی غذای مورچه گرفته است. الگوریتم بهینهسازی کلونی مورچهها یک الگوریتم مناسب یافتن راهحلهای تقریبی برای مسائل بهینهسازی ترکیباتی است که ابتدا برای حل مسائل بهینهسازی گسسته مانند مسأله فروشنده دورهگرد [3-2]، مسیریابی [6-4] و زمانبندی [8-7] معرفی شد. رایجترین روشهای پیشبینی پیوند در شبکههای اجتماعی به دودستهی روشهای باناظر و بدون ناظر تقسیمبندی شدهاند. طبق مطالعات انجام شده، روشهای بدون ناظر، دقت بالاتری نسبت به روشهای باناظر دارند. ویژگیهای مورد استفاده در تعیین میزان شباهت بین موجودیتها که از گراف شبکه استخراج میشوند، شامل ویژگیهای محلی و نیمهمحلی و سراسری است که ویژگیهای محلی از مزیت سرعت و ویژگیهای سراسری از مزیت دقت برخوردارند. ویژگیهای نیمه محلی نیز به منظور برقراری موازنه بین دقت و پیچیدگی محاسباتی ارائه شدهاند.[9]
-2پیشینه پژوهش
Getoor در مقاله[10] برای اولین بار مبحث پیوند کاوی مطرح شد. روشهای پیش بینی پیوند به دو دسته با ناظر و بدون ناظر تقسیم میشوند. در [11] روشهای با نظارت بیشتر بر روی الگوریتم های دسته بندی و استفاده از ویژگی هایی همچون همسایگان مشترک و طول مسیر و ... تمرکز دارند. روشهای بدون نظارت بر اساس الگوریتمهای خوشهبندی بوده و گرهها را با توجه به شباهت آنها به خوشههایی تقسیم می-کنند. فایر و همکاران در [12] تأثیر محاسبه هر یک از ویژگی ساختاری را در پیش بینی پیوند، برای 5 مجموعه داده سنجیده اند. Papadimitrio و همکارانش در [13] الگوریتم Friendlink را به عنوان یک سیستم پیشنهاد دهنده جهت دوستیابی ارائه میکنند. این الگوریتم، تشابه میان گرهها در یک گراف غیر مستقیم ساخته شده از یک داده های ارتباطی را مییابد. این الگوریتم به عنوان داده ورودی از ارتباطات یک گراف و به عنوان خروجی از ماتریس تشابه میان هر دو گره استفاده می-کند. در نتیجه، پیشنهاد دوستی میتواند بر اساس وزن در ماتریس تشابه داده شوند. Symeonidis و همکارانش در [14]
الگوریتم SpectralLink را جهت دوستیابی برای کاربر جدید پیشنهاد می کنند. در نتیجه، پیشنهاد دوستی بر اساس امتیاز تشابه در ماتریس داده میشود. اعظم کی پور و همکارانش در [15] یک رویکرد محلی را برای پیش بینی پیوند بین دو رأس پیشنهاد می دهد که از یک معیار تعیین شباهت بین جفت رأس های گراف شبکه استفاده می کند. N.Azizifard در [16] جهت خوشه بندی کاربران شبکه اجتماعی از الگوریتم Random Walk استفاده شده است که می تواند در یک شبکه، ارتباطات را پیدا کند.
-1-2 معیارهای پیش بینی پیوند
شاخص همسایگان مشترک: این روش یکی از سادهترین روشهایی است که برای پیشبینی پیوند بهکار میرود. دو گره تمایل به ایجاد ارتباط دارند اگر همسایگان مشترک بیشتری داشته باشند. روش محاسبه آن بهصورت فرمول - - 1 است به-طوریکه a,b دو گره و - D - و - E - بیانگر مجموعهای از همسایگان گرههای a,b است. شاخص سالتون: شاخص سالتون برای پیدا کردن شاخص شباهت براساس زاویه کسینوسی بین ردیفهایی از ماتریس مجاورت که گره های a,b را دارند استفاده میشود و بهصورت فرمول - 2 - محاسبه میشود: شاخص جکارد: Jaccard در سال 1901 برای مقایسهی شباهت و تنوع مجموعههای نمونه پیشنهاد شد. این شاخص نرخ همسایگان رایج گرههای a,b را برای همهی گرههای همسایه نشان میدهد . در نتیجه مقدار شاخص jaccard از اینکه گرههای با درجه بالاتر شاخص شباهت بیشتری با سایر گرهها داشته باشند جلوگیری میکند. مقدار این شاخص به صورت فرمول - 3 - محاسبه میشود: شاخص سورنسون: یک معیار مشابه معیار jaccard توسط سورنسون در سال 1948پیشنهاد شد تا شباهت بین قطعات را اندازه میگیردکه به صورت فرمول - 4 - محاسبه میشود: کاتز: در سال1953، کاتز شباهت را با استفاده از مسیر عمومی توصیف کرد. ایدهی این روش این است که مسیرهای بیشتری بین دو گره هستند. اندازهگیری katz به صورت فرمول - 5 - تعریف شده است: اتصال ترجیحی: اتصال ترجیحی به عنوان مدلی برای رشد شبکه ها، احتمال ایجاد پیوند جدید به گره متناسب با - - هست . شباهت دو گره u و v از رابطه - 8 - بهدست می آید.
-3 روش پیشنهادی
در دور اول هر مورچه اول گره اول خود را بهصورت تصادفی انتخاب میکند گرههای بعدی طبق رابطه - 9 - ایجاد میشود. یک سطر جدید به ماتریس اضافه میکنیم. هارمونی یا بردار پاسخ جدید با احتمال HMCR از هارمونیهای قبلی و با احتمال 1-HMCR بهصورت تصادفی انتخاب میشود. برای ایجاد یک هارمونی یا راه حل جدید ابتدا یک عدد تصادفی بین صفر و یک تولید میکنیم، این عدد تصادفی با HMCR مقایسه میشود و اگر کوچکتر از آن باشد، یک مقدار تصادفی از فضای جستجو برای متغیر L ام انتخاب میگردد، در غیر این-صورت از ماتریس حافظه یک مقدار انتخاب میشود. در صورتیکه از ماتریس حافظه یک مقدار انتخاب شد سپس عدد تصادفی دیگری تولید میشود و با PAR مقایسه میشود. در صورتیکه عدد تصادفی کوچکتر از PAR باشد، این متغیر انتخاب شده از ماتریس حافظه به مقدار کوچکی با توجه به رابطه - 13 - تغییر پیدا میکند:
