Technische Samenvatting: Heuristische en Exacte Modulariteitsoptimalisatie met Grootte-Gestructureerde Gemeenschappen

Probleemstelling

Gemeenschapsdetectie is een fundamentele taak in netwerkanalyse, toch falen standaardalgoritmen vaak om domeinspecifieke voorkennis met betrekking tot gemeenschapsgroottes te integreren. In toepassingen zoals marktsegmentatie, neurowetenschap (hersenenconnectomen) en genomica (chromosomale interacties) beschikken experts vaak over kennis van redelijke bereiken voor gemeenschapsgroottes. Echter, bestaande onbeperkte methoden produceren frequent verdelingen met extreme grootteverschillen (bijvoorbeeld één enorme gemeenschap en vele triviaal kleine) of sluiten niet aan bij biologische of functionele realiteiten.

Hoewel multi-resolutietechnieken gebruikers indirect de gemiddelde gemeenschapsgrootte beïnvloeden door een resolutieparameter ($\gamma$) af te stemmen, controleert deze aanpak niet de grootte van individuele gemeenschappen, noch garandeert het dat alle gemeenschappen binnen een specifiek door de gebruiker gedefinieerd bereik vallen. Dit artikel behandelt het Grootte-Gestructureerde Maximum-Modulariteitsprobleem (SMM): het vinden van een verdeling van een netwerk die de modulariteit maximaliseert, terwijl ervoor wordt gezorgd dat elke gemeenschapsgrootte $n_c$ voldoet aan $n_{min} \le n_c \le n_{max}$.

Methodologie

De auteurs stellen een tweeledige aanpak voor het oplossen van het SMM-probleem voor: een exacte optimalisatie-baseline en een schaalbare heuristiek.

1. Exacte Optimalisatie-baseline (SMMk)

Om een grondwaarheid voor betrouwbaarheid te vestigen, formuleren de auteurs het probleem als een Integer Program (IP).

• Formulering: Zij breiden de standaard Integer Programming-formulering voor het Maximum Modulariteit $k$-partition-probleem (MMk) uit.
• Beperkingen: Het model bevat lineaire beperkingen om de groottegrenzen af te dwingen. Specifiek introduceren zij beperkingen die garanderen dat voor elke niet-lege gemeenschap $c$, het aantal knopen $\sum x_{ic} \ge n_{min}$ is, en voor alle potentiële gemeenschappen $\sum x_{ic} \le n_{max}$.
• Oplosser: Het model wordt opgelost met de Gurobi-optimizer om globaal optimale (of bijna-optimale) verdelingen te verkrijgen voor kleine tot middelgrote grafen. Dit dient als baseline voor de evaluatie van de heuristiek.

2. Heuristische Optimalisatie (Gestructureerde Leiden - CL)

Het direct afdwingen van groottebeperkingen binnen standaard modulariteitsheuristieken (zoals het Leiden-algoritme) is problematisch omdat lokale knoopverplaatsingen de groottegrenzen gemakkelijk kunnen schenden (bijvoorbeeld het verplaatsen van een knoop naar een nieuwe singleton-gemeenschap schendt $n_{min} > 1$).

• Strafbenadering: In plaats van een barrièremethode (die het zoekruimte beperkt), hanteren de auteurs een strafbenadering. Zij transformeren het beperkte probleem naar een onbeperkt probleem door een gewijzigde doelfunctie te optimaliseren:
  $$Q'(G, P) = Q(G, P) - \phi \Theta(P)$$
  Waar $\Theta(P)$ een straf functie is voor gemeenschappen die de groottebeperkingen schenden, en $\phi$ een strafgewicht is.
• Straffunctie: De straf $\theta(n_c)$ voor een gemeenschap van grootte $n_c$ is gedefinieerd als:
  $$\theta(n_c) = \begin{cases} \sqrt{n_{min} - n_c} & \text{als } n_c < n_{min} \\ \sqrt{n_c - n_{max}} & \text{als } n_c > n_{max} \end{cases}$$
  De wortelfunctie is gekozen omdat deze sub-additief is, wat voorkomt dat het algoritme vastloopt in lokale optima waar het splitsen van een grote schendende gemeenschap in twee kleinere schendende gemeenschappen een lagere totale straf oplevert.
