پایان نامه بهینه سازی پیش بینی لینک در شبکه های اجتماعی به کمک منطق فازی

مقطع کارشناسی ارشد ناپیوسته رشته مهندسی کامپیوتر

چکیده

امروزه محبوبیت سایت های شبکه های اجتماعی در بین افراد غیر قابل انکار است، سایت هایی که امکانات زیادی را برای ارتباطات بین افراد در اختیار کاربران قرار می دهند. یکی از مشکلات اساسی در آنالیز این نوع شبکه ها پیش بینی ارتباطات جدید بین افراد شبکه می باشد.

روش فازی به عنوان یکی از روش های مطرح در هوش مصنوعی، راه ساده ای را برای ساخت نتیجه ی صریح، مبهم، نویزدار و مفقود شده را مهیا می سازد. در نتیجه منطق فازی به ابزاری برای مدل کردن پیچیدگی های دنیای واقعی بدل شده است. این مدل ها معمولا از موارد مشابه خود بسیار دقیق تر بوده و نتایج دقیق تری به ما ارائه می دهند. به همین دلیل منطق فازی پتانسیل لازم برای ارئه ی لینک پیشنهادی دقیق تر را خواهد داشت و چارچوبی که در این تحقیق ارائه خواهیم داد بر اساس این منطق توسعه خواهد یافت.

با توجه به رویکرد های فوق ما در این تحقیق با ارائه ی چارچوبی پیشنهادی جهت ارائه ی الگوریتمی هوشمند بر اساس ترکیب منطق فازی با الگوریتم های CN، Jaccard ، PA که الگوریتم هایی برای پیش بینی لینک در گراف اجتماعی هستند، سعی در بهبود نتایج حاصله نمودیم. بررسی نتایج حاصله نشان داد که الگوریتم پیشنهادی دقت بیشتری در پیش بینی لینک داشته اما به دلیل وجود مراحل فازی و دفازی سازی، سرعت کمتری را دارا می باشد.

کلمات کلیدی:

پیش بینی لینک در شبکه های اجتماعی- منطق فازی- الگوریتم های پیش بینی لینک بر مبنای شباهت

فصل اول

مقدمه و طرح مسئله

مقدمه:

شبکه‌ های اجتماعی، نسل جدیدی از وب‌سایت‌ ها هستند که این ‌روزها در کانون توجه کاربران شبکه جهانی اینترنت قرار گرفته‌اند. این گونه سایت‌ها بر مبنای تشکیل اجتماعات آنلاین فعالیت می‌کنند و هر کدام دسته‌ای از کاربران اینترنتی با ویژگی خاصی را گرد هم می‌آورند. شبکه‌ های اجتماعی را گونه‌ای از رسانه‌های اجتماعی می‌دانند که امکان دستیابی به نحوه جدیدی از برقراری ارتباط و به اشتراک‌گذاری محتوا در اینترنت را فراهم آورده‌اند. صدها میلیون نفر از کاربران اینترنت عضو صدها شبکه‌ اجتماعی مختلف هستند و بخشی از فعالیت آنلاین روزانه‌شان در این سایت‌ها می‌گذرد .

پیش بینی وقوع لینک ها، یک مساله اساسی و بنیادین در شبکه ها می باشد. در موضوع پیش بینی لینک، نمایی از یک شبکه داده می شود و مایل هستیم که بدانیم در آینده نزدیک، احتمالا چه تراکنش هایی میان اعضای فعلی شبکه روی می دهد و یا اینکه کدام یک از تراکنش های موجود را از دست می دهیم. هر چند این مساله به صورت گسترده ای مورد مطالعه و بررسی قرار گرفته است؛ با این حال، مشکل چگونگی ترکیب بهینه و موثر اطلاعات حاصل از ساختار شبکه با داده های توصیفی فراوان مربوط به گره و یال، تا حد زیادی پابرجا می ماند. L. Backstrom, , 2011))

برای مدلسازی شبکه های اجتماعی، از گراف استفاده می کنند که در آن افراد گره ها را تشکیل می دهند و روابط بین افراد با یال ها نمایش داده می شود. در این بین یک گراف اجتماعی بزرگ به وجود می آید.

ما در این کار سعی خواهیم نمود که با تحلیل شبکه های اجتماعی ارتباطات احتمالی را پیش بینی نماییم. پیش بینی ارتباطات یک زیرشاخه از تحلیل شبکه های اجتماعی می باشد که در آن بایستی با توجه به مشاهدات و ارتباطات موجود، یک سری ارتباطات را که به صورت مستقیم قابل مشاهده نیستند یا وجود ندارند استنتاج کرد یا حدس زد.

