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

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

چکیده:

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

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

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

نتایج

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

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

چکیده:

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

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

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

اگر فضای مسئله را به صورت یک گراف در نظر بگیریم آنگاه پیش بینی لینک عبارت است از پیش بینی میزان احتمال ارتباط بین دو گره گراف در آینده، با دانستن این که در وضعیت فعلی هیچ ارتباطی بین این گره ها وجود ندارد. بنا بر تعریف قراردادی پیش بینی لینک می تواند به صورت زیر فرموله شود: گرتف شبکه اجتماعی (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) طبق رابطه زیر افزایش خواهد یافت.

 

نتیجه گیری

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

ارائه یک بهبود برای الگوریتم پیش بینی لینک آدامیک آدار

چکیده

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

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

روش حل مسأله

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

نحوه ی آماده سازی شبکه

شبکه مورد بررسی در این تحقیق شبکه نویسندگان همکار سایت SIDمی باشد این شبکه به صورت داده  های خام  در فرمت XML می باشد. برای هر سال یک فایلXMLوجود دارد. ابتدا این فایلها را با یکدیگر ادغام می کنیم. سپس برای استفاده از این شبکه نیاز است که گراف مجموعه ی زمان آموزش و زمان تست از این شبکه استخراج شود. گراف مجموعه ی آموزش شامل نویسندگان مقالات و لینکهای بین آنها در سالهای 79 تا 84 میباشد. گراف آزمون شامل نویسندگان مقالات و لینکهای بین آنها در سالهای 85 تا 91 است. در این مرحله انواع مختلفی از نگاشت ها انجام می شود. این نگاشتها شامل موارد زیر میشوند:نگاشت مقاله ها به فایلXMLمربوطه: از آنجایی که این شبکه به صورتXMLذخیره شده است،به کمک این نگاشت می توان محل مقاله ی مورد نظر را در فایل XMLفایل مربوطه بدست آورد به کمک این نگاشت می توان به راحتی سایر اطلاعات مربوط به مقاله از جمله کلمات کلیدی مقاله، سازمان ارائه دهند مقاله لینک PDF مقاله و زمان گرداوری مقاله دست پیدا نمود.نگاشت مقاله به نویسندگان: به کمک این نگاشت میتوان نویسنده های هر مقاله را برحسب ID آنها بدست اورد.نگاشت نویسندگان به مقالات: به کمک این نگاشت می توان مقالات نوشته شده توسط هر نویسنده را بدست اورد.نگاشت مقالات به خلاصه مقاله: به کمک این نگاشت می توان به متن خلاصه ی هر مقاله دست پیدا نمود.نگاشت مقالات به کلمات کلیدی مقالات: به کمک این نگاشت می توان به کلمات کلیدی خلاصه ی هر مقاله دست یافت.نگاشت مقالات به کلمات ریشه ی کلمات کلیدی مقالات: به کمک این نگاشت می توان به ریشه ی کلمات کلیدی مستخرج از متن خلاصه ی مقالات دسترسی پیدا نمود.برای این نگاشت ها یک سری توابع نگاشت در هم استفاده میکنیم. از طریق تعریف کلید و مقدار  برای این توابع نگاشت ها را انجام می دهیم.

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

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

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

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

استخراج کلمات کلیدی

