بخشی از مقاله
خلاصه
شبکههای اجتماعی مجموعه ای از افراد دارای سلیقه یا منافع مشترک هستند که برای دستیابی به اهداف خاصی گرد هم میآیند. یک شبکه اجتماعی گروهی از افراد یا موجودیتهایی هستند که با یکدیگر در حال همکاری یا رقابت میباشند. این افراد یا موجودیتها میتوانند اشخاص، سازمان ها، گروهها، موجودات زنده، بیماریها، صفحات اینترنتی یا ترکیبی از آنها باشد. در اصل هر موجودیتی که قابلیت اتصال به سایر موجودیتهای دیگر را دارد میتواند عضو یک شبکه اجتماعی باشد. نمونههای شبکه های اجتماعی رایج عبارتند از فیسبوک، توییتر و لینکداین. یک موضوع بسیار مهم در شبکههای اجتماعی، موضوع پیشبینی لینک - پیوند - است، که در مسائل بازاریابی، امنیتی و پزشکی کاربرد دارد. در این مقاله، نخست به معرفی و کاربردهای پیش بینی لینک پرداخته میشود. سپس روش های گوناگون پیش بینی لینک بیان میگردند. آنگاه معیارهای ارزیابی این روش ها مرور و بررسی میشوند.
کلمات کلیدی: پیش بینی پیوند، روش همسایگی مشترک، معیار شباهت، گام برداری تصادفی، فیس بوک، تخصیص منابع، یادگیری خودکار
1. مقدمه و تاریخچه
شبکه های اجتماعیمعمولاً بهصورت گراف الگوسازی میشوند. در این شبکه ها گره ها افراد، و یالها ارتباطات بین افراد را نشان میدهند. پیش بینی لینک در شبکههای اجتماعی به معنی پیش بینی وجود ارتباط میان دو گره بر اساس ویژگی های گره ها و دیگر ارتباطات موجود در گراف است. به عبارت دیگر اگر در زمان ti یک تصویر از مجموعه لینک ها داشته باشیم، هدف پیش بینی لینک ها در زمان ti+1 است.[1]تحلیل شبکههای اجتماعی یک موضوع بسیار مهم در حوزه ریاضیات و علوم کامپیوتر است. پیشبینی لینک در اینترنت و دانش وب و همچنین برای به وجودآورن فراپیوند1 در وب و پیشبینی فرا پیوند در وب به کار میرود.
برای بررسی تعامل پروتئین ها نیز از روشهای پیشبینی لینک استفاده میشود. همچنین در مسایل امنیتی، مانند شناسایی حملات تروریستی از روشهای پیشبینی لینک استفاده میشود. اهمیت پیش بینی لینک به دلیل طبیعت دینامیک شبکه های اجتماعی است. اعضا و پیوندهای ارتباطی بین آن ها در این شبکه ها مدام در حال افزایش هستند و این پیوندها ممکن است به دلایل گوناگون از دست برود؛ لذا با پیش بینی این پیوندها می توان شبکه ها را تکمیل نمود و اطلاعات از دست رفته را بازیابی کرد. برای کشف و پیش بینی این پیوندها نیاز به اطلاعاتی است کهغالباً از ساختار گرافی شبکه استخراج می شوند و به عنوان معیارهایی برای پیش بینی مورد استفاده قرار می گیرند.[2]
بسیاری از تحقیقات در تجزیه و تحلیل شبکه های اجتماعی به بهره برداری از اطلاعات کاربران و روابط اجتماعی مانند دوستی متمرکز شده اند. با این حال در بعضی از پژوهشها، برای بهبود عملکرد پیش بینی لینک از اطلاعات دیگر از جمله اطلاعات خوشه ها و انجمن ها استفاده می شود. در آزمایش های مختلف، فنگ و همکاران نشان دادند وقتی که ساختار خوشهای شبکه ها رشد می کند، دقت و صحت اقدامات پیش بینی لینک براساس اطلاعات ساختاری بهتر می شود. این نتایج باعث شد که به نوعی از اطلاعات انجمنها برای بهبود عملکرد پیشبینی لینک استفاده شود.[3]بیشتر پژوهش های سالهای اخیر در مساله پیش بینی لینک از اطلاعات ساختاری گراف استفاده میکنند. در ادامه به پژوهشهای مهم در این باره می پردازیم . [4]
2.پژوهش های مرتبط
روشهای مبتنی بر معیارهای شباهت این روش ها ساده ترین روش پیش بینی لینک هستند که یک امتیاز به هر دو گره y و x داده که این امتیازتخصیص می دهند که این امتیاز بر حسب میزان شباهت دو گره به هم است. تمام لینک هایی که مشاهده نشده اند و قرار است که پیش بینی شوند بر حسب میزان شباهت دو گره به هم رتبه بندی می شوند و لینک هایی که امتیازشان بیشتر است پیش بینی می شوند. این روش بیشتر بر اساس ساختار شبکه، لینک ها را پیش بینی می کند. مانند روش های مبتنی بر فاصله که در آن گره هایی که در کمترین فاصله از هم قرار دارند شانس بیشتری برای پیش بینی لینک بین آنها در آینده دارند.
روش های مبتنی بر آمار در این روش ها از مدل های آماری ورویکردهای بیزی استفاده می شود.روش های مبتنی بر بیشترین احتمال در این روش ها علاوه بر بررسی ساختار گراف، ویژگی ها و خصوصیاتی که باعث می شود احتمال وجود لینک بیشتر شود را استخراج می کنند.از دیدگاهی دیگر، روش های پیش بینی لینک به سه دسته ی محلی ، نیمه محلی و سراسری تقسیم می شوند .[2]روش های محلی: در این روش ها فرض بر این است که تنها از اطلاعات محلی همبندی یک گره در شبکه - مانند تعداد همسایه های او - اطلاع داریم. روش های نیمه محلی: این دسته از روش ها نسبت به روش های محلی اطلاعات بیشتری از همبندی شبکه در اختیار دارند اما نیازمند کل اطلاعات همبندی شبکه نیستند. این روش ها با هدف ایجاد تعامل بین دو دسته ی محلی و سراسری به وجود آمده اند و مشکلات روش های سراسری که عبارتند از زمانبر بودن و دشواری یافتن ساختار کامل شبکه را نخواهند داشت.
روش های سراسری: در این دسته از روش ها تمام مسیرهای موجود بین دو گره در نظر گرفته میشوند و فرض بر این است که اطلاعات کاملی از همبندی شبکه در اختیار داریم.همچنین، از دیدگاهی دیگر روش های مختلف پیش بینی لینک با توجه به وجود یا نبود ناظر مرکزی به دو دسته کلی با ناظر و بدون ناظر تقسیم بندی می شوند.[5]روش های بدون ناظر، روش هایی هستند که بدون بررسی پیش زمینه روند به وجود آمدن لینک ها درگذشته، تنها به کمک ویژگی های ساختاری موجود در گراف شبکه به پیش بینی لینک در آینده می پردازند.روش های با ناظر پس از یادگیری یک یا چند مرحله از فرآیند به وجود آمدن لینک ها درگذشته ، به پیش بینی لینک های آینده می پردازند.
الگوریتم های پیش بینی لینک بدون ناظرغالباً از ویژگی های ساختاری مانند تعداد همسایه های مشترک، طول کوتاه ترین مسیر میان دو گره ، درجه دو گره استفاده می کنند. این روشهاعمدتاً تنها از یک تصویر لحظه ای گراف شبکه استفاده کرده و بدون در نظر گرفتن محتوای شبکه مورد بررسی، تنها به کمک ویژگی های ساختاری گراف شبکه سعی در پیش بینی لینک ها در تصویر لحظه بعدی از شبکه می کند. این روش ها معمولاً از سرعت مناسبی برخوردار بوده ولی دقت خروجی این دسته از روش ها نسبت به روش های پیش بینی لینک با ناظر کمتر است.الگوریتم های پیش بینی لینک با ناظر گاهی اوقات با یادگیری پارامتر های یک مدل احتمالاتی و یا بررسی روند تکامل یک زیرساختار خاص در گراف شبکه به پیش بینی لینک می پردازند. درمجموع از اطلاعات هر روشی که به نوعی شباهت دو گره را نسبت به یکدیگر در گراف شبکه نشان دهد را می توان به نوعی برای پیش بینی لینک نیز استفاده نمود.
3. الگوریتم ها و روش های پیش بینی لینک
در این بخش به بررسی تعدادی از الگوریتم ها و روش های پیش بینی لینک در شبکه های اجتماعی می پردازیم:
.1-3 روش های مبتنی بر فاصله یکی از ساده ترین روش ها برای پیش بینی لینک استفاده از معیار فاصله است. در این روش برای زوج گره ای که بین آن ها لینکی وجود ندارد و در فاصله کمی از یکدیگر قرار دارند، بیشترین احتمال برای به وجود آمدن ارتباط میان آن دو نسبت به سایرین وجود دارد. . [1]
.2-3 روش های مبتنی بر درجه در این روشها تنها از درجه گره ها برای رتبه بندی لینک ها استفاده می شود. در این معیار احتمال اینکه یک یال جدید دارای نقطه پایانی x یا y باشد، متناسب با درجه ی گره x است. احتمال آنکه دو نویسنده با یکدیگر همکاری کنند، متناسب با ضرب درجه ی آن دو نویسنده در گراف است. به این روش همبستگی ترجیحی گفته می شود. رابطه زیر نحوه محاسبه امتیاز لینک ها بر اساس معیار همبستگی ترجیحی نشان می دهد که در آن - [ - تعداد همسایه های گره x است .[6]
.3-3 روش همسایههای مشترک در این روش امتیاز یک لینک برابر با تعداد همسایه های مشترک میان نقاط انتهایی آن خواهد بود.فرمول زیر نحوه محاسبه ی تعداد همسایه های مشترک میان دو گره را نشان می دهد. رابطه بالا کلی است و می توان در حالت های مختلفی آن را محاسبه نمود. می توان همسایه های مشترک را تنها همسایه های مرتبه اول میان دو گره در نظر گرفت و یا همسایههای مرتبه دوم یعنی همسایههای همسایه گره موردنظر و یا مراتب بالاتر را نیز در نظر گرفت.
.4-3 ضریب جاکارد یکی از معیارهای سنجش شباهت در استخراج داده ها، ضریب جاکارد است. اگر ضریب جاکارد را به عنوان معیاری برای رتبه بندی یال ها استفاده کنیم، در کل به نوعی حالت نرمال شده روش همسایه های مشترک است. در این روش تعداد همسایه های مشترک میان دو گره بر اجتماع همسایه های آن دو تقسیم می شود. رابطه زیر نحوه ی محاسبه ی ضریب جاکارد را نشان می دهد. ضریب جاکارد می گوید که دو گره شبیه تر به یکدیگر هستند اگر تعداد همسایه های مشترک زیاد و تعداد همسایه های غیرمشترک کمی داشته باشند.[8] فرمول زیر نحوه محاسبه این روش را نشان میدهد.
.5-3 شاخص آدامیک-آدار آدامیک و آدار در زمینه وب برای تشخیص شباهت دو وب سایت به یکدیگر معیاری را معرفی کردند. طبق این معیار پس از به دست آوردن ویژگی های مشترک دو صفحه در وب، به ویژگی هایی که نادر بوده و تنها میان دو صفحه موردنظر به وجود آمده است، وزن بالاتری داده می شود.[9] فرمول زیر نحوه محاسبه این معیار را نشان میدهد.
.6-3 روش :Friendlink این روش با در نظر گرفتن یک کران، مسیرهای کوتاه تر از این کران را بین دو راس بررسی میکند و بدین ترتیب از مزیت سرعت روشهای محلی و دقت روشهای سراسری استفاده میکند. رابطه زیر نحوه محاسبه این روش را نشان میدهد، که در آن | ℎ , | تعداد مسیرهای با طول i بین x و y است .[10]
.7-3 روش تخصیص منابع روش تخصیص منابع براساس ایده اختصاص منابع در شبکههای پیچیده ارایه شده است. دو گره x,y که به طور مستقیم میان آنها لینکی وجود ندارد را در نظر بگیرید، گره x میتواند یک سری منبع را به کمک همسایه هایش بهعنوان واسطه به سمت گره y هدایت کند. در حالت ساده هر گره ی واسطه تنها توانایی انتقال یک واحد از منبع را دارا است و به این صورت عمل می کند که تمامی منبع دریافتی را به سمت تمامی همسایه هایش رها می سازد. اکنون میزان شباهت گرهy با گره x برابر با میزان منابعی است که این گره از گره x دریافت می کند . نحوه محاسبه شباهت بدین روش در رابطه زیر نشان داده شده است.[11]
.8-3 روش کتز در این روش از تعداد و طول مسیرها میان دو گره جهت پیش بینی لینک استفاده می شود. مسیرها نیازی نیست که کوتاه ترین مسیر باشند. برای کاهش اثر مسیرهای طولانی در تعیین امتیاز یک لینک، از یک ضریب به نام β در این فرمول استفاده شده است. این کار باعث می شود که پیش بینی لینک میان گره ها در نواحی پرجمعیت اطراف آن ها نسبت به سایر نقاط بیشتر باشد. رابطه زیر نحوه محاسبه امتیاز یک لینک بر اساس معیار کتز را نشان می دهد .[12]در رابطه بالا | ℎ . | مجموعه تمام مسیرهای به طول L از گره x به گره y است. همان طور که قبلا نیز اشاره شدβ > 0 ، یک ضریب کنترلی است. اگر مقدار این ضریب خیلی کم باشد ، معیار کتز شبیه همسایه های مشترک میشود. معمولا این مقدار بین 0.0005 تا 0.025 است.
.9-3 روش انتشار جریان - prop flow - یک روش مبتنی بر مسیر برای پیش بینی لینک است، به طوری که نسبت به نویزهای ساختاری که در فاصله دوری از گره ی مبدأ قرار دارند، حساس نیست. یال های گراف وزن دار فرض می شوند، وزن هر یال نشان دهنده ظرفیت آن یال برای عبور جریان است. درصورتی که گراف وزن دار نباشد، می توان وزن همه ی یال ها را برابر با یک در نظر گرفت. این روش به این صورت عمل می کند که ابتدا از یک گره یک واحد جریان به سمت سایر گره ها فرستاده می شود. برحسب وزن یال ها، احتمال آنکه جریان موردنظر از یک یال عبور کند محاسبه می شود. هرچقدر وزن آن یال بیشتر باشد، احتمال بیشتری دارد که جریان از آن عبور کند. پس از محاسبه تمامی احتمال ها، گره ای که دارای بیشترین احتمال باشد، گره ای است که بیشترین شانس برای ایجاد لینک با آن وجود دارد.[13]
.10-3 الگوریتم گام برداری تصادفی دو نوع گام برداری وجود دارد: گام برداری مرسوم و گام برداری نظارتی. از هر کدام از این دو نوع روش در پیش بینی لینک استفاده شده است. از نظر نوع شبکه، روش های مبتنی بر گام برداری تصادفی در شبکه های شامل یک یا چند نوع گره و همچنین وزن دار و بدون وزن مورد استفاده قرار گرفته اند.از آنجا که در گام برداری تصادفی مرسوم همه گره ها در شبکه اهمیت یکسانی دارند، یال های شبکه بدون وزن یا همگی با وزن یکسان در نظر گرفته میشوند. گام برداری تصادفی مرسوم بر روی شبکه ای حرکت میکند که یال های آن نشان دهنده اعتماد بین کاربران است، در واقع هنگامی بین دو کاربر یال وجود دارد که آنها به یکدیگر اعتماد داشته باشند. هنگامی که کاربر x به کاربر y اعتماد داشته باشد، احتمال پذیرش نظرات y توسط x
