خوارزمية Fast Unfolding: كيف تكتشف المجتمعات في الشبكات الضخمة بكفاءة؟

مقدمة في تحليل الشبكات الاجتماعية واكتشاف المجتمعات

يتضمن تحليل الشبكات الاجتماعية دراسة الأنماط والعلاقات المعقدة داخل الشبكات الواقعية الضخمة التي قد تتألف من ملايين العقد. إذا كان لديك معرفة أساسية بـنظرية الرسم البياني (Graph Theory)، يمكنك البدء في إجراء هذه التحليلات. لقد فتح العالم الرقمي آفاقًا جديدة تمامًا لإنشاء العلاقات والتفاعلات، وأطلق العنان لمحيط هائل من البيانات التي يمكننا تحليلها للحصول على فهم أعمق للسلوك البشري.

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

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

ما هي الشبكة؟

الشبكة هي نسيج من العلاقات الشخصية المترابطة. على سبيل المثال، يمكن للأفراد المختلفين التواصل مع بعضهم البعض في مجموعة على وسائل التواصل الاجتماعي من خلال شبكة ديناميكية من العلاقات. تتألف الشبكة من عقد (nodes) (أفراد فاعلون، أشخاص، أو أشياء داخل الشبكة) وروابط (ties)، أو حواف (edges)، أو وصلات (links) (العلاقات أو التفاعلات) التي تربطهم.

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

يصف Reicher S. D. في كتابه The Determination of Collective Behavior المجموعة بأنها مجموعة من الأفراد الذين يعتبرون أنفسهم مجموعة. يتمتع أعضاء نفس المجموعة بمجموعة من المعتقدات والسلوكيات المشتركة.

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

وفقًا لـ David W. McMillan (في كتابه Sense of Community: A Definition and Theory)، يمكن تعريف المجتمع على النحو التالي:

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

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

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

ما هي خوارزمية Fast Unfolding؟

استُخدمت خوارزمية Fast Unfolding لتحديد المجتمعات اللغوية في شبكة هواتف محمولة بلجيكية تضم 2.6 مليون عميل. كما استُخدمت لتحليل رسم بياني للويب يضم 118 مليون عقدة وأكثر من مليار وصلة. استغرق تحديد المجتمعات في مثل هذه الشبكة الضخمة 152 دقيقة فقط. لذا، فإن هذه الخوارزمية سريعة وفعالة في آن واحد.

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

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

المرحلة الأولى: تحسين المعيارية (Modularity Optimization)

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

المرحلة الثانية: تجميع المجتمعات (Community Aggregation)

1. تتكون المرحلة الثانية من الخوارزمية من بناء شبكة جديدة تكون عقدها الآن هي المجتمعات التي تم العثور عليها خلال المرحلة الأولى.
2. نقوم ببناء عقد جديدة عن طريق دمج جميع العقد الموجودة في المجتمع كـعقدة واحدة.
3. تُعطى أوزان الروابط بين العقد الجديدة (المجتمعات المدمجة) بمجموع أوزان الروابط بين العقد في المجتمعين المقابلين.
4. تؤدي الروابط بين عقد نفس المجتمع إلى حلقات ذاتية (self-loops) للمجتمع في الشبكة الجديدة.
5. تُكرر المرحلة الأولى حتى لا يمكن تحقيق أي تحسين إضافي في المعيارية.

كيف يتم حساب الربح في المعيارية (Gain in Modularity)؟

تُقاس جودة التقسيم (Quality of Partition) بـالمعيارية (Modularity)، وهي قيمة عددية تتراوح بين -1 و 1، وتقيس كثافة الروابط داخل المجتمعات مقارنة بالروابط بين المجتمعات.

يمكن حساب الربح في المعيارية (∆Q) الذي يتم الحصول عليه عن طريق نقل عقدة معزولة i إلى مجتمع C بسهولة بواسطة المعادلة التالية:

حيث:

• Σin هو مجموع أوزان الروابط داخل المجتمع C.
• Σtot هو مجموع أوزان الروابط المتصلة بـعقد في المجتمع C.
• ki هو مجموع أوزان الروابط من العقدة i إلى العقد في المجتمع C.
• m هو مجموع أوزان جميع الروابط في الشبكة.

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

تطبيق عملي لخوارزمية Fast Unfolding

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

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

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

مزايا خوارزمية Fast Unfolding

تتميز خوارزمية Fast Unfolding بعدة مزايا تجعلها خيارًا مفضلاً في العديد من التطبيقات:

• بساطة التنفيذ: خطواتها بديهية وسهلة التطبيق، والنتائج غير خاضعة للإشراف (unsupervised)، مما يعني أنها لا تتطلب بيانات تدريب مسبقة.
• سرعة فائقة: الخوارزمية سريعة للغاية. تشير المحاكاة الحاسوبية على شبكات معيارية ضخمة جدًا إلى أن تعقيدها خطي (linear) على البيانات النموذجية والمتفرقة.
• كفاءة الحساب: قد يرجع ذلك إلى سهولة حساب الربح في المعيارية (Gain in Modularity) وانخفاض عدد المجتمعات بشكل كبير بعد بضع تمريرات فقط.

قيود خوارزمية Fast Unfolding

على الرغم من مزاياها، تواجه الخوارزمية بعض القيود:

• حد الدقة (Resolution Limit): يفشل تحسين المعيارية (modularity optimization) في تحديد المجتمعات الأصغر من مقياس معين. لذا، فإنه يسبب حدًا للدقة على المجتمعات المحسوبة باستخدام نهج تحسين المعيارية البحت.
• الشبكات الصغيرة: بالنسبة للشبكات الصغيرة، يكون احتمال دمج مجتمعين منفصلين عن طريق نقل كل عقدة منخفضًا جدًا.

الخلاصة التقنية

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

نأمل أن تكون هذه المعلومات مفيدة لك. إذا كان لديك أي أسئلة أو استفسارات، فلا تتردد في طرحها. شكرًا لقراءتك!