التقريب السريع لمركزية التوسط من خلال العينة

مركزية التوسط هي مقياس أساسي في تحليل الشبكات الاجتماعية، حيث تعبر عن أهمية أو تأثير رؤوس فردية في الشبكة من حيث النسبة المئوية لأقصر المسارات التي تمر من خلالها. الحساب الدقيق في الشبكات الكبيرة مكلف للغاية، ومن الضروري وجود خوارزميات تقريب سريعة في هذه الحالات. نقدم خوارزميتين فعالتين عشوائيتين لتقدير التوسط. تستند الخوارزميات إلى العينة العشوائية لأقصر المسارات وتقدم ضمانات احتمالية حول جودة التقريب. تقوم الخوارزمية الأولى بتقدير التوسط لجميع الرؤوس: جميع القيم المقدرة تقع ضمن عامل إضافي ɛ من القيم الحقيقية، مع احتمال لا يقل عن 1-δ. تركز الخوارزمية الثانية على أفضل K من الرؤوس ذات أعلى وسطية وتقرب وسطها ضمن عامل مضاعف ɛ، مع احتمال لا يقل عن 1-δ. هذه هي الخوارزمية الأولى التي يمكنها حساب مثل هذا التقريب لأفضل K من الرؤوس. نستخدم نتائج من نظرية بُعد VC لتطوير حدود لحجم العينة اللازمة لتحقيق التقريبات المرغوبة. من خلال إثبات حدود عليا وسفلى لبُعد VC لمجموعة مرتبطة بالمشكلة المطروحة، نحصل على حجم عينة مستقل عن عدد الرؤوس في الشبكة ويعتمد فقط على كمية مميزة نسميها قطر الرأس، وهو العدد الأقصى من الرؤوس في أقصر مسار. في بعض الحالات، يكون حجم العينة مستقلاً تمامًا عن أي خاصية للرسم البياني. يُظهر التقييم التجريبي الواسع الذي قمنا به باستخدام الشبكات الحقيقية والاصطناعية أن خوارزميتنا أسرع بشكل ملحوظ وأكثر قابلية للتوسع مع زيادة عدد الرؤوس في الشبكة مقارنة بالخوارزميات التي قدمت سابقًا مع ضمانات تقريب مماثلة.