كيف تكتشف خوارزمية سريعة الانتشار المجتمعات في الشبكات الكبيرة

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

لقد فتح العالم الرقمي طريقة مختلفة تمامًا لإنشاء العلاقات. كما أطلق العنان لمحيط من البيانات يمكننا تحليلها للحصول على فهم أفضل للسلوك البشري.

تشير بيانات الوسائط الاجتماعية إلى جميع الأفكار والمعلومات الأولية التي تم جمعها من نشاط وسائل التواصل الاجتماعي للفرد. يمكننا إنشاء شبكات من أنشطة وسائل التواصل الاجتماعي هذه للحصول على تصور أفضل لهذا الفرد.

يمكن أن تتنوع هذه الشبكات على نطاق واسع وقد تشمل أصدقاءك على Facebook ، أو المنتجات التي اشتريتها مؤخرًا على Amazon ، أو التغريدات التي أحببتها أو أعادت تغريدها ، أو طعامك المفضل الذي طلبته من Zomato ، أو البحث الذي أجريته على Google ، أو الصورة التي أعجبتك مؤخرًا على Instagram .

تستخدم الشركات هذه الشبكات لتصنيف مستخدميها إلى مجموعات مختلفة. هذا يساعدهم

  • القيام بأبحاث السوق
  • توليد العملاء المحتملين
  • خدمة أفضل لعملائهم
  • البحث عن الصور ومقاطع الفيديو ومشاركتها
  • اكتشف وناقش المحتوى الشائع
  • مشاركة المعلومات حول الخدمات والمطاعم
  • التواصل مع الآخرين حول اهتمام أو هواية مشتركة
  • و اكثر.

القائمة لا حصر لها إلى حد كبير.

قبل أن ندخل في الأعشاب الضارة ، دعنا نحلل بسرعة التمييز بين المكونات المختلفة للشبكة.

ما هي الشبكة؟

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

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

ما هي المجموعة؟

يصف Reicher SD في تحديد السلوك الجماعي المجموعة بأنها مجموعة من الأفراد الذين يعتبرون أنفسهم مجموعة. أعضاء نفس المجموعة لديهم مجموعة من المعتقدات والسلوكيات المشتركة.

ما هو المجتمع؟

وفقًا لديفيد دبليو ماكميلان ( الإحساس بالمجتمع: تعريف ونظرية ) ، يمكن تعريف المجتمع على النحو التالي:

" الإحساس بالانتماء للمجتمع هو شعور لدى الأعضاء بالانتماء ، والشعور بأن الأعضاء مهمون لبعضهم البعض وللمجموعة ، وإيمان مشترك بأن احتياجات الأعضاء ستُلبى من خلال التزامهم بأن يكونوا معًا. "

المجتمعات أو الوحدات الفرعية هي الشبكات الفرعية في شبكة والتي تكون عُقدًا شديدة الترابط.

يشير المجتمع إلى وجود هياكل داخلية لها خصائص خاصة أو تلعب نفس الدور في الشبكة.

مجموعات الأفراد أو الكائنات شديدة الارتباط داخل هذه الشبكات هي مجتمعات. عادة ما تقع عند نقطة تقاطع الشبكة والمجموعة.

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

سنلقي نظرة على خوارزمية التجديد السريع الشهيرة . قارن فينسينت سي بلونديل والمؤلفون المشاركون في الورقة هذه الخوارزمية مع خوارزميات اكتشاف المجتمع الأخرى. اكتشفوا أن هذه الخوارزمية تتفوق في الأداء على كل خوارزمية أخرى في الشبكات الكبيرة.

ما هي خوارزمية الكشف السريع؟

تم استخدام خوارزمية Fast Unfolding لتحديد المجتمعات اللغوية في شبكة الهاتف المحمول البلجيكية التي تضم 2.6 مليون عميل.

كما تم استخدامه لتحليل رسم بياني على الويب لـ 118 مليون عقدة وأكثر من مليار رابط.

استغرق تحديد المجتمعات في مثل هذه الشبكة الضخمة 152 دقيقة فقط. لذلك هذه الخوارزمية سريعة وفعالة.

كيف تعمل الخوارزمية

تعمل الخوارزمية على مرحلتين:

