Command Palette
Search for a command to run...
نُواة رسمية فعالة للرسوم البيانية الكبيرة لمقارنة الرسوم البيانية
نُواة رسمية فعالة للرسوم البيانية الكبيرة لمقارنة الرسوم البيانية
S. V. N. Vishwanathan Karsten Borgwardt. Kurt Mehlhorn Tobias Petri Nino Shervashidze
الملخص
لا تُ-scalable الحُزم الرسومية الحديثة إلى الرسومات الكبيرة التي تحتوي على مئات العقد وآلاف الحواف. في هذه المقالة، نقترح مقارنة الرسومات من خلال عدّ الرسوم الفرعية (graphlets)، أي الرسوم الفرعية المكونة من ( k ) عقد، حيث ( k \in {3; 4; 5} ). وبما أن التعداد الشامل لجميع الرسوم الفرعية يكون مكلفًا جدًا من حيث التكلفة الحسابية، نُقدّم حلين مسرّعين مبنيين على أساس نظري: الأول يعتمد على العينة (sampling)، والثاني مصمم خصيصًا للرسومات ذات الدرجة المحدودة (bounded degree graphs). وفي التقييم التجريبي، أظهرت الحُزم الجديدة التي اقترحناها قدرة فعّالة على مقارنة الرسومات الكبيرة التي لا يمكن التعامل معها بواسطة الحُزم الحالية للرسومات.