PaperlayerView exact revision on arXiv

Source-linked AI summary

Graph analysis and modularity of brain functional connectivity networks: searching for the optimal threshold

Cécile Bordier, Carlo Nicolini, Angelo Bifone

arXiv:1705.06481v1q-bio.NCphysics.data-anphysics.soc-ph

TL;DR

Choosing a sparsification threshold for brain-network community detection is difficult because removing weak, noise-affected links can also discard genuine connections. The paper tests percolation analysis on synthetic networks with planted modular structure and brain-like topological features. It reports that the percolation threshold corresponds to maximum information retrieval by community-detection algorithms under noise and intersubject variability.

  • Problem

    Sparsification removes weak links affected by experimental noise, but weak links may also contain structural information, making the optimal threshold for community detection an open question.

    Source: connectivity, marking the inception of… · p. 2, Discussion · p. 12

  • Method

    The authors apply percolation analysis to synthetic networks with planted modular structure and brain-like topological features, evaluating community detection with different noise and intersubject variability.

    Source: Discussion · p. 12, Conclusion · p. 12

  • Results

    The percolation threshold—the highest threshold preserving the giant component’s connectedness—corresponds to maximum information retrieval about planted modular structure across community-detection algorithms under noise and intersubject variability.

    Source: Conclusion · pp. 12–13

  • Takeaways & Limitations

    Percolation analysis provides a data-driven strategy for selecting sparsification thresholds when comparing brain networks with different connectivity strengths.

    Source: Discussion · p. 12

    The validation uses synthetic networks with planted modular structure and topological features akin to real-world brain connectivity graphs.

    Source: Conclusion · p. 12

Abstract

from arXiv · show

Neuroimaging data can be represented as networks of nodes and edges that capture the topological organization of the brain connectivity. Graph theory provides a general and powerful framework to study these networks and their structure at various scales. By way of example, community detection methods have been widely applied to investigate the modular structure of many natural networks, including brain functional connectivity networks. Sparsification procedures are often applied to remove the weakest edges, which are the most affected by experimental noise, and to reduce the density of the graph, thus making it theoretically and computationally more tractable. However, weak links may also contain significant structural information, and procedures to identify the optimal tradeoff are the subject of active research. Here, we explore the use of percolation analysis, a method grounded in statistical physics, to identify the optimal sparsification threshold for community detection in brain connectivity networks. By using synthetic networks endowed with a ground-truth modular structure and realistic topological features typical of human brain functional connectivity networks, we show that percolation analysis can be applied to identify the optimal sparsification threshold that maximizes information on the networks' community structure. We validate this approach using three different community detection methods widely applied to the analysis of brain connectivity networks: Newman's modularity, InfoMap and Asymptotical Surprise. Importantly, we test the effects of noise and data variability, which are critical factors to determine the optimal threshold. This data-driven method should prove particularly useful in the analysis of the community structure of brain networks in populations characterized by different connectivity strengths, such as patients and controls.

Introduction

Brain connectivity analyses use graph methods, including community detection, to study modular structure. Because sparsification removes noisy weak links but may also discard genuine connections, the paper proposes percolation analysis to choose a threshold for community detection.

connectivity, marking the inception of the “connectomic era” in brain neuroscience. Functional

  • Brain modules are clusters with denser connections among their nodes than to the rest of the network, reflecting functional segregation.This organization is thought to confer robustness and adaptability to brain connectivity networks.Source: connectivity, marking the inception of… · p. 2
  • Sparsification removes weak links that are most affected by experimental noise, but weak connections may also carry genuine modular information.The paper frames threshold choice as balancing noise removal against loss of potentially genuine connections.Source: connectivity, marking the inception of… · pp. 2–3
  • Percolation analysis iteratively removes the weakest edges and tracks the largest connected component, with its breakup marking the percolation threshold.The proposed threshold is intended to maximize information about network modular structure.Source: connectivity, marking the inception of… · p. 3
  • The study compares retrieved and planted community structures with Normalized Mutual Information across sparsification thresholds using three community-detection methods.The methods are Newman’s modularity, InfoMap, and Asymptotical Surprise.Source: connectivity, marking the inception of… · p. 3
  • The authors report that an appropriate sparsification threshold can maximize information about community structure and discuss comparisons across networks with different noise levels and connectivity strengths.Such comparisons are relevant to cross-sectional studies of populations such as patients and healthy controls.Source: connectivity, marking the inception of… · p. 3

Materials and Methods