در این مرحله کلمات رایج غیر مفید از متن خلاصه ی کلمات حذف می شوند. در ابتدا تمامی اعراب و علائم نگارشی از متن حذف میگردند. سپس کلمات غیر مفید رایج از بین کلمات خلاصه حذف می گردند. برای استخراج کلمات غیرمفید مراحل مختلف طی شد. این مراحل عبارتند از:حذف کلمات رایج زبان فارسی: لیستی از کلمات فارسی رایج زبان فارسی وجود دارد که به کمک این لیست حدوداً500کلمه ای، بخشی از کلمات رایج از متن خلاصه حذف گردیدند. حذف کلمات احترام از جمله مهندس، دکتر و ... حذف برخی از افعال بدست آوردن لیستی از کلمات رایج در میان تمامی مقاله ها به کمک روشtf/idfاین مرحله برحسب محتوای متنی هر شبکه می تواند لیست متفاوتی از کلمات را به کاربر ارائه دهد.استخراج ریشه ی کلمات کلیدی: در مراحل بعدی به دو صورت از کلمات کلیدی متن خلاصه ی مقالات استفاده شده است. یک بار کلمات کلیدی بدون در نظر گرفتن ریشه ی کلمات و یک بار با در نظر گرفتن ریشه ی کلمات. می توانیم ریشه ی کلمات را به جای خود کلمات به عنوان کلمه ی کلیدی در نظر بگیریم. از این طریق کلماتی مانند موضوع وموضوع ها با یکدیگر یکسان در نظر گرفته می شوند و در محاسبه ی شباهت بردارهای زمینه ی کاری افراد تأثیر خواهندداشت.برای استخراج ریشه ی کلمات از ابزار توسعه یافته در مرکز تحقیقات مخابرات استفاده شده است. ابزار ریشه یاب در سطح دوم این جعبه ابزار، یعنی سطح ریخت شناسی، قرار گرفته است. این ابزار برای استخراج ریشه ی کلمات تنها از ساختار کلمه استفاده می کند و مستقل از محتوای آن عمل می کند.این مرحله یکی از بخش های مهم الگوریتم محسوب می شود.

استخراج موضوع مقالات

