تحليل النمطية
- قدّمه
- Newman, M. E. J. & Girvan, M.
- السنة
- 2004
- النوع
- Community detection / graph partitioning
- العائلة
- Network science
هذا النص ترجمة آلية ولم تتم مراجعته بعد. اقرأ النص الأصلي بالإنجليزية
ماذا تفعل؟
تحليل النمطية هو طريقة في علم الشبكات، صاغها نيومان وجيرفان في عام 2004، تكتشف البنية المجتمعية في الرسوم البيانية عن طريق قياس ما إذا كانت الحواف تتركز داخل المجموعات أكثر مما هو متوقع بالصدفة. دليل الجودة الكمي Q الخاص بها يوجه الخوارزميات التي تقسم العقد إلى مجموعات متماسكة، مما يجعلها الإطار الأكثر اعتمادًا على نطاق واسع للكشف عن المجتمعات في الشبكات الاجتماعية والبيولوجية والتكنولوجية.
الفكرة الحدسية وراء الطريقة
إذا قمت بإعادة توصيل جميع حواف الشبكة بشكل عشوائي مع الحفاظ على درجة كل عقدة سليمة، فستحصل على نموذج صفري لا يحتوي على مجتمعات حقيقية. تقارن النمطية توزيع الحواف الفعلي بهذا النموذج الصفري: إذا كان التقسيم ينتج عددًا أكبر بكثير من الحواف داخل المجموعات مما يتوقعه النموذج الصفري، فإن Q يكون مرتفعًا، مما يشير إلى بنية مجتمعية حقيقية. يبحث المحسن في مساحة التقسيمات الممكنة عن الانقسام الذي يزيد من Q، ويكشف عن المجموعات الطبيعية التي تشير إليها بنية الشبكة، دون الحاجة إلى أن يحدد المحلل عدد المجتمعات مقدمًا.
التاريخ
تم تقديم دالة النمطية Q بواسطة نيومان وجيرفان في عام 2004 كجزء من مجموعة من تقنيات الكشف عن المجتمعات. قام نيومان في ورقة PNAS لعام 2006 بتشكيل النهج الطيفي لتحسين النمطية، وجعلت طريقة لوفين (بلونديل وآخرون، 2008) التحسين واسع النطاق عمليًا، مما أدى إلى شيوع تحليل النمطية عبر علم الاجتماع والبيولوجيا وعلوم الكمبيوتر. تم تحديد مشكلة حد الدقة بواسطة فورتوناتو وبارثيلمي في عام 2007، مما حفز على تحسين الخوارزميات مثل لايدن (تراج وآخرون، 2019) التي تصحح أيضًا المجتمعات ضعيفة الاتصال.
متى تُستخدم
استخدم تحليل النمطية عندما يكون لديك مجموعة بيانات علائقية يمكن تمثيلها كرسم بياني وترغب في تحديد مجموعات فرعية متماسكة دون تحديد عددها مسبقًا - على سبيل المثال، اكتشاف الفصائل في الشبكات الاجتماعية، أو الوحدات الوظيفية في شبكات تفاعل البروتين، أو مجموعات المواضيع في شبكات الاستشهاد. وهي مناسبة للرسوم البيانية غير الموجهة والموجهة التي تحتوي على عشرات العقد على الأقل وهيكل حواف غير تافه بوضوح. لا تستخدمها عندما تكون الشبكة صغيرة جدًا (أقل من حوالي 30 عقدة) أو شبه كاملة، عندما تحمل أوزان الحواف معلومات حاسمة يتجاهلها نموذج صفري ثنائي بسيط، عندما يكون من المعروف أن المجتمعات تتداخل بشكل كبير (استخدم طرق المجتمعات المتداخلة بدلاً من ذلك)، أو عندما تحتاج إلى حدود مختبرة إحصائيًا بدلاً من استدلال تحسين.
الحدود والاعتبارات
- حد الدقة: تحسين النمطية يفشل بشكل منهجي في اكتشاف المجتمعات الأصغر من مقياس تحدده حجم الشبكة، ويدمج الوحدات الصغيرة المتميزة حقًا.
- تحسين NP-hard الدقيق يعني أنه لا يتم استخدام سوى التقريبات في الممارسة العملية، ويمكن أن تؤدي عمليات التشغيل المختلفة للخوارزميات العشوائية إلى تقسيمات مختلفة.
- يفترض النموذج الصفري نموذج التكوين (تسلسل درجة شبيه بإردوس-ريني)، والذي قد يكون غير مناسب للشبكات ذات التوزيعات الدرجية ذات الذيل الثقيل أو الهيكل الهرمي.
- لا يمكن للحدود المجتمعية الصلبة أن تمثل العضويات المتداخلة في العالم الحقيقي.
لا تغني شروط المصدر عن المراجعة العلمية المستقلة أو التحقق بواسطة محرك تحليل.
نقاط القوة
- لا حاجة لتحديد عدد المجتمعات مقدمًا؛ يظهر التقسيم من البيانات.
- يوفر قيمة كمية واحدة Q تسهل المقارنة المباشرة للتقسيمات أو الشبكات المختلفة.
- الخوارزميات التقريبية السريعة (لوفين، لايدن) تتوسع لتشمل ملايين العقد.
- قابلة للتطبيق على الشبكات غير الموجهة والموجهة والموزونة مع امتدادات مناسبة.
- مطبقة على نطاق واسع في المكتبات القياسية (NetworkX، igraph، Gephi)، مما يقلل من حاجز الاستخدام.
التطبيقات
- اكتشاف الفصائل الاجتماعية، غرف الصدى، أو مجموعات التعاون في الشبكات الاجتماعية عبر الإنترنت وغير المتصلة بالإنترنت.
- تحديد الوحدات الوظيفية في الشبكات البيولوجية مثل تفاعل البروتين والرسوم البيانية التنظيمية الجينية.
- الكشف عن مجموعات المواضيع أو التخصصات في شبكات الاستشهاد والتعاون في التأليف.
- تقسيم شبكات العملاء أو المنتجات في أنظمة التسويق والتوصية.
- تقسيم شبكات البنية التحتية (شبكات الطاقة، النقل) لتحليل المرونة.
- اكتشاف مجتمعات المواضيع في الرسوم البيانية للروابط التشعبية أو التواجد المشترك في اللغويات الحاسوبية.
كيف يعمل
كيف يعمل
يتم تمثيل الشبكة كمصفوفة تجاور A (أو قائمة حواف مكافئة)، حيث تساوي القيمة A_ij 1 إذا كانت العقدتان i و j متصلتين و 0 بخلاف ذلك. يتم حساب درجات العقد (k_i, k_j) وإجمالي عدد الحواف m كمدخلات لصيغة النمطية.
يتم تعريف درجة النمطية Q على أنها نسبة الحواف التي تقع داخل المجتمعات مطروحًا منها النسبة المتوقعة بموجب نموذج تكوين صفري (إعادة توصيل عشوائي يحافظ على الدرجات). تتراوح Q تقريبًا من -0.5 إلى 1؛ القيم التي تزيد عن حوالي 0.3 تشير إلى بنية مجتمعية ذات معنى.
الصيغة
Q = \frac{1}{2m}\sum_{ij}\left[A_{ij} - \frac{k_i k_j}{2m}\right]\delta(c_i, c_j)نظرًا لأن البحث الشامل عبر جميع التقسيمات الممكنة هو مسألة NP-hard، فإن الخوارزميات العملية تقرب الحل الأمثل. تشمل الأساليب الشائعة طريقة لوفين (التجميع الجشع)، وخوارزمية لايدن (متغير مصحح وأسرع)، والتحسين الطيفي باستخدام المتجهات الذاتية لمصفوفة النمطية، والتلدين المحاكى.
يتم تعيين كل عقدة للمجتمع الذي يزيد من Q للتقسيم العام. تنتج الخوارزمية عادةً مخططًا هرميًا، مما يسمح بفحص البنية المجتمعية على مستويات دقة متعددة، من المجتمعات الفوقية الواسعة إلى المجموعات الدقيقة.
يتم تقييم التقسيم الناتج بواسطة قيمة Q النهائية، وفحوصات الاستقرار عبر عمليات تشغيل متعددة للخوارزمية، وعند توفر الحقيقة الأساسية، المقاييس الخارجية مثل المعلومات المتبادلة المعيارية. تشير قيمة Q المنخفضة أو النتائج غير المستقرة عبر عمليات التشغيل إلى بنية مجتمعية ضعيفة أو غائبة.
الأخطاء الشائعة
- قبول تشغيل واحد لمحسن عشوائي دون التحقق من الاستقرار عبر عمليات تشغيل متعددة أو بذور عشوائية.
- تجاهل حد الدقة والاستنتاج بأن مجتمعًا كبيرًا مدمجًا متجانس حقًا.
- استخدام النمطية الثنائية على شبكة موزونة دون تكييف النموذج الصفري لدمج أوزان الحواف.
- معاملة Q فوق 0.3 كحد عالمي للبنية 'الجيدة' دون النظر إلى نوع وحجم الشبكة.
- خلط جودة التحسين (Q مرتفع) مع صلاحية التفسير - لا تزال المجتمعات بحاجة إلى فحص جوهري.
الأسئلة الشائعة
ما هي قيمة Q الجيدة؟
غالبًا ما يُستشهد بقيمة Q التي تزيد عن 0.3 تقريبًا على أنها تشير إلى بنية مجتمعية ذات معنى، ولكن هذا الحد يعتمد على نوع وحجم الشبكة. يمكن أن تحتوي الشبكات الكبيرة جدًا ذات البنية الضعيفة على Q قريب من 0.1 ومع ذلك تكشف عن مجموعات قابلة للتفسير، بينما قد تصل الشبكات الصغيرة الكثيفة إلى Q أعلى من 0.5. افحص المجتمعات جوهريًا دائمًا بدلاً من الاعتماد على Q وحده.
أي خوارزمية يجب أن أستخدمها لزيادة Q إلى الحد الأقصى؟
تعتبر خوارزمية لايدن (تراج وآخرون، 2019) هي الافتراضية الموصى بها حاليًا: فهي أسرع من طريقة لوفين الأصلية وتصحح ميلها لإنتاج مجتمعات ضعيفة الاتصال. بالنسبة للرسوم البيانية الكبيرة جدًا، تظل لوفين خيارًا عمليًا. تُفضل الطرق الطيفية عندما تحتاج إلى نتائج قابلة للتكرار وحتمية على الشبكات الأصغر.
هل يمكن لتحليل النمطية اكتشاف المجتمعات المتداخلة؟
لا يمكن لتحسين النمطية القياسي تعيين كل عقدة لمجتمع واحد بالضبط ولا يمكنه اكتشاف التداخل. إذا كنت تتوقع أن تنتمي العقد إلى مجموعات متعددة في وقت واحد، فاستخدم طرق المجتمعات المتداخلة مثل طريقة تخلل الزمر أو أساليب تحليل المصفوفة غير السالبة بدلاً من ذلك.
كيف يؤثر حد الدقة على تحليلي؟
يميل تحسين النمطية إلى دمج المجتمعات الأصغر من حوالي sqrt(m) حافة في مجتمعات أكبر. هذا يعني أن المجموعات الصغيرة الحقيقية يمكن أن تكون غير مرئية عندما تكون الشبكة كبيرة. للتخفيف من ذلك، قم بتغيير معلمة الدقة (المتوفرة في لايدن وبعض تطبيقات لوفين) وقارن التقسيمات عبر عدة قيم دقة.
هل يجب أن أطبق تحليل النمطية على شبكة موجهة؟
نعم، مع نموذج صفري معدل يحافظ على تسلسلات الدرجات الداخلية والخارجية، كما هو مطبق في أدوات مثل igraph. تطبيق النمطية غير الموجهة بشكل أعمى على شبكة موجهة يتجاهل عدم تناسق العلاقات ويمكن أن يؤدي إلى تقسيمات مضللة.
طرق ذات صلة
المصادر
Newman, M. E. J., & Girvan, M. (2004). Finding and evaluating community structure in networks. Physical Review E, 69(2), 026113.
افتح مرجع DOIتم النسخ.Newman, M. E. J. (2006). Modularity and community structure in networks. Proceedings of the National Academy of Sciences, 103(23), 8577–8582.
افتح مرجع DOIتم النسخ.