Skip to content
بازگشت به نتایج جست‌وجو

مرکزیت بینابینی

معرفی‌شده توسط
Freeman, L. C.
سال
1977
نوع
Centrality measure
خانواده
Network science

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

اندازه قلم

چه کاری انجام می‌دهد؟

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

شهود پشت روش

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

تاریخ

لینتون فریمن مرکزیت بینابینی را در مقاله برجسته خود در Sociometry در سال ۱۹۷۷ تدوین کرد و از استفاده‌های غیررسمی قبلی این مفهوم توسط باولاس (۱۹۴۸) در آزمایش‌های ارتباطی بهره برد. فرمول‌بندی فریمن چندین شهود مبهم در مورد اهمیت گره را در یک معیار واحد قابل محاسبه ادغام کرد و به تعریف متعارف مورد استفاده در علم شبکه تبدیل شد. الگوریتم اولریک برندس در سال ۲۰۰۱ محاسبه را از O(V^3) به O(VE) کاهش داد و مرکزیت بینابینی را برای شبکه‌هایی با هزاران گره عملی کرد و جایگاه آن را به عنوان یک ابزار استاندارد در نرم‌افزارهای تحلیل شبکه اجتماعی تثبیت کرد.

چه زمانی استفاده شود

هنگامی که سؤال تحقیق شما در مورد واسطه‌گری، دروازه‌بانی یا گره‌های پل است - بازیگرانی که حذف آن‌ها جریان اطلاعات یا انسجام شبکه را مختل می‌کند - از مرکزیت بینابینی استفاده کنید. این روش برای گراف‌های بدون جهت و جهت‌دار، و برای گراف‌های وزن‌دار که وزن یال‌ها نشان‌دهنده فاصله یا هزینه هستند، مناسب است. این روش به ویژه در شبکه‌های ارتباطی، شبکه‌های استنادی، گراف‌های همکاری و زنجیره‌های تأمین ارزشمند است. هنگامی که واسطه‌گری تمرکز نظری نیست، از آن به عنوان تنها معیار مرکزیت استفاده نکنید: مرکزیت درجه ساده‌تر و برای سؤالات صرفاً اتصال کافی است، و مرکزیت ویژگی یا PageRank انتشار اعتبار را بهتر نشان می‌دهد. از آن برای شبکه‌های پراکنده بسیار بزرگ بدون پیاده‌سازی کارآمد اجتناب کنید، زیرا محاسبه ساده O(V^2 E) است.

محدودیت‌ها و ملاحظات

  • حتی با الگوریتم برندس، از نظر محاسباتی در شبکه‌های بسیار متراکم پرهزینه است؛ ممکن است برای گراف‌های در مقیاس وب به الگوریتم‌های تقریبی نیاز باشد.
  • فرض می‌کند که بازیگران از کوتاه‌ترین مسیرها استفاده می‌کنند، که ممکن است در شبکه‌هایی که جریان‌ها از مسیرهای طولانی‌تر عبور می‌کنند (مانند گشت‌زنی تصادفی در شبکه‌های الکتریکی) غیرواقعی باشد.
  • به لبه‌های گمشده یا نویزی حساس است: حتی چند پیوند مشاهده نشده می‌تواند رتبه‌بندی بینابینی را به شدت تغییر دهد.
  • به تمام کوتاه‌ترین مسیرها وزن یکسانی می‌دهد، حتی زمانی که ظرفیت یال‌ها یا قدرت روابط به طور قابل توجهی متفاوت است.

شرایط منبع جایگزین بررسی علمی مستقل یا اعتبارسنجی توسط موتور تحلیل نیست.

نقاط قوت

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

کاربردها

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

چگونه کار می‌کند

چگونه کار می‌کند

1

برای هر جفت مرتب از گره‌های متمایز (s, t) در شبکه، تمام کوتاه‌ترین مسیرها (ژئودزیک‌ها) بین آن‌ها شناسایی می‌شوند. برای گراف‌های وزن‌دار، کوتاه‌ترین مسیرها با حداقل وزن کل یال تعریف می‌شوند؛ برای گراف‌های بدون وزن، با کمترین تعداد هاپ. این مرحله، جهان مسیرهایی را که بینابینی بر روی آن‌ها توزیع خواهد شد، تعیین می‌کند.

2

