التجميع الهرمي للشبكات

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

في خوارزمية التجميع الهرمي، الوزن${\displaystyle W_{ij}}$يتم أولاً تعيينها لكل زوج من الرؤوس${\displaystyle (i,j)}$في الشبكة. يُستخدم الوزن، الذي قد يختلف باختلاف التطبيق (انظر القسم أدناه)، للإشارة إلى مدى ترابط الرؤوس. بعد ذلك، بدءًا من فصل جميع العقد في الشبكة، يتم البدء في ربط العقد من الأعلى وزنًا إلى الأدنى بين الأزواج (في حالة التقسيم، يبدأ من الشبكة الأصلية ويتم إزالة الروابط من الأدنى وزنًا إلى الأعلى). مع إضافة الروابط، تبدأ المجموعات الفرعية المتصلة في التشكل. تمثل هذه المجموعات هياكل مجتمعات الشبكة.

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

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

هناك معياران استُخدما سابقًا بنجاح متفاوت، وهما عدد المسارات المستقلة بين كل زوج من الرؤوس، والعدد الإجمالي للمسارات بين الرؤوس مُرجّحًا بطول المسار. مع ذلك، يتمثل أحد عيوب هذين المعيارين في ميلهما إلى فصل الرؤوس الطرفية المنفردة عن مجموعاتها الصحيحة نظرًا لقلة عدد المسارات المؤدية إليها. لهذا السبب، يُعدّ استخدامهما في تقنيات التجميع الهرمي غير مثالي. ^{[ 1 ]}

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

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

• بنية الشبكة
• التصنيف العددي
• بنية الشجرة