gemenskapsdetektering

Gemenskapsdetektering is the process of finding groups of vertices, known as communities or modules, within a graph such that vertices inside each group are more densely connected to each other than to vertices in other groups. The concept is central to network science, social network analysis, biology, and information retrieval, where uncovering hidden structure can reveal functional relationships or social subgroups.

The problem can be formalised as an optimisation problem on an adjacency matrix. A popular objective is modularity maximisation, which measures the difference between the observed edge density within communities and the expected density under a null model. Optimisation is NP-hard, so heuristic algorithms are used. Common methods include greedy agglomerative or divisive algorithms, spectral clustering based on eigenvectors of the Laplacian, the Louvain method, Infomap which uses random walks, and label propagation techniques.

Beyond modularity, alternative quality functions exist, such as stochastic block models that provide probabilistic descriptions, or fitness functions that allow overlapping communities. Overlap can be handled by link partitioning or fuzzy clustering. Dynamic and multilayer networks extend the framework to time‑varying or multiplex structures, capturing community evolution or cross‑platform interactions.

Applications span sociology, where communities correspond to friend groups or professional circles; biology, where modules represent protein complexes or metabolic pathways; and marketing, where customer segments are inferred from transaction networks. The field continues to evolve with advances in scalable algorithms, statistical validation, and integration with machine‑learning pipelines.