در این فصل دلیل پرداختن به موضوع پروژه و صورت مساله آن مورد بررسی قرار می گیرد. بدین منظور ابتدا مقدماتی در رابطه با شبکه های اجتماعی، گراف اجتماعی، منطق فازی، پیش بینی لینک در شبکه های اجتماعی به اختصار مطالبی ارائه می شود، سپس مساله ای که پایان نامه سعی در حل آن دارد مطرح می گردد و در انتها رویکرد بکار رفته در تحقیق و ساختار پایان نامه ارائه می شود.

هدف اصلی تحقیق بررسی روش­های موجود در زمینه پیش بینی لینک ارتباط جدید در شبکه های اجتماعی و ارائه راهکار جدید به کمک منطق فازی در زمینه پیش بینی لینک در گراف اجتماعی می باشد.

1-2- شبکه های اجتماعی (پرهیزکار، 1392)

در سال های اخیر فضای اینترنت اهمیت بیشتری در زندگی روزانه مردم پیدا کرده است. مردم از اینترنت برای ارتباط برقرار کردن با دیگران، خرید و فروش الکترونیکی محصولات، جستجوی اطلاعات و انجام بسیاری کارهای دیگر استفاده می کنند و بدین شکل، اینترنت به یک شبکه اجتماعی گسترده تبدیل گردیده است.

شبکه ی اجتماعی ساختاری اجتماعی است که از گره هایی(که عموماً فردی یا سازمانی هستند) تشکیل شده‌ است که توسط یک یا چند نوع خاص از وابستگی به هم متصل اند، برای مثال: قیمت‌ها، الهامات، ایده‌ها و تبادلات مالی، دوست‌ها، خویشاوندی، تجارت، لینک‌های وب، سرایت بیماری‌ها (اپیدمولوژی) یا مسیرهای هواپیمایی. ساختارهای حاصل اغلب بسیار پیچیده هستند. شبکه های اجتماعی گروهی از افراد یا سازمان های دارای سلیقه یا منافع مشترک هستند که برای دستیابی به اهداف خاصی گرد می آیند. تحلیل شبکه‌های اجتماعی روابط اجتماعی را با اصطلاحات رأس و یال می‌نگرد. هر عضو را یک بازیگر[1] می گویند. ویژگی شبکه های اجتماعی وجود روابط [2] و تعاملات[3] پیچیده بین بازیگران است. رأس‌ها بازیگران فردی درون شبکه‌ها هستند و یال‌ها روابط میان این بازیگران هستند. انواع زیادی از یال‌ها می‌تواند میان رأس‌ها وجود داشته باشد. نتایج تحقیقات مختلف بیانگر آن است که می توان از ظرفیت شبکه‌های اجتماعی در بسیاری از سطوح فردی و اجتماعی به منظور شناسایی مسائل و تعیین راه حل آنها، برقراری روابط اجتماعی، اداره امور تشکیلاتی، سیاستگذاری و رهنمون سازی افراد در مسیر دستیابی به اهداف استفاده نمود. به عنوان مثال، نتایج مطالعات در حوزه سیاستگذاری گردشگری نشان می دهد شبکه‌های اجتماعی به واسطه تاثیرگذاری روی متغیرهای رفتاری بر جذب گردشگران خارجی به مقاصد گوناگون تاثیرگذار هستند و می توان از این شبکه ها به منظور شکل‌گیری اعتماد و کاهش ریسک تصمیم‌گیری کاربران در انتخاب یک مقصد خاص گردشگری بهره گرفت.

در ساده‌ترین شکل یک شبکه ی اجتماعی نگاشتی از تمام یال‌های مربوط، میان رأس‌های مورد مطالعه‌است. شبکه ی اجتماعی هم چنین می‌تواند برای تشخیص موقعیت اجتماعی هر یک از بازیگران مورد استفاده قرار گیرد. این مفاهیم غالباً در یک گراف شبکه ی اجتماعی نشان داده می‌شوند که درآن، نقطه‌ها رأس‌ها و خط‌ها نشانگر یال‌ها هستند.

از دلایل عمده تشکیل شبکه های اجتماعی می توان به روابط فردی، روابط کاری ، روابط علمی، سلیقه ها و علایق و تفریحات مشترک،  انگیزه های اجتماعی-سیاسی اشاره نمود. (پرهیزکار، 1392)

1-3-تحلیل شبکه های اجتماعی[4] (پرهیزکار، 1392)

آنالیز و یا تحلیل شبکه های اجتماعی به معنای مطالعه ویژگی های شبکه های اجتماعی و روابط بین افراد و بخش های یک شبکه با رویکرد تئوری شبکه ای یا گراف است.

تحلیل شبکه های اجتماعی نوعی مطالعه میان رشته ای در حوزه های مختلف است، از جمله: جامعه شناسی، علوم اطلاعات، علوم ارتباطات، مدیریت و سازمان، انسان شناسی، جغرافیا، روانشناسی اجتماعی، زبان شناسی، اپیدمیولوژی، اقتصاد و بازرگانی.

