الخوارزميات الخاصة بالكثافة العليا للرسوم البيانية ذات الوزن الرأسي

إن العثور على الكثافة العليا للرسوم البيانية له إمكانيات هائلة في رؤى الحاسوب وأبحاث الشبكات الاجتماعية، من بين مجالات أخرى. في رؤى الحاسوب، يمكن أن يظهر الهياكل الأساسية، وفي أبحاث الشبكات الاجتماعية، يساعد في تحديد المجتمعات المرتبطة ارتباطًا وثيقًا. مشكلة الكثافة العليا هي العثور على رسم بياني فرعي بأقصى كثافة متوسطة. ومع ذلك، فإن معظم الخوارزميات الخاصة بالعثور على الرسوم البيانية ذات الكثافة العليا تعتمد على الرسوم البيانية ذات الوزن الحدي، حيث يمكن أن تمثل أوزان الحواف قيمة واحدة فقط، في حين أن التطبيقات العملية تشمل أبعادًا متعددة. لحل التحدي، نقترح خوارزميتين لحل مشكلة الرسم البياني الفرعي الأكثر كثافة في رسم بياني ذي وزن رأسي. أولاً، نقدم خوارزمية دقيقة تستند إلى الخوارزمية الأصلية لجولدبيرغ. من خلال الاستكشاف والتحليل النظري، نتحقق بدقة من صحة الخوارزمية المقترحة ونؤكد أنها يمكن أن تعمل بكفاءة في زمن متعدد الحدود O(n(n + m)log2n) هي تعقيدها الزمني. يمكن تطبيق نهجنا على تحديد المجموعات الفرعية المرتبطة ارتباطًا وثيقًا والتي تظهر الحد الأقصى من الكثافة المتوسطة في المواقف الحقيقية. بالإضافة إلى ذلك، نقدم باستمرار خوارزمية تقريبية تضمن نسبة تقريب دقيقة قدرها 2. في الختام، تعزز مساهماتنا الأسس النظرية لمعالجة مشكلة الرسم البياني الفرعي الأكثر كثافة.