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

A Knowledge Based Framework for Link Prediction in Social Networks

Abstract Social networks have a dynamic nature so their structures change over time. In this paper, we propose a new evolutionary method to predict the state of a network in the near future by extracting knowledg from its current structure. This method is based on the fact that social networks consist of communities. Observing current state of a given network, the method calculates the probability of a relationship between each pair of individuals who are not directly connected to each other and estimate the chance of being connected in the next time slot. We have tested and compared the method on one synthetic and one large real dataset with 117 185 083 edges. Results show that our method can predict the next state of a network with a high rate of accuracy


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

چکیده

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

مدل تکاملی پیشنهادی

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

اجزای مدل ارائه شده

ساخت گراف وزن دار

نخست ما به طور خلاصه الگوریتم تکاملی را توصیف می کنیم. در این الگوریتم، هر فرد به عنوان یک راه حل احتمالی را بر اساس یک روش مجاورت و منبع خاص ذخیره شده در ساختاریک آرایه است. طول این آرایه برابر تعداد گره های کل گراف است. هر سلول از این آرایه از 1 تا n (طول آرایه) تعیین کننده یک گره در گراف است . به عنوان مثال، سلول  10 مربوط به گره 10است.اگر یک شبکه دارای 7 گره باشد، یک فرد را می توان به عنوان یک گره از مجموعه ای ازاین گره ها نشان داد که در شکل زیر تعریف شده است.

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

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

شکل 8 به عنوان مثال به روز رسانی فضای باور را نشان می دهد. پنج گره برای به روز رسانی فضای باور انتخاب شده اند که در شکل 4از همان شبکه نشان داده شده است. اگر ماتریس از قبل خالی بود، آن را توسط فراوانی تکرار گره ها و همسایگان خود پر می کنیم. به عنوان مثال، گره  5 به گره1، بیش از20 درصد (یک بار از 5 بار) در ارتباط بوده است. اگر ما این فضای باور را که در شکل زیر نشان داده شده است در نظر بگیریم یک گراف وزن دار جهت دار خواهیم داشت.

 

محاسبه احتمالات

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

فرض کنید ، G (E V W)، بیانگر ورودی های گراف وزن دار است، که در آن V مجموعه ای از گره ها و E مجموعه ای از یال ها بین هر جفت از گره ها از این رو، هر یک از یا لها E(IJ)  و j i V علاوه بر اینW مجموعه ای از وزن یال ها باW(IJ)>1 W(J I) 0< است ≤ 1 برای تمام یال هاو  برای هر جفت از گره غیر متصلKI،) جایی که ، K V و (I، K) / E، اگر یک گره با J) V و (I، I)،(J وجود دارد، وزن تخمینی بین i و k به صورت زیر محاسبه :

اگر یک لینک بین دو گره i و k در غیاب گره j وجود دارد، پس, J ,K ) W’(Iرا می توان به عنوان وزن برآورد شده برای هر لینک تفسیر کرد. برای هر مسیر مشابه وزن بر این اساس محاسبه می شود و در نهایت، احتمال رابطه بین گره i و k به صورت زیر قابل محاسبه است:

که در آن n تعداد مسیر بین i و k است.

رتبه بندی احتمالات

پس از محاسبه تمام احتمالات، جفت پیش بینی شده باید بر اساس رتبه بندی احتمالات انتخاب شود. این فرایند در الگوریتم زیر نشان داده شده است:

Algorithm CA-LP (G,A,B,L)

Input:

G: an undirected and unweighted graph, G(V,E)

A: adjacency matrix of G

B: Belief Space matrix

L: desired number of top predicted links

Output:

O: n*n matrix of L probabilities where

O(i,j)=P(i,j), ( i,j are members of V)

Main:

1: Map Belief space to a weighted directed Graph

2: Compute

P(i,k) by extracting weights from B according to

(1) and (2), for all pairs where A(i,k)=0 and A(i,j), A(j,k)=1

3: Store probabilities in a array

4: Sort the array

5: Choose the top-L and store in O where O(i,k)=P(i,k)

 

منابع

A Knowledge Based Framework for Link Prediction in Social Network Pooya Moradian Zadeh(B) and Ziad Kobti School of Computer Science, University of Windsor, Windsor, ON, Canada moradiap,kobti}@uwindsor.ca

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

 

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

چکیده

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

روش پیشنهادی

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

استخراج ویژگی

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

 

