ارایه روشی جدید برای پیش بینی لینک بین رأس های موجود درشبکه های اجتماعی

چکیده

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

مقدمه

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

روش شناسی پژوهش

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

که در آن (Cn(u,z تعداد همسایه های مشترک دو رأس z و u است.رابطة بالا برای تعداد بالای دوستان مشترک رأس میانی با دو رأس اصلی، امتیاز مثبت قائل می شود و به همین دلیل، مجموع این تعداد در صورت معادله قرار داده شده است تا میزان شباهت را افزایش دهد. از سوی دیگر، برای درجة رأس میانی امتیاز منفی در نظر گرفته شده ودر مخرج معادله جای می گیرد.در مقایسه هایی که بین این روش و روش های معرفی شده صورت گرفته است، مشاهده می شود که این معیار کارایی قابل قبولی نسبت به روش های دیگر دارد که در ادامه این کارایی اثبات می شود.

یافته های پژوهش

در این بخش الگوریتم پیشنهادی این پژوهش با سیزده ویژگی شرح داده شده، مقایسه می شود وکارایی آن به صورت تجربی اثبات خواهد شد . برای این کار، از دو مجموعه داد ه واقعی Facebook و Epinions استفاده شده است. مجموعه داده های شبکه اجتماعیEpinionsکه یک شبکة اجتماعی به شمار می رود در نظر گرفته شده و از 49 k کاربر و k 487یال بین جفت رأس ها تشکیل شده است مجموعه داده ای Facebook که در 30 اکتبر 2009جمع آوری شده شامل 3/7k کاربر و از  13.7k یال است. برای ارزیابی و مقایسه روش ها و الگوریتم های مختلف پیشگویی پیوند با روش پیشنهادی، از معیار MAP استفاده شده است، تا در بررسی کارایی الگوریتم مورد نظر، روی ترتیب دوستان پیشنهاد داده شده با این رو شها، تأکید بیشتری شود. معادله MAPبه صورت رابطه زیر تعریف می شود:

در این رابطه N تعداد کاربران در مجموعه دادة آزمایشی Rتعداد کاربران مرتبط با کاربر Uمجموعه آزمایشی و precision: مقدار precision در k امین موقعیت فهرست پیشنهادها برای uاست توجه کنید که MAP در واقع هر دو مقدار precisionوrecall را درخود دارد و از نظر هندسی در زیر منحنی precision-recall جای دارد.به منظور ارزیابی روش ها، از هر مجموعه آموزشی به صورتی کاملاً تصادفی، 1000 رأس انتخاب شد و با در نظر گرفتن همه ارتباطات میان آنها، پس از محاسبه و مقایسة مقادیر معیارها، آزمایش های لازم روی آنها انجام گرفت. از آنجایی که با این انتخاب همه رأس ها، حتی رأس هایی که هنوز دوستی ندارند و به اصطلاح افراد تازه وارد این شبکه اجتماعی به شمار میروند نیز انتخاب می شوند، این امکان وجود دارد که در نتایج همه انواع روش های معرفی شده، با دقت پایینی مواجه شویم؛ چراکه این نوع رأس ها، با مشکلی به نام آغاز سرد  برخورد می کنند که یک مشکل رایج در ارائه پیشنهادهای شبکه های اجتماعی محسوب می شود. در این حالت، اطلاعاتی از فرد تازه وارد در دست نیست تا بتوان از این طریق، علایق وی را شناسایی کرد و پیشنهادهای مناسب را به او ارائه داد در شبکه های اجتماعی مشهوری چون Facebook که از روش«  دوست دوست » برای ارائة پیشنهادها استفاده می کنند، این مشکل از راه بررسی اسامی موجود در پست الکترونیکی فرد و تطابق آن با اعضای شبکه اجتماعی و ارائه اسامی تطابق یافته، از بین می رود.در گوگل پلاس نیز برای حل این مشکل، فرد را وادار می کنند که در آغاز ورود به شبکه، ده نفردوست را انتخاب کرده و معرفی کند.برای تفکیک داده های آموزشی و آزمایشی در هر دو مورد از اعتبارسنجی ضربدری ده لایه ای  استفاده شد و الگوریتم ها به کمک زبان نرم افزاری جاوا، به اجرا گذاشته شدند . مقایسه بین الگوریتم های مختلف در رابطه با مجموعه داده ه ای انتخابی و نتایج آن، در جدول 1 نشان داده شده است.

همان طور که در جدول 1 مشاهده می شود، روش جدید در رابطه با مجموعه داده Epinions پس از معیار ضریب خوشه بندی، بهترین جواب را داده است و در مقایسه با سایر معیارها بهتر عمل کرده است. در مورد Facebook نیز به کمک روش پیشنهادی، در مجموع بهترین پاسخ در رابطه با مجموعه دادة انتخابی به دست آمده است؛ در حالیکه در این مجموعه داده، ضریب خوشه بندی دارای کارایی بسیار پایینی بوده است. بنابراین همان گونه که در جدول 1 مشاهده می شود، روش جدید در مورد هر دو مجموعه داده در مقایسه با سایر رو شها، پاسخهای مناسب و قابل قبولی خواهد داشت و پیش بینی های خوبی را ارائه می دهد.

نتیجه گیری  

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

منابع:

ارائة روشی جدید برای پیشگویی پیوند بین رأس های موجود درشبکه های اجتماعی اعظم کی پور مرتضی براری ، حسین شیرازی

پیش بینی لینک مبتنی بر زمان در شبکه های دو بخشی

پیش بینی لینک مبتنی بر زمان در شبکه های دو بخشی

چکیده

شناخت هرچه بیشتر مکانیزم رفتاری انسان ها در شبکه ها، بر فهم ما از نحوه تکامل و رشد شبکه ها تاثیر بسزایی دارد. در یک شبکه آنلاین رفتار انسان ها را می توان همچون یک گراف دو بخشی user-object در نظر گرفت که در آن کاربران توسط لینک هایی به اشیا متصل هستند. پیشبینی لینک از روش هایی است که توسط آن می توان رفتار آینده افراد را پیشبینی کرد. در این مقاله پیش بینی لینک از دیدگاه تفکیک زمانی مورد بررسی قرار می گیرد. در تفکیک زمانی نشان می دهیم که دنباله پیمایشات هر فرد را می توان به چندین دنباله پیمایش با بازه زمانی مختلف تبدیل کرد. همچنین بحث سالخوردگی لینک ها را بیان می کنیم و تاثیر گذر زمان بر توانایی لینک ها برای پیش بینی لینک های آینده نشان خواهیم داد. از اطلاعات زمانی برای ساخت شبکه دو بخشی وزن دار زمانی (TWBN) استفاده می کنیم و سپس با استفاده از فیلترهای مشارکتی سعی در ساخت یک سیستم پیش بینی لینک خواهیم داشت.

تفکیک زمانی و ساخت گراف TWBN:

تفکیک زمانی:

کاربران در میان منابع موجود در سایت های اطلاعاتی به دنبال علایق خود می گردند. علایق کاربران در طول زمان تغییر می کند. سابقه پیمایش کاربران در واقع از زیر دنباله هایی تشکیل شده که هر کدان بیانگر علاقه کاربر در یک دوره خاصل است. در جدول 1 سابقه پیمایشات پنج کاربر شبکه نشان داده شده است. همانطور که می بینید دنباله پیمایشات کاربر از روز 3 شروع و تا روز 10 ادامه می یابد. در این بازه گاهی کاربر در مدت زمان محدودی چندین انتخاب داشته و سپس تا چندین روز بعد انتخاب دیگری ندارد. برای نمونه کاربر 1 از بازه زمانی 3 تا 4 سه انتخاب و از بازه 9 تا 10 دو انتخاب دارد. فاصله زمانی میان این دو بازه به 5 روز می رسد. مسلما آیتم های انتخاب شده توسط کاربر که در یک بازه بودند رابطه بیشتری نسبت به آیتم هایی که در بازه زمانی متفاوت بوده اند دارند. در شبکه های واقعی اختلاف این بازه ها بیشتر است. اگر بتوان آیتم های پیموده شده نزدیک به هم را تفکیک کرد بهتر می توان شباهت میان آنها را مشخص کرد. در این مقاله ما دنباله پیمایشات کاربران را به بازه های مختلف تفکیک می کنیم. برای تفکیک سازی پیمایشات اینگونه عمل می شود که اگر فاصله بین دو انتخاب متوالی کاربر از k روز بیشتر باشد. این امر نشان دهنده این است که کاربر علاقه اش عوض شده است. مثلا اگر k=5 در نظر بگیریم پیمایشات کاربر 1 به دو زیر پیمایش تقسیم می شود. بعد از تفکیک سازی سابقه پیمایشات هر کاربر به زیر دنباله های متناظر، از این زر دنباله ها برای ساخت سطرهای ماتریس پیمایش استفاده کنیم. (هر زیر دنباله یک سطر را نشان می دهد). ماتریس پیمایش A[m*n] از m کاربر و n آیتم تشکیل شده و درایه [i,j] این ماتریس مخالف صفر است اگر کاربر i، آیتم j را پیموده باشد. سطرهای این ماتریس دنباله پیمایشات کاربران را نشان می دهد. انتخاب اندازه K از اهمیت بالایی برخوردار است. اگر K خیلی کوچک باشد موجب می شود که ماتریس پیمایش تنگ شود. اگر K بزرگ باشد باعث می شود که تفکیک زمانی رخ ندهد. پیدا کردن مقدار مناسب برای K خیلی مهم است.

ساخت گراف TWBN

با گذشت زمان از ارش لینک موجود برای پیشبینی لینک های آینده کاسته می شود. هرچه فاصله شکل گیری یک لینک با زمان فعلی بیشتر باشد (لینک پیر) تاثیر آن در پیش بینی لینک های فعلی کمتر خواهئ بود و بلعکس/ برای اینکه تاثیر گذر زمان را بر لینکها مدل کنیم ما از فاصله زمانی در جهت وزن دار کردن لینک ها استفاده می کنیم. این وزن بیانگیر اهمیت لینک در پیش بینی لینک های آینده است. ما از فرمول ارائه شده در مقاله 6 به عنوان معیاری در جهت وزن دهی لینک ها استفاده می کنیم.

در اینجا Tu,i زمانی را که کاربر U، آیتم I را پیموده و Now Time زمان فعلی را بیان می کند. الگوریتم پیشگو باید بالهای موجود در زمان و Now Time را پیشبینی کند. ضریب تاثیر اختلاف زمانی است و مقدار ≥ 0 است. یک مقدار ثابت و مقدار آن <1   0< است. اگر زیاد باشد، i  و Wu بیشتر می شود. (تاثیر فاصله زمان کم خواهد شد). و بلعکس، هرچه توان بزگتر باشد مقدار Wu,i کوچکتر خواهد بود. در این مقاله ما مقدار را برابر با                       و =0.5 در نظر گرفته شده است.

ما از فرمول فوق برای وزن دهی بال های موجود در گراف استفاده می کنیم. نتیجه کار تشکیل گراف TWBN است.

فیلترهای مشارکتی:

یکی از موفق ترین رویکردها در بحث سیستم های پیش بینی لینک، فیلترهای مشارکتی (CF) هستند که با استفاده از تجربه وب سعی در پیشبینی لینک های آینده دارد. ایده اصلی CF این است که اگر دو کاربر x و y آیتم های مشابه ای را پیموده باشند امید است که در آینده عملکرد مشابه ای نیز داشته باشند. CF ها با استفاده از دیتا بیسی از پیمایشات قبلی کاربران سعی در پیشبینی عملکرد آینده کاربران جدید دارد. یکی گروهی از فیلترهای مشارکتی ها تکنیک های model- base CF هستند. این روش ها از ماتریس پیمایش کاربران برای ساخت یک مدل خاص بهره می جویند و سپس از این مدل برای پیشبینی عملکرد کاربران جدید استفاده می کند. مدل می تواند یک فرایند داده کاوی با یادگیری ماشین باشد. از نمونه های این روش می توان به Bayesian Belief net CF [16] و Clustering CF [14] و Item-base CF [18,17] اشاره کرد. در این مقاله ما از روش Item- base CF استفاده خواهیم کرد. ایده این روش بر این اصل استوار است که آیتم هایی که کاربر در آینده انتخاب می کند رابطه نزدیکی به آیتم هایی که او قبلا انتخاب کرده دارد. هرچه ارتباط میان یک آیتم با آیتم های پیموده شده قبلی کاربر بیشتر احتمال انتخاب آن بیشتر است. در این روش ماتریس مربعی I[n*n] ساخته می شود که درایه [I,j] آن شباهت آیتم i و j را نشان می دهد. برای سنجش میزان شباهت میان دو آیتم معیارهای متنوعی همچون کسینوس، فاصله اقلیدسی و همبستگی وحود دارد که ما از قانون همبستگی گیرسون استفاده می کنیم. این معیار وابستگی خطی میان دو متغیر را نشان می دهد. طبق این معیار، همبستگی (تغییرات همسو) میان دو متغیر تصادفی برابر است با

E عملگر امید ریاضی، cov کوواریانس، و نماد انحراف معیار استاندارد است. برای ساخت ماتریس I ما از ماترس مجاورت گراف TWBN استفاده می کنیم.

ارزیابی:

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

تفسیر آزمایش

همانطور که در شکل a.4 می بینید الگوریتم TWCF قادر بوده پیشبینی هایی با دقت بالاتری داشته باشد. این امر نشان دهنده این است که استفاده از تفکیک زمانی و بحث سالخوردگی لینکها توانسته تاثیر مثبتی در پشیبینی داشته باشد. نمودارها روندی نزولی دارند به این علت که هرچه اندازه مجموعه آموزش بیشتر می شود میزان پراکندگی ماتریس پیمایشات کمتر شده و در نتیجه شباهت میان آیتم ها بهتر تشخیص داده می شود. در جدول 2 مقادیر عددی ناشی از آزمایش نشان داده شده است .در شکل b.4 عملکرد الگوریتم ها بر حسب مقدار r نشان داده ایم. در این شکل محور افقی مقدار r و محور عمودی تعداد پیشبینی های درست را نشان می دهد. همانطور که می بینید روش پیشنهادی در مقایسه با دیگر الگوریتم ها از دقت بالاتری برخوردار است. روش های TWCF و TCF و CF همگی بر پایه همبستگی میان آیتم ها کار می کنند. در CF ما تاثیرات زمانی را در محاسبه همبستگی میان آیتم ها بکار نبردیم. در TCF ما تنها بحث سالخوردگی را در محاسبه همبستگی بکار بردیم و در TWCF ما هم بحث سالخوردگی و هم تفکیک زمانی را بکار بردیم و نشان دادیم که تفکیک زمانی موجب بهبود عملکرد می شود.

نتیجه گیری

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

معرفی کتاب

کتاب:

Trust-based Collective View Prediction

 

  که در سال 2016 توسطLuo, T., Chen, S., Xu, G., Zhou, J.منتشر شده و بخشهای ان به شرح زیر است:

Introduction

Related Work

Collaborative Filtering

Sentiment Analysis

Theoretical Foundations

Models, Methods and Algorithms

Framework for Robustness Analysis

Conclusions

برای تهیه این کتاب می توانید به لینک زیر مراجعه کنید:

http://www.springer.com/us/book/9781461472018

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

Friendlink: Link Prediction in Social Networks via Bounded Local Path Traversal

Abstract

Online social networks (OSNs) like Facebook,Myspace, and Hi5 have become popular, because they allow users to easily share content or expand their social circle.OSNs recommend new friends to registered users based on local graph features (i.e. based on the number of commonfriends that two users share). However, OSNs do not exploit all different length paths of the network. Instead, they consider only pathways of maximum length 2 between a user and his candidate friends. On the other hand, there are global approaches, which detect the overall path structure in a network, being computationally prohibitive for huge-size social networks. In this paper, we provide friend recommendations, also known as the link prediction problem, by traversing all paths of a bounded length, based on the “algorithmic small world hypothesis”. As a result, we are able to provide more accurate and faster friend recommendations. We perform an extensive experimental comparison of the proposed method against existing link prediction algorithms, using two real data sets (Hi5 and Epinions). Our experimental results show that our FriendLink algorithm outperforms other approaches in terms of effectiveness and efficiency in both real data sets

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

خلاصه حاصل از تجزیه و تحلیل مقاله

چکیده

شبکه های آنلاین اجتماعی ، دوستان جدید را به کاربران ثبت شده بر مبنای خصوصیات گراف محلی ( تعداد دوستان مشترک میان دوکاربر) پیشنهاد می دهد. هر چند شبکه های آنلاین اجتماعی ازتمام ظرفیت های مسیرشبکه استفاده نمی کنند. انها تنها بر روی مسیر های با حداکثر طول 2 میان یک کاربر  و دوست منتخب اش تمرکز دارند. از سوی دیگر، رویکردهای جهانی وجود دارند که تمامی ساختارهای مسیری در یک شبکه را که از نظر محاسبانی برای شبکه های اجتماعی بزرگ بسیار سخت است ، شناسایی می کنند. در این مقاله ما پیشنهادات دوست یابی را که به عنوان مشکل پیش بینی ارتباط(پیوند) شناخته می شود ،  با استفاده از پیمودن تمامی مسیرهای با طول محدود بر مبنای فرضیه های جهان کوچکِ الگوریتمی ، ارائه می دهیم. د رنتیجه ما قادر خواهیم بود تا پیشنهادات دوست یابی سریع و دقیق تری را فراهم آوریم . ما همچنین انواع روش های مشتق از روش مان را که برای انواع شبکه ها(مستقیم/غیر مستقیم/ثبت شده /غیر ثبت شده) به کار می رود را ارائه می دهیم. مقایسه تجربی میان روش های پیشنهادی در برابر الگوریتم های پیش بینی لینک ، با استفاده از پایگاه های داده ترکیبی و سه پایگاه داده واقعی ( فیس بوک،  اپینیون،HI5 ) انجام دادیم. ما همچنین نشان دادیم که با استفاده از اطلاعات درباره هر دو حاشیه های مثبت  و منفی می توانیم سیستم پیشنهادات دوستی را بهبود بخشیم.

شبکه های آنلاین اجتماعی مانند فیس بوک ، مای اسپس حاوی حجم گیگابایتی از داده هایی هستند که می توانند برای پیش بینی ان که چه کسی دوست چه کسی است کاوش شوند. شبکه های آنلاین اجتماعی اطلاعات کاربران اجتماعی را جمع می کنند ، و به دیگر افراد برمبنای دوستان مشترک شان پیشنهاد دوستی می دهند. در این مقاله که گستره کارهای قبلی است ما بروی پیشناهدات بر مبنای لینک هایی که  گره های یک شبکه های آنلاین اجتماعی را به هم مرتبط می سازد، تمرکز می کنیم.که دو روش عمده برای حل مشکل پیش بینی لینک وجود دارد. اولین که بر مبنای خصوصیات محلی یک شبکه است و به طور عمده بر روی گره های ساختار تمرکز دارد ، دومی بر مبنای خصوصیات جهانی است که  تمامی ساختارهای مسیری در یک شبکه را شناسایی می کند برای مثال یک رویکر محلی در شکل شماره 1 نشان داده شده است ،  فیس بوک  از این شکل پیشنهاد برای پیشنهادات دوستان جدید برای یک کاربر هدف استفاده می کند. "افرادی که ممکن است شما بشناسید ": لیست دوستان پیشنهادی بر مبنای تعداد دوستان مشترک هر دوست منتخب با کاربر هدف رتبه بندی می شود. در روش ما ما فرض می کنیم که یک فرد می تواند با فرد دیگر با مسیرهای بسیاری با طول های متفاوت متصل گردد( از طریق زنجیره انسانی( برای مثال در شکل 1 بر اساس شبکه اجتماعی موجود کاربر 1 می تواند با احتمالی مساوی می تواند از کاربر 4 و 7 پیشناد دوستی دریافت کند هر چند اگر ما مسیرهای طول 3 را درنظر بگیریم ، در انصورت کاربر 4  باید  احتمال بالاتری داشته باشد تا به عنوان یک دوست توسط کاربر 1 پیشنهاد داده شود. در مقایسه با روش های جهانی، که تمامی ساختارهای مسیری یک شبکه را شناسایی می کند ، روش ما کاراتر خواهد بود. به این معنا که  در روش ما بر مبنای مسیرهای محدودی است که زمان کمتری نیاز است و پیچیدگی کمتری نسبت به الگوریتم های جهانی دارد ، دلیل ان است که تنها مسیرهای طولL را در یک شبکه بر مبنای “فرضیه های جهان کوچک الگوریتمی “پیگیری می کنیم در حالیکه روش های جهانی تمامی ساختارهای مسیری را شناسایی می کنند.   روش ما خلاصه می شود به صورت زیر: ما یک شاخص تشابه گره ای جدید را تعریف کردیم که تمامی ویژگی های محلی و جهانی یک شبکه را بهره برداری می کند.

شکل شماره 1 مثالی از شبکه اجتماعی

روش پیشنهادی:

در این بخش ، با استفاده از یک مقال ، چارچوب روش ما با نام لینک دوستی  Friendlink   بیان می شود سپس ما مراحل الگوریتم پیشنهادی را انالیز می کنیم .  روش لینک دوستی  Friendlink   ، تشابه میان گره ها(نودها) در یک گراف غیر مستقیم ساخته شده از یک داده های ارتباطی را می یابد.  الگوریتم لینک دوستی  Friendlink    به عنوان داده ورودی از ارتباطات یک گراف   و به عنوان خروجی از ماتریس تشابه میان هر دو گره در  استفاده می کند . در نتیجه، پیشنهاد دوستی می تواند بر اساس وزن در ماتریس تشابه داده شوند.  در شکل 1.9 الگوریتم نشان داده شده است . اگر ما یک دوست جدید به کاربر شماره 1 بخواهیم پیشنهاد دهیم ، در ان نشانه مستقیمی برای این کار در ماتریس اصلی مجاورت  که در شکل شماره 2 نشان داده شده است ، وجود ندارد. بعد از اجرای .  الگوریتم لینک دوستی  Friendlink     ، میتوانیم ماتریس تشابه میان دو گره (نود) گراف   را پیدا کنیم و دوستان را بر اساس اهمیت پیشنهاد دهیم . در ابتدا ما ماتریس نزدیکیِ  را تغییر می دهیم به طوری که به جای داشتن میزان0/1 ، میزان ورودی(i.j) ماتریس لیستی از مسیرها ازi بهj باشد. ایده کار این است که اگر شما ماتریس نزدیکی0/1 یک گراف را داشته باشید و سپس ان را به ماتریس توانN افزایش دهید. در انصورت نتیجه داده های ورودی(I,j) نشان می دهند که چه میزان طول مسیر ام از گره viتا گرهvj وجود دارد ، در اینجا طول به تعداد حاشیه ها سنجیده می شود. سپس به جای شمارش ِ مسیرها ، ما به دنبال تمامی مسیرهای واقعی خواهیم بود. سپس ماتریس ضرب را از ماتریس مجاروت در خودش اجرا می کنیم اما به جای ضرب و اضافه کردن داده های وردی ، ما تمامی مسیرها از  گرهvi تا گرهvj را ایجاد می کنیم،  همانطور که در شکل شماره 4 نشان داده شده است ما تمامی مسیرهای طول 2 و3 را که هر گره در گراف  را به گره گراف دیگر متصل می کند نشان داده ایم . تمامی حلقه های موجود در مسیر حذف شده اند.

شکل 2: ماتریس نزدیکیA گراف

شکل شماره 3: ماتریس نزدیکیA گراف به توان 2

شکل شماره 4ماتریس کاربر که شامل تمامی مسیرها با طول 2 و 3 درگراف در مثال بیان شده

سپس ما تشابه میان گره  viو گره vjبرای هر مسیر با طول l تولید شده را آپدیت کرده به صورتی که گره آغازین viو گره مقصد vjمی باشد. برای محاسبه میزان تشابه میان گره viو vjما از  استفاده کردیم. در مثال ، فرض کنید ما تشابه میان کاربر1 با کاربر4 و 7 را می خواهیم محاسبه کنیم. به ترتیب . در ابتدا همانطور که در شکل 4 نشان داده شده است تشابه میان کاربر1و4  بر مبنای سه مسیر که انها را به هم وصل می کند محاسبه می شود . بر اساس هر یک از مسیرها و  دارای وزنی به میزان 0.1428 می باشد. (1 مسیر طول 2 که دو گره را به هم وصل می کند به 7 مسیر با طول 2 تقسیم می شود که می تواند میان انها وجود داشته باشد) در حالی که مسیر1-8-9-4 وزنی به میزان 0.0119 ( 1 مسیر با طول 3 که دو گره رابه هم وصل می کند به 42 مسیر با طول 3 که میتواند میان انها وجود داشته باشد تقسیم می شود) در نتیجه تشابه کلی میان کاربر 1 و 4 برابر است با 0.2975. ثانیا همانطور که در شکب 4 نشان داده شده است دو مسیر 11-5-7 و 1-6-7 وجود دارد که کاربر 1 و 7 را به هم وصل می کند. وزن هر یکاز مسیرها 0.1428 می باشد تشابه کلی میان دو کاربر 1و 7 برابر است با 0.2856.باید توجه داشت که وزن طول هر یک از مسیرها به صورت نسبت میان طولl مسیر موجود به کل مسیرهای محتمل با طول lمحاسبه می شود که توسط Eqمخرج محاسبه می شود. در شکل 5 ما ماتریس تشابه گره گراف را نشان داده ایم . درنتیجه دوستان جدید بر اساس وزن کلی انها که توسط نسبت تجمعی محاسبه شده تمامی مسیرهایی که انها را به کاربر هدف متصل می کند محاسبه می شود. در مثال ما ، درشکل 5 کاربر 1 می تواند پیشنهادکاربر4 را به عنوان دوست دریافت کند. زیرا که کاربر 1 از طریق مسیرهای زیادی با کاربر4 متصل می شود تا کاربر7. و این پیشنهاد منطقی است .

شکل شماره 5 ماتریس تشابه گره ، احتمال اینکه دو کاربر با هم دوست شوند را نشان می دهد

الگوریتم لینک دوستیfriend link

در این بخش الگوریتم به جزییات توضیح داده می شود . این الگوریتم تشابه گره ای میان هردو گره در گراف را محاسبه کند. داده اولیه الگوریتم تعداد n از گره های گراف . ماتریس نزدیکیA و طول مسیرها l است . برای شماره گذاری تمامی مسیرها ساده در گراف  می تواند از الگوریتم روبین استفاده کرد. هرچند الگوریتم روبین ماتریس  را جهت پیداکردن تمامی مسیرهای متفاوت میان هر دو زوج گره به کار می برد. در حالی که تعداد گره ها در گراف  است . در ادامه ما الگوریتم روبین را سفارشی سازی می کنیم تا تنها مسیرهای با طولl را مناسب برای هدف ما ایجاد کند. درشکل 6 دیده می شود که الگوریتم لینک دوستی ما شامل یک برنامه اصلی و دو کارکرد است . در برنامه اصلی ما مارتیس نزدیکی را طوری تغییر می دهیم به طوری که به جای داشتن میزان0/1 ، میزان ورودی(i.j) ماتریس لیستی از مسیرها ازi بهj باشد. سپس ما الگوریتم ماتریس ضرب را اجرا کردیم توجه داشته باشید برای ساده تر بودن، ما کدهای حلقه ها حذف شده اند. در نهایت تشابه میان گره ها برای هر طول مسیر آپدیت گردید. برای آپدیت کردن میزان تشابه میان دو گره I,jما ازEq استفاده نمودیم . ما مسیرهای حلقه ای را در سنجش تشابه در نظر نگرفتیم

شکل شماره 6: الگوریتم friend link

مقایسه الگوریتم لینک دوستی با سایر روشها

در اینجا ما الگوریتم لینک دوستی را با الگوریتم های MD,RCT,RWR,KATZ,AA,PA,FOAF,SPمقایسه می کنیم. جدول 3 میزان میانگین متوسط دقت (MAP)برای الگوریتم های تست شده برای پایگاه داده ای Epinions 49k  ، فیس بوک3.7k ، و Hi5 63k را نشان می دهد. همانطور که دیده می شود میزان عملکرد لینک دوستی در تمام سه پایگاه داده را نشان می دهد. در مقابل MD,RCT,RWR,Katz,SP تنها شبکه های اجتماعی را با خصوصیات جهانی پیگیری می کنندو خصوصیات محلی گراف د رنظر گرفته نمی شود. در لینگ دوستی Friend Linkتمامی خصوصیات محلی و جهانی درگراف لحاظ می شود. علاوه بر این قادر به فراهم اوردن پیشنهادات دوستی دقیق نیستند زیرا که انها تنها خصوصیات محلی گراف را مورد استفاده قرار می دهند.

 منابع:

Friendlink: Link Prediction in Social Networks via Bounded Local Path Traversal Alexis Papadimitriou Panagiotis Symeonidis Yannis Manolopoulos 

معرفی کتاب

کتاب:

Link Prediction in Social Networks

Role of Power Law Distribution

  که در سال 2016 توسط   Srinivas, Virinchi, Mitra, Pabitra منتشر شده و شامل 6بخش به شرح زیر است:

Chapter 1

Introduction

Chapter2

Link Prediction Using Thresholding Nodes Based on Their Degree

Chapter3

Locally Adaptive Link Prediction

Chapter4

Two-Phase Framework for Link Prediction

Chapter5

Applications of Link Prediction

Chapter6

Conclusion

جهت تهیه این کتاب می توانید به لینک زیر مراجعه کنید:

https://www.amazon.com/Link-Prediction-Social-Networks-SpringerBriefs-ebook/dp/B01AZ0OD84