gemeenschapsdetectie

Gemeenschapsdetectie, ook wel community detection genoemd, is een taak in netwerktheorie die gericht is op het opdelen van een netwerk in gemeenschappen of clusters. In een dergelijke indeling vormen knopen binnen dezelfde gemeenschap doorgaans meer onderlinge verbindingen met elkaar dan met knopen uit andere gemeenschappen, wat inzicht geeft in de structuur en functies van het netwerk.

De gebruikte benaderingen proberen meestal een kwaliteitseigenschap te maximaliseren, zoals modulariteit of de beschrijving van informatie via korte paden van random walks (Infomap). Veel toegepaste algoritmen zijn modulariteitsgebaseerde methoden als Louvain en Leiden (die schaalbaar zijn naar grote netwerken), informatie-theoretische methoden zoals Infomap, en propagatie- of wandelalgoritmen zoals Label Propagation of Walktrap. Er bestaan ook methoden voor overlappende gemeenschappen (zoals clique-percolation) en voor dynamische netwerken, waarbij gemeenschappen in de loop van de tijd veranderen.

Toepassingen bevinden zich in sociale netwerken, biologie en netwerken van biologische processen, hersennetwerken, transport en infrastructuur, marketing en aanbevelingssystemen, en epidemiologie, waar gemeenschappen kunnen duiden op functionele modules, gezamenlijke dynamiek of gerichte interventies.

Knelpunten zijn onder meer de resolutie-issues van modulariteit (kleine en grote gemeenschappen kunnen worden gemist), meerdere optima die vergelijkbaar zijn (de degeneratie van oplossingen), en gevoeligheid voor netwerkkwaliteit en -grootte. Bij dynamische netwerken vereist tijdsafhankelijke detectie vaak continue updates, wat de complexiteit verhoogt.

Evaluatie van resultaten gebeurt vaak met statische maatstaven zoals modulariteit of conductance, en met vergelijking ten opzichte van een bekende referentiepartitie via NMI of de Rand-index. Bij gebrek aan ground truth kan men interne kwaliteitsscores of stabiliteitsmetingen gebruiken.