در این قسمت تمامی مقالات موجود در مجموعه ی داده ای را با موضوع های استخراج شده برچسب می زنیم. در واقع برای هر مقاله ی موجود میزان تداخل آن مقاله با موضوع ها را محاسبه می کنیم مجموعهی اسناد را با D مجموعه ی کلمات موجود در دامنه را با V نشان می دهیم. در این مرحله این مجموعه شامل کلمات کلیدی استخراج شده در مرحله ی قبل می باشد. به این دلیل که کلمات ورودی الگوریتمLDAهرچه مفیدتر باشند و بیشتر مفهوم سند را نشان دهند الگوریتم مذکور عملکرد بهتری خواهد داشت A نشان دهنده ی مجموعه ی نویسندگان و Hنشان دهنده ی مجموعه ی موضوعات استخراج شده در این بخش میباشد. هرنویسنده در نوشتن تعدادی مقاله مشارکت داشته است که جزء مجموعه یDهستند. پس هر نویسندهی عضوAدر نوشتن مجموعه ی مقالاتی همکاری داشته است که این مجموعه را با Daنشان می دهند،کهaنشان دهنده ی کد نویسنده ی مقالات این مجموعه است. برای استخراج موضوع مقاله ها از الگوریتم LDAتوسعه یافته در مقاله ی استفاده شده است. علت استفاده ازLDAبرتری این روش نسبت به روش های مشابه استخراج موضوع است. این مدل موضوعی روی مجموعه های گسسته مانند مجموعه های متنی استفاده میشودLDAبه موضوع های زیادی از قبیل فیلتر کردن همکارانه طبقه بندی متن ها، ابهام زدایی حسی کلمات، و پیشنهاد جامعه اعمال شده است. LDAدر واقع یک مدل مولد برای متن و دیگر مجموعه های گسسته ی داده ای است.در زمینه ی مدلسازی متنی، این مدل مدعی است که هر سند به صورت ترکیبی از موضوع ها تولید شده است.بنابراین این الگوریتم با گرفتن متن اسناد و تعداد موضوع های درخواستی میزان تداخل اسناد با موضوع ها را به عنوان خروجی برمی گرداند. این الگوریتم برای هر مقاله یک ماتریس تعریف میکند.درایه های این ماتریس متناسب با میزان اولیه ی ارتباط کلمات با موضوع ها می باشند. این مقادیر معمولا برای تمام موضوع ها یکسان در نظر گرفته میشوند. مقدار بهینه ی این پارامتر در فصل بعد مورد بررسی قرار گرفته است. همچنین این الگوریتم برای هر کلمه یک ماتریس با ابعاد تعریف می کند. درایه های این ماتریس متناسب با میزان اولیه ی ارتباط اسناد با موضوع ها می باشند. این مقادیرنیز معمولاً برای تمام موضوع ها یکسان در نظر گرفته می شوند. مقدار بهینه ی این پارامتر نیز در فصل بعد مورد بررسی قرارگرفته است. LDAهر سند را به صورت یک توزیع چند جمله ای روی موضوع ها در نظر می گیرد. بدین صورت که برای هر کلمه که در سند وجود دارد توزیع موضوع روی کلمات را به ما خواهد داد، یعنی ماتریسی که سطرهای آن کلمات و ستونهای آن موضوعها هستند. یکی از ورودیهای الگوریتمKاست که تعداد موضوعهایی را نشان میدهد که انتظار داریم الگوریتم استخراج نماید. اگرkموضوع تعریف کنیم،یک ماتریس تعریف می شود که توزیع موضوعها را بر روی کلمات موجود در دامنه ی کلمات نشان می دهد. در واقع احتمال اینکه کلمه یwدر موضوعkام باشد نشان داده می شود. این مقادیر احتمال با چندین بار اعمال کردن الگوریتمLDAبه ماتریس اولیه بدست می آیند. مقدار بهینه ی تعداد این تکرارها در فصل بعد مورد بررسی قرار گرفته است. سپس از طریق این توزیع، توزیع سند روی موضوعها، با استفاده از کلمات استفاده شده در این سند و توزیع موضوعها روی این کلمات،محاسبه می شود. در واقع ماتریسی با ابعاد تعریف میشود. سطرهای این ماتریس مقالات و ستونهای آن موضوع ها میباشند. در نتیجه هر درایه ی این ماتریس نشان دهنده ی احتمال تعلق یک مقاله به یک موضوع خاص میباشد. در واقع احتمال اینکه سندDiبا موضوعkام مرتبط باشد برای هر مقاله مجموع این مقادیر برابر با 1 می باشد این مقادیر احتمال نیز با چندین بار اعمال کردن الگوریتمLDAبه ماتریس اولیه بدست می آیند. مقدار بهینه ی تعداد این تکرارها نیز در فصل بعد مورد بررسی قرار گرفته است. به طور کلی ما برای هر کاربر شبکه ی اجتماعی و در واقع برای هر مقاله یک بردار تعریف میکنیم که نشان دهنده ی توزیع موضوعی آن مقاله می باشد. سپس از این توزیعهای موضوعی برای بدست آوردن زمینه های کاری نویسندگان استفاده کرده و سپس از تخمین شباهت زمینه های کاری نویسندگان برای پیشبینی لینک بین آنها استفاده میکنیم. این توزیع موضوعی در واقع به صورت ماتریسی که درایه های آن تداخل موضوعی مقالات با موضوعهای تعریف شده را نشان میدهد نمود پیدا میکند. در نهایت، به عنوان خروجی این مرحله از الگوریتم، به تعداد مقالات موجود در مجموعه ی داده ای بردار موضوع داریم، که درایه های این بردارها میزان تداخل سند مربوطه با موضوعات استخراج شده را نشان می دهند.استخراج زمینه های کاری نویسندگان در این مرحله، با استفاده از بردارهای بدست آمده در مرحله ی قبل، برای تمامی نویسندگان یک بردار علاقمندی می سازیم. درایه های این بردارها نشان دهنده ی میزان علاقمندی نویسنده ی مورد نظر به زمینه ی کاری مربوطه است. تعداد درایه های این بردارها با تعداد درایه های بردارهای موضوعی مقالات برابر میباشد. در واقع می توان به کمک موضوع های هر مقاله، زمینهی کاری هر نویسنده را نیز مشخص نمود. بر این اساس زمینه ی کاری هر نویسنده از میانگین موضوعهای تمامی مقاله های نوشته شده توسط وی بدست می اید. برای استخراج زمینه های کاری نویسندگان روشهای مختلفی ازجمله ماکزیمم گیری بین موضوعهای مقالات نویسنده نیز بررسی شد که در مجموع این روش مناسب تر از بقیه بود.لازم به ذکر است که تعداد موضوع های استخراج شده برای تمامی مقاله ها و نویسندگان یکسان و برابر بوده و علاوه برآن عنوان موضوع ها نیز یکسان می باشد. به عنوان مثال اگر 100 موضوع برای هر مقاله مشخص شود، تمامی نویسندگان نیز دارای همین 100 موضوع میباشند. میزان ارتباط هر نویسنده با هر موضوع به کمک عدد احتمال اطلاق شده به آن موضوع برای مقالات نوشته شده توسط آن نویسنده محاسبه میشود. هر فرد نویسنده ی تعدادی مقاله میباشد. برای بدست آوردن میزان فعالیت نویسنده ها در زمینه های کاری مختلف میانگین درایه های متناظر در بردارهای موضوع مقالات منتشر شده توسط این نویسنده را محاسبه میکنیم و آنها را در برداری به نام بردار علاقمندی قرار میدهیم.

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

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

