بررسی معیارهای مرکزیت (Centrality) در تحلیل شبکه های اجتماعی

معیارهای مرکزیت (centrality)

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

• فراوانی درجات گره ها(Degree distribute)
• بینابینی (betweenness)
• نزدیکی (closeness)
• دوری از مرکز(Eccentricity)
• آسیب پذیری (Vulnerability)
• دسترسی گره ها(Reach)
•  کارایی گره(Efficiency)
•  تنش(Stress)
•  قدرت(Power)
•  بردار ویژه(Eigen Vector)
•  آسیب ­پذیری گره(Node vulnerability)
•  رتبه ­صفحه(Page rank)
•  Hits

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

روش‌های مبتنی بر همسایه

•  مرکزیت درجه
•  امتیازدهی K-Shell

 روش‌های مبتنی بر مسیر.

•  مرکزیت نزدیکی..
•  مرکزیت بینابینی..
•  حفره ساختاری..

 روش‌های تکراری یا مبتنی بر ارزش

• مرکزیت مقادیر ویژه
•  PageRank

همانطور که میبینید تنوع این معیارها و تعداد آنها بسیار زیاد است از همین رو ما به توضیح مهمترین و پرکاربردترین آنها  اکتفا خواهیم کرد.

فراوانی درجات گره ها(Degree distribute)

žدرجه یک گره تعداد گره هایی است که با آن گره در همسایگی مستقیم قرار دارد.žهر چقدر درجه یک گره بیشتر باشد، اهمیت آن گره بیشتر می شود.žمثلا در شبکه وب، اگر درجه ورودی یک دامنه زیاد باشد، یعنی سایت مرجع است، و اگر درجه خروجی آن زیاد باشد، یعنی اینکه سایتی است که از اطلاعات (اخبار) سایت های دیگر استفاده می کند.žتوزیع درجات، توزیع احتمال این درجات روی کل شبکه است.žتوزیع درجات شبکه  p(k) با استفاده از رابطه p(k)=n_k/n   محاسبه می شود.

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

• بینابینی (betweenness)

žبینابینی عبارت است از نسبت تعداد دفعاتی که یک گره یا یک یال بر روی کوتاهترین مسیر میان نودهای مختلف یک گراف قرار می گیرد. بینابینی یک نود خاص در شبکه عبارت است از تعداد کوتاهترین مسیرهای میان نودهای شبکه که از یک نود خاص رد میشوند.

در حقیقت این معیار محاسبه می‌کند چه تعداد از نودهای شبکه برای ارتباط سریعتر با هم (با واسطه کمتر) به این نود نیاز دارند. هر چه بینابینی نود زیادتر باشد یعنی اینکه نود در مکان استراتژیک‌تری قرار گرفته است.همچنین نشان دهنده درصدی از اطلاعات است که از یک گره می گذرد و مشخص کننده توانایی یک گره برای تسهیل گسترش ارتباط بین سایر عناصر گرههای گراف است و در واقع نمایشی برای میزان قابلیت هر گره برای کمک به دسترسی سایرین به اطلاعات و یا گسترش یک تاثیر در شبکه می باشد. این معیار برای یافتن محل  افرادی که توانایی مرتبط ساختن با جفت ها و گروه های دیگر را دارند نشان  می دهد.

• نزدیکی (closeness)

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

žنزدیکی گره x برابر است  با عکس متوسط کوتاهترین فاصله گره  x  تا سایر گره های گراف.žچه مدت زمان می برد که اطلاعات از یک گره به دیگر گره ها برسد(گره هایی که به آن دسترسی دارد).žجهت پیدا کردن سریع ترین محل انتشار مناسب است.

این معیار در صورتی در شبکه قابل محاسبه است که کل شبکه همبند باشد. در صورتی که نودهایی وجود داشته باشند که دسترسی به یکدیگر نداشته باشند d_ij مساوی بینهایت شده و این معیار برای آن ها صفر خواهد بود و غیر قابل استفاده خواهد گردید. در این حالت معیار کارایی استفاده میشود که فرمولی شبیه نزدیکی دارد اما محدودیت همبند بودن گراف را مرتفع میسازد.

• قدرت (power)

žاین معیار مشابه معیار مرکزیت درجه می­باشد. با این تفاوت که برای تخمین مرکزیت یک گره، علاوه بر استفاده از تعداد همسایه­های محلی آن گره (گرههایی که مستقیما با آن گره در ارتباط هستند)، درصدی از تعداد گره هایی را که آن گره در محدوده بزرگتری با آنها در ارتباط غیر مستقیم است را در نظر می­گیرد و قدرت یک گره را بر اساس قدرت همسایگانش تخمین می­زند.

قدرت میتواند تعاریف متفاوتی داشته باشد. از یک نگاه، نودی که با نودهایی در ارتباط است که خود آن نودها با افراد دیگری در ارتباط نیستند میتواند به نوعی تداعی قدرت مافیایی باشد. از این منظر قدرت زیاد یک نود در گرو قدرت کم نودهای همسایه است. بر این اساس قدرت نودهای همسایه رابطه معکوسی با قدرت خود نود دارد.از منظر دیگر میتوان رابه قدرت یک نود را با همسایگانش رابطه مستقیمی در نظر گرفت و با زاویه دید دیگری به قدرت نگاه کرد: قدرتمند کسی است که دوستان قدرتمندی داشته باشد.

بر اساس این دو تعریف، قدرت یک نود رابطه بازگشتی (recursive) با قدرت خودش دارد: قدرت هر نود با قدرت نودهای همسایه اش ربط دارد و قسمتی از قدرت نودهای همسایه نیز به قدرت نود اول وابسته است.

 

• مرکزیت مقادیر ویژه Eigenvector Centrality

• این روش [42] اهمیت گره‌ها را بر اساس گره‌های مجاور محاسبه می‌کند. این محاسبه در گراف‌های با اتصال قوی اتفاق می‌افتد. اگر گره‌ای به گره‌هایی که دارای اهمیت بالایی هستند متصل باشد تحت تأثیر آن‌ها اهمیت او نیز بالا می‌رود. این روش به‌صورت تکراری برای محاسبه گره اهمیت همسایگان را نیز در نظر می‌گیرد. ابتدا به همه گره‌ها یک امتیاز اولیه داده می‌شود. در ادامه به‌صورت زنجیره‌ای تا زمانی که به پایداری برسد این امتیازدهی ادامه می‌یابد. امتیازدهی در این روش بر اساس این مفهوم است که گره‌های با اتصالات بالا به گره‌های دنبال کننده آن‌ها از نظر امتیاز کمک می‌کنند. روش رتبه‌بندی صفحه ازاین‌روش الگوبرداری کرده است.

•  

• رتبه صفحه (page rank)

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

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

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

• آسیب پذیری (Vulnerability)

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

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

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

 

آدرس کانال تلگرام سایت بیگ دیتا:

t.me/bigdata_channel

آدرس کانال سروش ما:
https://sapp.ir/bigdata_channel

جهت دیدن سرفصل های دوره های آموزشی بر روی اینجا کلیک کنید.

جهت ثبت نام در دوره های آموزشی بر روی اینجا کلیک کنید.

بازدیدها: 18708