دراسة نمذجة وحساب لمؤشر الإحباط في الشبكات الموقعة

الملخص يعد حساب مؤشر الإحباط لرسم بياني موقع خطوة أساسية نحو حل المشكلات في العديد من المجالات بما في ذلك الشبكات الاجتماعية، العلوم السياسية، الفيزياء، الكيمياء، وعلوم الأحياء. يحدد مؤشر الإحباط المسافة التي تفصل شبكة عن حالة التوازن الهيكلي التام. على الرغم من أن تعريف مؤشر الإحباط يعود إلى الخمسينيات، فإن حسابه الدقيق بشكل خوارزمي، والذي يرتبط ارتباطًا وثيقًا بمشكلات الرسم البياني الكلاسيكية NP الصعبة، لم يصبح نقطة تركيز إلا في السنوات الأخيرة. نطور ثلاثة نماذج جديدة من البرمجة الخطية الثنائية لحساب مؤشر الإحباط بدقة وكفاءة كحل لمشكلة تحسين عالمية. من خلال حل النماذج باستخدام التفرع ذو الأولويات وعدم المساواة الصحيحة في Gurobi، يمكننا حساب مؤشر الإحباط لشبكات موقعة حقيقية بها أكثر من 15,000 حافة في أقل من دقيقة على أجهزة ميسورة التكلفة. نقدم تحليلاً شاملاً للأداء لكل من الشبكات العشوائية والحقيقية الموقعة ونوضح أن نماذجنا تتفوق على جميع الطرق الموجودة بعوامل كبيرة. بناءً على زمن الحل، ومخرجات الخوارزمية، وعامل التفرع الفعال، نبرز تفوق نماذجنا على كل من الطرق الدقيقة والخيالية في الأدبيات.