میانی مرکزی

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

هدارش (تعریف)

میانی مرکزی برای گرهٔ $v$ برابر است با:

$g(v)=\sum _{s\neq v\neq t}{\frac {p_{st}(v)}{p_{st}}}$

که $p_{st}$ همهٔ کوتاه‌ترین راه‌های میان جفت‌گرهٔ $s$ و $t$ است و $p_{st}(v)\subseteq p_{st}$ همهٔ کوتاه‌ترین راه‌هایی است میان جفت‌گرهٔ $s$ و $t$ که از $v$ نیز می‌گذرند. بخش کردن بر $p_{st}$ برای هنجارور (نرمال) کردن سنجه است. از آنجایی که $p_{st}(v)\leq p_{st}$ همواره داریم $g(v)\leq 1$ . اندازهٔ بزرگ میانی مرکزی گره‌ای[3] نشان دهندهٔ آن است که این گره به دیگر گره‌های گراف از راه‌هایی کوتاه دسترسی بیابد یا در میانهٔ راه‌های کوتاه به دیگر گره‌هاست.

زمینه‌های در پیوند

میانی مرکزی به زمینهٔ همبندی گراف‌ها نیز بسیار نزدیک است. از آنجایی که گره‌ای با اندازهٔ میانی مرکزی بالا در میانهٔ بسیاری راه‌های دیگر جای دارد، برداشتنش می‌تواند گراف را ناهمبند کند. هم‌چنین میانی مرکزی به زمینهٔ مجموعهٔ برش نزدیک می‌کند.

منابع

Freeman, Linton (1977). "A set of measures of centrality based on betweenness". Sociometry. 40: 35–41. doi:10.2307/3033543.
Newman, M.E.J. (2010). Networks: An Introduction. Oxford, UK: Oxford University Press. ISBN 978-0-19-920665-0.
Brandes, Ulrik (2001). "A faster algorithm for betweenness centrality". The Journal of Mathematical Sociology. doi:10.1080/0022250X.2001.9990249. Check date values in: |accessdate= (help); |access-date= requires |url= (help)

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[freeman1977-1] Freeman, Linton (1977). "A set of measures of centrality based on betweenness". Sociometry. 40: 35–41. doi:10.2307/3033543.

[NewmanNetworks-2] Newman, M.E.J. (2010). Networks: An Introduction. Oxford, UK: Oxford University Press. ISBN 978-0-19-920665-0.

[3] Brandes, Ulrik (2001). "A faster algorithm for betweenness centrality". The Journal of Mathematical Sociology. doi:10.1080/0022250X.2001.9990249. Check date values in: |accessdate= (help); |access-date= requires |url= (help)