تحلیل شبکه اجتماعی رویکرد پژوهشی است ، که به الگوهای روابط بین افراد، گروه ها و سازمانها می پردازد و ابتدا در جامعه شناسی، روانشناسی اجتماعی و علوم ارتباطات شکل گرفت. دانشمندان حوزه وب سنجی از این رویکرد در مطالعات حوزه وب استفاده کرده اند و به تحلیل شبکه های اجتماعی محیط پیوسته پرداخته اند. آنها معتقدند، شبکه های رایانه ای نیز به دلیل اینکه می توانند افراد و سازمان ها را با هم مرتبط کنند، امکان این را دارند که بر اساس تحلیل های شبکه اجتماعی مورد مطالعه قرار بگیرند. بسیاری انواع شبکه های اجتماعی دیگر در محیط مجازی شکل گرفته و هر روز هم گسترش بیشتری می یابد. آنالیز شبکه‌های اجتماعی علاوه بر سروکارداشتن با اشخاص (افراد، سازمان‌ها، ایالات) به عنوان واحدهای گسسته ی تحلیل، برروی چگونگی ساختار رشته‌ها که اشخاص و روابط میان آن‌ها را تحت تاثیر قرار می‌دهد نیز تمرکز می‌کند.

شکل یک شبکه ی اجتماعی به تعیین میزان سودمندی شبکه برای افراد آن شبکه کمک می‌کند. به طور جزئی شبکه‌های محکم برای اعضایشان نسبت به شبکه‌هایی که تعداد زیادی اتصالات ضعیف برای افراد خارج از شبکه ی اصلی دارند، کمتر مفید واقع می‌شوند. بیشتر شبکه‌های باز با اتصالات اجتماعی و رشته‌های ضعیف، شانس بیشتری برای دسترسی به ایده‌ها و دست آوردهای جدید نسبت به شبکه‌های بسته با رشته‌های طویل فراهم می‌آورد. به بیان دیگر گروهی از دوستان که تنها دارای ارتباط با یکدیگر هستند، اطلاعات و دست آوردهای یکسانی را به اشتراک می‌گذارند. اما گروهی از افراد که دارای ارتباط با بخش‌های اجتماعی دیگر هستند شانس بیشتری برای دسترسی به محدوده ی وسیعتری از اطلاعات دارند. افراد برای دستیابی به موفقیت بهتر است که با شبکه‌های گوناگونی ارتباط داشته باشند تا اینکه ارتباطات زیادی درون یک شبکه داشته باشند. به طور مشابه افراد می‌توانند تأثیرگذاری و ایفای نقش به عنوان واسطه در برقراری ارتباط بین دو شبکه که به هم متصل نیستند را تمرین کنند.(این کار پر کردن سوراخ‌های ساختاری نامیده می‌شود).

آنالیز شبکه‌های اجتماعی چشم انداز متناوبی را ایجاد می‌کند که در آن خواص افراد نسبت به ارتباطات و رشته‌های میان آن‌ها در شبکه از اهمیت کمتری برخوردار است. این معبر ایجاد شده‌است تا برای توضیح بسیاری از پدیده‌های جهان واقعی مفید واقع شود، اما مجال کمتری برای نمایندگی‌های فردی باقی می‌گذارد تا توانمندی‌های فردیشان روی موفقیت تأثیرگذار باشد زیرا بخش زیادی از این توانمندی‌ها درون ساختار شبکه باقی می‌ماند.

1-4- مقدمه ای برای منطق فازی (میرزاده رهنی،1391)

در سال 1965 میلادی مقاله ای با عنوان مجموعه های فازی[5] توسط دکتر لطفی عسگرزاده[6] استاد ایرانی الاصل دانشگاه کالیفرنیا برکلی( که خود را به اختصار زاده می نامد) در مجله اطلاعات و کنترل[7] به چاپ رسید که اولین سند منتشر شده در این زمینه و آغاز تحولی قابل توجه در علوم ریاضی و مهندسی است. در این مقاله مجموعه فازی به عنوان مجموعه ای با مرزهای غیر دقیق معرفی شده است. در سال 1974 میلادی، زاده عبارت منطق فازی[8] را در مقاله دیگری معرفی و به کار برد. در این مقاله همچنین اصطلاح استدلال تقریبی[9] نیز بیان و تعریف شده است. در دهه 1960 و پیش از آن که زاده مقاله اول خود را منتشر کرد وی متخصصی صاحب نظر در زمینه تحلیل سیستم ها[10] بود. نیاز به ریاضیات و منطق فازی در این سال ها به ذهن زاده رسید. این نیاز از آن جا ناشی می شد که علی رغم تلاش وسیعی که وی و همکارانش در تحلیل سیستم های دینامیکی به کار می برند و علی رغم پیشرفت ها و موفقیت های گسترده ای که در این زمینه کسب کرده بودند، در تحلیل سیستم هایی که با روابط انسانی سر و کار دارند ناموفق بودند. سوالی که ذهن زاده را مشغول کرده بود آن بود که چرا تحلیل سیستم هایی مانند سیستم های فیزیکی مکانیکی و الکترونیکی و یا به عبارتی سیستم هایی که در دینامیک آن ها روابط انسانی موثر نیست[11] با کمک ریاضیات کلاسیک مقدور و ممکن است ولی در سیستم هایی که با موجودات زنده[12] سر و کار دارند مانند سیستم های اقتصادی، اجتماعی، بیولوژیکی، فلسفی و حقوقی تحلیل سیستم های پیچیده و در بسیاری موارد غیر ممکن است. پاسخ زاده به این سوال آن بود که:

