خوارزمية غريفان-نيومان

خوارزمية غريفان-نيومان، (بالإنجليزية: Girvan–Newman algorithm)‏، الخوارزمية، أُطلق عليها هذا الاسم بعد أن أصبحت طريقة ميشيل غريفان ومارك نيومان، وهي واحدة من الطرق المستخدمة في اكتشاف المجتمعات في النظم المعقدة. حيث كانت ترتبط فكرة «بنية المجتمع» بتكوين المجموعات، على الرغم من أنها ليست هي نفسها. يتكون المجتمع من مجموعة فرعية من العُقد الداخلية التي يكون ارتباطات العقدة بالعقدة فيها كثيفًا، بينما تكون حواف العُقد في المجتمعات الأخرى أقل كثافة. وهناك العديد من الطرق البديلة للكشف عن المجتمعات في شبكات المعلومات. وتشتمل هذه الشبكات على التجمع الهرمي وتقسيم الرسوم البيانية لبلوغ الحد الأقصى لدلالات الجودة مثل الشبكة النمطية وزيادة عامل المفاجأة إلى الحد الأقصى وما إلى ذلك.

الحافة البينية وبناء المجتمع

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

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

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

وتتلخص أدناه خطوات الخوارزمية لاكتشاف المجتمع

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

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

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