هيكل المجتمع

جزء من سلسلة عن
علم الشبكات
نظرية
الرسم البياني شبكة معقدة العدوى عالم صغير خالية من المقياس هيكل المجتمع الترشيح تطور القدرة على التحكم رسم بياني رأس المال الاجتماعي تحليل الرابط تحسين المعاملة بالمثل إنهاء التماثل الجنسي الانتقالية المرفق التفضيلي نظرية التوازن تأثير الشبكة التأثير الاجتماعي
أنواع الشبكات
معلوماتية (حوسبة) اتصالات ينقل اجتماعي التعاون العلمي بيولوجي العصبية الاصطناعية مترابطين دلالي مكاني التبعية تدفق على الشريحة
الرسوم البيانية
سمات زمرة عنصر يقطع دورة هيكل البيانات حافة حلقة حيّ طريق قمة الرأس Adjacency list / matrix Incidence list / matrix Types Bipartite Complete Directed Hyper Labeled Multi Random Weighted
Metrics Algorithms
Centrality Degree Motif Clustering Degree distribution Assortativity Distance Modularity Efficiency
Models
Topology Random graph Erdős–Rényi Barabási–Albert Bianconi–Barabási Fitness model Watts–Strogatz Exponential random (ERGM) Random geometric (RGG) Hyperbolic (HGN) Hierarchical Stochastic block Blockmodeling Maximum entropy Soft configuration LFR Benchmark Dynamics Boolean network agent based Epidemic/SIR
Lists Categories
Topics Software Network scientists Category:Network theory Category:Graph theory
v t e

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

في دراسة الشبكات ، مثل شبكات الكمبيوتر والمعلومات والشبكات الاجتماعية والشبكات البيولوجية، وُجِد أن عددًا من الخصائص المختلفة تحدث بشكل شائع، بما في ذلك خاصية العالم الصغير ، وتوزيعات الدرجات الثقيلة ، والتجمع ، وغيرها. وهناك سمة مشتركة أخرى وهي بنية المجتمع. ^{[1] [2] [3] [4] [5]} في سياق الشبكات، يشير هيكل المجتمع إلى حدوث مجموعات من العقد في شبكة متصلة داخليًا بكثافة أكبر من بقية الشبكة، كما هو موضح في صورة المثال على اليمين. يشير هذا التباين في الاتصالات إلى أن الشبكة بها انقسامات طبيعية معينة داخلها.

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

قد لا تحتوي بعض الشبكات على أي بنية مجتمعية ذات معنى. على سبيل المثال، لا تعرض العديد من نماذج الشبكات الأساسية، مثل الرسم البياني العشوائي ونموذج باراباسي-ألبرت ، بنية المجتمع.

تعتبر هياكل المجتمع شائعة جدًا في الشبكات الحقيقية. تتضمن الشبكات الاجتماعية مجموعات مجتمعية (أصل المصطلح، في الواقع) بناءً على الموقع المشترك والاهتمامات والمهنة وما إلى ذلك. ^{[5] [6]}

إن العثور على بنية مجتمعية أساسية في شبكة ما، إن وجدت، أمر مهم لعدد من الأسباب. تسمح لنا المجتمعات بإنشاء خريطة واسعة النطاق لشبكة ما، حيث تعمل المجتمعات الفردية مثل العقد الفرعية في الشبكة مما يجعل دراستها أسهل. ^[7]

كما تلقي المجتمعات الفردية الضوء على وظيفة النظام الذي تمثله الشبكة، حيث تتوافق المجتمعات غالبًا مع الوحدات الوظيفية للنظام. في الشبكات الأيضية، تتوافق هذه المجموعات الوظيفية مع الدورات أو المسارات، بينما في شبكة تفاعل البروتين ، تتوافق المجتمعات مع البروتينات ذات الوظائف المماثلة داخل الخلية البيولوجية. وبالمثل، تشكل شبكات الاستشهاد مجتمعات حسب موضوع البحث. ^[1] إن القدرة على تحديد هذه الهياكل الفرعية داخل الشبكة يمكن أن توفر نظرة ثاقبة حول كيفية تأثير وظيفة الشبكة وطوبولوجيا كل منهما على الآخر. يمكن أن تكون هذه الرؤية مفيدة في تحسين بعض الخوارزميات على الرسوم البيانية مثل التجميع الطيفي . ^[8]

ومن المهم أن نلاحظ أن المجتمعات غالبًا ما تمتلك خصائص مختلفة تمامًا عن الخصائص المتوسطة للشبكات. وبالتالي، فإن التركيز فقط على الخصائص المتوسطة عادةً ما يغفل العديد من السمات المهمة والمثيرة للاهتمام داخل الشبكات. على سبيل المثال، في شبكة اجتماعية معينة، قد توجد مجموعات اجتماعية ومجموعات صامتة في نفس الوقت. ^[7]

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

