Published August 5, 2023
| Version v1
Publication
The Computational Complexity of Hierarchical Clustering Algorithms for Community Detection: A Review
Creators
- 1. Wrocław University of Science and Technology
- 2. AGH University of Krakow
- 3. Hue University
- 4. Trường ĐH Nguyễn Tất Thành
Description
Community detection is a highly active research area that aims to identify groups of vertices with similar properties or interests within complex real-world networks. Over the years, a large number of papers have been published, resulting in the development of various community detection algorithms that consider factors such as the type of networks, the nature of communities, and applications. Despite numerous relevant review and survey papers, the literature lacks a comprehensive analysis of the computational complexity of existing community detection algorithms. This review aims to address this gap by providing a more detailed analysis and evaluation of the computational complexity of hierarchical clustering algorithms for community detection, including two main categories: agglomerative and divisive algorithms. We also highlight the main theoretical concepts, emphasizing the benefits and drawbacks of each approach, both in theory and in practical applications. This review helps researchers and practitioners in this field better understand valuable information on the differences and unique features of community detection algorithms with hierarchical community structure.
Translated Descriptions
⚠️
This is an automatic machine translation with an accuracy of 90-95%
Translated Description (Arabic)
يعد الكشف المجتمعي مجالًا بحثيًا نشطًا للغاية يهدف إلى تحديد مجموعات الرؤوس ذات الخصائص أو الاهتمامات المتشابهة داخل شبكات العالم الحقيقي المعقدة. على مر السنين، تم نشر عدد كبير من الأوراق، مما أدى إلى تطوير خوارزميات اكتشاف مجتمعية مختلفة تأخذ في الاعتبار عوامل مثل نوع الشبكات وطبيعة المجتمعات والتطبيقات. على الرغم من العديد من أوراق المراجعة والمسح ذات الصلة، فإن الأدبيات تفتقر إلى تحليل شامل للتعقيد الحسابي لخوارزميات الكشف المجتمعية الحالية. تهدف هذه المراجعة إلى معالجة هذه الفجوة من خلال توفير تحليل وتقييم أكثر تفصيلاً للتعقيد الحسابي لخوارزميات التجميع الهرمي لاكتشاف المجتمع، بما في ذلك فئتين رئيسيتين: الخوارزميات التكتلية والخوارزميات المثيرة للانقسام. كما نسلط الضوء على المفاهيم النظرية الرئيسية، مع التأكيد على فوائد وعيوب كل نهج، سواء من الناحية النظرية أو في التطبيقات العملية. تساعد هذه المراجعة الباحثين والممارسين في هذا المجال على فهم أفضل للمعلومات القيمة حول الاختلافات والسمات الفريدة لخوارزميات الكشف المجتمعي ذات الهيكل المجتمعي الهرمي.Translated Description (French)
La détection communautaire est un domaine de recherche très actif qui vise à identifier des groupes de sommets ayant des propriétés ou des intérêts similaires au sein de réseaux complexes du monde réel. Au fil des ans, un grand nombre d'articles ont été publiés, ce qui a abouti au développement de divers algorithmes de détection de communautés qui prennent en compte des facteurs tels que le type de réseaux, la nature des communautés et les applications. Malgré de nombreux documents de revue et d'enquête pertinents, la littérature manque d'une analyse complète de la complexité computationnelle des algorithmes de détection de la communauté existants. Cette revue vise à combler cette lacune en fournissant une analyse et une évaluation plus détaillées de la complexité informatique des algorithmes de clustering hiérarchique pour la détection de la communauté, y compris deux catégories principales : les algorithmes agglomératifs et diviseurs. Nous mettons également en évidence les principaux concepts théoriques, en soulignant les avantages et les inconvénients de chaque approche, à la fois en théorie et dans les applications pratiques. Cette revue aide les chercheurs et les praticiens dans ce domaine à mieux comprendre les informations précieuses sur les différences et les caractéristiques uniques des algorithmes de détection communautaire avec une structure communautaire hiérarchique.Translated Description (Spanish)
La detección comunitaria es un área de investigación muy activa que tiene como objetivo identificar grupos de vértices con propiedades o intereses similares dentro de redes complejas del mundo real. A lo largo de los años, se han publicado una gran cantidad de artículos, lo que ha dado como resultado el desarrollo de varios algoritmos de detección comunitaria que consideran factores como el tipo de redes, la naturaleza de las comunidades y las aplicaciones. A pesar de los numerosos documentos de revisión y encuesta relevantes, la literatura carece de un análisis exhaustivo de la complejidad computacional de los algoritmos de detección de la comunidad existentes. Esta revisión tiene como objetivo abordar esta brecha al proporcionar un análisis y evaluación más detallados de la complejidad computacional de los algoritmos de agrupamiento jerárquico para la detección comunitaria, incluidas dos categorías principales: algoritmos aglutinantes y divisivos. También destacamos los principales conceptos teóricos, haciendo hincapié en los beneficios e inconvenientes de cada enfoque, tanto en la teoría como en las aplicaciones prácticas. Esta revisión ayuda a los investigadores y profesionales en este campo a comprender mejor la valiosa información sobre las diferencias y características únicas de los algoritmos de detección comunitaria con estructura comunitaria jerárquica.Additional details
Additional titles
- Translated title (Arabic)
- التعقيد الحسابي لخوارزميات التجميع الهرمي للكشف المجتمعي: مراجعة
- Translated title (French)
- The Computational Complexity of Hierarchical Clustering Algorithms for Community Detection : A Review
- Translated title (Spanish)
- La complejidad computacional de los algoritmos de agrupación jerárquica para la detección de comunidades: una revisión
Identifiers
- Other
- https://openalex.org/W4382560654
- DOI
- 10.1142/s2196888823300016
References
- https://openalex.org/W14929449
- https://openalex.org/W1554338108
- https://openalex.org/W1966773605
- https://openalex.org/W1971421925
- https://openalex.org/W2015953751
- https://openalex.org/W2026601878
- https://openalex.org/W2029373408
- https://openalex.org/W2031243162
- https://openalex.org/W2033590892
- https://openalex.org/W2038920443
- https://openalex.org/W2047940964
- https://openalex.org/W2056897951
- https://openalex.org/W2095293504
- https://openalex.org/W2098236822
- https://openalex.org/W2104240253
- https://openalex.org/W2112439948
- https://openalex.org/W2122603314
- https://openalex.org/W2131681506
- https://openalex.org/W2132202037
- https://openalex.org/W2132914434
- https://openalex.org/W2148606196
- https://openalex.org/W2160987050
- https://openalex.org/W2471188671
- https://openalex.org/W2503222705
- https://openalex.org/W2792353048
- https://openalex.org/W2792473587
- https://openalex.org/W2793868694
- https://openalex.org/W2806754339
- https://openalex.org/W2890128605
- https://openalex.org/W2901693736
- https://openalex.org/W2961187130
- https://openalex.org/W2963383438
- https://openalex.org/W3003570729
- https://openalex.org/W3026728971
- https://openalex.org/W3045237327
- https://openalex.org/W3046680677
- https://openalex.org/W3093301018
- https://openalex.org/W3098422831
- https://openalex.org/W3098742898
- https://openalex.org/W3102247132
- https://openalex.org/W3102822398
- https://openalex.org/W3106188259
- https://openalex.org/W3119943343
- https://openalex.org/W3119958346
- https://openalex.org/W3125626040
- https://openalex.org/W3126033509
- https://openalex.org/W3153283566
- https://openalex.org/W3158827677
- https://openalex.org/W3163230711
- https://openalex.org/W3203290590
- https://openalex.org/W4210567369
- https://openalex.org/W4210901545
- https://openalex.org/W4224986603
- https://openalex.org/W4226341425
- https://openalex.org/W4300815771
- https://openalex.org/W4301621763
- https://openalex.org/W4312856860
- https://openalex.org/W4317383769
- https://openalex.org/W4322761889
- https://openalex.org/W4323061307