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

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

چکیده

شناخت هرچه بیشتر مکانیزم رفتاری انسان ها در شبکه ها، بر فهم ما از نحوه تکامل و رشد شبکه ها تاثیر بسزایی دارد. در یک شبکه آنلاین رفتار انسان ها را می توان همچون یک گراف دو بخشی 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

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

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

چکیده:

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

ماشین بردار پشتیبان در پیش بینی لینک

الگوریتم SVM اولیه در 1963 توسط Vladimir Vapnik ابداع شد و در سال 1995 توسط Vapnik و Corinna Cortes برای حالت غیر خطی تعمیم داده شد. ماشین بردار پشتیبانی (Support vector machines) یکی از روش های یادگیری با نظارت (Supervised learning) است که از آن برای طبقه بندی و رگرسیون استفاده می کنند.

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

مدلسازی رفتار داده ها در شبکه های اجتماعی با استفاده از روش SVM

فرض کنید که اطلاعات حاصل از رفتارهای مختلف یک شبکه اجتماعی را به صورت مجموعه زیر نمایش دهیم:

{(x₁,C₁),(x₂,C₂)…, (x_n,C_n)}

X_i یک نمونه از گره را نشان می دهد. به عنوان مثال x_i می تواند یک نمونه الگوی رفتاری یک گره در شبکه باشد. C_i کلاس یا طبقه مربوط به نمونه x_i را مشخص می کند. به عنوان مثال C_i می تواند نشان دهنده یک نمونه الگوی رفتاری x_i باشد.

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

روش طبقه بندی در این مدل

فرض کنیم مجموعه نقاط داده {(x₁,C₁),(x₂,C₂)…, (x_n,C_n)} را در اختیار داریم و می خواهیم آنها را به دو طبقه C_i=(-1,1) تفکیک کنیم. هر X_i یک بردار p بعدی از اعداد حقیقی است که در واقع همان متغیرهای بیانگر رفتار نرم افزار هستند.

روشهای طبقه بندی خطی، سعی دارند که با ساختن یک ابرسطح (که عبارت است از یک معادله خطی)، داده ها را از هم تفکیک کنند. روش طبه بندی ماشین بردار پشتیبان که یکی از روش های طبقه بندی خطی است، بهترین ابرسطحی را پیدا می کند که با حداکثر فاصله (maximum margin) داده های مربوط به دو طبقه را از هم تفکیک کند. به منظور درک بهتر مطلب، در شکل 1 تصویری از یک مجموعه داده متعلق به دو کلاس نشان داده شده که روش ماشین بردار پشتیبان بهترین ابرسطح را برای جداسازی آنها انتخاب می کند.

در شکل داده ها دو بعدی هستند یعنی هر داده تنها از دو متغیر تشکیل شده است.

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

در این بخش می خواهیم نحوه ساخت ابرسطح جداکننده را بر روی یک مثال با جزئیات شرح دهیم. تصویر دقیقی از نحوه تشکیل ابرسطح جداکننده توسط ماشین بردار پشتیبان در شکل 2 نشان داده شده است.

ابتدا یک پوسته محدب در اطراف نقاط هر کدام از کلاسها در نظر بگیرید. در شکل 2 در اطراف نقاط مربوط به کلاس 1- و نقاط مربوط به کلاس 2+ پوسته محدب رسم شده است. خط p خطی است که نزدیکترین فاصله بین دو پوسته محدب را نشان می دهد.

h که در واقع همان ابرسطح جداکننده است، خطی است که p را از وسط نصف کرده و بر آن عمود است.

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

ایده اصلی این است که یک جداکننده مناسب انتخاب شود. منظور، جداکننده ای است که بیشترین فاصله را با نقاط همسایه از هر دو طبقه دارد. این جواب در واقع بیشترین مرز را با نقاط مربوط به دو طبقه مختلف دارد و می تواند با دو سطح ابرسطح موازی که حداقل از یکی از نقاط دو طبقه عبور می کنند، کران دار شود. این بردارها، بردارهای پشتیبان نام دارند. فرمول ریاضی این دو ابرسطح موازی که مرز جداکننده را تشکیل می دهند. در عبارت (1) و (2) نشان داده شده است:

(1)      W.x-b=1

(2)      w.x-b=-1

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

(3)      برای داده های مربوط به طبقه اول w.x_i-b≥1

(4)      برای داده های مربوط به طبقه دوم w.x_i-b≤-1

می توان این محدودیت را به صورت رابطه زیر نشان داد:

لذا این مساله بهینه سازی بدین شکل تعریف می شود:

به حداقل رساندن w، با درنظر گرفتن محدودیت زیر می باشد.

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

نتایج

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