Graph theory methods: applications in brain networks

Abstract

Network neuroscience is a thriving and rapidly expanding field. Empirical data on brain networks, from molecular to behavioral scales, are ever increasing in size and complexity. These developments lead to a strong demand for appropriate tools and methods that model and analyze brain network data, such as those provided by graph theory. This brief review surveys some of the most commonly used and neurobiologically insightful graph measures and techniques. Among these, the detection of network communities or modules, and the identification of central network elements that facilitate communication and signal transfer, are particularly salient. A number of emerging trends are the growing use of generative models, dynamic (time-varying) and multilayer networks, as well as the application of algebraic topology. Overall, graph theory methods are centrally important to understanding the architecture, development, and evolution of brain networks.

Keywords: connectome; functional MRI; graph theory; neuroanatomy; neuroimaging.

Figures

Figure 1.. Modularity. (A) Schematic network plot showing a set of nodes and edges interconnected to form two relatively distinct modules (communities). Note that the two modules are linked via a single hub node (black) that maintains two bridges between the two modules. Panels (B) to (E) use a 77-node data set from reference 74, representing the 77 areas and directed weighted projections of the rat cerebral cortex. (B) The plot at the top illustrates the varying number of modules as the value of the resolution parameter is increased from 0.1 to 4.0. The number of detected modules increases from 1 to 22 within this range. (C) The matrix plot represents the variation of information between all detected partitions within the range of the resolution parameter plotted above. Dark blue corresponds to a variation of information (distance) of zero, ie, identity. The region around gamma=0.7 is the most homogeneous region within the range. (D) The rat cerebral cortex connection matrix (weights displayed on log-scale), reordered by module assignment for gamma=0.7. The three modules are indicated with white boundaries. (E) The multiscale co-assignment matrix, computed using the method described in ref. 37. Co-assignment varies between 1 (node pair in same module at all scales) to 0 (node pair never co-assigned at any scale). Tree plot at the bottom shows all hierarchically clustered solutions, with the top one corresponding to the same three modules shown in panel (C). Within each of the three modules, additional modular structure is detected.

Figure 2.. Paths and rich club organization. (A) Schematic network plot illustrating an optimally short path (length three steps) that links the two nodes shown in black; intermediate nodes are shown in gray. (B) Left: Using the rat cerebral cortex data set from ref 74, this plot shows the density of subgraphs, compared with a degree-sequence preserving null model, with subgraphs increasing in size from 1 to N (N=77) and with nodes arranged by total degree. Subgraph of size 1 comprises the single node with highest degree, subgraph size 2 the one comprising the two highest degree nodes, and so forth. Red data points indicate subgraphs for which the density is significantly above that of the null model (P<0.001, false discovery rate-corrected). Middle: Rat cerebral cortex connection matrix, with node arranged by total degree (highest degree node in the top row and left-most column). Note dense (nearly full) connectivity among the top 15 high-degree nodes (white lines). Right: Edge betweenness displayed in the same node ordering as middle panel. Note that there are numerous edges with high edge betweenness in upper left section of the matrix. These edges link high-degree nodes and they also participate in a large number of shortest paths across the network.