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

چکیده:

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

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

مسئله پیش بینی لینک

اگر فضای مسئله را به صورت یک گراف در نظر بگیریم آنگاه پیش بینی لینک عبارت است از پیش بینی میزان احتمال ارتباط بین دو گره گراف در آینده، با دانستن این که در وضعیت فعلی هیچ ارتباطی بین این گره ها وجود ندارد. بنا بر تعریف قراردادی پیش بینی لینک می تواند به صورت زیر فرموله شود: گرتف شبکه اجتماعی (V,E) داده شده است، یال e=(u,v)ЄE نشان دهنده تعامل بین گره های v و u در یک بازه زمانی مشخص است. برای زمان t≤t’ فرض می کنیم که G[t,t’] نمایانگر زیرگرافی از G است که شامل تمامی یا های G در بازه زمانی [t,t’] است. پس از انتخاب دو بازه زمانی [t₀,t’₀] و [t₁,t’₁] به طوریکه t’₀<t₁، الگوریتم پیش بینی لینک باید تنها با دسترسی به گراف G[t₀,t’₀]، در خروجی یال هایی را پیش بیینی کند که در گراف G[t₀,t’₀] وجود ندارند اما در گراف G[t₁,t’₁] به وجود خواهند آمد. بازه ی [t₀,t’₀] بازه آموزش و بازه [t₁,t’₁] بازه تست نامیده می شود.

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

در مقاله پیش رو، لینک های چندگانه و اتصال به خود وجود ندارد و شبه به صورت گرتف ساده و غیر جخت دار G=(V,E) تعریف شده؛ به طوری که V مجموعه گره ها، E مجموعه لینک ها، n=lVl تعداد گره های G و U مجموعه جهانی شامل تمامی لینک های ممکن G است.عمل پیش بینی لینک یافتن لینک های گمشده و یا لینک های ناموجودی است که در آینده ایجاد خواهد شد. هدف این روش اختصاص دادن یک امتیاز، score(x,y)، به هر زوج از گره ها UЄ(x,y) است. این امتیاز میزان شباهت بین دو گره را می گرداند. برای یک زوج گره ی (x,y) در U-E، score(x,y) بزرگتر، نشان دهنده ی احتمال بیشتر برای وجود یک لینک بین گره های x و y است. برای آزمایش دقت نتایج الگوریتم، لینک های مشاده شده ی E بصورت تصادفی به دو بخش تقسیم شده اند:

E^T: مجموعه آموزشی که به عنوان اطاعات شناخته شده مورد عمل قرار می گیرد.

E^p: مجموعه تست که اطلاعات آن برای آزمون دقت نتایج بوده و برای پیش بینی لینک استفاده نمی شود.

اجتماع دو مجموعه E^T و E^p برابر E و اشتراک آنها برابر Ф می باشد.

به عنوان مثال شکل زیر الف شبکه ای با 15 گره و 21 لینک موجود را نشان می دهد. هدف ما یافتن لینک های بالقوه ی 84 زوج گره غیر متصل است. برای آزمایش دقت الگوریتم نیاز است که برخی از لینک های موجود به عنوان مجموعه تست انتخاب شوند و بقیه به عنوان مجموعه آموزش، به عنوان نمونه 5 لینک به عنوان لینک های مجموعه تست، که در شکل 2.ب با خط چین نمایش داده شده، برگزیده شده اند. سپس الگوریتم تنها با استفاده از اطلاعات موجود در مجموعه آموزشی یا همان گراف آموزشی که در شکل 2.ب با خطوط پیسته نمایش داده شده است، عمل می کند. الگوریتم در نهایت امتیازی به هر یک از 89 زوج گره که شامل 84 لینک غیر موحود عضو U-E و 5 لینک تست عضو E^p می دهد. در اصل، یک الگوریتم پیش بینی لینک یک لیست مرتب شده از تمام لینک های مشاهده نشده (U-E^T) فراهم می کند یا به طور معادل برای تعیین احتمال وجود هر لینک مشاهده نشده، امتیاز S_xy را به آن نسبت می دهد به طوری که (x,y0ЄU-E^T. برای تعیین دقت الگوریتم های پیش بینی، دو معیار استاندارد AUC و Precision وجود دارد.

AUC

AUC عبارت است از سطح زیر نمودار ROC با منحنی مشخصه عملکرد سیستم. در یک پیاده سازی الگوریتمیک برای افزایش سرعت، اغلب به جای تولید یک لیست مرتب از امتیاز های شباهت، امتیاز هر لینک مشاهده نشده را محاسبه می کنیم. سپس هر بار به طور تصادفی یک لینک گمشده عضو E^p و یک لینک ناموجود عضو U-E برای مقایسه امتیازشان برگزیده می شوند، اگر از میان n مقایسه ی مستقل، n’ بار لینک گمشده امتیاز بیشتری داشته باشد و n” بار امتیاز مشابهی داشته باشد آنگاه امتیاز AUC عبارت است از:

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

.

Precision

با در نظر گرفتن رتبه بندی تمام لینک ها مشاهده نشده، precision به عنوان نسبت آیتم های انتخاب شده ی مناسب به مجموع آیتم های انتخاب شده، تعریف می شود. به این ترتیب اگر از بین تمام لینک های مشاهده نشده، L لینک بالاتر در نظر گرفته شوند، از میان آنها m لینک درست پیش بینی شده باشند، precision به صورت زیر تعریف می شود:

الگوریتم پیشنهادی DLA-LP

شبکه ای از اتوماتاهای یادگیر متناظر با گره های گراف ایجاد می گردد. در این DLA هر اتوماتا معادل یک گره و هر اقدام، معادل یک یال می باشد. به دلیل کامل بودن گراف تعداد اقدام های هر اتوماتا در گرافی با n گره، برابر با n-1 است. خروجی DLA ترتیبی از اقدام های انتخاب شده توسط اتوماتاها می باشد که مسیری که با n گره تولید می کند. وجود گره های تکراری در مسیر بلامانع می باشد. این مسیر با توجه به میزان مطلوبیت (تابع برازش مسیر)، باعث پاداش به اقدام های واقع در ان می شود. در نهایت پس از چندین تکرار از بردار احتمالات DLA به عنوان امتیاز شباهت یال ها استفاده خواهد شد.

تابع برازش

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

به روز رسانی احتمال ها

پس از هر تکرار و پیدا کردن یک مسیر، الگوریتم احتمال اقدام های اتوماتاهای فعال شده را به طبق رابطه زیر به روز رسانی می کند. بدین ترتیب که امتیاز برازش مسیر محاسبه می شود و با امتیاز برازش بهترین مسیری که تا به حال توسط الگوریتم ایجاد شده است مقایسه می گردد. بر اساس نتیجه مقایسه، بردار احتمال اقدام DLA به روز رسانی خواهد شد، بدین صورت که اگر امتیاز برازش مسیر ایجاد شده بزرگتر و یا مساوی امتیاز برازش بهترین مسیری که تا به حال ایجاد شده است باشد، همه اتوماتاهای یادگیر فعال شده، اقدام انتخابی خود را طبق الگوریتم یادگیری، پاداش می دهند. به عنوان مثال در صورتی که در تکرار (t) امتیاز برازش مسیر ایجاد شده بزرگتر و یا مساوی امتیاز برازش بهترین مسیر باشد و یک اتوماتای یادگیر DLA از مجموعه اقدام های مجاز خود اقدام i را انتخاب کرده باشد، بر اساس احتمال انتخاب اقدام i در تکرار (t+1) طبق رابطه زیر افزایش خواهد یافت.

 

نتیجه گیری

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