أخيرًا، هناك تطبيق مهم وجده اكتشاف المجتمع في علم الشبكات وهو التنبؤ بالروابط المفقودة وتحديد الروابط الزائفة في الشبكة. أثناء عملية القياس، قد لا تتم ملاحظة بعض الروابط لعدد من الأسباب. وبالمثل، قد تدخل بعض الروابط بشكل خاطئ في البيانات بسبب الأخطاء في القياس. يتم التعامل مع كلتا الحالتين بشكل جيد بواسطة خوارزمية اكتشاف المجتمع لأنها تسمح للمرء بتعيين احتمال وجود حافة بين زوج معين من العقد. ^[9]

إن العثور على مجتمعات داخل شبكة عشوائية قد يكون مهمة صعبة من الناحية الحسابية . إن عدد المجتمعات، إن وجدت، داخل الشبكة غير معروف عادةً، وغالبًا ما تكون المجتمعات غير متساوية الحجم و/أو الكثافة. ولكن على الرغم من هذه الصعوبات، فقد تم تطوير العديد من الطرق للعثور على المجتمعات واستخدامها بمستويات متفاوتة من النجاح. ^[4]

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

في طريقة القطع الأدنى، يتم تقسيم الشبكة إلى عدد محدد مسبقًا من الأجزاء، وعادةً ما تكون بنفس الحجم تقريبًا، ويتم اختيارها بحيث يتم تقليل عدد الحواف بين المجموعات. تعمل الطريقة بشكل جيد في العديد من التطبيقات التي كانت مخصصة لها في الأصل ولكنها أقل من مثالية للعثور على بنية المجتمع في الشبكات العامة لأنها ستجد المجتمعات بغض النظر عما إذا كانت ضمنية في البنية أم لا، وستجد عددًا ثابتًا منها فقط. ^[10]

هناك طريقة أخرى للعثور على هياكل المجتمع في الشبكات وهي التجميع الهرمي . في هذه الطريقة، يتم تعريف مقياس التشابه لقياس نوع ما (عادةً ما يكون طوبولوجيًا) من التشابه بين أزواج العقد. تشمل المقاييس المستخدمة بشكل شائع تشابه جيب التمام ومؤشر جاكارد ومسافة هامينج بين صفوف مصفوفة التجاور . ثم يتم تجميع العقد المتشابهة في مجتمعات وفقًا لهذا المقياس. هناك العديد من المخططات الشائعة لإجراء التجميع، وأبسطها هما التجميع أحادي الارتباط ، حيث يتم اعتبار مجموعتين مجتمعات منفصلة إذا وفقط إذا كان لجميع أزواج العقد في مجموعات مختلفة تشابه أقل من عتبة معينة، والتجميع الكامل للارتباط ، حيث يكون لجميع العقد داخل كل مجموعة تشابه أكبر من عتبة. تتمثل إحدى الخطوات المهمة في كيفية تحديد العتبة لإيقاف التجميع التراكمي، مما يشير إلى بنية مجتمعية شبه مثالية. تتكون الإستراتيجية الشائعة من بناء مقياس واحد أو أكثر لمراقبة الخصائص العالمية للشبكة، والتي تبلغ ذروتها في خطوة معينة من التجميع. النهج المثير للاهتمام في هذا الاتجاه هو استخدام مقاييس التشابه أو الاختلاف المختلفة، مجتمعة من خلال المجاميع المحدبة ، ^[11] تقريب آخر هو حساب كمية تراقب كثافة الحواف داخل المجموعات فيما يتعلق بالكثافة بين المجموعات، مثل كثافة التقسيم، والتي تم اقتراحها عندما يتم تعريف مقياس التشابه بين الحواف (الذي يسمح بتعريف المجتمعات المتداخلة)، ^[12] وتم تمديدها عندما يتم تعريف التشابه بين العقد، مما يسمح بالنظر في تعريفات بديلة للمجتمعات مثل النقابات (أي مجموعات العقد التي تشترك في عدد مماثل من الروابط فيما يتعلق بنفس الجيران ولكنها ليست بالضرورة متصلة ببعضها البعض). ^[13] يمكن توسيع هذه الأساليب للنظر في الشبكات متعددة الأبعاد، على سبيل المثال عندما نتعامل مع شبكات بها عقد ذات أنواع مختلفة من الروابط. ^[13]

