خوارزمية غريفان-نيومان
تعريفًا بالموضوع، خوارزمية غريفان-نيومان، ، الخوارزمية، أُطلق عليها هذا الاسم بعد أن أصبحت طريقة ميشيل غريفان ومارك نيومان، وهي واحدة من الطرق المستعملة في اكتشاف المجتمعات في النظم المعقدة. حيث كانت ترتبط فكرة «بنية المجتمع» بتكوين المجموعات، على الرغم من أنها ليست هي نفسها. يتكون المجتمع من مجموعة فرعية من العُقد الداخلية التي يكون ارتباطات العقدة بالعقدة فيها كثيفًا، بينما تكون حواف العُقد في المجتمعات الأخرى أقل كثافة. وهناك الكثير من الطرق البديلة للكشف عن المجتمعات في شبكات المعلومات. وتشتمل هذه الشبكات على التجمع الهرمي وتقسيم الرسوم البيانية لبلوغ الحد الأقصى لدلالات الجودة مثل الشبكة النمطية وزيادة عامل المفاجأة إلى الحد الأقصى وما إلى ذلك. ونتناول فيما يلي مزيدًا من التفاصيل.
وتتلخص أدناه خطوات الخوارزمية لاكتشاف المجتمع
كذلك، وكانت النتيجة النهائية لخوارزمية غريفان-نيومان هي مخطط الشجرة. ومثلما تم تشغيل خوارزمية غريفان-نيومان فقد تم إنتاج مخطط الشجرة من أعلى إلى أسفل (مثلًا، انقسام الشبكة حتى في مجتمعات مختلفة مع الإزالة المتوالية للروابط). حيث تمثل العُقد الفردية أوراق مخطط الشجرة.
ومن ناحية أخرى، فالحقيقة هو أنه يتم إعادة حساب هذه البينيات فقط لأنها هي تلك التي تتأثر بالإزالة، وربما تُقلل من وقت التشغيل للمحاكاة العملية في أجهزة الحاسوب. ومع ذلك، فلا بد من إعادة حساب مركزية البينية مع كل خطوة أو أخطاء شديدة تحدث. والسبب في ذلك هو أن الشبكة نفسها تتكيف مع الظروف الجديدة المحددة بعد إزالة الحافة. فمثلًا، إذا كان هناك مجتمعان متصلان بأكثر من حافة، لا يكون هناك ضامن على أن جميع هذه الحواف سيكون لها بينية عالية. ولقد علمنا بحسب هذه الطريقة، أن هناك واحدة على الأقل منها سوف تمتلك بينية عالية، لكن لم يُعرف شيء أكثر من ذلك. ولقد تأكد من خلال إعادة حساب البينية بعد إزالة جميع الحواف، أن هناك واحدة على الأقل من الحواف المتبقية بين المجتمعين سيكون لديها قيمة عالية دائمًا.
- يتم أولاً حساب البينية لجميع الحواف الموجودة في الشبكة.
- إزالة الحافة بحسب أعلى بينية.
- تتأثر بينية جميع الحواف بالإزالة المُعاد إحصاؤها.
- تُكرر الخطوات 2 و3 حتى تتلاشى أي حواف.
الحافة البينية وبناء المجتمع
كذلك، تعتمد طريقة التجمع الهرمي على تحديد الوزن لكل حافة ووضع هذه الحواف في الشبكة الفارغة البدائية، بدءًا من الحواف ذات الأوزان الثقيلة وصولاً إلى الحواف ذات الأوزان الخفيفة. حيث تُعد الحواف ذات الأوزان الأكبر داخل المجتمع هي الأوزان الأكثر مركزية. وعلى الرغم من اكتشاف التقاليد في المجتمع، فتعرض هذه الطريقة بعض الباثولوجيا. فواحدة منها مثلًا، هي عدم القدرة على التصنيف في المجتمع، حيث تتصل العقدة التي ترتبط بالشبكة من حافة واحدة فقط.
ومن جهة أخرى، تمت دارسة بينية فيرتكس في الماضي كمعيار للمركزية والتأثر بالعُقد في شبكات المعلومات. ولأي عقدة ، فقد تم تعريف بينية فيرتكس بأنها عدد المسارات الأقل بين أزواج العُقد التي تعمل من خلالها. والتي تُعتبر مقياسًا لتأثير العقدة على تدفق المعلومات بين العُقد الأخرى، خاصة في الحالات التي تتدفق فيها المعلومات عبر شبكة المعلومات والتي تتبع في المقام الأول المسار الأقصر المتاح. وقدمت خوارزمية غريفان-نيومان هذا التعريف لحالة الحواف، حيث عرّفت «الحافة البينية» بأنها هي الحافة التي يكون فيها عدد المسارات أقصر بين أزواج العُقد التي تعمل على طول ذلك. أما إذا كان هناك أكثر من مسار قصير بين زوج العُقد، فيتوجب على كل مسار أن يُحدد الوزن المساوي لهذا الوزن الإجمالي لجميع المسارات المساوية للوحدة. أما إذا احتوت شبكة المعلومات على المجتمعات أو المجموعات التي ترتبط فقط على نحو غير محكم من قبل الحواف المتداخلة بين المجموعات، كان من الواجب على جميع المسارات الأقصر بين المجتمعات المختلفة أن تتقدم على طول واحد من هذه الحواف القليلة. ومن ثم، سيكون لحواف ربط المجتمعات الحافة البينية العالية (على الأقل واحدة منهم). ويتم فصل المجموعات عن بعضها البعض عن طريق إزالة هذه الحواف، ثم يتم الكشف عن البناء المجتمعي الأساسي لشبكة المعلومات.
من جانب آخر، وتعمل خوارزمية غريفان-نيومان في الطريق المعاكس. فبدلاً من محاولة بناء المقياس الذي يخبرنا على أي من تلك الحواف هي الأكثر مركزية للمجتمعات، فإنها تركز على تلك الحواف الأقل مركزية، الحواف التي يكون أغلبها «بين» المجتمعات. وتم الكشف عن هذه المجتمعات عن طريق الإزالة التدريجية للحواف من الرسم البياني الأصلي، بدلاً من إضافة الحواف الأقوى للشبكة الفارغة البدائية.
📝 هل في هذه المقالة خطأ؟
إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.
ما رأيك في هذه المقالة؟