برای هر جفت (s, t) تعداد کل کوتاه‌ترین مسیرها sigma(s, t) شمارش می‌شود. هنگامی که چندین مسیر با طول مساوی وجود دارد، هر کدام به طور جداگانه شمارش می‌شوند. این مخرج، کل ترافیک کوتاه‌ترین مسیر بین s و t را بدون هیچ محدودیتی در مسیریابی نشان می‌دهد.

فرمول
\sigma(s,t) = \text{number of shortest paths from } s \text{ to } t
3

برای هر گره کاندید v (که v نه s است و نه t)، تعداد کوتاه‌ترین مسیرهای sigma(s, t) که واقعاً از v عبور می‌کنند، به صورت sigma(s, t | v) ثبت می‌شود. نسبت sigma(s, t | v) / sigma(s, t) کسری از ترافیک کوتاه‌ترین مسیر بین s و t را که از طریق v هدایت می‌شود، نشان می‌دهد.

فرمول
\sigma(s,t|v) = \text{shortest paths from } s \text{ to } t \text{ passing through } v
4

این کسورات بر روی تمام جفت‌های معتبر (s, t) جمع می‌شوند تا امتیاز خام بینابینی C_B(v) به دست آید. گره‌ای که حذف آن بسیاری از کوتاه‌ترین مسیرهای دوطرفه را قطع کند، مجموع بالایی را جمع‌آوری می‌کند و نشان‌دهنده موقعیت واسطه‌گری حیاتی ساختاری است.

فرمول
C_B(v) = \sum_{s \neq v \neq t} \frac{\sigma(s,t|v)}{\sigma(s,t)}
5

امتیازات خام با اندازه شبکه افزایش می‌یابند و مقایسه بین شبکه‌هایی با اندازه‌های مختلف را بی‌معنی می‌کنند. نرمال‌سازی با (n-1)(n-2)/2 برای گراف‌های بدون جهت (یا (n-1)(n-2) برای گراف‌های جهت‌دار) امتیازات را به [0, 1] مقیاس‌بندی مجدد می‌کند، جایی که ۱.۰ به این معنی است که گره بر روی هر کوتاه‌ترین مسیر قرار دارد و ۰ به این معنی است که بر روی هیچ مسیری قرار ندارد. برندس (۲۰۰۱) الگوریتم O(VE) را معرفی کرد که تمام امتیازات بینابینی را به طور همزمان محاسبه می‌کند به جای تکرار جستجو برای هر گره.

فرمول
C_B^{\text{norm}}(v) = \frac{C_B(v)}{(n-1)(n-2)/2}

دام‌های رایج

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

پرسش‌های متداول

مرکزیت بینابینی چگونه با مرکزیت درجه متفاوت است؟

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

آیا باید از امتیازات بینابینی نرمال‌شده یا خام استفاده کنم؟

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

چگونه با لبه‌های وزن‌دار برخورد کنم؟

وزن‌های یال را برای نشان دادن فاصله یا هزینه تنظیم کنید، نه شباهت. اکثر پیاده‌سازی‌ها (NetworkX، igraph) پارامتر وزن را می‌پذیرند که به عنوان فاصله تفسیر می‌شود؛ اگر وزن‌های شما قدرت یا شباهت را نشان می‌دهند، قبل از محاسبه بینابینی آن‌ها را معکوس کنید (مثلاً وزن = ۱/شباهت).

آیا مرکزیت بینابینی برای شبکه‌های جدا از هم معنی‌دار است؟

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

شبکه من میلیون‌ها گره دارد - آیا هنوز می‌توانم مرکزیت بینابینی را محاسبه کنم؟

محاسبه دقیق با الگوریتم برندس O(VE) است و ممکن است خیلی کند باشد. از تقریب‌های تصادفی (مانند نمونه‌برداری k گره منبع) موجود در NetworkX (betweenness_centrality با پارامتر k) یا کتابخانه‌های گراف مانند graph-tool استفاده کنید، که فواصل اطمینان را بر روی امتیازات تقریبی ارائه می‌دهند.

روش‌های مرتبط

منابع

  1. Freeman, L. C. (1977). A set of measures of centrality based on betweenness. Sociometry, 40(1), 35–41.

    باز کردن مرجع DOI
    کپی شد.
  2. Brandes, U. (2001). A faster algorithm for betweenness centrality. Journal of Mathematical Sociology, 25(2), 163–177.

    باز کردن مرجع DOI
    کپی شد.