The authors use synthetic networks to test how well thresholded graphs recover a known modular structure. Two simulation types allow them to examine both network structure and the effects of noise and intersubject variability.

Materials and Methods

  • The simulations test whether thresholding allows community-detection methods to retrieve a predetermined ground-truth modular structure.The networks are intended to support validation for functional connectivity analyses using resting-state fMRI.Source: Materials and Methods · p. 3
  • The authors run LFR network simulations and complex LFR simulations that include intersubject variability and different noise levels.The latter simulation type is used to assess the influence of noise and data variability in a realistic experimental-data mimic.Source: Materials and Methods · p. 3

connectivity networks are composed of modules with heterogeneous size distributions. This structure

The LFR benchmark supplies networks with planted communities and heterogeneous degree and community-size distributions. The authors set mixing parameters and network characteristics to construct the Simulation 1 networks.

connectivity networks are composed of modules with heterogeneous size distributions. This structure

Simulation 1

  • The topological mixing parameter μt sets each node’s fraction of edges to other communities, while μw controls the average balance of internal and external incident edge weights.For each node, the within-community edge fraction is 1−μt and the between-community fraction is μt.Source: Simulation 1 · p. 4
  • Simulation 1 uses N = 600 nodes, average degree ⟨k⟩ = 12, maximum degree maxk = 50, and μt = μw = 0.2.Community sizes range from 5 to 50 nodes, are sampled from a power law with exponent τc = 1, and each mixing-parameter setting is run nine times.Source: Simulation 1 · p. 4

Simulation 2

Simulation 2 generates node time courses from an LFR-derived connectivity matrix, then adds noise and aggregates simulated subjects into group connectivity matrices. Community partitions are compared with the planted structure.

Simulation 2

  • The authors transform the LFR matrix into the nearest positive-definite matrix and use Cholesky decomposition to generate correlated node time courses.Multiplying random time series by the Cholesky factor produces series whose correlations follow the original connectivity matrix.Source: Simulation 2 · p. 5
  • The simulation adds Rician noise and generates multiple subject instances to mimic intersubject variability.The resulting datasets include populations of 20, 40, or 60 subjects and SNR values of 35 or 70.Source: Simulation 2 · pp. 5–6
  • For each simulated subject, pairwise Pearson correlations form an N × N matrix, and individual matrices are Fisher-transformed and averaged into group matrices.The resulting partitions are compared with the planted partition; the flowchart depicts generation and analysis of the synthetic datasets.Source: Simulation 2 · pp. 5–6

Sparsification and Percolation Threshold

Sparsification removes weak edges to reduce graph density, but those links may be noise-sensitive. Percolation analysis identifies a threshold by tracking when the largest connected component begins to break apart.

Sparsification and Percolation Threshold

  • Sparsification removes weaker, noise-sensitive links and reduces graph density, making analysis more computationally tractable.Weak links may also contain structural information, motivating a threshold that balances their removal with preserving network structure.Source: Sparsification and Percolation Threshold · p. 6
  • Percolation analysis applies thresholds at different edge-weight levels and tracks the largest connected component.Figure 3 illustrates the component’s stepwise size changes with threshold and marks the percolation threshold t*.Source: Sparsification and Percolation Threshold · p. 6, Figure 3 · p. 7
  • The percolation threshold is where the largest connected component starts breaking apart as edge-weight thresholds rise.The component is identified in thresholded graphs via breadth-first search.Source: Sparsification and Percolation Threshold · p. 6

Community detection

The study applies community-detection methods based on different principles to brain functional-connectivity networks. These include modularity optimization, random-walk description length, and an information-theoretic Surprise objective.

Community detection

  • Three community-detection methods based on conceptually different principles are applied to the networks.They are Newman’s modularity, InfoMap, and Asymptotical Surprise.Source: Community detection · p. 7
  • Newman’s modularity seeks a partition by maximizing within-cluster edge density against a null model based on random edge rewiring.The method’s optimization is described as typically hierarchical in the supplied passage.Source: Community detection · p. 7
  • InfoMap uses heuristics to minimize the description length of a random walker defined on the network.The study used an implementation available in igraph-0.7.1.Source: Community detection · p. 7
  • Asymptotical Surprise maximizes relative entropy between observed and expected intracluster density under an Erdos-Renyi null model.The approach is described as quasi-resolution-limit free and able to resolve modules of widely different sizes.Source: Community detection · p. 8

Evaluation of retrieved partition