در این فرمولB و Aبردارهای زمینه ی کاری دو نویسنده هستندKبرابر با تعداد موضوع ها میباشد. در ادامه طبق فرمول زیر به محاسبه ی میزان شباهت میان دو نویسنده با یکدیگر پرداخته میشود، که مشاهده می شود که از ترکیب معیار آدامیک آدار و شباهت کسینوسی بردارهای بدست آمده استخراج شده است:

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

نتایج

با توجه به نتایج بدست آمده، الگوریتم های آدامیک آدار و کتز از نتایج خوبی برخوردار هستند. در مقایسه ی روشهای پیشنهادی با سایر روشها می توان به این نتایج رسید که در دو نمودار زیر مشخص است:

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

منابع

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

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

چکیده

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

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

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

الگوریتم جستجوی گرانشی

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

قانون جاذبه: هر ذره سعی دارد ذرات دیگر را به یک نیرویی جذب کند.این نیرو طبق رابطه زیر محاسبه می شود:  

قانون حرکت: سرعت فعلی هر جسم متأثر است از سرعت قبلی خود و شتابی که جسم در حالت کنونی دارد. این سرعت مطابق رابطه زیر است.

براساس رابطه بالا F مقدار نیروی گرانشی که دو جسم به هم وارد می کنند G ثابت گرانشی ،1M و 2 M  جسم های اول و دوم را نمایش می دهند .  Rفاصله بین دو جسم را نشان می دهد. رابطه بالا قانون نیوتون را نمایش می دهد که طبق این قانون ، مقدار نیروی بین دو جسم با ضرب جرم دو جسم رابطه مستقیم و با عکس فاصله بین دو جسم رابطه معکوس دارد. رابطه دوم نشان می دهد وقتی که به یک جسم نیرویی وارد می شود در همان جهت به جسم شتاب وارد می شود.در الگوریتم جستجوی گرانشی، عامل ها دارای چهار پارامتر مکان  جرم لختی  ، جرم گرانشی فعال  و جرم گرانشی غیرفعال  هستند . مکان هر جسم نشان دهنده یک راه حل برای مساله است. گرانش و جرم لختی با یک تابع تناسب  تعیین می شوند. الگوریتم با جرم لختی و گرانش جهت دهی می شود درحالی که هر جسم خود یک راه حل است. اجسام سنگین تر بقیه اجسام را به سمت خود جذب می کنند. بنابر این در فضای مساله اجسام سنگین تر یک راه حل بهینه برای مساله هستند.همانطور که از قوانین نیوتون می دانیم جرم لختی جسم در برابر حرکت جسم مقاومت می کند یعنی اینکه جسمی که جرمش بیشتر باشد حرکتش کندتر است.بنابراین عامل های با جرم بیشتر به آرامی جابجا می شوند از این رو فضای محلی بیشتری را جستجو می کنند. ثابت گرانش، دقت الگوریتم را تنظیم می کند این مورد شبیه به دما در الگوریتم SAاست. این الگوریتم یک الگوریتم با حافظه کم است با این حال می تواند شبیه به یک الگوریتم با حافظه بالا کارآمد باشد.ما در اینجا فرض می کنیم که ثابت گرانشی برای همه یکسان است . جرم اینرسی بیشتر یک حرکت کٌند از عامل ها را در فضای جستجوی خود فراهم می کند که همین امر باعث میشود عمل جستجو دقیقتر باشد . در مقابل جرم گرانشی بیشتر باعث جاذبه بیشتر عامل ها می شود و همین امر باعث می شود که عمل همگرایی زودتر صورت گیرد. مراحل الگوریتم جستجوی گرانشی به شرح الگوریتم 1 عبارت اند از: (مرحله 1) تعریف اولیه عامل، (مرحله 2) محاسبه بهترین میزان برازش، (مرحله 3) محاسبه ثابت گرانش، (مرحله 4) محاسبه جرم عامل ها،(مرحله 5) محاسبه شتاب عامل، (مرحله 6) سرعت و مکان عامل ها، (مرحله 7) تکرار مراحل 2 تا 6 است. در ادامه به شرح مراحل می پردازیم.