• Progressief Schema: Het algoritme start met $\phi = 0$ (onbeperkt). Als de resulterende verdeling de beperkingen schendt, wordt $\phi$ verhoogd (beginnend bij $10^{-4}$ en verdubbelend) en wordt de optimalisatie herinitialiseerd vanuit de vorige oplossing. Dit gaat door totdat een haalbare verdeling is gevonden.

Belangrijkste Resultaten

De auteurs evalueerden de voorgestelde Gestructureerde Leiden (CL)-methode tegenover Onbeperkte Leiden (UL) en de Gestructureerde Integer Programming (CIP)-baseline over synthetische en real-world netwerken.

Synthetische Benchmarks

• Geplante Partition-modellen: In netwerken met bekende grondwaarheid-gemeenschappen presteerden CL en CIP aanzienlijk beter dan UL in opsporingspercentages (gemeten door Adjusted Mutual Information, AMI), met name wanneer de mengparameter laag tot gemiddeld was. UL faalde frequent bij het terugvinden van de geplante gemeenschappen omdat het verdelingen produceerde met groottes buiten het verwachte bereik.
• Ring van Cliques: In een graf van 50 cliques (grootte 5) die sequentieel verbonden zijn, vond UL alleen de juiste verdeling terug als de resolutieparameter handmatig werd afgestemd op een specifiek bereik ($[5, 40]$). In tegenstelling hiermee vond CL de geplante verdeling nauwkeurig terug bij de standaardresolutie ($\gamma=1$) wanneer het juiste groottebereik $[2, 8]$ werd gegeven.
• Betrouwbaarheid: De opsporingspercentages van de heuristische CL waren consequent dicht bij, en soms gelijk aan, de exacte CIP-baseline, wat aantoont dat de heuristiek in deze contexten geen nauwkeurigheid opoffert voor snelheid.

Real-world Netwerken

• Hersenenconnectoom: Toegepast op het Boedapest hersenenconnectoom-netwerk, produceerde UL een triviale verdeling van vier gemeenschappen (corresponderend met hemisferen), wat geen nut heeft voor de neurowetenschap.
• Domein-uitlijning: Door CL toe te passen met een groottebereik afgeleid van expertkennis (gebaseerd op de Brainnetome- en Schaefer-atlassen, $[43, 187]$ knopen), produceerde de methode 6 gemeenschappen. Dit resultaat sluit veel beter aan bij bekende functionele hersenclusters (bijvoorbeeld de 7 clusters gedefinieerd door Yeo et al.) dan het onbeperkte resultaat.
• Controle van Variatie: De auteurs demonstreerden dat het veranderen van de resolutieparameter in UL de gemiddelde gemeenschapsgrootte controleert, maar faalt in het controleren van de variatie (variantie) van groottes. CL biedt directe controle over zowel het gemiddelde als de variatie, waardoor wordt gegarandeerd dat alle gemeenschappen binnen de gespecificeerde grenzen vallen.

Betekenis en Claims

Het artikel beweert dat de voorgestelde methode een geprincipeerde manier biedt om domeinexpertise te integreren in gemeenschapsdetectie.

• Directe Controle: In tegenstelling tot de "trial-and-error"-praktijk van het afstemmen van resolutieparameters, stelt CL gebruikers in staat om expliciet de minimum- en maximumgrootte van gemeenschappen te definiëren, wat direct inspreekt op de behoeften van domeinexperts.
• Schaalbaarheid: Hoewel de exacte IP-methode (CIP) door computergewicht beperkt is tot kleinere grafen, is de CL-heuristiek schaalbaar en toepasbaar op grote netwerken, waardoor het praktisch is voor real-world toepassingen.
• Implementatie: De methode is geïmplementeerd binnen het Python Leiden-algoritme-pakket, waardoor het toegankelijk is voor direct gebruik.

De auteurs concluderen dat hoewel modulariteit bekende beperkingen heeft (zoals het resolutielimiet en het ontbreken van een duidelijke statistische onderbouwing), het vermogen om groottebeperkingen af te dwingen via hun heuristiek zorgt voor informatiever en domein-uitgelijnde verdelingen. Zij suggereren dat toekomstig werk zou kunnen onderzoeken hoe groottebeperkingen in andere kaders, zoals Stochastische Blockmodellen (SBM's), kunnen worden geïntegreerd om deze beperkingen te benutten binnen een context van statistische inferentie.