هناك خوارزمية أخرى شائعة الاستخدام للعثور على المجتمعات وهي خوارزمية جيرفان نيومان . ^[1] تحدد هذه الخوارزمية الحواف في الشبكة التي تقع بين المجتمعات ثم تزيلها، تاركة وراءها المجتمعات نفسها فقط. يتم إجراء التعريف من خلال استخدام مقياس نظرية الرسم البياني المركزية الوسيطة ، والذي يعين رقمًا لكل حافة يكون كبيرًا إذا كانت الحافة تقع "بين" العديد من أزواج العقد.

تُرجع خوارزمية جيرفان-نيومان نتائج ذات جودة معقولة وهي شائعة لأنها تم تنفيذها في عدد من حزم البرامج القياسية. لكنها تعمل أيضًا ببطء، حيث تستغرق وقتًا O( m ² n ) على شبكة من n رأسًا و m حافة، مما يجعلها غير عملية للشبكات التي يزيد عدد العقد فيها عن بضعة آلاف. ^[14]

على الرغم من عيوبها المعروفة، فإن إحدى أكثر الطرق استخدامًا على نطاق واسع لاكتشاف المجتمعات هي تعظيم الوحدات النمطية. ^[14] الوحدات النمطية هي دالة فائدة تقيس جودة قسم معين من الشبكة إلى مجتمعات. تكتشف طريقة تعظيم الوحدات النمطية المجتمعات من خلال البحث في الأقسام المحتملة للشبكة عن قسم واحد أو أكثر يتمتع بوحدات نمطية عالية بشكل خاص. نظرًا لأن البحث الشامل في جميع الأقسام المحتملة عادة ما يكون مستعصيًا على الحل، فإن الخوارزميات العملية تعتمد على طرق تحسين تقريبية مثل الخوارزميات الجشعة أو التلدين المحاكى أو التحسين الطيفي، مع وجود مناهج مختلفة تقدم توازنات مختلفة بين السرعة والدقة. ^{[15] [16]} أحد أساليب تعظيم الوحدات النمطية الشائعة هو طريقة لوفين ، والتي تعمل بشكل متكرر على تحسين المجتمعات المحلية حتى لا يمكن تحسين الوحدات النمطية العالمية بعد الآن نظرًا للاضطرابات في حالة المجتمع الحالية. ^{[17] [18]}

إن فائدة تحسين الوحدات النمطية مشكوك فيها، حيث ثبت أن تحسين الوحدات النمطية غالبًا ما يفشل في اكتشاف مجموعات أصغر من مقياس معين، اعتمادًا على حجم الشبكة ( حد الدقة ^[19] )؛ من ناحية أخرى، يتميز مشهد قيم الوحدات النمطية بتدهور كبير في الأقسام ذات الوحدات النمطية العالية، والتي تقترب من الحد الأقصى المطلق، والتي قد تكون مختلفة جدًا عن بعضها البعض. ^[20]

تحاول الأساليب القائمة على الاستدلال الإحصائي ملاءمة نموذج توليدي لبيانات الشبكة، التي تشفر بنية المجتمع. الميزة الإجمالية لهذا النهج مقارنة بالبدائل هي طبيعته الأكثر مبدئية، والقدرة على معالجة القضايا ذات الأهمية الإحصائية بطبيعتها . تعتمد معظم الأساليب في الأدبيات على نموذج الكتلة العشوائية ^[21] بالإضافة إلى المتغيرات بما في ذلك العضوية المختلطة، ^{[22] [23]} تصحيح الدرجة، ^[24] والهياكل الهرمية. ^{[25] يمكن إجراء} اختيار النموذج باستخدام مناهج مبدئية مثل الحد الأدنى لطول الوصف ^{[26] [27]} (أو ما يعادله، اختيار النموذج البايزي ^[28] ) واختبار نسبة الاحتمالية . ^[29] يوجد حاليًا العديد من الخوارزميات لإجراء استدلال فعال لنماذج الكتلة العشوائية، بما في ذلك انتشار الاعتقاد ^{[30] [31] ومونت} كارلو التراكمي . ^[32]

على النقيض من الأساليب التي تحاول تجميع شبكة معينة بناءً على دالة موضوعية، فإن هذه الفئة من الأساليب تعتمد على نماذج توليدية، والتي لا تعمل فقط كوصف للهيكل واسع النطاق للشبكة، بل يمكن استخدامها أيضًا لتعميم البيانات والتنبؤ بحدوث روابط مفقودة أو زائفة في الشبكة. ^{[33] [34]}

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

