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

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