مرکزیت PageRank در داده کاوی شبکه اجتماعی

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

در درجه مرکزیت بیان کردیم که هر فردی که تعداد ارتباط بیشتری داشته باشد فرد مهم‌تری در شبکه اجتماعی است. در مرکزیت بردار ویژه بیان کردیم علاوه بر تعداد، میزان قدرت افرادی که به آنها لینک وجود دارد نیز بسیار مهم است. آیا این تعریف تمام مشکلات را رفع میکند؟ خیر. دلیل رو باید مثال توضیح می دیم.

فرض کنید یک آدم بسیار معروف در شبکه اجتماعی وجود دارد (یک گره مهم شبکه اجتماعی)، خوب بر اساس تعریف مرکزیت بردار ویژه، هر فردی که این فرد با آن در ارتباط باشد نیز می تواند فرد مهمی باشد. اما این تعریف یک مشکل دارد اونم اینکه “اگر یک نفر مهم، با کاربر X ارتباط داشته باشه دلیل قابل قبولی برای اینکه کاربر X کاربر مهمی است نمی باشد” این امر منطقی هم است.
خوب برای حل این مشکل باید چکار کرد؟استفاده از معیار معیار PageRank راه حل این مسئله است.

معیار PageRank  به زبان ساده یعنی: فرض کنید یک فرد بسیار مهم و پرقدرت با ۱۰۰ نفر در ارتباط است، در PageRank ما قدرت فرد را به ۱۰۰ قسمت تقسیم میکنیم و هر یک از افرادی با این فرد مهم در ارتباط است ۱/۱۰۰ امتیاز قدرت را دریافت میکند. توجه داشته باشید در مرکزیت بردار ویژه هر یک از گره های همسایه تمام امتیاز قدرت را دریافت می کردند.
در شبکه اجتماعی ارتباط بین افراد میتواند بدون جهت باشد یا جهت دارای باشد (برای کسب اطلاعات دقیق تر این مطلب رو مطالعه کنید). توی این دو نوع شبکه معیار PageRank  یکم با هم فرق میکند. در ادامه معیار مرکزیت بردار ویژه را در هر یک از این دو نوع شبکه بررسی می کنیم.
شبکه اجتماعی با ارتباطات بدون جهت: توی یک شبکه اجتماعی مبتنی بر دوستی، ارتباط دوستی بین افراد بدون جهت است، یعنی وقتی X دوست Y است، بر عکس رابطه هم درست است یعنی  Y هم دوست X است. در این نوع شبکه های مرکزیت PageRank به صورت زیر است.

مرکزیت PageRan : در این نوع شبکه ها قدرتی که یک گره از همسایه هایش می گیرد کسری از تعداد ارتباطات آنها است. فرض کنید گره X یک همسایه مهم دارد که میزان مهم بودن آن۲۰ است، و  این همسایه خودش ۱۰ تا ارتباط دارد. در نتیجه سهم گره X از قدرت این همسایه برابر ۲ است. در مرکزیت بردار ویژ همه ۲۰ واحد به همه همسایه ها انتقال پیدا می کرد.

شبکه اجتماعی با ارتباطات جهت دارد: در بعضی از شبکه های اجتماعی، ارتباط بین افراد جهت دارد است مثلا شبکه های اجتماعی که بحث Follow در آنها مطرح است یک نمونه از این نوع هستند. به این معنا که اگر کاربر X  ، کاربر Y را Follow کند، برعکس رابطه ممکن است وجود نداشته باشد (ممکن است کاربر Y کاربر X را Follow نکند).
مرکزیت PageRan در شبکه های جهت دارد: فرض کنید اگر کاربر X  ، کاربر Y را Follow کند و همچنین اگر کاربر Y، کاربر Z را Follow کند.

رابطه بین سه کاربر در شبکه اجتماعی

برای تعیین قدرت کاربر Y، تنها قدرت همسایه های که آنها Y را Follow کرده اند مهم است (در این مثال تنها قدرت کاربر X در نظر گرفته می شود و قدرت کاربر Z در نظر گرفته نمی شود)، اگر گره X در این مثال ۵ تا همسایه داشته باشد، یک پنجم قدرت آن به گره Y منتقل می شود.

یکی از مهمترین کاربردهای PageRan  در الگوریتم رتبه بندی گوگل است. در مطلب بعدی در مورد آن صحبت خواهیم کرد.