مرحله 1: تعریف اولیه عامل

مکان N عدد از عامل ها به صورت تصادفی تعیین می شوند. برای تعیین مکان عامل ها از رابطه زیر استفاده می کنیم:

مرحله 2: محاسبه بهترین میزان برازش

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

اگر مساله بیشینه باشد:

 (t)fit میزان برازشj امین عامل را نشان می دهد (t) worstو (t) bestبهترین و بدترین میزان برازش را نشان می دهد.

مرحله 3: محاسبه ثابت گرانش

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

که در اینجا α و G ثابت است که در ابتدای برنامه تعیین می شوند. T تعداد گام های تکرار است0

مرحله 4: محاسبه جرم عامل ها

که Mai و Mpi به ترتیب جرم فعال و غیرفعال هستند درحالی که جرم Mii لختی عامل i است.

مرحله 5: محاسبه شتاب عامل

شتاب i امین عامل در گام t به صورت رابطه زیر محاسبه می شود.

Fid(t) کل نیروی وارده به عامل i ام است که به صورت رابطه زیر محاسبه می شود.

Kbest مجموعه k عامل اول با بهترین مقدار تناسب و بزرگ ترین جرم است Kbest بازمان به صورت خطی کاهش می یابد.

به صورت رابطه زیر محاسبه می شود.

Fij(t)نیروی وارده از عامل i به j در بعد d در گام t است Rij(t). فاصله اقلیدسی بین دو عامل است j و i است G(t) ثابت گرانشی که ثابت است.

مرحله 6: سرعت و مکان عاملها

سرعت و مکان هر عامل در گام (t+1)بر اساس زیر محاسبه می شود.

Vi سرعت عامل i ام در d امین بعد را نشان می دهد. Ai شتاب iامین عامل در dامین بعد را نشان می دهد.Xi مکان i امین عامل در d امین بعد را نشان می دهد.

مرحله 7: تکرار مراحل 2 تا 6

مراحل 2 تا 6 تا زمانی که به بهترین جواب نرسیده ایم تکرار می شود . بهترین مقدار تابع تناسب در نهایت به عنوان تناسب نهایی در نظر گرفته میشود. نمودار و روند کلی کار در شکل  نشان داده شده است

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

در این بخش به مساله نگاشت مدل گرانشی برای پیش بینی لینک م یپردازیم . درروش پیشنهادی (طبق شکل) ابتدا انجمن ها را از گراف استخراج می کنیم .تشخیص انجمن ها و استخراج آن ها طبق پیاده سازی الگوریتم و روش لوین صورت گرفته است . برای مدیریت و تصمیم سازی ها، پس از استخراج انجمن ها به هر انجمن یک عامل تخصیص می دهیم. یعنی به تعداد انجمن ها عامل ایجادمی کنیم و هر عامل را به یک انجمن انتساب می دهیم . در این مدل پس ازاختصاص عامل ها از الگوریتم جستجوی گرانشی استفاده می کنیم. یعنی ابتدا مقدار ثابت گرانشی را تعیین می کنیم که ما آن را برابر مقدار 9.8 انتخاب کرده ایم. سپس چگالی انجمن ها را طبق رابطه محاسبه و به عنوان مقدار جرم آن ها قرارمی دهیم. حال دو انجمن (یا دو عامل) را انتخاب می کنیم تا میزان فاصله آن ها( تناسب معکوس با تعداد یا لهای بین آ نها) را مشخص کنیم.در ادامه نیروی بین دو عامل را با استفاده از روابط بالا اندازه می گیریم.سپس بر اساس مقدار یک آستانه (مقداری ثابت متناسب با نیروی بیشینه بین تمام عامل ها) میزان انتخاب دو عامل را برای پیش بینی تعیین می کنیم. اگر این نیرو از این آستانه کوچک تر بود دو عامل برای پیش بینی برگزیده نمی شوند . بعد از گزینش عامل ها، پیش بینی لینک بین دو عامل گزینش شده انجام می شود . برای تمامی زوج عامل ها این روال تکرار می شود و در نهایت فرآیند پیش بینی لینک کامل می گردد. ما در صورت انتخاب راهبرد مناسب در تخصیص پردازنده ها به عامل ها، به افزایش سرعت پاسخگویی (کاهش زمان پیش بینی ) و مقیا س پذیری مساله پیش بینی (مقاومت در برابر افزایش عناصر و گره ها)، کمک می کنیم.همان گونه که گفتیم، الگوریتم جستجوی گرانشی دارای مراحل مختلفی است که ما برای نگاشت این مدل گرانشی در مساله پیش بینی لینک به شرح زیر عمل می کنیم و معماری مناسبی ارایه می دهیم. در این معماری هر عامل را به عنوان یک جسم در نظر می گیریم که دارای جرم است. برای محاسبه جرم هر عامل ابتدا باید در GSAمیزان برازش را به دست بیاوریم . در مدل پیشنهادی چگالی گراف را به عنوان تابع برازش در نظر می گیریم.چگالی گراف از رابطه زیر محاسبه می شود که در آن |V|تعداد گره های موجود آن انجمن و |E| تعداد یا لهای یک انجمن  است.

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