سیستم هایی که با موجودات زنده سر و کار دارند سیستم هایی هستند که مرزها و محدوده های تیز[13] ، صریح و دقیق ندارند و آن ها را می توان به عنوان سیستم هایی با مرزهایی غیردقیق طبقه بندی کرد. علت عدم توانایی ریاضیات در تحلیل سیستم های با مرزهای غیر دقیق نیز آن است که در ریاضیات کلاسیک اصولا مجموعه های با مرزهای غیردقیق تعریف نشده اند. به عبارت دیگر ریاضیات کلاسیک تنها می تواند به تحلیل سیستم هایی بپردازد که در مجموعه های صریح و دقیق تعریف شده باشند. در ریاضیات کلاسیک همه چیز با "آری " یا "نه" است. یا یک عنصر متعلق به مجموعه ای هست یا متعلق به آن مجموعه نیست. چراغ یا روشن است یا خاموش. همه چیز یا “A” است یا “Not A” . عناصر نمی توانند تا اندازه ای عضو یک مجموعه باشند. "زاده" می گفت: ریاضیات جدیدی باید ابداع شود که بتواند مجموعه هایی را که اعضا آن الزاما تعلق صددرصد به آن مجموعه ندارند بیان نماید. وی چنین مجموعه هایی را مجموعه های فازی نامید. کلمه فازی از نظر لغوی یعنی کرکی، درهم و برهم، پرزدار، مبهم، ناروشن، تار.

در مجموعه های فازی، برای تعیین میزان تعلق هر عضو به آن مجموعه کمیتی با عنوان " درجه عضویت" [14]یا میزان عضویت معرفی شود که بین صفر و یک تغییر می کند. درجه عضویت صفر مشخص کننده آن است که عضو هیچگونه تعلقی به آن ندارد. درجه عضویت یک نشان دهنده آن است که تعلق عضو به مجموعه موردنظر قطعی و صددرصد نسبی است و از صفر تا صددرصد برایی عناصر مختلف می تواند تغییر کند. مثلا اگر مجموعه "افراد قد بلند یک شهر" را در نظر بگیریم با یک مجموعه فازی سروکار داریم که افراد مختلف متناسب با طول قدشان میزان عضویتی بین صفر و یک در این مجموعه پیدا می کنند.

یکی از ویژگی های مجموعه های فازی آن است که آنها "وابسته به موضوع"[15] هستند. این برخلاف مجموعه های صریح[16] در ریاضیات کل یک است که "مستقل از موضوع"[17] می باشند. در حالی که عبارت "دایره" به عنوان یک عبارت ریاضی در تهران و توکیو و سوئد یک مفهوم را می رساند. عبارت "قدبلند" در این شهرها مفهوم یکسانی ندارد. "قدبلند" یک مجموعه فازی و دایره یک مجموعه صریح است. دایره متعلق به ریاضیات کلاسیک و قدبلند متعلق به ریاضیات فازی است.

Abstract

Nowadays the popularity of social networking sites among people is undeniable, web Sites provide a lot of facilities of communication‘s people for users. These social networks are growing very fast and adding new members to the network or creating a new relationship between people in the network, these networks are expanding. One of the fundamental problems in this kind of networks is analyzing to predict new connections between people in the network.

Fuzzy method as one of the techniques in artificial intelligence provides a simple way to make a definitive, ambiguous, noisy, missing conclusion. As a result, fuzzy logic has become a tool for modeling the complexities of the real world. These models are usually much more accurate than Similar models and they can provide us with more accurate results. So fuzzy logic has sufficient potential to provide More accurate Recommended Links and the framework is presented in this thesis have been developed based on this logic.

Based on the above approach, In this thesis by offering a framework for the development of the intelligent algorithm based on combining fuzzy logic with algorithms like CN, Jaccard, PA which are predicting the links in the social graph, We tried to improve results.

The results showed that the proposed algorithm has more accurate predictions, but because of the fuzzy and Dfazy, it has less speed.