پیشبینی ارتباط (لینک) در شبکه گراف های اجتماعی (link prediction)

پیشبینی لینک وجود ارتباط در شبکه گراف های اجتماعی (link prediction)

پیشبینی لینک یا وجود ارتباط میان دو موجودیت بر اساس ویژگی‌های موجودیت‌ها و دیگر لینک‌های مشاهده شده در گراف را پیشبینی لینک[1] می‌گویند . یا به عبارت دیگر اگر در زمان n0  یک تصویر لحظه‌ای از مجموعه لینک‌ها داشته باشیم، هدف پیش‌بینی لینک‌ها در زمان n1 می‌باشد . در سال 2005 در مقاله ای اولین بار به طور رسمی مبحثی به نام لینک کاوی مطرح شد. در این مقاله پیش‌بینی لینک به عنوان یکی از زیر شاخه‌های لینک کاوی مطرح شده است. در شبکه‌های بیولوژیکی مثل شبکه‌های تعامل پروتئین-پروتئینی و شبکه‌های متابولیکی کشف ارتباط میان پروتئین‌ها نیازمند صرف وقت و هزینه برای انجام آزمایشات مربوطه در آزمایشگاه می‌باشد. می‌توان به کمک پیشبینی لینک در این شبکه‌ها ضمن کاهش هزینه‌ها، تعداد آزمایشات لازم را کاهش داد. گاهی در برخی از شبکه‌ها یک سری لینک به خاطر وجود نویز در شبکه به صورت اتفاقی به وجود می‌آیند. این لینک‌های نادرست می‌تواند ساختار شبکه را به هم بریزد و مطالعه آن را با مشکل مواجه کند. می‌توان به کمک پیشبینی لینک این لینک‌ها را شناسایی و از شبکه حذف کرد. اگر بتوان از گراف زمان A گراف زمان B و از گراف زمان B گراف زمان BC و … را محاسبه کرد، عملاً می‌توان مدل تکاملی شبکه را بدست آورده و به کمک آن شناخت بهتری از شبکه مورد نظر بدست آورد. در حوزه پزشکی می‌توان شیوع یک بیماری خاص و بررسی اثر واکسن تولید شده را بر روی آن به کمک پیش‌بینی لینک مورد مطالعه قرار داد.

 

مسئله مشابهی به پیشبینی لینک به نام کشف ارتباطات مفقوده [5]وجود دارد. تفاوت این مسئله با پیشبینی لینک این گونه بیان شده است که در پیش‎بینی لینک گراف شبکه پویاِ[6] می‌باشد. منظور از پویا بودن گراف این است که گره‌ها و یال‌ها شبکه می‌توانند در طول زمان اضافه یا حذف شوند. این در حالی است که در مسئله کشف ارتباطات مفقوده گراف شبکه به صورت ایستا[7] در نظر گرفته می‌شود.

تعریف جامعی از پیشبینی لینک در مقالات علمی ارائه شده است. طبق این تعریف می‌توان استخراج داده‌ها [8]را به نوعی یک نوع پیشبینی لینک در نظر گرفت. در این تعریف استخراج داده‌ها عملاً یک گراف دوبخشی است که در یک بخش کلمات و در بخش دیگر اسناد می‌باشند. حال وظیفه استخراج داده‌ها پیش‌بینی لینک میان کلمات با اسناد متناظر است.

یکی از مسائل نزدیک به پیش‌بینی لینک در گراف‌های دوبخشی، مسئله‌ی پیشنهاد بر اساس همکاری گروهی[9] در سامانه‌های پیشنهاد دهنده[10] است . اساس روش پیشنهاد بر اساس همکاری گروهی بر این است که اگر فرد A دارای عقیده‌ی شبیه به فرد B در یک سری از مسائل داشته باشد، آنگاه احتمال آنکه عقیده‌ی A شبیه به عقیده‌ی B در مورد مسئله‌ی جدید  باشد، بسیار بیشتر از فرد دیگری است که به طور تصادفی انتخاب شده باشد. بنابراین در مسئله پیشنهاد بر اساس همکاری گروهی، نیاز است که گره‌های (افراد) شبیه به هم را تشخیص دهیم. این دقیقاً همان نیازی اصلی در پیشبینی لینک است. بنابراین برخی از الگوریتم‌های به کار رفته در مسئله‌ی پیشنهاد بر اساس همکاری گروهی، مناسب برای پیش‌بینی لینک نیز می‌باشند. معمولاً مسئله‌ی پیشنهاد بر اساس همکاری گروهی، در فروشگاه‌های آنلاین برای پیشنهاد یک کالا یا خدمات به کاربران استفاده می‌شود.

 

الگوریتم های پیشبینی ارتباطات یا Link Prediction  سه قابلیت مهم را در اختیار ما قرار میدهد:

1- پیشبینی ارتباطاتی که ممکن است در آینده ایجاد شوند
2- کشف ارتباطات گم شده که به هر دلیل در زمان جمع آوری اطلاعات از دست رفته اند
3- کشف ارتباطات پنهان یعنی رابطه هایی که وجود دارد ولی اثر از آن در داده ها نیست

روش‌های مختلف پیشبینی لینک

می‌توان روش‌های مختلف پیشبینی لینک را به دو دسته کلی تقسیم‌بندی نمود. دسته اول روش‌هایی هستند که بدون بررسی پیش زمینه روند به وجود آمدن لینک‌ها در گذشته، تنها به کمک ویژگی‌های ساختاری موجود در گراف شبکه به پیش‌بینی لینک‌ها در آینده می‌پردازند. ابن دسته را می‌توان روش‌های بدون ناظر در نظر گرفت. دسته دوم از روش‌ها پس از یادگیری[1] یک یا چند مرحله از فرآیند به وجود آمدن لینک‌ها در گذشته، به پیش‌بینی ‌لینک می‌پردازند. این دسته از روش‌ها را می‌توان روش‌های پیش‌بینی لینک باناظر نام‌گذاری نمود.

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

مبتنی بر همسایه مشترک

• آدامیک آدارAdamic and Adar
• اختصاص منابع Resource Allocation
• شباهت کسینوسی Cosine Similarity
• SimRank
• CommonNeighbor
• ضریب جاکارد Jaccard’s Coefficient
• اندیس سورنسن Sørensen Index

مبتنی بر مسیر یا فاصله Distance (فاصله کمتر احتمال ارتباط بیشتر)

• روش‌های مبتنی بر گام تصادفی
• Rooted PageRank
• Katz

مبتنی بر درجه (درجه های بیشتر احتمال ارتباط بیشتر)

• Preferential   Attachment

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

• Adamic Adar
• Common Neighbors
• Cosine Similarity
• Jaccard Coefficient
• Resource Allocation
• Sourensen Index

[1] Training

[2] Precision-Recall

[1] Link Prediction

[2] Intraction

[3] Training Interval

[4] Test Interval

[5] Missing link detection

[6] Dynamic

[7] Static

[8] Information Retrival

[9] Collaborative Filtering

[10] Recommender Systems

بازدیدها: 14178