مركزية البينونة
- قدّمه
- Freeman, L. C.
- السنة
- 1977
- النوع
- Centrality measure
- العائلة
- Network science
هذا النص ترجمة آلية ولم تتم مراجعته بعد. اقرأ النص الأصلي بالإنجليزية
ماذا تفعل؟
تقيس مركزية البينونة، التي صاغها لينتون سي. فريمان في عام 1977، عدد المرات التي تقع فيها عقدة على أقصر مسار يربط كل زوج آخر من العقد في شبكة. تعمل العقد ذات البينونة العالية كجسور أو وسطاء: إزالتها تقسم الشبكة إلى مكونات غير متصلة بشكل أكثر حدة من إزالة أي عقد أخرى.
الفكرة الحدسية وراء الطريقة
فكر في شبكة طرق مدينة حيث تمر جميع طرق عبور البلاد عبر تقاطع واحد. هذا التقاطع لديه أقصى بينونة حتى لو كان لديه عدد معتدل فقط من الطرق. في شبكة اجتماعية، يشغل شخص يمرر المعلومات بشكل روتيني بين مجموعتين منفصلتين بخلاف ذلك نفس الموقف: قد لا يعرف الكثير من الناس مباشرة، لكنهم يجلسون على المسار الحرج الذي يحافظ على تماسك الشبكة. تقيس مركزية البينونة بالضبط هذا الدور الوسيط، بغض النظر عن عدد الاتصالات الخام.
التاريخ
صاغ لينتون فريمان مركزية البينونة في ورقته البحثية الرائدة في علم الاجتماع عام 1977، مستفيدًا من الاستخدامات غير الرسمية السابقة للمفهوم من قبل بافلاس (1948) في تجارب الاتصال. وحدت صياغة فريمان العديد من الحدس الفضفاض حول أهمية العقدة في مقياس واحد قابل للحساب وأصبحت التعريف القياسي المستخدم في علم الشبكات. قللت خوارزمية أولريك براندس لعام 2001 الحساب من O(V^3) إلى O(VE)، مما جعل مركزية البينونة عملية للشبكات التي تحتوي على آلاف العقد وترسخ مكانتها كأداة قياسية في برامج تحليل الشبكات الاجتماعية.
متى تُستخدم
استخدم مركزية البينونة عندما يكون سؤال بحثك حول الوساطة، أو البوابات، أو عقد الجسر - الجهات الفاعلة التي من شأن إزالتها أن تعطل تدفق المعلومات أو تماسك الشبكة. وهي مناسبة للرسوم البيانية الموجهة وغير الموجهة، وللرسوم البيانية الموزونة حيث تمثل أوزان الحواف المسافة أو التكلفة. وهي ذات قيمة خاصة في شبكات الاتصالات، وشبكات الاستشهاد، ورسوم التعاون، وسلاسل التوريد. لا تستخدمها كقياس مركزي وحيد عندما لا تكون الوساطة هي التركيز النظري: مركزية الدرجة أبسط وكافية لأسئلة الاتصال البحتة، ومركزية المتجه الذاتي أو PageRank تلتقط انتشار الهيبة بشكل أفضل. تجنبها للشبكات المتفرقة الكبيرة جدًا بدون تنفيذ فعال، لأن الحساب الساذج هو O(V^2 E).
الحدود والاعتبارات
- مكلفة حسابيًا على الشبكات الكثيفة جدًا حتى مع خوارزمية براندس؛ قد تكون هناك حاجة لخوارزميات تقريبية للرسوم البيانية على نطاق الويب.
- تفترض أن الجهات الفاعلة تستخدم أقصر المسارات، وهو ما قد يكون غير واقعي في الشبكات التي تعبر فيها التدفقات مسارات أطول (مثل، المشي العشوائي في الشبكات الكهربائية).
- حساسة للحواف المفقودة أو المشوشة: حتى عدد قليل من الروابط غير المرصودة يمكن أن يغير ترتيبات البينونة بشكل كبير.
- تعطي وزنًا متساويًا لجميع أقصر المسارات حتى عندما تختلف سعات الحواف أو قوة العلاقات اختلافًا كبيرًا.
لا تغني شروط المصدر عن المراجعة العلمية المستقلة أو التحقق بواسطة محرك تحليل.
نقاط القوة
- تلتقط أدوار الوساطة والجسر الهيكلية التي تفوتها مركزية الدرجة والمتجه الذاتي تمامًا.
- قابلة للتطبيق على الشبكات الموجهة وغير الموجهة والموزونة وغير الموزونة بنفس الصيغة.
- الدرجة المطبّعة تمكّن من مقارنة ذات مغزى للعقد داخل شبكة واحدة وعبر شبكات ذات أحجام مختلفة.
- خوارزمية براندس تجعل الحساب قابلاً للتتبع للشبكات التي تحتوي على ملايين العقد عند تنفيذها في مكتبات محسّنة مثل NetworkX أو igraph.
- تفسير نظري راسخ: ترتبط العقد ذات البينونة العالية تجريبيًا بالتحكم في المعلومات والسلطة والثقوب الهيكلية في الأبحاث التنظيمية والاجتماعية.
التطبيقات
- تحديد البوابات ووسطاء المعلومات في شبكات الاتصال التنظيمية.
- اكتشاف عقد البنية التحتية الحيوية في دراسات النقل وشبكات الطاقة وطوبولوجيا الإنترنت.
- العثور على المؤلفين أو الأوراق الوسيطة الرئيسية في شبكات الاستشهاد والتعاون.
- رسم خرائط الثقوب الهيكلية ومواقع الوساطة في شبكات التحالفات بين الشركات.
- تحديد المنتشرين المؤثرين في نماذج الأوبئة وانتشار الشائعات.
- تحديد أولويات العقد للتدخلات المستهدفة (مثل التطعيم، التعطيل) في أبحاث الصحة العامة والأمن.
كيف يعمل
كيف يعمل
لكل زوج مرتب من العقد المميزة (s, t) في الشبكة، يتم تحديد جميع أقصر المسارات (الجيوديسية) بينهما. بالنسبة للرسوم البيانية الموزونة، تُعرّف أقصر المسارات بالحد الأدنى لوزن الحافة الإجمالي؛ بالنسبة للرسوم البيانية غير الموزونة، بأقل عدد من القفزات. تحدد هذه الخطوة عالم المسارات التي سيتم توزيع البينونة عليها.
لكل زوج (s, t) يتم عد العدد الإجمالي لأقصر المسارات sigma(s, t). عندما توجد مسارات متعددة متساوية في الطول، يتم عد كل منها بشكل منفصل. يمثل هذا المقام إجمالي حركة مرور أقصر المسارات بين s و t دون أي قيود على التوجيه.
الصيغة
\sigma(s,t) = \text{number of shortest paths from } s \text{ to } tلكل عقدة مرشحة 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تُجمع هذه الكسور لجميع الأزواج الصالحة (s, t) لإنتاج درجة البينونة الخام C_B(v). العقدة التي يؤدي إزالتها إلى فصل العديد من أقصر المسارات بين الأزواج تجمع مجموعًا عاليًا، مما يشير إلى موقع وسيط حرج هيكليًا.
الصيغة
C_B(v) = \sum_{s \neq v \neq t} \frac{\sigma(s,t|v)}{\sigma(s,t)}تنمو الدرجات الخام مع حجم الشبكة، مما يجعل المقارنات عبر الشبكات ذات الأحجام المختلفة غير ذات مغزى. التطبيع بواسطة (n-1)(n-2)/2 للرسوم البيانية غير الموجهة (أو (n-1)(n-2) للرسوم البيانية الموجهة) يعيد قياس الدرجات إلى [0, 1]، حيث يعني 1.0 أن العقدة تقع على كل أقصر مسار و 0 يعني أنها لا تقع على أي منها. قدم براندس (2001) خوارزمية O(VE) تحسب جميع درجات البينونة في وقت واحد بدلاً من تكرار البحث لكل عقدة.
الصيغة
C_B^{\text{norm}}(v) = \frac{C_B(v)}{(n-1)(n-2)/2}الأخطاء الشائعة
- معاملة البينونة العالية على أنها مكافئة للدرجة العالية دون التحقق من كليهما؛ يمكن لعقدة طرفية أن تحتل المرتبة الأولى في البينونة بينما تحتل المرتبة الأخيرة في الدرجة.
- مقارنة درجات البينونة الخام (غير المطبّعة) عبر شبكات ذات أحجام مختلفة.
- تجاهل اتجاه الحافة في الشبكات الموجهة، مما قد ينتج عنه تحديد مضلل للوسطاء عندما تكون التدفقات غير متناظرة.
- تطبيق البينونة القياسية على الشبكات الموزونة دون التأكد من أن أوزان الحواف تُفسر بشكل صحيح كتكاليف (وليس تشابهات) في خوارزمية أقصر المسارات.
- تجاهل طرق البينونة التقريبية للشبكات الكبيرة وتعطيل الحساب على ملايين العقد.
الأسئلة الشائعة
كيف تختلف مركزية البينونة عن مركزية الدرجة؟
تقيس مركزية الدرجة الاتصالات المباشرة؛ تحصل المحور الذي يحتوي على العديد من الروابط على درجة عالية. تقيس مركزية البينونة عدد المرات التي تقع فيها عقدة على أقصر المسارات بين الآخرين؛ تحصل الجسر الذي يربط مجموعتين متفرقتين على درجة عالية حتى مع وجود عدد قليل من الروابط المباشرة. المقياسان يلتقطان جوانب متعامدة للأهمية الهيكلية.
هل يجب أن أستخدم درجات البينونة المطبّعة أم الخام؟
استخدم الدرجات المطبّعة كلما قارنت العقد عبر شبكات ذات أحجام مختلفة أو قدمت النتائج للقراء غير المطلعين على حجم شبكتك. درجات الخام مقبولة فقط للمقارنات داخل شبكة ثابتة واحدة حيث يكون المقام ثابتًا.
كيف أتعامل مع الحواف الموزونة؟
اضبط أوزان الحواف لتمثيل المسافة أو التكلفة، وليس التشابه. تقبل معظم التطبيقات (NetworkX، igraph) معلمة وزن تُفسر على أنها مسافة؛ إذا كانت أوزانك تمثل القوة أو التشابه، فاعكسها (على سبيل المثال، الوزن = 1 / التشابه) قبل حساب البينونة.
هل مركزية البينونة ذات مغزى للشبكات غير المتصلة؟
بالنسبة للرسوم البيانية غير المتصلة، أقصر المسارات بين العقد في المكونات المختلفة غير محددة (لانهائية). تتعامل معظم البرامج مع هذه الأزواج على أنها تساهم بصفر في المجموع، مما قد يقلل من الدرجات. قم بتحليل كل مكون متصل بشكل منفصل أو استخدم متغيرًا مثل مركزية الإجهاد مع معالجة صريحة للأزواج غير المتصلة.
شبكتي تحتوي على ملايين العقد - هل ما زلت أستطيع حساب مركزية البينونة؟
الحساب الدقيق باستخدام خوارزمية براندس هو O(VE) وقد يكون بطيئًا جدًا. استخدم تقريبات عشوائية (مثل، أخذ عينات من k عقد مصدر) متاحة في NetworkX (betweenness_centrality مع معلمة k) أو مكتبات الرسوم البيانية مثل graph-tool، والتي توفر فترات ثقة على الدرجات التقريبية.
طرق ذات صلة
المصادر
Freeman, L. C. (1977). A set of measures of centrality based on betweenness. Sociometry, 40(1), 35–41.
افتح مرجع DOIتم النسخ.Brandes, U. (2001). A faster algorithm for betweenness centrality. Journal of Mathematical Sociology, 25(2), 163–177.
افتح مرجع DOIتم النسخ.