Community Detection
Bogumił Kamiński, Paweł Prałat, François Théberge · 2021
In this chapter, we first introduce basic definitions and properties that are expected to be present in a partition returned by a good community detection algorithm. The problem we try to address is unsupervised in nature and so we typically do not know how to benchmark a given algorithm run on a particular real-world network. As a result there is often a need to construct synthetic graphs with a given community structure and to then rigorously evaluate them. Since finding communities is an important task, it has generated many multidisciplinary research projects. As a result, algorithms use different ideas and approaches, such as the graph modularity function, hierarchical clustering, label propagation, spectral bisection method, and the information-theoretic method. We concentrate on non-overlapping communities. Overlapping communities are separately discussed in a later chapter.