فهرست مطالبصفحهعنوان 10چکیده11فصل اول: مقدمه و طرح مسئله121-1-مقدمه131-2- شبکه های اجتماعی141-3-تحلیل شبکه های اجتماعی161-4- مقدمه ای برای منطق فازی191-5- بیان مسئله221-6- توصیف ریاضی مسئله پیش بینی لینک ها231-7- ساختار پایان نامه24فصل دوم: مبانی نظری و پیشینه ی تحقیق252-1- مقدمه252-2-مفاهیم اولیه در زمینه پیشنهاد لینک در شبکه 252-2-1- گراف252-2-2-گراف اجتماعی262-2-3- تحلیل شبکههای اجتماعی272-2-4-منابع داده کاوی در شبکه های اجتماعی272-3- انواع روش های پیش بینی لینک282-3-1- الگوریتم های بر مبنای شباهت292-3-1-1-شاخص شباهت محلی29293030303031313132322-3-1-2- شاخص های شباهت سراسری32333334343535362-3-1-3- شاخص های شباهت شبه محلی363737382-3-2-متدهای بیشترین احتمال382-3-2-1-روشهايمبتنيبر بیش ترین احتمال3841422-4-منطق فازی422-4-1- مدل فازی متغیرها442-4-2- تعریف متغیر زبانی452-4-3-روش چهار مرحله ای استفاده از منطق فازی462-4-4- عملیات بر روی مجموعه های فازی462-4-4-1-عملگر مکمل472-4-4-2-عملگراجتماع482-4-4-3-عملگر اشتراک492-4-5- رابطه بین مجموعه های فازی492-4-6- ترکیب روابط فازی492-4-7-اتصال دهنده ها512-4-8-رابطه ایجاب512-4-9-رابطه استنتاج522-5- مروری بر کارهای انجام شده در زمینه پیشنهاد لینک60فصل سوم:روش پیشنهادی613-1- مقدمه613-2- روش پیشنهادی643-2-1- تشریح ورودی های سیستم فازی663-2-2- فازی سازی پارامترهای ورودی سیستم فازی پیشنهادی683-2-3- قوانین پایگاه دانش سیستم فازی713-2-4- خروجی سیستم فازی پیشنهادی713-3- جمع بندی 73فصل چهارم: محاسبات و یافته های تحقیق744-1- مقدمه744-2- مشخصات پایگاه داده مورد استفاده:754-3-آماده سازی داده ها و شبیه سازی روش پیشنهادی784-4-روش ارزیابی نتیجه خروجی 804-5- مقایسه ی نتایج حاصل از اجرای روش پیشنهادی و روش های CNو Jaccard814-6- جمع بندی و نتیجه گیری 83فصل پنجم:نتیجه گیری و پیشنهادات845-1- نتیجه گیری855-2- کارهای آینده86فهرست مراجع90Abstract فهرست شکل هاصفحهعنوان39شکل 2-1- دندروگرامشبکهبا5نود40شکل 2-2- دودندروگرامبرایشبکهبا6نود41شکل 2-3- یک تصویر از برآورد شباهت برای مدل بلاک احتمالی42شکل 2-4- تابع مشخصه مجموعه غیرفازی A43شکل 2-5-مجموعه فازی اعداد نزدیک به صفر43شکل 2-6- نمونه ای از یک تابع عضویت مثلثی44شکل 2-7- تابع عضویت سرعت ماشین62شکل 3-1- شمای کلی سیستم فازی پیشنهادی اول63شکل 3-2- شمای کلی سیستم فازی پیشنهادی دوم64شکل3-3- مثالی از محاسبه اختلاف میانگین وزن یال بین هر نود و همسایگان مشترک67شکل 3-4- توابع تعلق مربوط به پارامترهای ورودی67شکل 3-5- تابع تعلق تعداد همسایه های مشترک به ازای CNxy=671شکل 3-6- خروجی سیستم فازی: میزان احتمال ایجاد لینک جدید بین دو نود x,y75شکل 4-1- تابع تعلق مربوط به پارامتر ورودی "تعداد همسایه های مشترک" (CNxy)76شکل 4-2- تابع تعلق مربوط به پارامتر ورودیRA76شکل 4-3- تابع تعلق مربوط به پارامتر ورودی " اختلاف میانگین وزن یال های بین هر نود و همسایگان مشترک آن دو نود"77شکل 4-4- تابع تعلق مربوط به پارامتر ورودی شاخص ارتباط ترجیحی (PAxy)77شکل 4-5- تابع تعلق مربوط به پارامتر ورودی شاخص جاکارد78شکل 4-6- خروجی سیستم فازی: میزان احتمال ایجاد لینک جدید بین دو نود در شبکه فهرست جدول هاصفحهعنوان 32جدول 2-1: مقایسه متد های شباهت محلی36جدول 2-2- مقایسه متد های katz ، LP و LHN238جدول 2-3- مقایسهالگوریتمهايمختلفپيشبيني در5شبكهمتفاوت68جدول 3-1- قوانین پایگاه دانش سیستم فازی پیش بینی لینک اول69جدول 3-2- قوانین پایگاه دانش سیستم فازی پیش بینی لینک دوم74جدول 4-1- خصوصیات توپولوژیکی شبکه ی USAirline80جدول 4-2- مقایسه ی نتایج روش پیشنهادی با روش RA81جدول 4-3-مقایسه ی نتایج روش پیشنهادی با روش CN و Jaccard چکیدهامروزه محبوبیت سایت های شبکه های اجتماعی در بین افراد غیر قابل انکار است، سایت هایی که امکانات زیادی را برای ارتباطات بین افراد در اختیار کاربران قرار می دهند. یکی از مشکلات اساسی در آنالیز این نوع شبکه ها پیش بینی ارتباطات جدید بین افراد شبکه می باشد.روش فازی به عنوان یکی از روش های مطرح در هوش مصنوعی، راه ساده ای را برای ساخت نتیجه ی صریح، مبهم، نویزدار و مفقود شده را مهیا می سازد. در نتیجه منطق فازی به ابزاری برای مدل کردن پیچیدگی های دنیای واقعی بدل شده است. این مدل ها معمولا از موارد مشابه خود بسیار دقیق تر بوده و نتایج دقیق تری به ما ارائه می دهند. به همین دلیل منطق فازی پتانسیل لازم برای ارئه ی لینک پیشنهادی دقیق تر را خواهد داشت و چارچوبی که در این تحقیق ارائه خواهیم داد بر اساس این منطق توسعه خواهد یافت.با توجه به رویکرد های فوق ما در این تحقیق با ارائه ی چارچوبی پیشنهادی جهت ارائه ی الگوریتمی هوشمند بر اساس ترکیب منطق فازی با الگوریتم های CN، Jaccard ، PAکهالگوریتم هایی برای پیش بینی لینک در گراف اجتماعی هستند، سعی در بهبود نتایج حاصله نمودیم. بررسی نتایج حاصله نشان داد که الگوریتم پیشنهادی دقت بیشتری در پیش بینی لینک داشته اما به دلیل وجود مراحل فازی و دفازی سازی، سرعت کمتری را دارا می باشد. کلمات کلیدی:پیش بینی لینک در شبکه های اجتماعی- منطق فازی- الگوریتم های پیش بینی لینک بر مبنای شباهت فصل اولمقدمه و طرح مسئله 1-1-مقدمه: شبکه های اجتماعی، نسل جدیدی از وب‌سایت‌ها هستند که این روزها در کانون توجه کاربران شبکه جهانی اینترنت قرار گرفته‌اند. این گونه سایت‌ها بر مبنای تشکیل اجتماعات آنلاین فعالیت می‌کنند و هر کدام دسته‌ای از کاربران اینترنتی با ویژگی خاصی را گرد هم می‌آورند. شبکه های اجتماعی را گونه‌ای از رسانه‌های اجتماعی می‌دانند که امکان دستیابی به نحوه جدیدی از برقراری ارتباط و به اشتراک‌گذاری محتوا در اینترنت را فراهم آورده‌اند. صدها میلیون نفر از کاربران اینترنت عضو صدها شبکه اجتماعی مختلف هستند و بخشی از فعالیت آنلاین روزانه‌شان در این سایت‌ها می‌گذرد .پیش بینی وقوع لینک ها، یک مساله اساسی و بنیادین در شبکه ها می باشد. در موضوع پیش بینی لینک، نمایی از یک شبکه داده می شود و مایل هستیم که بدانیم در آینده نزدیک، احتمالا چه تراکنش هایی میان اعضای فعلی شبکه روی می دهد و یا اینکه کدام یک از تراکنش های موجود را از دست می دهیم. هر چند این مساله به صورت گسترده ای مورد مطالعه و بررسی قرار گرفته است؛ با این حال، مشکل چگونگی ترکیب بهینه و موثر اطلاعات حاصل از ساختار شبکه با داده های توصیفی فراوان مربوط به گره و یال، تا حد زیادی پابرجا می ماند.L. Backstrom, , 2011))براي مدلسازي شبكه های اجتماعی، از گراف استفاده مي كنند كه در آن افراد گره ها را تشكيل ميدهند و روابط بين افراد با يال ها نمايش داده مي شود. در اين بين يك گراف اجتماعی بزرگ به وجود مي آيد.ما در این کار سعی خواهیم نمود که با تحلیل شبکه های اجتماعی ارتباطات احتمالی را پیش بینی نماییم. پیش بینی ارتباطات یک زیرشاخه از تحلیل شبکه های اجتماعی می باشد که در آن بایستی با توجه به مشاهدات و ارتباطات موجود، یک سری ارتباطات را که به صورت مستقیم قابل مشاهده نیستند یا وجود ندارند استنتاج کرد یا حدس زد.در این فصل دلیل پرداختن به موضوع پروژه و صورت مساله آن مورد بررسی قرار می گیرد. بدین منظور ابتدا مقدماتیدر رابطه با شبکه های اجتماعی، گراف اجتماعی، منطق فازی، پیش بینی لینک در شبکههای اجتماعی به اختصار مطالبی ارائه می شود، سپس مساله ای که پایان نامه سعی در حل آن دارد مطرح می گردد و در انتها رویکرد بکار رفته در تحقیق و ساختار پایان نامه ارائه می شود.هدف اصلی تحقیق بررسی روشهاي موجود در زمینه پیش بینی لینک ارتباط جدید در شبکه های اجتماعی و ارائه راهکار جدید به کمک منطق فازی در زمینه پیش بینی لینک در گراف اجتماعی می باشد. 1-2- شبکه های اجتماعی(پرهیزکار، 1392)در سال های اخیر فضای اینترنت اهمیت بیشتری در زندگی روزانه مردم پیدا کرده است. مردم از اینترنت برای ارتباط برقرار کردن با دیگران، خرید و فروش الکترونیکی محصولات، جستجوی اطلاعات و انجام بسیاری کارهای دیگر استفاده می کنند و بدین شکل، اینترنت به یک شبکه اجتماعی گسترده تبدیل گردیده است.شبکه ی اجتماعی ساختاری اجتماعی است که از گره هایی(که عموماً فردی یا سازمانی هستند) تشکیل شده است که توسط یک یا چند نوع خاص از وابستگی به هم متصل اند، برای مثال: قیمت‌ها، الهامات، ایده‌ها و تبادلات مالی، دوست‌ها،خویشاوندی، تجارت، لینک‌های وب، سرایت بیماری‌ها (اپیدمولوژی) یا مسیرهای هواپیمایی. ساختارهای حاصل اغلب بسیار پیچیده هستند. شبکه های اجتماعی گروهی از افراد یا سازمان های دارای سلیقه یا منافع مشترک هستند که برای دستیابی به اهداف خاصی گرد می آیند. تحلیل شبکههای اجتماعی روابط اجتماعی را با اصطلاحات رأس و یال می‌نگرد. هر عضو را یک بازیگر[1]می گویند. ویژگی شبکه های اجتماعی وجود روابط [2]و تعاملات[3] پیچیده بین بازیگران است. رأس‌ها بازیگران فردی درون شبکه‌ها هستند و یال‌ها روابط میان این بازیگران هستند. انواع زیادی از یال‌ها می‌تواند میان رأس‌ها وجود داشته باشد. نتایجتحقیقات مختلف بیانگر آن است که می توان از ظرفیت شبکههای اجتماعی در بسیاری از سطوح فردی و اجتماعی به منظور شناسایی مسائل و تعیین راه حل آنها، برقراری روابط اجتماعی، اداره امور تشکیلاتی، سیاستگذاری و رهنمون سازی افراد در مسیر دستیابی به اهداف استفاده نمود. به عنوان مثال، نتایج مطالعات در حوزه سیاستگذاری گردشگری نشان می دهد شبکههای اجتماعی به واسطه تاثیرگذاری روی متغیرهای رفتاری بر جذب گردشگران خارجی به مقاصد گوناگون تاثیرگذار هستند و می توان از این شبکه ها به منظور شکل‌گیری اعتماد و کاهش ریسک تصمیم‌گیری کاربران در انتخاب یک مقصد خاص گردشگری بهره گرفت.در ساده‌ترین شکل یک شبکه ی اجتماعی نگاشتی از تمام یال‌های مربوط، میان رأس‌های مورد مطالعه‌است. شبکه ی اجتماعی هم چنین می‌تواند برای تشخیص موقعیت اجتماعی هر یک از بازیگران مورد استفاده قرار گیرد. این مفاهیم غالباً در یک گراف شبکه ی اجتماعی نشان داده می‌شوند که درآن، نقطه‌ها رأس‌ها و خط‌ها نشانگر یال‌ها هستند.از دلایل عمده تشکیل شبکه های اجتماعی می توان به روابط فردی، روابط کاری ، روابط علمی، سلیقه ها و علایق و تفریحات مشترک، انگیزه های اجتماعی-سیاسی اشاره نمود.(پرهیزکار، 1392)