مدل ترکیبی

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

مقاومتر خواهد شد.برای انجام دسته بندی و ترکیب دسته بندهای پایه از نرم فزار RapidMinerاستفاده می شود.

ارزیابی

به منظور تفکیک داده های آموزشی و آزمایشی از روش 10Fold Cross Validation استفاده شده است. دراین روش کل مجموعه دادهها به 10 قسمت مساوی تقسیم میشوند. از 3 قسمت به عنوان مجموعه داده های آموزشی استفاده میشود و بر اساس آن مدل ساخته میشود و با یک قسمت باقی مانده عملیات ارزیابی انجام می شود. فرآیندمزبور به تعداد 10 مرتبه تکرار خواهد شد، به گونه ای که از هرکدام از 10 قسمت تنها یکبار برای ارزیابی استفاده شده ودر هر مرتبه یک دقت برای مدل ساخته شده، محاسبه میشود. در این روش ارزیابی دقت نهایی دسته بند برابر با میانگین دقت محاسبه شده خواهد بود. بدیهی است که در این شیوه ارزیابی، دقت محاسبه شده برای دسته بند قابل اعتماد بوده و دانش حاصل شده جامع خواهد بود.

مجموعه داده ها

جهت ارزیابی روش پیشنهادی از مجموعه داده های دو شبکه ی اجتماعی واقعی Hi5 و Facebook استفاده شده تاکارایی روش پیشنهادی بررسی شود. مشخصات کامل این مجموعه داده در جدول زیر آمده است.

 


 

 

نتابج حاصل از هر یک دسته بندهای پایه با استفاده از کلیه معیارهای شباهت مطرح شده و به ازای هر یک از مجموعه دادهه ای Facebook و Hi5 در جدول زیر آمده است.

 

 

 

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

 

 

 

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

 

 

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

 

نتیجه گیری

در این مقاله مدلی ارائه شده که با استفاده از روش های یادگیری جمعی نظیرالگوریتم ژنتیک و باترکیب چنددسته بند پایه میتواند مدل تکاملی شبکه را با پیشبینی پیوندهای آتی ، بدست آورد. این مدل با استفاده از مجموعه داده ای دو شبکه اجتماعی Hi5 و Facebook ارزیابی شده است، نتایج نشان داده که روش پیشنهادی می تواند پیوندهای بین موجودیتهای یک شبکه اجتماعی را با دقت و کارایی مناسب پیشبینی نماید که نسبت به دسته بندهای پایه، از کارایی خوبی برخوردار بوده و میتواند دقت پیشبینی را افزایش دهد.در ادامه کار و تحقیقات بعدی میتوان با درنظر گرفتن وزن هر دسته بند در ترکیب، از روش رأی گیری حداکثری وزن دار در ترکیب دسته بندها استفاده نمود تا به نتایج دقیق تری دست یافت.

پیشگویی پیوند در شبکه های اجتماعی با استفاده از ترکیب دسته بندی کننده ها (استفاده از الگوریتم GA وPSO)

پیشگویی پیوند در شبکه های اجتماعی با استفاده از ترکیب دسته بندی کننده ها (استفاده از الگوریتم GA  وPSO™)

چکیده