نتایج آزمایش های تجربی 

ما نتایج آزمایش های تجربی خود را در سه مرحله و به این شرح ارایه می دهیم .

مشخصات مجموعه داده ای ازمایش ها

میزان دقت مجموعه ای مورد ازمایش

میزان صحت مجموعه داده ای مورد ازمایش

منابع

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

An evolutionary algorithm approach to link prediction in dynamic social networks

An evolutionary algorithm approach to link prediction in dynamic social networks
Abstract
Many real world, complex phenomena have underlying structures of evolving networks where nodes and links are added and removed over time. A central scientific challenge is the description and explanation of network dynamics, with a key test being the prediction of short and long term changes. For the problem of short-term link prediction, existing methods attempt to determine neighborhood metrics that correlate with the appearance of a link in the next observation period. Recent work has suggested that the incorporation of topological features and node attributes can improve link prediction. We providean approach to predicting future links by applying the Covariance Matrix Adaptation Evolution Strategy(CMA-ES) to optimize weights which are used in a linear combination of sixteen neighborhood and node similarity indices. We examine a large dynamic social network with over 106nodes (Twitter reciprocal reply networks), both as a test of our general method and as a problem of scientific interest in itself. Our method exhibits fast convergence and high levels of precision for the top twenty predicted links. Based on our findings, we suggest possible factors which may be driving the evolution of Twitter reciprocal reply networks

.خلاصه فارسی حاصل از تجزیه و تحلیل مقاله​:

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

چکیده

در موارد بسیاری از جهان واقعی، پدیده ها و ساختارهای اساسی شبکه های پیچیده درحال تحول می باشند که در آن گره ها و لینک ها در طول زمان حذف یا اضافه می شوند. چالش علمی مرکزی شرح و توضیح پویایی این شبکه ها است، که با یک آزمون کلیدی سعی در پیش بینی تغییرات کوتاه مدت و بلند مدت دارد. برای حل این مشکل از پیش بینی لینک کوتاه مدت استفاده می کنیم، روش موجود بیانگر تلاش برای تعیین معیارهای محلی که با ظهور یک لینک در دوره مشاهده بعدی ارتباط دارد. که اختلاط ویژگی های توپولوژیک و ویژگی های گره را می توان برای بهبود پیش بینی لینک پیشنهاد کرد. رویکرد پیش بینی لینک آینده با استفاده از روش کوواریانس  ماتریس سازگاری تکامل یافته (CMA-ES) این است که برای بهینه سازی وزن در یک ترکیب خطی از شانزده شاخص محلی و شباهت گره استفاده می کند. ما به بررسی یک شبکه اجتماعی پویا بزرگ با بیش از 106 گره (شبکه توییتر پاسخ متقابل)که به عنوان یک آزمون از روش کلی و به عنوان یک مشکل مورد علاقه علمی استفاده شده است. روش ما  همگرایی سریع و سطح بالایی از دقت برای بیست لینک پیش بینی کرد. تضاد مبتنی بر یافته های ما، عوامل احتمالی است که ممکن است توسط محرک های شبکه تکامل توییتر (پاسخ متقابل) نشان داده شود.

