العد الفعال لأقصى تكرار للمجموعات في الرسوم البيانية الثنائية الزمنية

تعدين الرسم البياني الفرعي المتماسك هو مشكلة أساسية في تحليل الرسوم البيانية الثنائية. في الواقع، العلاقات بين نوعين من الكيانات تحدث غالبًا عند بعض الطوابع الزمنية المحددة، والتي يمكن نمذجتها كرسوم بيانية ثنائية زمنية. ومع ذلك، فإن المعلومات الزمنية غالبًا ما يتم تجاهلها من قبل الدراسات السابقة. علاوة على ذلك، قد يؤدي توسيع النماذج الحالية بشكل مباشر إلى فشل في العثور على بعض المجموعات الحرجة في الرسوم البيانية الثنائية الزمنية، التي تظهر في شكل أحادي الجانب (أي، طبقة واحدة). لسد الفجوة، نقترح في هذا البحث نموذجًا جديدًا، يسمى مجموعة التكرار الأقصى λ (MFG). بالنظر إلى الرسم البياني الثنائي الزمني 𝒢 = (U, V, ℰ)، تعتبر مجموعة الرؤوس V S ⊆ V مجموعة MFG إذا i) لا يوجد أقل من λ طابع زمني، يمكن عند كلٍ منها لمجموعة V S تكوين ثنائي (τ U ، τ V) مع بعض الرؤوس في U عند اللحظة المقابلة، و ii) تكون قصوى. لحل المشكلة، تم اقتراح طريقة التصفية والتحقق (FilterV) استنادًا إلى إطار Bron-Kerbosch، مع دمج تقنيات تصفية جديدة لتقليل مساحة البحث واستراتيجية قائمة على المصفوفات لتسريع التحقق من التكرار والقصوى. ومع ذلك، فإن تكلفة التحقق من التكرار في كل حساب لمجموعة المرشحين الصالحين والتحقق من القصوى قد تحد من قابلية توسيع FilterV إلى رسوم بيانية أكبر. لذلك، نقوم بتطوير نهج جديد غير قائم على التحقق (VFree) من خلال الاستفادة من هيكل العد الديناميكي المتقدم المقترح. من الناحية النظرية، نثبت أن VFree يمكن أن يقلل تكلفة كل حساب لمجموعة المرشحين الصالحين في FilterV بمقدار O (| V |). علاوة على ذلك، يمكن لـ VFree تجنب التحقق الصريح من القصوى بسبب نموذج البحث المطور. أخيرًا، تم إجراء تجارب شاملة على 15 رسمًا بيانيًا من العالم الحقيقي لإظهار كفاءة وفاعلية التقنيات والنموذج المقترح.