شکل ۳-۳ رویکرد های موجود در پیش بینی لینک ۵۳
شکل ۴-۱ توزیع جمعیت در شبکه اجتماعی فلیکر ۶۹
شکل ۴-۲ مثالی در مورد محاسبه مقدارPrecision و AUC 74
شکل ۴- ۳ منحنی ROCبرای مقایسه سه شاخص همسایگان مشترک,کاتز و آدامیک آدار ۷۶

شکل ۴-۲ نمایی از یک مدل بیزی ساده که به عنوان یک شبکه بیزین عمل مینماید ۷۸
شکل ۴-۳ گراف و roc curve precision-recall 81
شکل۴-۶ فلوچارت الگوریتم رقابت استعماری ۸۶
شکل ۴-۷ شمای کلی شبه کد الگوریتم ژنتیک ۸۹
شکل۴- ۸نمایی از الگوریتم بهینه سازی ازدحام ذرات ۹۱
نمودار۴-۵ precision- recall 95
نمودار ۴-۶مساحت زیر نمودار ROC curve 96
نمودار ۴-۷ نمودار تکرار ها وکارایی الگوریتم ها(Iteration-Best cost) 97
شکل۵-۱ فعالیت کاربران در شبکه اجتماعی فیس بوک ۱۰۲
شکل ۵-۱ نسبت مثال های مثبت و منفی در شبکه های اجتماعی ۱۰۳

