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

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