اكتشاف المجتمعات — تجميع الرسوم البيانية في الشبكات
- قدّمه
- Louvain: Blondel et al. (2008); Leiden: Traag et al. (2019); Girvan-Newman: Girvan & Newman (2002); Infomap: Rosvall & Bergstrom (2008)
- السنة
- 2002–2019 (algorithm family)
- النوع
- Graph-partitioning / clustering algorithm family
هذا النص ترجمة آلية ولم تتم مراجعته بعد. اقرأ النص الأصلي بالإنجليزية
ماذا تفعل؟
اكتشاف المجتمعات هو عائلة من خوارزميات تقسيم الرسوم البيانية التي تكتشف مجموعات فرعية متصلة بكثافة — مجتمعات — داخل شبكة. تم تأسيس المجال رسميًا لأول مرة من خلال مقياس التعديل بواسطة جيرفان ونيومان (2002)، وشهد المجال تقدمًا سريعًا مع طريقة لوفين (بلونديل وآخرون، 2008)، وتحسين لايدن (تراج وآخرون، 2019)، ونهج إنفوماب القائم على نظرية المعلومات. تجيب جميع المتغيرات على نفس السؤال: أي العقد تتجمع معًا بشكل أوثق فيما بينها مقارنة ببقية الشبكة؟
الفكرة الحدسية وراء الطريقة
تخيل شبكة اجتماعية كبيرة حيث يتحدث بعض الأشخاص بشكل أساسي مع دائرتهم المباشرة بينما يصلون إليها بشكل متقطع فقط. يكتشف اكتشاف المجتمعات تلك الدوائر تلقائيًا، دون الحاجة إلى تسميتها مسبقًا. تعيد الخوارزمية ترتيب العقد إلى مجموعات بحيث تكون الاتصالات الداخلية كثيفة والاتصالات بين المجموعات متفرقة — مما يزيد من درجة الجودة المسماة التعديل (أو، في إنفوماب، يقلل من طول وصف المشي العشوائي عبر الشبكة). النتيجة هي تقسيم: تنتمي كل عقدة إلى مجتمع واحد بالضبط، ويمكنك تصور الشبكة كمجموعة من التجمعات المتماسكة.
التاريخ
تم وضع دراسة بنية المجتمع في الشبكات على أساس كمي بواسطة جيرفان ونيومان (2002)، الذين قدموا مفهوم المركزية البينية للحواف كأداة للتقسيم الهرمي للشبكة. ثم قام نيومان وجيرفان (2004) بتأسيس مقياس التعديل Q رسميًا، والذي أصبح معيار الجودة القياسي. نشر بلونديل وآخرون (2008) طريقة لوفين — تحسين جشع من مرحلتين جعل اكتشاف المجتمعات عالي الجودة عمليًا على الشبكات التي تحتوي على ملايين العقد. حدد تراج ووالتمان وفان إيك (2019) عيبًا هيكليًا في لوفين — أنه يمكن أن ينتج مجتمعات غير متصلة داخليًا — وطوروا خوارزمية لايدن لتصحيحه، مما يضمن تقسيمات متصلة جيدًا. بالتوازي، طور روزفال وبيرجستورم (2008) إنفوماب، الذي يعيد صياغة اكتشاف المجتمعات كمشكلة ضغط: ابحث عن التقسيم الذي يقلل من طول وصف المشي العشوائي على الشبكة.
متى تُستخدم
اكتشاف المجتمعات مناسب عندما يكون لديك شبكة (بحد أدنى ~20 عقدة) وترغب في اكتشاف بنية جماعية كامنة دون تحديد المجموعات مسبقًا. يناسب الأهداف الاستكشافية والوصفية والتصنيفية على بيانات الأوزان الثنائية أو المستمرة للحواف، بما في ذلك بيانات الشبكات المقطعية والطولية. لا يتطلب سمات عقد أو توزيعات طبيعية. هذه الطريقة مناسبة بشكل خاص عندما يكون عدد المجتمعات غير معروف. إذا كانت الشبكة صغيرة جدًا (أقل من 20 عقدة)، يُفضل استخدام إحصائيات الشبكة الوصفية. النتائج حساسة لتعريفات أوزان الحواف وكثافة الشبكة، لذا تستحق هذه الخيارات تفكيرًا دقيقًا.
الحدود والاعتبارات
- تحسين التعديل عرضة للقيم المحلية؛ قد تختلف النتائج عبر التشغيلات ويجب الإبلاغ عنها كأفضل نتيجة من بين عدة تشغيلات.
- حد الدقة يعني أنه يمكن دمج المجتمعات الصغيرة جدًا في الشبكات الكبيرة معًا، مما يخفي البنية الدقيقة.
- النتائج حساسة لكيفية تعريف أوزان الحواف؛ يمكن أن تؤدي مخططات الأوزان المختلفة إلى تقسيمات مختلفة ذات مغزى.
- تتميز جيرفان-نيومان بتعقيد O(m²n) وهي غير عملية على الشبكات الكبيرة؛ يجب تفضيل لوفين أو لايدن للحجم.
لا تغني شروط المصدر عن المراجعة العلمية المستقلة أو التحقق بواسطة محرك تحليل.
نقاط القوة
- لا يتطلب تحديد عدد المجتمعات مسبقًا — يتم تحديد حجم التقسيم بواسطة البيانات.
- يتوسع إلى الشبكات الكبيرة: تعمل لوفين ولايدن في وقت شبه خطي، مما يجعلها عملية للشبكات التي تحتوي على ملايين العقد.
- تضمن لايدن مجتمعات متصلة جيدًا ومتماسكة داخليًا، مما يصحح عيب المجتمعات غير المتصلة في لوفين.
- قابل للتطبيق على الشبكات غير الموزونة والموزونة دون افتراضات توزيعية على البيانات.
التطبيقات
- تحديد مجموعات البحث في شبكات الاستشهاد والتعاون المشترك لرسم خرائط المجالات العلمية.
- اكتشاف الوحدات الوظيفية في شبكات تفاعل البروتين والبروتين في علم الأحياء.
- العثور على مجتمعات المستخدمين في شبكات وسائل التواصل الاجتماعي والاتصالات لتحليل السلوك.
- تقسيم شبكات العملاء في الأعمال والتسويق للكشف عن مجموعات العملاء المتماسكة.
- اكتشاف الكتل الهيكلية في شبكات البنية التحتية أو النقل أو سلاسل التوريد.
كيف يعمل
كيف يعمل
المدخل هو رسم بياني تمثل عقده كيانات (أشخاص، صفحات ويب، بروتينات، استشهادات) وتمثل حوافه علاقات بينها. قد تكون الحواف موجهة أو غير موجهة، وقد تحمل أوزانًا. بنية التجاور — أي العقد متصلة وكيف بقوة — هي المدخل الوحيد الذي تحتاجه الخوارزميات. لا يلزم وجود تسميات عقد أو فئات أو سمات خارجية، على الرغم من أنه يمكن استخدامها للتحقق من النتائج لاحقًا.
تبدأ كل خوارزمية بتعيين أولي للعقد إلى المجتمعات. في لوفين ولايدن، تبدأ كل عقدة كمجتمع فردي خاص بها. تبدأ جيرفان-نيومان بالشبكة الكاملة وتزيل بشكل متكرر الحافة ذات أعلى مركزية بينية، مما يكشف تدريجيًا عن بنية المجتمع. يبدأ إنفوماب من وصف المشي العشوائي للشبكة ويقوم بتشفيره باستخدام خريطة ذات مستويين لتقليل طول الكود.
تبحث المرحلة الأساسية عن تقسيم يزيد من التعديل Q (لوفين، لايدن) أو يقلل من طول كود معادلة الخريطة (إنفوماب). تقوم لوفين بتحريك العقد الفردية بشكل جشع بين المجتمعات لتحسين Q، ثم تجمع المجتمعات في عقد فائقة وتكرر — عملية من مرحلتين تتوسع بشكل جيد ولكنها قد تنتج مجتمعات غير متصلة. تقوم لايدن بتحسين لوفين من خلال ضمان أن كل مجتمع متصل داخليًا، باستخدام خطوة نقل وتحسين محلية قبل التجميع. تزيل جيرفان-نيومان الحواف بشكل متكرر وتسجل الشجرة الهرمية للانقسامات؛ يتم اختيار التقسيم الذي يزيد من Q عند أي قطع للشجرة الهرمية. ينبثق عدد المجتمعات من الخوارزمية نفسها؛ لا يلزم تحديده مسبقًا.
يتم تلخيص جودة التقسيم النهائي بواسطة درجة التعديل Q، والتي تتراوح من -0.5 إلى 1. تعتبر القيم التي تزيد عن ~0.3–0.5 بشكل عام مؤشرًا على بنية مجتمع ذات مغزى. نظرًا لأن تحسين التعديل يمكن أن يعلق في القيم المحلية، فإن تشغيل الخوارزمية عدة مرات وأخذ أفضل نتيجة هو ممارسة قياسية. يتم أيضًا فحص التقسيم بصريًا والتحقق المتقاطع مقابل أي سمات عقد متاحة أو تسميات حقيقة مؤكدة للتأكد من أنه ذو مغزى جوهري.
الأخطاء الشائعة
- تشغيل الخوارزمية مرة واحدة ومعاملة النتيجة الوحيدة كحقيقة أساسية — قم دائمًا بتشغيلها عدة مرات والإبلاغ عن أفضل تعديل أو استخدام طرق مجمعة.
- تجاهل حد الدقة: في الشبكات المتفرقة الكبيرة، يمكن امتصاص المجتمعات الصغيرة ولكن الحقيقية في مجتمعات أكبر دون سابق إنذار.
- تطبيق الخوارزميات القائمة على التعديل على شبكات تحتوي على أقل من 20 عقدة — لا يمكن تحديد بنية المجتمع بشكل موثوق على هذا النطاق.
- الخلط بين درجة تعديل عالية وبنية مجتمع مؤكدة في العالم الحقيقي؛ التعديل هو مقياس جودة للتقسيم، وليس اختبارًا استنتاجيًا لما إذا كانت المجتمعات ذات دلالة إحصائية.
الأسئلة الشائعة
أي خوارزمية يجب أن أختار — لوفين، لايدن، جيرفان-نيومان، أم إنفوماب؟
لوفين هي خط أساس سريع وشائع الاستخدام للشبكات الكبيرة. لايدن هي الخيار المفضل عندما تكون الدقة مهمة، لأنها تضمن مجتمعات متصلة داخليًا وتحقق عادةً تعديلًا أعلى. تنتج جيرفان-نيومان شجرة هرمية مفيدة للاستكشاف الهرمي ولكنها بطيئة جدًا للشبكات الكبيرة. إنفوماب مناسب بشكل جيد للشبكات الموجهة أو القائمة على التدفق حيث يكون مسار المتجول العشوائي ذا مغزى.
هل أحتاج إلى تحديد عدد المجتمعات مسبقًا؟
لا. تحدد لوفين ولايدن وإنفوماب عدد المجتمعات تلقائيًا من بنية الشبكة. تنتج جيرفان-نيومان شجرة هرمية كاملة يمكن قراءة أي عدد من المجتمعات منها؛ عادةً ما يتم اختيار التقسيم الذي يزيد من Q.
كيف أعرف ما إذا كانت المجتمعات التي تم العثور عليها ذات مغزى؟
توفر درجة التعديل Q مقياس جودة داخلي للبيانات؛ تشير القيم التي تزيد عن حوالي 0.3–0.5 إلى بنية مجتمع غير تافهة. بخلاف ذلك، يجب التحقق من صحة المجتمعات مقابل معرفة المجال، أو سمات العقد، أو التسميات الخارجية. لا يثبت ارتفاع Q وحده الأهمية الاجتماعية أو البيولوجية.
ماذا يحدث إذا اختلفت النتائج عبر التشغيلات؟
تحسين التعديل هو طريقة استدلالية ويمكن أن تنتج التشغيلات المختلفة تقسيمات مختلفة قليلاً، خاصة في لوفين. قم بتشغيل الخوارزمية عدة مرات (10-100 تشغيل على الأقل على الشبكات الكبيرة) وأبلغ عن التقسيم بأعلى Q. لايدن أكثر استقرارًا من لوفين لأن خطوة التحسين الخاصة بها أكثر شمولاً، ولكن التشغيلات المتكررة تظل ممارسة جيدة.
طرق ذات صلة
المصادر
Blondel, V.D., Guillaume, J.-L., Lambiotte, R. & Lefebvre, E. (2008). Fast Unfolding of Communities in Large Networks. Journal of Statistical Mechanics, 2008(10), P10008.
افتح مرجع DOIتم النسخ.Traag, V.A., Waltman, L. & van Eck, N.J. (2019). From Louvain to Leiden: Guaranteeing Well-Connected Communities. Scientific Reports, 9, 5233.
افتح مرجع المنشورتم النسخ.