پیشگویی پیوند در شبکه های اجتماعی یکی از فعالیت های مهم در تحلیل شبکه های اجتماعی است. اهمیت پیشگویی پیونددر شبکه های اجتماعی به دلیل طبیعت دینامیک آن هاست. اعضا و پیوندهای ارتباطی بین آن ها در این شبکه ها مدام در حال افزایش است و این پیوندها ممکن است به دلایل گوناگون از دست برود؛ لذا با پیشگویی این پیوندها امکان گسترش وتکمیل این شبکه ها و بازیابی اطلاعات و موارد از دست رفته را می توان به دست آورد. برای کشف و پیشگویی این پیوندها نیاز به اطلاعاتی است که غالباً از ساختار گرافی شبکه استخراج می شوند و به عنوان معیارهایی برای پیشگویی مورد استفاده قرار می گیرند. در این مقاله پس از معرفی دو معیار جدید که کارایی مؤثری در پیشگویی و نیز ارائۀ پیشنهادات از خود نشان داده اند روش جدیدی ارائه شده است که با ترکیب چند دسدته بندی کننده و با بهره گیدری از روش ها ی تکاملی الگوریتم ژنتیک و الگوریتم رقابت استعماری( عمل پیشگویی پیوند را به انجام می رساند. برای اثبات کار از دو مجموعهEpinions و Facebook استفاده شده است. ما نشان داده ایم که روش پیشدنهاد ی می تواند کار ا یی و دقت پیشگویی را افزایش دهد.

 

روش مورد استفاده در پیشگویی پیوند

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

دسته بندی برای پیشگویی پیوند

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

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

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

 روش ترکیب دسته بندی کننده ها

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

که در آن N تعداد دسته بندی کننده ها و c تعداد کلاس هاست  zi j خروجی برای کلاس i از دسته بندی کنند j است. wi ضریب وزنی معادل همین خروجی است . ازآنجایی که ما در پیشگویی پیوند با دو کلاس صفر و یک مواجهیم ، دوyمحاسبه می شود. در این روش، خروجی هر دسته بندی کننده رادرz1 و متمم صفر یا یک آن را  در z2قرار می دهیم. کلاس برنده برای هریک از داده ها هریک از یالها کلاسی است که بیشترین مقدار y را دارد. بدین معنی که پس از محاسبۀ yi ها کلاس مورد نظربرابرمقداراندیس y بزر گتر است .

بنابراین مسلم است هه در این قسمت ، مسئله اصلی پیداکردن وزن های wi برای شرکت در ترکیب خطی است. هریک از c دسته بندی کننده که قرار است با یکدیگر ترکیب شوند دارای وزن هایی برای هریک m از کلاس خود هستند. بنابراین m×c وزن داریم که باید به طریقی مقادیر آن رابیابیم . روشی که در این مقاله برای محاسبۀ وزن های مورد نیازاستفاده شده، الگوریتم رقابت استعماری است . در الگوریتم رقابت استعماری که پیش از این شرح داده شد، هر عنصرجمعی یک کشور نامیده می شود که ابعادی به اندازۀ تعداد عناصر مسئله عناصری که به دنبال یافتن آنها هستیم دارد . بنابراین در این روش ، ابعاد هریک از کشورها برابر m×cاست که مقادیر هریک از آن ها بین 25 و 25 - در نظر گرفته شده است . تابع شایستگی در این روش منطق با کارایی نهایی ترکیب دسته بندی کننده ها تعریف، می شود که این کارایی در این قسمت نیز مقدار AUC خروجی است در سایر مقادیر این الگوریتم ، از مقادیر پیش فرض الگوریتم استفاده کرده ایم .پس از این  وزن های مربوط به هریک از دسته بندی کننده هابا استفاده از الگوریتم رقابت استعماری محاسبه شد، باجایگذاری این مقادیر در معادلۀ خطی می تهوان کلاس مربوط به هریک از نمونه های داده ورودی را تعیین کرد.

با توجه به روش پیشنهادی و توضیحات ارائه شده درمقاله، مراحل کار را می توان به صورت زیر خلاصه کرد:

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

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





درجدول زیر نتایج مربوط به دسته بندی داده ها ی مربوط به مجموعه دادۀ Epinionsنشان داده شده است:

نتیجه گیری

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

منایع

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

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


 

چکیده

امروزه شبکه های اجتماعی برخط، به دلیل امکان ایجاد ارتباط بین افراد مختلف درسرتاسر دنیا محبوبیت زیادی دارند. این شبکه های اجتماعی که از امکانا تی مانند پیشنهاد دوست به کاربران برخوردارند، در اغلب موارد برای بیان پیشنهادهای خود، از ویژگی های محلی ساختار گراف شبکه استفاده میکنند. برای بیان پیشنهاد در این شبکه ها، رو شهای مختلفی با دو رویکرد محلی و سراسری پیمایش گراف شبکه پیشنهاد شده و مورد استفاده قرار میگیرد .در این مقاله روشی با رویکرد محلی ارائه شده است که در مقایسه با روش های دیگر، دارای کارایی مناسبی است، علاوه بر اینکه به دلیل محلی بودن رویکرد، از سرعت قابل قبولی برخورداراست. بر اساس ارزیابی ای که روی مجموعه داده های دو شبکه اجتماعی بزرگ 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 مشاهده می شود، روش جدید در مورد هر دو مجموعه داده در مقایسه با سایر رو شها، پاسخهای مناسب و قابل قبولی خواهد داشت و پیش بینی های خوبی را ارائه می دهد.

نتیجه گیری  

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

منابع:

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

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

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