۱-۱-مقدمه
اینترنت به عنوان یکی از مهم ترین ابداعات بشر در قرن اخیر، با قابلیت ها و کارکردهای متعدد و گسترده اش، بخش های مختلف زندگی انسانی را تحت تأثیرات مثبت و منفی خود قرار داده است. مبنا و هدف اصلی اینترنت، برداشتن فاصله جغرافیایی میان انسان های سراسر دنیا و ایجاد تحول در عرصه ارتباطات و تبادل اطلاعات است.[۱]
اینترنت، کار خود را به عنوان ابزار ارتباط متخصصان و خصوصاً جهت تبادل داده ها و منابع تحقیقاتی، شروع کرد و به مرور زمان توانست خود را تا سطح برقراری ارتباط بین افراد معمولی از طریق پست الکترونیکی ارتقا بخشد. پس از مدتی، اینترنت به منزله فضایی جدید جهت بسط فعالیت های تجاری در امور نقل و انتقالات مالی، بازاریابی و همچنین ابزار پیگیری برای مصرف کنندگان، مورد توجه واقع شد. وبلاگ ها و وب سایت ها، نرم افزارهای گفتگوی برخط، سرویس های پست الکترونیک و غیره امکانات جدیدی بودند که در پرتوی اینترنت و شبکه جهانی وب، در اختیار کاربران قرار گرفتند.
در حالی که هنوز هیچ کس تصور نمی کرد که روزی جنبه اجتماعی اینترنت به صورت یکی از کاربردهای اصلی آن درآید، شبکه های اجتماعی^[۱] اینترنتی پای به عرصه وجود گذاشتند. این موضوع در بین کاربران اینترنتی چنان مورد استقبال قرار گرفت که به جرأت می توان گفت یکی از تأثیرگذارترین سرویس های ارائه شده در اینترنت و وب که در سال های اخیر تحول شگرفی در نظام اجتماعی کشورهای مختلف جهان به وجود آورده، شبکه های اجتماعی اینترنتی بوده است.
شبکه های اجتماعی، نسل جدیدی از پایگاه هایی هستند که این روزها در کانون توجه کاربران شبکه جهانی اینترنت قرار گرفته اند. این گونه پایگاه ها بر مبنای تشکیلات برخط فعالیت می کنند و هر کدام دسته ای از کاربران اینترنتی با ویژگی خاص را گرد هم می آورند. شبکه های اجتماعی را گونه ای از رسانه های اجتماعی می دانند که امکان دستیابی به شکل جدیدی از برقراری ارتباط و به اشتراک گذاری محتوا در اینترنت را فراهم آورده اند.
تغییر و تحولات در نظام اجتماعی ناشی از اینترنت، انکار ناپذیر است. این تغییرات حتی شیوه برقراری ارتباط شاگرد و استاد و روش تدریس در سطوح دانشگاهی را هم متحول کرده است. این امر به طور اساسی قابلیت انجام تحقیقات توسط دانشجویان و به اشتراک گذاشتن یافته های آنها با دیگران را بالا برده است. پست الکترونیکی، اتاق های گفتگو و نشست های اینترنتی باعث گردیده تا ارتباط دانشجویان با استاد و مطالب درسی خود بیشتر گردد. این امر نکته مثبتی برای آینده آموزش و تعلیم محسوب می شود و همه اینها مرهون اینترنت، وب و شبکه های اجتماعی مجازی است.
اینترنت امروزه امکان کاملاً غیر منتظره برقراری ارتباطات بین افراد و شهروندان را فراهم نموده است؛ امری که در گذشته و در تاریخ روابط بین الملل در تئوری و در عمل به یک رؤیا شبیه بود. اینترنت به کلی این خط سیر را تغییر داده و امکان برقراری ارتباطات بین افراد و گروه های یک اجتماع با افراد و گروه های جوامع دیگر را در قالب شبکه های اجتماعی و سایر سایت هایی که رنگی اجتماعی به خود گرفته اند، مهیا کرده است. طبیعی است که این امر اثراتی جهانی از خود به جای خواهد گذاشت. امروزه، شهروندان جوامع مختلف با درنوردیدن مرزهای جغرافیایی می توانند عقاید، نظرات و اطلاعات خود را با یکدیگر به اشتراک بگذارند و از این رهگذر، به خلق قلمرو عمومی جهانی بپردازند که می تواند کاملا مجزا، و در مواردی متناقض، با قلمروهای ارتباطی در سطوح دیپلماتیک و دولتی باشد و بر همین اساس است که انبوهی از اطلاعات، عقاید و نظرات افراد، و انواع داده های مختلف در سایت های شبکه های اجتماعی وجود دارند وانگیزه خوبی را برای محققان و پژوهشگران حوزه های مختلف فراهم می آورند تا به این شبکه ها روی آورده، و از اطلاعات موجود در راه تحقق اهداف اقتصادی، اجتماعی، سیاسی و غیره بهره برداری نمایند. به همین دلیل در سال های اخیر،تحلیل شبکه های اجتماعی که به معنی کاوش و جستجو در شبکه های اجتماعی، جمع آوری اطلاعات و داده های موجود در این شبکه ها و تحلیل بر روی این اطلاعات است، از رونق چشم گیری برخوردار شده است.
شبکهی اجتماعی ساختاری اجتماعی است که از گره هایی(که عموماً فردی یا سازمانی هستند) تشکیل شده‌است که توسط یک یا چند نوع خاص از وابستگی به هم متصل اند، برای مثال: قیمت‌ها، الهامات، ایده‌ها و تبادلات مالی، دوست‌ها، خویشاوندی، تجارت، لینک‌های وب، سرایت بیماری‌ها (اپیدمولوژی) یا مسیرهای هواپیمایی. ساختارهای حاصل اغلب بسیار پیچیده هستند. تحلیل شبکه‌های اجتماعی^[۲] روابط اجتماعی را با اصطلاحات رأس^[۳] و یال^[۴] می‌نگرد. رأس‌ها بازیگران فردی درون شبکه‌ها هستند و یال‌ها روابط میان این بازیگران هستند.انواع زیادی از یال‌ها می‌تواند میان رأس‌ها وجود داشته باشد. نتایج تحقیقات مختلف بیانگر آن است که می توان از ظرفیت شبکه‌های اجتماعی در بسیاری از سطوح فردی و اجتماعی به منظور شناسایی مسائل و تعیین راه حل آنها، برقراری روابط اجتماعی، اداره امور تشکیلاتی، سیاستگذاری و رهنمون سازی افراد در مسیر دستیابی به اهداف استفاده نمود. به عنوان مثال، نتایج مطالعات در حوزه سیاستگذاری گردشگری نشان می دهد شبکه‌های اجتماعی به واسطه تاثیرگذاری روی متغیرهای رفتاری بر جذب گردشگران خارجی به مقاصد گوناگون تاثیرگذار هستند و می توان از این شبکه ها به منظور شکل‌گیری اعتماد و کاهش ریسک تصمیم‌گیری کاربران در انتخاب یک مقصد خاص گردشگری بهره گرفت. [۱]
در ساده‌ترین شکل یک شبکه ی اجتماعی نگاشتی از تمام یال‌های مربوط، میان رأس‌های مورد مطالعه‌است. شبکه ی اجتماعی هم چنین می‌تواند برای تشخیص موقعیت اجتماعی هر یک از بازیگران مورد استفاده قرار گیرد. این مفاهیم غالباً در یک نمودار شبکه ی اجتماعی نشان داده می‌شوند که درآن، نقطه‌ها رأس‌ها هستند و خط‌ها نشانگر یال‌ها میباشد.
فعالیت های متنوعی در تحلیل شبکه های اجتماعی صورت می گیرد که یکی از آنها را می توان پیش بینی لینک^[۵] در شبکه های اجتماعی دانست. در تحلیل شبکه های اجتماعی، ساختار این شبکه ها به صورت گراف هایی دیده می شود که در آن رأس های گراف نشان دهنده افرا د و اشیا، و لبه های گراف نمایانگر ارتباطات بین افراد و اشیا می باشد. قدرت پیش بینی احتمال ایجاد ارتباطات و لبه ها در آینده، توانایی هایی را در اختیار محققان و پژوهشگران قرار می دهد که از جمله آنها می توان به امکان ارائه پیشنهاد کالا و پیشنهاد دوست اشاره کرد. و آنچه در این پایان نامه صورت گرفته است به این حوزه از فعالیت های تحلیل شبکه های اجتماعی، مربوط می شود.
این پایان نامه به این صورت ساماندهی شده است که در ادامه این فصل پس از بیان مسایل و کلیات تحقیق، تعاریفی راجع به شبکه های اجتماعی، ویژگی ها و انواع آنها بیان شده است. در فصل دوم تحلیل شبکه اجتماعی، ضرورت ها و اهداف آن مورد بررسی قرار گرفته است. در فصل سوم مسایل مربوط به پیش بینی لینک، تعریف و رویکردهای موجود در آن بیان گردیده است. در فصل چهارم پس از شرح کامل روش های پیشنهادی، به تجزیه و تحلیل روش پیشنهادی با بهره گرفتن از استخراج ویژگی مناسب و بررسی شبکه اجتماعی مورد بحث پرداخته ایم و نهایتاً فصل آخر شامل نتیجه گیری ها، خلاصه ای از فعالیت های انجام شده و پیشنهادات برای ادامه کار می باشد.
۱-۲-کلیات و مسایل تحقیق
۱-۲-۱-تشریح و بیان موضوع تحقیق
شبکه اجتماعی ساختاری اجتماعی است که از گره هایی)که عموما فردی یا سازمانی هستند( تشکیل شده است و این گره ها توسط یک یا چند نوع خاص از وابستگی به هم متصل اند . تحلیل شبکه ها ی اجتماعی یا^[۶]SNAکه یک استراتژی برای تجزیه و تحلیل این ساختار است ساختار اجتماع را به شکل یک گراف و افراد و روابط اجتماعی را با اصطلاحات رأس و یال می نگرد. رأس ها کنشگران فردی یا سازمانی درون شبکه ها هستند و یال ها روابط و لینکهای میان این کنشگران هستند . انواع زیادی از لینکها نیز می تواند میان رأس ها وجود داشته باشد.
شبکه های اجتماعی شبکه هایی دینامیک هستند که مدام در حال افزایش اعضا و ارتباطات و لینکهای بین آنها هستند و متاسفانه این لینکها ممکن است به خاطر فرایند ایجاد ناقص و یا به خاطر این که این هنوز در این شبکه ها انعکاس نیافته اند)به عنوان مثال دوستان دنیای واقعی که یک ارتباط اجتماعی مجازی ایجاد نکرده اند(، از دست برود. در رابطه با این لینکها و ارتباطات مساله پیش بینی لینک^[۷] اهمیت پیدا می کند. این مساله به معنی پیش بینی احتمال برقراری یک ارتباط بین دو رأس است ، با دانستن این مساله که در حال حاضر ارتباطی بین این دو رأس وجود ندارد. سه رویکرد برای انجام پیش بینی لینک وجود دارد:
اولی شامل مدل های سنتی )غیربیزین( است که مجموعه ای از ویژگی ها را برای آموزش یک مدل دسته بندی باینری استخراج می کند. در این حالت هر نقطه داده به یک جفت رأس در گراف شبکه اجتماعی مربوط می شود. در اینجا برای هر جفت رأس تصمیم می گیریم که برای آن لینک وجود داشته باشد یا نداشته باشد. از آنجایی که پیش بینی لینک در این حالت تبدیل به یک دسته بندی باینری شده است از همه ابزار رایج دسته بندی بانظارت مثل naive bayes ، شبکه های عصبی، SVM ، k نزدیکترین همسایه و غیره می توان استفاده نمود. مساله اصلی در این رویکرد تعیین ویژگی های مناسب برای دسته بندی است.
دومی، رویکردهای احتمالاتی است که احتمال الحاق موجودیت ها در یک شبکه اجتماعی را با بهره گرفتن از مدل های گرافیکی بیزین مدل می کند. ایده اصلی در استفاده از مفاهیم بیزین، بدست آوردن یک احتمال ثانویه است که به شانس اتصال یک جفت رأس که مورد نظر ماست اشاره دارد. مزیت این روش این است که این مقدار خود می تواند به عنوان یک ویژگی مطرح شود.
و رویکرد سوم رویکردهای جبرخطی-آماری است که شباهت بین ندها در یک شبکه را با بهره گرفتن از ماتریس های شباهت کاهش رتبه محاسبه می کند. این الگوریتم ها روشی را پیشنهاد می دهد که یک تابع F را که مستقیماً روی ماتریس مجاورت یا ماتریس لاپلاسین گراف کار می کند، آموزش می دهد.
۱-۲-۲-ضرورت انجام تحقیق
پیش بینی لینک یک امر مهم برای تحلیل شبکه های اجتماعی است که کاربردهایی در حوزه های دیگر مثل بازیابی اطلاعات، بایوانفورماتیک و تجارت الکترونیک دارد. در حوزه علم وب و اینترنت می تواند در کارهایی از قبیل ایجاد ابرلینک وب اتوماتیک و پیش بینی ابرلینک سایت های وب کاربرد داشته باشد. در تجارت الکترونیک، یکی از مهم ترین کاربردهای آن ایجاد سیستم های پیشنهاد دهنده است . در بایو انفورماتیک می تواند در پیش بینی تعامل پروتئین پروتئین PPI و یا برای تفسیر گراف PPI مورد استفاده قرار گیرد. و از همه مهم تردر کاربردهای مربوط به امنیت، می تواند برای شناسایی گروه ها ی مخفی تروریست ها و مجرمان، ردیابی فعالیت های این شبکه ها و یا حذف رأس های آنها و ایجاد اختلال به کار رود و نیز به عنوان یک پیشنهاد دهنده دوست به منظور پیشبرد اهداف سیاسی، اعتقادی، اقتصادی و غیره مورد استفاده قرار گیرد.
بنابراین پیش بینی لینک به دلیل کاربردهایی که در مسایل مختلف اجتماعی، اقتصادی، سیاسی، دفاعی و امنیتی، و غیره دارد، یکی از مباحث مورد اهمیت در تحلیل شبکه های اجتماعی است.
در حال حاضر روش های بسیاری برای انجام عمل پیش بینی لینک ارائه شده و مورد استفاده قرار گرفته است. اما به دلیل اهمیت موضوع و کاربردهای وسیعی که خصوصاً در سال های اخیر داشته است، این مسأله هنوز باز است و تلاش ها برای ارائه راه حل های دقیق تر همراه با کارایی بالاتر همچنان وجود دارد. خصوصاً این که برخی از کاربردها مانند کشف و شناسایی گروه های مجرمان و تبهکاران نیاز به دقتی بالا دارد و هزینه اشتباه در آن زیاد است.
باتوجه به این مسأله، شناخت، تعیین و انتخاب ویژگی هایی که بتواند در بهبود پیش بینی ها موثر باشد بسیار با اهمیت جلوه می کند و نیز انتخاب روش و الگوریتمی که با هزینه کمتر، پاسخ بهتری را در ارائه پیش بینی ها ارائه کند، دارای اهمیت است.
شبکه های بیزین^[۸] در زمینه استدلال احتمالی به طور گسترده مورد استفاده قرار می گیرند. شبکه های بیزین به درخت متصل بر روی احتمالات استدلال شده تبدیل می شوند.اخیرا شبکه های بیزین به تجزیه زیرگراف اصلی ماکزیمم درخت متصل تبدیل می شوند و بیشتر ازدرخت های متصل کاربرد دارند.شبکه های بیزین تکنولوژی ایده آلی را برای ترکیب منبع اجتماعی فراهم می آورند[۱۶]. شبکه بیزین یک مدل گرافیکی برای نمایش احتمالات ما بین متغیرهای مورد نظر می باشد . [۱۸ , ۱۹]
استفاده از شبکه های بیزین به منظور درک پیچیدگی شبکه ها به منظور فهمیدن پیچیدگی شبکه های اجتماعی ،رفتار محلی اشخاص یا عامل های شبکه های اجتماعی باید درک شود و همچنین چگونه آنها با هم عمل می کنند و با محیط چگونه تعامل برقرار میکنند میباشد.به منظور مدل کردن این رفتار محلی بین عامل ها از تکنیک های شبکه های بیزین استفاده میکنیم. رفتارهای محلی را با بهره گرفتن از متریک ها اندازه گیری میکنیم واز شبکه های بیزین برای مدل کردن روابط متقابل بین متریک ها که به عنوان رفتارهای محلی هستند استفاده میکنیم و لینک ها بین اشخاص که در رفتارشان ظاهر میشود شکل میگیرد.