Robust dynamic community detection with applications to human brain functional networks

Abstract

While current technology permits inference of dynamic brain networks over long time periods at high temporal resolution, the detailed structure of dynamic network communities during human seizures remains poorly understood. We introduce a new methodology that addresses critical aspects unique to the analysis of dynamic functional networks inferred from noisy data. We propose a dynamic plex percolation method (DPPM) that is robust to edge noise, and yields well-defined spatiotemporal communities that span forward and backwards in time. We show in simulation that DPPM outperforms existing methods in accurately capturing certain stereotypical dynamic community behaviors in noisy situations. We then illustrate the ability of this method to track dynamic community organization during human seizures, using invasive brain voltage recordings at seizure onset. We conjecture that application of this method will yield new targets for surgical treatment of epilepsy, and more generally could provide new insights in other network neuroscience applications.

Fig. 1. Illustration of DPPM principles and effectiveness.

a Schematic of the bridges used to walk plexes within dynamic communities across time. Blue edges represent inferred connectivity, while red edges connecting the same (solid) or adjacent (dotted) vertices facilitate movement. b Illustrative example showing how a simple community (in orange) is tracked by DPPM across time in a manner allowing for both coalescence and fragmentation. This community at first grows at t + 1, and then fragments at t + 2. Another community present at t (purple) perishes at t + 1. c Comparison of DPPM (with 2-plex of size m = 3, 2nd column), CPM (with 1-plex of size m = 3, 3rd column), and MMM (with γ = 1, ω = 1, 4th column) in determining communities across two adjacent time points t and t  + 1. The connected component at time t + 1 shares increasingly more edges components at time t from the top to the bottom row of plots. In the preferred results, the dynamic communities (1st column) depend on the number of edges shared from time t to t + 1. Whereas DPPM treats these as three distinct scenarios, neither CPM nor (effectively) MMM distinguish the three cases. In CPM and MMM, the colorbar indicates the proportion of community membership over n = 100 repetitions of community detection. d Example dynamic community tracking in the presence of missing edges. Dynamic community membership for ten example sequential time index networks computed using DPPM (with 2-plex of size m = 4), CPM (with 1-plex of size m = 3), and MMM (with γ  = 1, ω = 1). While DPPM detects a single dynamic community in time, the other two methods do not.

Fig. 2. In an example of dynamic community expansion, DPPM outperforms two existing methods.

Illustration of community expansion in nodes (a) and in edges (b). a Two-dimensional representation of the nodes on an 8 × 8 grid at five time intervals. Color (blue) indicates when a node becomes recruited to the largest community. b Adjacency matrices for the simulated network of 64 nodes at the same five time intervals. Color (black) indicates an edge between a node pair. c Dynamic community detection results for each method, from left to right: true expansion, DPPM with parameters m = 4 and k = 2, CPM with parameter m = 4, and MMM with parameters γ = 0.1, ω = 0.1; see Supplementary Figs. 2 and 6a for results with different parameter choices, and see Fig. 4a, e for average results over 100 realizations of the simulation. Color indicates community membership. The largest community detected by DPPM is most consistent with the true expansion.

Fig. 3. In three additional examples of dynamic community evolution, DPPM outperforms two existing methods.

Community detection for each method in the case of a community contraction, b community splitting, and c community merging. From left to right in each subfigure: true community evolution, DPPM with parameters m = 4 and k = 2, CPM with parameter m = 4, and MMM with parameters γ = 0.1, ω = 0.1; see Fig. 4 and Supplementary Figs. 3–6 for results with different parameter choices. Color indicates community membership. In all cases, the largest community detected by DPPM is most consistent with the true community evolution.

Fig. 4. DPPM performs with higher sensitivity and specificity than two existing methods in the four simulation scenarios.

Specificity and sensitivity of DPPM (blue), CPM (red), and MMM (yellow) for n = 100 independent simulations with different noise instantiations of each dynamic community evolution scenario. a Community expansion, b Community contraction, c Community splitting, and d Community merging. Each circle indicates the result of one simulation with one parameter configuration (see “Methods”). e Summary results for each community tracking method applied to each simulation scenarios. Bars indicate the mean sensitivity and specificity for each parameter configuration of each method. Dots indicate the results of the n = 100 simulations for each simulation scenario and method.

Fig. 5. Application of DPPM reveals new characteristics of dynamic communities before and after human seizure onset.

a Top: Voltage time series recorded at nine electrodes to illustrate pre-seizure and seizure voltage dynamics. Middle: Example recruitment of a large community at seizure onset. Before seizure onset (t < 0 s) small communities appear briefly; color indicates community membership. After seizure onset (t > 0 s) a large dynamic community appears (red) that persists for over 30 s. Bottom: Temporal evolution of the size of the seizure onset community (red). Nearly all nodes participate in the seizure onset community. b Example expansion of the seizure onset community. Each circle denotes an electrode on the 8 × 8 electrode grid, and red (black) indicates electrodes recruited (not yet recruited) into the dynamic community. Community lifespan (c) and maximum community size (d) for all pre-seizure communities (gray histograms) and the seizure onset community observed for each of the four seizures of this patient (four arrows, red indicates the community shown in (a)). Node loyalty averaged over the four seizures for (e) all pre-seizure communities and (f) the seizure onset community. In both panels, warm (cool) colors indicate nodes that participate in communities for longer (shorter) times. The black circles indicate a subset of electrodes that have high node loyalty before and during early seizure. g Median recruitment order to the seizure onset community for four seizures. Warm (cool) colors indicate electrodes recruited earlier (later) into the seizure onset community. h Mean recruitment time to large amplitude ictal oscillations observed for the same patient, as reported in ref. . Warm (cool) colors indicate electrodes recruited earlier (later) into ictal spread. Histograms of the size (i) and the lifespan (j) of the maximum community during the pre-seizure (blue) and seizure (red) intervals from each patient and seizure. The maximal community tends to be larger and of longer duration during seizure. The mean number of communities (k) and the longest community duration (l) during seizure for patients with good (Engel 1,2) and poor (Engel 3,4) surgical outcomes. Each circle indicates an individual seizure, and the red square the population mean (n = 27 from nine patients with low Engel score, and n = 11 from three patients with high Engel score). Worse surgical outcomes exhibit more communities with longer maximal duration during seizure.

Fig. 6. Illustration of simple simulated networks.

Adjacency matrices in which black at coordinate (i, j) indicates an edge from node i to node j. a Seven node network at time t. b Seven node networks at time t + 1, with 7, 8, and 9 edges. Red indicates edges added to the leftmost network. c Nine node network.