مقدمه

شبکه های اجتماعی در طول زمان تغییر می کنند که می توان از انها برای مدل سازی گروه های پویای متغیر استفاده کرد. افراد، بیانگر گره ها هستندکه ممکن است داخل و یا خارج از شبکه باشند، در حالی که این فعل و انفعالات، ممکن است باعث تقویت یا تضعیف مدل های رشد بسیاری از شبکه های خاص جهانی شود ولی اما پویایی در آینده مشکل این شبکه ها است. در این مقاله تمرکز اصلی بر روی  مشکل پیش بینی لینک است: با توجه به پیش زمینه از یک شبکه مانند Gt= (V, Et) با گره های V (گره موجود در تمام مراحل زمانی) و Et لینک ها، در زمان t ما به دنبال پیش بینی لینک که در زمان t + 1 رخ می دهد هستیم.روشهای پیش بینی لینک را می توان به طور گسترده به سه گروه دسته بندی کرد: استراتژی مبتنی بر شباهت، الگوریتم حداکثر احتمال، و مدل های احتمالی. همانطور که توسط لو و همکارانش اشاره شد دو روش انتهایی می تواند برای یک شبکه بزرگ بیش از 100000 گره وقت گیر باشد. با توجه به علاقه ما به شبکه های بزرگ و با تعداد گره های زیاد پراکنده ، تمرکز اصلی بر اطلاعات محلی و استفاده از شاخصهای شباهت برای توصیف احتمال تعاملات آینده است. بادر نظر گرفتن دو گروه عمده شاخص های شباهت:  شاخص شباهت توپولوژیکی و شباهت مبتنی بر ویژگی گره.به نظر نمی رسد که شاخصهای شباهت در همه حالات بهترین عملکرد را داشته باشند. بسته به شبکه و تجزیه و تحلیل اقدامات مختلف باید امیدوار به بهترین نتیجه بود.این نشان می دهد که پیش بینی بهترین لینک وابسته به ساختار ذاتی و فردی مرتبط با شبکه و نه از مجموعه کامل از بهترین روشهای پیش بینی است. علاوه بر این پیش بینی بهترین لینک ممکن است به عوامل درونی و برونی شبکه در حال  تکامل نیز بستگی داشته باشد.شاخص شباهت توپولوژیکی از رمزگذاری اطلاعات در مورد همپوشانی نسبی بین گره های همسایه استفاده می کنند. ما انتظار داریم که دو گره با بیشترین شباهت توپولوژیکی  "مشابه" هستند (به عنوان مثال، همپوشانی در دوستان به اشتراک گذاشته خود)، با احتمال زیادتر ممکن است که در آینده آنها با یک لینک به هم وصل شوند  مانند شاخص همسایگان مشترک و بسیاری از دیگر از شاخصهای شباهت توپولوژیک، که برای ارتباط یا وقوع لینک در آینده نشان داده شده است .هدف کلی در اینجا ارائه یک روش پیش بینی لینک که شامل هر دو اطلاعات توپولوژیکی و کاربری خاص باشد و سریع ترین پاسخ با کمترین پارامتر ممکن و عدم پیچیدگی محاسباتی را دارا باشد.در این مقاله، ما با رسم یک مدل خطی برای ترکیب معیارهای شباهت های محلی و داده ه ای خاص گره ها و استفاده از یک الگوریتم تکاملی پیدا کردن ضرایب سعی در بهینه سازی روش پیش بینی لینک داریم. با فرض اینکه که تمام شاخص های شباهت از اهمیت مساوی برخوردار هستند، ما اجازه می دهیم که برای تنظیم وزن ترکیب خطی از از روش کوواریانس ماتریس سازگاری تکامل (CMA-ES). استفاده کنیم.به وضوح ، مدل بهینه ای که ساختار فرضمان را با شاخص های شباهت ترکیب می کند ممکن است خطی نباشد و این یک محدودیت برای کار ما است . ولی می توان گفت ، کار ما چندین برتری نسبت به روش های دیگر پیش بینی لینک دارد و این روش آشکار می کند که یک مدل خطی ساده قابل مقایسه (توسعه پذیر) تولید می شود و دستاورد هایی قابل توجه ( اگر نه بهترتر ) برای توسعه مکانیسم هایی پیش بینی لینک در شبکه های در حال تکامل ارایه می دهد.در بسیاری از روش ها ، تلاش برای پیش بینی لینک مناسب  درهر دو حالت ساختار مدل و پارامترهای ان است. برای از میان برداشتن این چالش ، مجموعه ای از ویژگی های شبکه های بزرگ در نظر گرفته می شود، که محققان از ان برای کاهش پیچیدگی محاسباتی با انجام ازمایش و نمونه برداری استفاده می کنند. رویکرد ما استفاده از روش CMA-ES برای پیش بینی لینک که شامل چند شاخص پیش بینی لینک، صرف نظر از عملکرد فرض اصلی می باشد. مزیت این روش ان است هیچ فرضی از کلاس شبکه و نه دانش قبلی در مورد سیستم و تجزیه و تحلیل قبلی مورد نیاز نیست.اگر چه روش ما برای پیش بینی لینک در شبکه های اجتماعی پویا بزرگ متمرکز است و این روش مستقل از نوع شبکه می باشد و ممکن است به عوامل مختلف مانند بیولوژیکی، زیرساخت های اجتماعی و شبکه های مجازی بستگی داشته باشد. ما از نماد شانزده شاخص شباهت متداول در اینجا استفاده می کنیم و تاکید می کنیم که هر شاخص شباهت دیگری نیز ممکن است برای گسترش مطالعات می تواند استفاده شود. انتخاب معیارهای شباهت تا حد زیادی به داده های موجود (به عنوان مثال، ابرداده برای گره ها و شاخص های توپولوژیک مناسب در دسترس در زمینه شبکه در حال مطالعه) و اندازه شبکه تحت بررسی بستگی دارد. محدودیت دیگر چندین روش نظارت برای پیش بینی لینک است که تفسیر مدل های متفاوت هریک از انها ممکن است اطلاعات کمی یا اشتباهی در مورد عملکرد فرآیندهای تکاملی شبکه در اختیار ما قرار دهد. هدف روش ما ارائه شفافیت و تشخیص بهترین شاخص برای پیش بینی لینک در شبکه های در حال تکامل در اینده است .  در سال های اخیر موجی از علاقه برای مشاهده فعالیت توییتر از طریق تحلیل شبکه اجتماعی به راه افتاده است.. در بسیاری از مطالعات، گره ها نشان دهنده افراد و لینک ها نشان دهنده رفتار انها است (پاسخ متقابل) .برنامه ما برای پیش بینی لینک در توییتر (شبکه پاسخ متقابل)  طراحی شده واین روش برای اولین بار توسط Bliss و همکارانش ارائه شده است. ما تحولات این شبکه را در مقیاس زمانی یک هفته در نظر می گیریم که در آن گره ها نشان دهنده کاربران و لینک ها نشان دهنده شواهد (رفتارها) پاسخ های متقابل در طول مدت زمان تجزیه و تحلیل است. در حالی که بسیاری از مطالعات دیگر نیز بیانگر همین حرف ما یعنی استفاده از پاسخ متقابل به عنوان شواهدی از تعاملات اجتماعی و فعال افراد است. با توجه به اندازه بزرگ از شبکه های که ما به دنبال  مطالعه انها هستیم و این فرضیه که احتمال دوستی (ارتباط) بین دوستانی که از قبل سابقه مشارکت داشته اند بیشتر است نسبت به کسانی که اصلا با هم در ارتباط نبوده اند و از این رو این مطلب باعث ایجاد محدودیت پیش بینی لینک های جدید در زمان t + 1 که بین افراد که در طول یک مسیر  در زمان t عبور می کنند، خواهد شد. بخشهای این مقاله بدین صورت است که: در بخش اول ما داده های مورد استفاده، شانزده شاخص تشابه  و الگوریتم تکاملی مورد استفاده برای تکامل وزن در این شاخص ها را توضیح می دهیم. در بخش دوم توضیح روش در حال مطالعه و در بخش سوم بحث در مورد اهمیت این یافته ها و همچنین جهت آینده برای کار بیشتر در این زمینه صحبت خواهیم کرد.

An evolutionary algorithm approach to link prediction in dynamic social networks Catherine A. Bliss∗, Morgan R. Frank, Christopher M. Danforth, Peter Sheridan Dodds