مكتبة الرسوم البيانية المعززة:هل هناك خوارزمية أنيقة مدمجة في BGL لاكتشاف المجتمع؟

Question

هل يستخدم أي شخص BGL لخوادم الإنتاج الكبيرة؟

• من كم عقدة تتكون شبكتك؟
• كيف تتعامل كشف المجتمع
• هل لدى BGL أي طرق رائعة لاكتشاف المجتمعات؟
• في بعض الأحيان قد يتم ربط مجتمعين معًا بواسطة حافة واحدة أو اثنتين، ولكن هذه الحواف غير موثوقة ويمكن أن تتلاشى.في بعض الأحيان لا توجد حواف على الإطلاق.

هل يمكن لأحد أن يتحدث باختصار عن كيفية حل هذه المشكلة.من فضلك افتح ذهني وألهمني.

لقد تمكنت حتى الآن من العمل إذا كانت العقدان في جزيرة (في مجتمع) بطريقة باهظة الثمن ، لكنني الآن بحاجة إلى معرفة أي عقدتين في جزر منفصلة هي الأقرب إلى بعضهما البعض.لا يمكننا إلا أن نستخدم الحد الأدنى من البيانات الجغرافية غير الموثوقة.

إذا قارناها مجازيًا بالبر الرئيسي والجزيرة وأخرجناها من سياق المسافة الاجتماعية.أريد معرفة أي قطعتين من الأرض هما الأقرب لبعضهما عبر مسطح مائي.

Answer 1

لقد استخدمت BGL للرسوم البيانية التي تحتوي على ملايين العقد، ولكن حجم الرسم البياني الذي يمكنك استخدامه يعتمد على الخوارزمية التي تحاول تشغيلها.يمكنك حساب المسافات بين العقد بسرعة.هناك 4 خوارزميات للمسار الأقصر والتي تكون أكثر قابلية للتطبيق اعتمادًا على بياناتك:(أزواج فردية من النقاط، لجميع أزواج النقاط، رسوم بيانية متفرقة وكثيفة،...).

أما بالنسبة لاكتشاف المجتمع، فلا توجد أي خوارزميات مدمجة في BGL خصيصًا لذلك (ولكن ربما يمكنك المساهمة بواحدة عند الانتهاء من مشروعك).هناك بعض الخوارزميات التي قد تكون مفيدة في بناء خوارزمية اكتشاف المجتمع.ال أقصى تدفق/دقيقة قطع تُستخدم الخوارزميات عادةً في اكتشاف المجتمع (إذا كان هناك الكثير من التدفق المحتمل بين عقدتين، فمن المحتمل أن يكونا في نفس المجتمع، وإذا لم يكن هناك الكثير من التدفق، فمن المرجح أن يمثل الحد الأدنى الطرق بين العقدتين مجتمعات).هناك أيضًا استدلالات لترتيب تقليل عقد الرسم البياني عرض النطاق.من المرجح أن تكون العقد التي تشكل "المجتمعات" قريبة من بعضها البعض في مثل هذا الترتيب.

Answer 2

بقدر ما أعرف، ليس لدى BGL أي خوارزميات مخصصة لاكتشاف المجتمع.

هل تقصد بكلمة "جزيرة" رسمًا بيانيًا فرعيًا منفصلاً؟

كما أن الرسوم البيانية لا تحتوي على أي فكرة عن "المسافة".

هذه "المسافة الاجتماعية" هي شيء سيتعين عليك تحديده.بمجرد الانتهاء من ذلك، يتم إنجاز جزء كبير من العمل.

هناك العديد من الطرق المدرجة في الصفحة التي قمت بالارتباط بها، ومعظمها يتطلب منك فقط تحديد شيء مثل مقياس "المسافة"، ثم إدخال تعريفاتك في الخوارزمية.

@ ديفيد نعمة

الرسوم البيانية التي لا تحتوي على أوزان حافة تتعلق فقط بالترابط، وليس لديها فكرة عن المسافة.إذا كنت تريد التحدث عن الشبكة، فيمكنك التحدث عن المسافة.لكن الرسم البياني الذي لا يحتوي على أوزان حواف ليس له أي مسافة، إلا إذا كنت تريد افتراض وزن حافة ضمني قدره 1 لجميع الحواف.ولكن هذا في الواقع مجرد تحويل الرسم البياني إلى شبكة.

ويتحدث أيضًا عن المسافة بين رسمين بيانيين منفصلين.لنمذجة ذلك، عليك تقديم مفهوم خارجي للمسافة بين العقد، منفصلة عن مسافة الحافة.