خوارزميات المطابقة في نموذج الكتلة العشوائية النادرة

نموذج الكتلة العشوائية (SBM) هو تعميم لنموذج إردوش-رينيو للرسم البياني العشوائي الذي يصف تفاعل عدد محدود من المجتمعات المتميزة. في الرسوم البيانية النادرة لإردوش-رينيو، يُعرف أن خوارزمية كارب وسيربسر ذات الزمن الخطّي تحقق أحجام مطابقة قريبة من المثالية بشكل شبه مؤكد، مما يوفر قانون الأعداد الكبيرة لأحجام المطابقة لمثل هذه الرسوم البيانية من حيث حلول لمعادلة تفاضلية عادية. نقدم امتدادًا لهذا التحليل، محددين نطاقات واسعة من معلمات نموذج الكتلة العشوائية التي تحقق فيها خوارزمية كارب--سيربسر أحجام مطابقة قريبة من المثالية، ولكن نثبت أنها لا يمكن أن تعمل بشكل مثالي على حالات SBM العامة. كما نعتبر مشكلة بناء مطابقة عبر الإنترنت، حيث تصل رؤوس نصف من نموذج الكتلة العشوائية ثنائية الاتجاه واحدة تلو الأخرى، ويجب مطابقتها كما تصل. نوضح أن الحد الأدنى لنسبة التنافسية 0.837 الذي وجده ماستين وجايل للاحتمال في حالة إردوش-رينيو هو ضيق كلما كانت الدرجات المتوقعة في جميع المجتمعات متساوية. نقترح عدة خوارزميات ذات زمن خطّي للمطابقة عبر الإنترنت في نموذج الكتلة العشوائية العامة، لكننا نثبت أنه على الرغم من الأداء التجريبي الجيد جداً، لا يحقق أي من هذه الخوارزميات المثالية الأسيموطية عبر الإنترنت.