أحد الأساليب هو إيجاد " المجموعات القصوى ". أي إيجاد المجموعات التي لا تشكل رسمًا بيانيًا فرعيًا لأي مجموعة أخرى. الخوارزمية الكلاسيكية لإيجاد هذه المجموعات هي خوارزمية برون-كيربوش . يمكن استخدام تداخل هذه المجموعات لتحديد المجتمعات بعدة طرق. أبسطها هو النظر فقط في المجموعات القصوى الأكبر من الحجم الأدنى (عدد العقد). يحدد اتحاد هذه المجموعات بعد ذلك رسمًا بيانيًا فرعيًا تحدد مكوناته (الأجزاء المنفصلة) المجتمعات. ^[35] غالبًا ما يتم تنفيذ مثل هذه الأساليب في برامج تحليل الشبكات الاجتماعية مثل UCInet.

النهج البديل هو استخدام مجموعات ذات حجم ثابت . يمكن استخدام تداخل هذه لتحديد نوع من الرسم البياني الزائد المنتظم أو بنية هي تعميم للرسم البياني الخطي (الحالة عندما ) والمعروفة باسم " رسم بياني للمجموعات ". ^[36] تحتوي الرسوم البيانية للمجموعات على رؤوس تمثل المجموعات في الرسم البياني الأصلي بينما تسجل حواف الرسم البياني للمجموعات تداخل المجموعة في الرسم البياني الأصلي. يؤدي تطبيق أي من طرق اكتشاف المجتمع السابقة (التي تعين كل عقدة لمجتمع) على الرسم البياني للمجموعات بعد ذلك إلى تعيين كل مجموعة لمجتمع. يمكن بعد ذلك استخدام هذا لتحديد عضوية المجتمع للعقد في المجموعات. مرة أخرى، بما أن العقدة قد تكون في عدة مجموعات، فيمكن أن تكون عضوًا في عدة مجتمعات. على سبيل المثال، تحدد طريقة تسرب المجموعة ^[37] المجتمعات على أنها مجموعات تسرب من المجموعات . للقيام بذلك، تجد جميع المجموعات في شبكة، أي جميع الرسوم البيانية الفرعية الكاملة للعقد. ثم يقوم بتعريف مجموعتين متجاورتين إذا كانتا تشتركان في عقد، أي أن هذا يستخدم لتحديد الحواف في رسم بياني للمجموعة. ثم يتم تعريف المجتمع على أنه أقصى اتحاد للمجموعة حيث يمكننا الوصول إلى أي مجموعة من أي مجموعة أخرى من خلال سلسلة من تجاورات المجموعة. أي أن المجتمعات هي مجرد مكونات متصلة في رسم بياني للمجموعة. نظرًا لأن العقدة يمكن أن تنتمي إلى عدة مجموعات تسلل مختلفة للمجموعة في نفس الوقت، يمكن للمجتمعات أن تتداخل مع بعضها البعض. ${\displaystyle k}$${\displaystyle k}$${\displaystyle k=2}$${\displaystyle k}$${\displaystyle k}$${\displaystyle k}$${\displaystyle k}$${\displaystyle k-1}$${\displaystyle k}$${\displaystyle k}$${\displaystyle k}$${\displaystyle k}$${\displaystyle k}$

يمكن تمثيل شبكة أو إسقاطها على مساحة كامنة عبر طرق تعلم التمثيل لتمثيل نظام بكفاءة. بعد ذلك، يمكن استخدام طرق التجميع المختلفة للكشف عن هياكل المجتمع. بالنسبة للمساحات الإقليدية، يمكن استخدام طرق مثل اكتشاف مجتمع Silhouette القائم على التضمين ^[38] . بالنسبة للمساحات الكامنة فوق الهندسية، يمكن استخدام طريقة الفجوة الحرجة أو طرق التجميع القائمة على الكثافة المعدلة أو التسلسل الهرمي أو القائمة على التقسيم. ^[39]

إن تقييم الخوارزميات، للكشف عن أيها أفضل في الكشف عن بنية المجتمع، لا يزال سؤالاً مفتوحاً. يجب أن يستند إلى تحليلات الشبكات ذات البنية المعروفة. ومن الأمثلة النموذجية اختبار "المجموعات الأربع"، حيث يتم تقسيم الشبكة إلى أربع مجموعات متساوية الحجم (عادةً ما يكون لكل منها 32 عقدة) ويتم تغيير احتمالات الاتصال داخل المجموعات وبينها لإنشاء هياكل أكثر أو أقل تحديًا لخوارزمية الكشف. تعد مثل هذه الرسوم البيانية المرجعية حالة خاصة من نموذج التقسيم l المزروع [ 40 ^] لكوندون وكارب ، أو بشكل عام من " نماذج الكتلة العشوائية "، وهي فئة عامة من نماذج الشبكة العشوائية التي تحتوي على بنية المجتمع. تم اقتراح معايير أكثر مرونة أخرى تسمح بأحجام مجموعات متفاوتة وتوزيعات درجات غير تافهة، مثل معيار LFR ^{[41] [42]} وهو امتداد لمعيار المجموعات الأربع الذي يتضمن توزيعات غير متجانسة لدرجة العقدة وحجم المجتمع، مما يجعله اختبارًا أكثر صرامة لطرق الكشف عن المجتمع. ^{[43] [44]}