The retrieved community partitions are evaluated against planted partitions using NMI, sensitivity, and specificity. The measures use community overlap and assignment counts to assess similarity and classification performance.

Evaluation of retrieved partition

  • The study used three coefficients to evaluate community-detection methods, comparing extracted communities with the planted community at different threshold levels in its synthetic networks.Sensitivity and Specificity range from 0 to 1, with 1 denoting a perfect match.Source: Evaluation of retrieved partition · pp. 8–9
  • NMI measures similarity between two community structures, ranging from 0 for no information about the planted partition to 1 for corresponding partitions.Its calculation uses overlap counts between communities in the two partitions.Source: Evaluation of retrieved partition · p. 8
  • Sensitivity and specificity assess false-negative and false-positive assignments, respectively, after matching communities by their greatest overlap.The resulting values are calculated for each community and averaged over the partition; 1 denotes a perfect match.Source: Evaluation of retrieved partition · p. 9

Results

In the noiseless LFR-network test, percolation analysis identifies the threshold corresponding to the point where community-detection performance departs from its optimum. The results also show that excessive removal of weak edges is deleterious.

Results

  • The first test has no noise or subject variability, and the community-detection methods are applied directly to the generated LFR matrix.In this scenario, all links correspond to true correlations and no spurious edges are included.Source: Simulation 1 · pp. 9–10
  • NMI between detected and ground-truth partitions is evaluated as a function of threshold for Newman modularity, InfoMap, and Asymptotical Surprise.The reported setting is μt = μw = 0.2, and the gray region shows percolation thresholds obtained across runs.Source: Simulation 1 · p. 9, Figure 4 · p. 9
  • Percolation analysis identifies the threshold corresponding to departure from optimal community-detection performance in noiseless networks.The results show that excessive removal of weak edges is deleterious.Source: Simulation 1 · pp. 9–10
  • The percolation threshold is the minimum threshold value that preserves connectivity and network centrality.Source: Simulation 1 · p. 10

Simulation 2

Across Newman, InfoMap, and Asymptotical Surprise, percolation thresholds fell near maximum NMI, and percolation analysis identified a quasi-optimal sparsification threshold despite noise and data variability.

Simulation 2

  • With increasing threshold, NMI first rose and then fell; the initial rise was interpreted as removing weak links dominated by spurious correlations.Further threshold increases remove structurally relevant correlations and reduce recovery of the planted modular structure.Source: Simulation 2 · p. 10
  • NMI maxima coincided with simultaneously large Sensitivity and Specificity values.Source: Simulation 2 · p. 10
  • Across all three community detection methods, percolation thresholds fell near maximum NMI.Source: Simulation 2 · p. 10
  • Percolation analysis detected a quasi-optimal sparsification threshold for community detection with experimental noise and data variability.Source: Simulation 2 · p. 11

Discussion

The discussion argues that equal-density thresholding can bias comparisons between groups with different connectivity strengths. It presents network-specific percolation thresholding as a way to maximize information about community membership.

Discussion

  • Equal-density graphs can retain more weak, potentially spurious links in weaker-connectivity groups while excluding important links in stronger-connectivity groups.Source: Discussion · p. 12
  • Such imbalances can make group topologies appear more random, so observed differences may reflect noise levels rather than genuine topological differences.Source: Discussion · p. 12
  • Community membership depends on the local balance of within-module and between-module edges, not overall edge density.Source: Discussion · p. 12
  • The optimal sparsification threshold is network-specific, and percolation-based independent thresholding is proposed to maximize information about group memberships.Source: Discussion · p. 12

Conclusion

In synthetic networks with brain-like topology, the percolation threshold corresponds to maximum information about planted modular structure, including under noise and intersubject variability. The findings support a data-driven basis for identifying an optimal sparsification threshold.

Conclusion

  • The work explores percolation analysis, grounded in statistical physics, for determining the sparsification threshold.Source: Conclusion · p. 12
  • The study tests threshold selection in synthetic networks with ground-truth modular structure and topological features akin to real-world brain connectivity graphs.Source: Conclusion · p. 12
  • The percolation threshold—the highest threshold preserving the giant component—maximizes information on planted modules across algorithms despite noise and intersubject variability.The authors describe this threshold as balancing the loss of genuine edges against spurious correlations introduced by noise.Source: Conclusion · pp. 12–13
  • The authors conclude that their findings provide evidence for an optimal sparsification threshold and a theoretical basis for its identification using a data-driven method.Source: Conclusion · p. 13

Related papers

Loading 1705.06481v1…