المرحلة 1

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

المرحلة الثانية

  1. تتمثل المرحلة الثانية من الخوارزمية في بناء شبكة جديدة أصبحت عقدها الآن المجتمعات التي تم العثور عليها خلال المرحلة الأولى. لذلك ، نبني العقد من خلال دمج جميع العقد في المجتمع كعقدة واحدة.
  2. يتم إعطاء أوزان الارتباط بين العقد من خلال مجموع أوزان الروابط بين العقد في المجتمعين المتوافقين.
  3. الارتباط بين عقد نفس المجتمع يؤدي إلى حلقات ذاتية للمجتمع في الشبكة الجديدة.
  4. كرر المرحلة 1 حتى لا يمكن تحقيق المزيد من التحسينات.

كيف يتم حساب الكسب في نمطية

يتم قياس جودة القسم ( Q ) من خلال نمطية (ويعرف أيضًا باسم نمطية القسم). إنها قيمة عددية بين -1 و 1 ، وتقيس كثافة الروابط داخل المجتمعات مقارنة بالروابط بين المجتمعات.

و كسب في نمطية (ΔQ) التي تم الحصول عليها عن طريق تحريك عقدة معزولة ط في المجتمع C يمكن بسهولة أن يتم حسابها من قبل:

Σin هو مجموع أوزان الروابط الموجودة داخل C.

Σtot هو مجموع أوزان الروابط الواقعة على العقد في C.

ki هو مجموع أوزان الروابط من i إلى العقدة في C.

م هو مجموع أوزان جميع الروابط في الشبكة.

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

التشغيل الجاف للخوارزمية

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

في المرحلة التالية ، نبني العقد عن طريق دمج جميع العقد في هذا المجتمع في عقدة واحدة. في المجتمع الأخضر ، لدينا ما مجموعه 5 عقد وهناك إجمالي 7 حواف بينها.

لذلك بعد التجميع المجتمعي ، سيكون وزن الحلقة الذاتية للعقدة الخضراء 14 (7 * 2 لأنه رابط ثنائي الاتجاه). وبالمثل ، سيكون وزن الحلقة الذاتية للعقدة الحمراء 16 ، وستكون العقدة الزرقاء 4 ، وستكون العقدة الزرقاء الفاتحة 2.

سيكون وزن الحافة بين العقدة الخضراء والزرقاء 4 حيث يوجد إجمالي 4 حواف بين المجتمع الأخضر والأزرق بعد Modularity Optimization.

في الخطوة التالية ، نقوم بإعادة تقييم نمطية العقد الجديدة ونقوم بنفس العملية مرة أخرى.

وأخيرا، وحصلنا على اثنين من المجتمعات، الأخضر و الأزرق الفاتح. يحتوي المجتمع الأخضر على 26 حلقة ذاتية حيث يوجد إجمالي 13 حافة بين عقد المجتمع الأخضر. ولدينا 12 حافة في مجتمع الأزرق الفاتح ، إجمالي 24 حلقة ذاتية.

مزايا الخوارزمية

  1. خطواتها بديهية وسهلة التنفيذ والنتيجة غير خاضعة للإشراف.
  2. الخوارزمية سريعة للغاية. تشير عمليات المحاكاة الحاسوبية على شبكات معيارية ضخمة جدًا إلى أن تعقيدها خطي على البيانات النموذجية والمتفرقة. قد يكون هذا بسبب سهولة حساب Gain in Modularity ويقل عدد المجتمعات بشكل كبير بعد تمريرات قليلة.

حدود الخوارزمية

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

استنتاج

إذا كنت معلقة هناك لفترة طويلة ... شكرا! آمل أن تكون هناك معلومات قيمة بالنسبة لك.

إذن أنت تعرف الآن كيف تعمل خوارزمية التجدد السريع ، وأنها فعالة للغاية لاكتشاف المجتمعات في شبكات كبيرة جدًا.

الطريقة التي تحسب بها Gain in Modularity تجعل الخوارزمية تتفوق في الأداء على كل الخوارزمية الأخرى الموجودة. أرسل لي ملاحظة إذا وجدت أنها مفيدة أو لديك أي أسئلة للمتابعة.

شكرا للقراءة!