تبدأ معايير القياس التي يتم إنشاؤها بواسطة الكمبيوتر والمستخدمة بشكل شائع بشبكة من المجتمعات المحددة جيدًا. بعد ذلك، يتم تدهور هذا الهيكل عن طريق إعادة توصيل الروابط أو إزالتها ويصبح من الصعب على الخوارزميات اكتشاف القسم الأصلي. في النهاية، تصل الشبكة إلى نقطة حيث تكون عشوائية بشكل أساسي. يمكن تسمية هذا النوع من معايير القياس "مفتوحة". يتم تقييم الأداء على هذه المعايير من خلال مقاييس مثل المعلومات المتبادلة الطبيعية أو تباين المعلومات . يقارنون الحل الذي تم الحصول عليه بواسطة خوارزمية ^[42] بهيكل المجتمع الأصلي، وتقييم التشابه بين كلا القسمين.

خلال السنوات الأخيرة، تم الحصول على نتيجة مفاجئة إلى حد ما من قبل مجموعات مختلفة والتي تظهر أن هناك انتقال طوري في مشكلة اكتشاف المجتمع، مما يدل على أنه مع تساوي كثافة الاتصالات داخل المجتمعات وبين المجتمعات بشكل متزايد أو تقلص كليهما (على نحو مكافئ، مع ضعف بنية المجتمع أو قلة الشبكة)، تصبح المجتمعات فجأة غير قابلة للاكتشاف. بمعنى ما، لا تزال المجتمعات نفسها موجودة، حيث لا يزال وجود وغياب الحواف مرتبطًا بعضوية المجتمع في نقاط النهاية الخاصة بها؛ ولكن يصبح من المستحيل نظريًا تصنيف العقد بشكل أفضل من الصدفة، أو حتى التمييز بين الرسم البياني والرسم البياني الناتج عن نموذج فارغ مثل نموذج إردوس-ريني بدون بنية مجتمع. هذا الانتقال مستقل عن نوع الخوارزمية المستخدمة لاكتشاف المجتمعات، مما يعني وجود حد أساسي لقدرتنا على اكتشاف المجتمعات في الشبكات، حتى مع الاستدلال البايزي الأمثل (أي بغض النظر عن مواردنا الحسابية). ^{[45] [46] [47]}

لنأخذ نموذج كتلة عشوائية بإجمالي عدد العقد والمجموعات ذات الحجم المتساوي، وليكن و احتمالات الاتصال داخل المجموعات وبينها على التوالي. إذا ، فإن الشبكة ستمتلك بنية مجتمعية لأن كثافة الارتباط داخل المجموعات ستكون أكبر من كثافة الارتباطات بين المجموعات. وفي الحالة المتفرقة، وليكن المقياس كما يلي بحيث تكون الدرجة المتوسطة ثابتة: ${\displaystyle n}$${\displaystyle q=2}$${\displaystyle p_{\text{in}}}$${\displaystyle p_{\text{out}}}$${\displaystyle p_{\text{in}}>p_{\text{out}}}$${\displaystyle p_{\text{in}}}$${\displaystyle p_{\text{out}}}$${\displaystyle O(1/n)}$

${\displaystyle p_{\text{in}}=c_{\text{in}}/n}$و${\displaystyle p_{\text{out}}=c_{\text{out}}/n}$

ومن ثم يصبح من المستحيل اكتشاف المجتمعات عندما: ^[46]

${\displaystyle c_{\text{in}}-c_{\text{out}}={\sqrt {2(c_{\text{in}}+c_{\text{out}})}}}$

• شبكة معقدة
• تَسَلسُل
• نظرية الشبكات
• نظرية التسرب

• الكشف عن المجتمع في الرسوم البيانية – مقدمة
• هل هناك تطبيقات لخوارزميات الكشف عن المجتمع في الرسوم البيانية؟ – Stack Overflow
• ما هي الفروقات بين خوارزميات اكتشاف المجتمع في igraph؟ – Stack Overflow