A hands-on tutorial on network and topological neuroscience

The following Python 3 packages are necessary to perform the computations presented below. The accompanying Jupyter Notebook can be found on GitHub (Table 1) or Zenodo (Centeno and Santos 2021).

The basic unit on which graph theory and TDA are applied in the context of rsfMRI in our work is the adjacency or functional connectivity matrix (Fig. 1g), which presents the connections between all vertices in the network (Bassett and Sporns 2017; Fornito et al. 2016; Sporns 2018; Sporns et al. 2000). Typically, rsfMRI matrices are symmetric and do not specify the direction of connectivity (i.e., activity in area A drives activity in area B), thus yielding undirected networks (Fig. 1b and f). In contrast, non-symmetric matrixes would produce directed networks.

Before calculating any metrics on such matrices, several crucial factors must be considered when dealing with connectivity data (Jalili 2016; Hallquist and Hillary 2018). One critical decision is whether one wants to keep the information about edge weights. When the edges’ weights (e.g., correlation values in rsfMRI connectivity) are maintained, the network will be weighted (Fig. 1d and f). Another approach is to use an arbitrary threshold or density, e.g., only keep and binarise the 20% strongest connections (Fig. 1a and b). There is currently no gold standard for the weighting issue in rsfMRI matrices (Fornito et al. 2016; Jalili 2016) and may also be dependent on the dataset or proposed analysis (van den Heuvel et al. 2017). Brain network data are often analysed using a specific thresholding procedure (or criteria). These thresholded brain networks often display ubiquitous signatures of the brain as a complex system, such as skewed degree distributions, clustering, Giant components, small wordness, and short average path lengths, to name a few (Eguíluz et al. 2005). However, some of these properties, considered signatures of complex networks, are observed, even when one threshold normally distributed data (Cantwell et al. (2020). Yet, some brain network properties are not robust towards changes in the threshold (Garrison et al. 2015). Those results raised the awareness for using methods of network analysis that are independent of thresholding, such as minimum spanning trees (van Dellen et al. 2018; Stam et al. 2014) or topological data analysis (Phinyomark et al. 2017), as we will discuss below. Please see Chapter 11 in Fornito et al. (2016) and van Wijk et al. (2010); Simpson et al. (2013) for a more in-depth discussion on the issue of matrix thresholding and statistical connectomics.

Another relevant discussion about rsfMRI matrices is the interpretation of negative weights or anticorrelations. The debate of what such negative correlations mean in neurophysiology is still going on (Zhan et al. 2017). Studies have suggested that they could be considered artefacts introduced by global signal regression or pre-processing methods or simply by large phase differences in synchronised signals between brain areas (Chen et al. 2011; Murphy et al. 2009). Nevertheless, a few authors have suggested that anticorrelations might carry biological meaning underlying long-range synchronisation and that in diseased states, alterations in these negative correlations could indicate network reorganisation (Chen et al. 2011; Zhan et al. 2017). Negative weights can be absolutised to keep the potential biological information they may carry. If one decides to discard them, it is crucial to remember that some physiological information might be lost (Chen et al. 2011; Zhan et al. 2017; Fornito et al. 2016; Hallquist and Hillary 2018).

In this tutorial, we will use an undirected, absolutised (positively) weighted matrix. In our Jupyter notebook tutorial on GitHub (Centeno and Santos 2021), we provide an example matrix which is an average of all connectivity matrices available in our repository.

To follow the steps below, we assume that rsfMRI was already pre-processed and converted to a matrix according to some atlas. Steps and explanations on data pre-processing and atlas choices are beyond the scope of this paper; please see Strother (2006) or the NI-edu course materials (Table 1) for further information. Details on our Jupyter Notebook’s dataset pre-processing can be found in Brown et al. (2012); Biswal et al. (2010).

When working with fMRI brain network data, it is helpful to generate some plots (e.g., the heatmaps for matrix visualisation and distribution plots of edge weights) to facilitate data exploration, comprehension, and flag potential artefacts. In brain networks, we expect primarily weak edges and a smaller proportion of strong ones. When plotted as a probability density of log10, we expect the weight distribution to have a Gaussian-like form Fornito et al. (2016).

Here, we will cover the most commonly used graph metrics in network neuroscience (see Fig. 2), also in line with Fornito et al. (2016). First, we need to create a graph object using the package NetworkX (Hagberg et al. 2008) and remove the self-loops (i.e., the connectivity matrix’s diagonal).

Vertex degree quantifies the total number of vertex connections in an undirected binary network (Fornito et al. 2016). In an undirected weighted network like our rsfMRI matrix, the vertex degree is analogous to the vertex strength (i.e., the sum of all edges of a vertex) and equivalent to its degree centrality. This metric is one of the most fundamental metrics in network analysis and is a useful summary of how densely individual vertices are connected. It can be computed as the sum of edge weights of the neighbours of vertex \(i \) as follows:where \({w}_{ij}\) is the weight of the edge linking vertices \(i\) and \(j\).

By removing the argument weight from the function, one can compute the degree of binarised networks where all edges are either 0 or 1 (useful if working with a sparse/not fully connected matrix). This change will give the vertex degree by calculating the number of edges adjacent to the vertex. One can also remove the specified vertex to estimate the degree/strength of all vertices. The degree/strength distribution allows us to scope the general network organisation in a single shot by displaying whether the network contains a few highly connected vertices, i.e., hubs (Hallquist and Hillary 2018).

where \(\mathrm{V}\) is a set of vertices, \(d\left(i,j\right)\) is the shortest path between vertices \(i\) and \(j\), and \(N\) is the number of vertices in the network.

The clustering coefficient assesses the tendency for any two neighbours of a vertex to be directly connected (or more strongly connected in the weighted case) to each other and can also be termed cliquishness (Hallquist and Hillary 2018; Watts and Strogatz 1998). This metric is also used to compute the small-worldness coefficient (ratio between the characteristic path length and the clustering coefficient relative to random networks) (Watts and Strogatz 1998). The formula can be defined as follows:where \({s}_{i}\) is the degree/strength of vertex\(i\), and the edge weights are normalised by the maximum weight in the network, such that \({\widehat{w}}_{ij} =\frac{{w}_{ij}}{\mathrm{max}\left(w\right)}\).

where \(V\) is a set of vertices, \({\sigma }_{ij}\) is the total number of shortest paths between \(i\) and \(j\), and \({\sigma }_{ij}\left(h\right)\) is the number of those paths that pass through \(h\). For weighted graphs, edges must be greater than zero, and the metric considers the sum of the weights (Fornito et al. 2016). Again, it is necessary to use the distance when using this shortest path-based metric. This formula can also be normalised by putting \(\frac{2}{\left(N-1\right)\left(N-1\right)}\) in front of the sum (N being the number of vertices).

The minimum spanning tree is the backbone of a network, i.e., the minimum set of edges necessary to ensure that paths exist between all vertices without forming cycles (Stam et al. 2014; van Dellen et al. 2018). A few main algorithms are used to build the spanning tree, with Kruskal’s algorithm being implemented in NetworkX (Kruskal 1956). Briefly, this algorithm ranks the distances between vertices, adds the ones with the smallest distance first, and at each added edge, it checks if cycles are formed or not. The algorithm will not keep an edge that results in the formation of a cycle.

Modularity states how divisible a network is into different modules (or communities). The identification of the modules is performed by the community detection algorithm (Fornito et al. 2016; Meunier et al. 2010; Bullmore and Sporns 2009). Here, we will use the Louvain algorithm (Blondel et al. 2008) as recommended by Fornito et al. (2016). It works in a two-step iterative manner, first looking for communities by optimising modularity locally and then concatenating vertices that belong to the same module (Blondel et al. 2008).

In this section, we will use TDA on our rsfMRI adjacency matrices. TDA can identify different network characteristics by addressing the high-order structure of a network beyond pairwise connections as used in graph theory (Carlsson 2020; Battiston et al. 2020; Kartun-Giles and Bianconi 2019). TDA generally uses topology and geometry methods to study the shape of the data (Carlsson 2009). A core feature of TDA is the ability to provide robust results compared with alternative methods, even if the data are noisy (Blevins and Bassett 2020; Expert et al. 2019). In this context, it is essential to frame the difference between noise and systematic error for applications of TDA properly. Noise is caused by factors that affect the measurement of the variable of interest entirely at random. Systematic errors, however, are not determined exclusively by chance. They are introduced by a factor that systematically influences the variable of interest measurement (e.g. by an inaccuracy involving either the observation or measurement process). In rsfMRI (and other brain-related measures), both types of noise can be present.

One of the benefits of using TDA in network neuroscience is the possibility of finding global properties of a network that are preserved regardless of the way we represent the network (Petri et al. 2014), as we will illustrate below. Those properties are the so-called topological invariants.

We will cover a few fundamental TDA concepts: filtration, simplicial complexes, Euler characteristic, phase transitions, Betti numbers, curvature, and persistent homology. A summary can be found in Fig. 3.

As indicated in the earlier section on graph theory, there is no consensus on the necessity or level of thresholding performed on rsfMRI-based adjacency matrices. However, TDA overcomes this problem by investigating functional connectivity over all possible thresholds in a network. This process of investigating network properties looking for all possible thresholds instead of choosing a fixed one is called filtration (Fig. 3b and Supplementary Material 1). It consists of changing the threshold, e.g., the density d of the network, from \(0 \le d\le 1\). This yields a nested sequence of networks, in which increasing d leads to a more densely connected network. Notice that the notion of filtration is not only used in high order interactions but has also been applied in pair wise, graph-theoretical work (Wang et al. 2018; Gracia-Tabuenca et al. 2020).

In TDA, we consider that the network as a multidimensional structure called the simplicial complex. Such a network is not only made up of the set of vertices (0-simplex) and edges (1-simplex) but also of triangles (2-simplex), tetrahedrons (3-simplex), and higher k-dimensional structures (Fig. 3a). In short, a k-simplex is an object in k-dimensions and, in our work, is formed by a subset of k+1 vertices of the network (Fig. 4).

We can encode a network into a simplicial complex in several ways (Lambiotte et al. 2019; Edelsbrunner and Harer 2010; Maletić et al. 2008). However, here, we will focus on building a simplicial complex only from the brain network’s cliques, i.e., we will create the so-called clique complex of a brain network. In a network, a k-clique is a subset of the network with \(k\) all-to-all connected nodes. 0-clique corresponds to the empty set, 1-cliques correspond to nodes, 2-cliques to links, 3-cliques to triangles, and so on. In the clique complex, each k + 1 clique is associated with a k-simplex. This choice for creating simplexes from cliques has the advantage of using pairwise signal processing to create a simplicial complex from brain networks, such as in Giusti et al. (2015). It is essential to mention that other strategies to build simplicial complexes beyond pairwise signal processing are still under development, such as applications using multivariate information theory together with tools from algebraic topology (Baudot 2019a, b; Barbarossa and Sardellitti 2020; Baudot et al. 2019; Baudot and Bennequin 2015; Rosas et al. 2019; Gatica et al. 2020).

Our Jupyter Notebook provides the code to visualise the clique complex developed in (Santos et al. 2019). To create the 3-D plots, we used mesh algorithms available in Plotly (Inc. 2015), together with a mesh surface of the entire brain available in Fan et al. (2016); Bakker et al. (2015). In Fig. 5, we display an example of 3-D visualisation of 3-cliques in the 1000 Functional Connectomes data. When we increase the filtration density d, we obtain more connections, and more 3-cliques arise. In Fig. 5, only 3-cliques are shown; however, the same can be done for higher-dimensional cliques like a tetrahedron, et cetera. In Supplementary Material 1, we offer filtration in a functional brain network up to 4-cliques. In the Jupyter Notebook, we can also visualise the clique complex at arbitrary sizes, up to computational limits. The computation is not shown here as code blocks due to its size and complexity (see the Jupyter Notebook).

The Euler characteristic is one example of topological invariants: the network properties that do not depend on a specific graph representation. We first introduce the Euler characteristic for polyhedra, as illustrated in Fig. 6. Later, we translate this concept to brain networks. In 3-D convex polyhedra (for example, a cube, a tetrahedron, et cetera, see Fig 6), the Euler characteristic is defined as the numbers of vertices minus edges plus faces of the considered polyhedra. For convex polyhedra without cavities (holes in its shape), which are isomorphous to the sphere, the Euler characteristic is always two, as you can see in Fig. 6. If we take the cube and make a cavity, the Euler drops to zero as it is in the torus. If we make two cavities in a polyhedral (as in the bitorus), the Euler drops to minus two (Fig. 7). We can understand that the Euler characteristic tells us something about a polyhedron’s topology and its analogous surface. In other words, if we have a surface and we make a discrete representation of it (e.g., a surface triangulation), its Euler characteristic will always be the same, regardless of the way we do it.

We can now generalise the definition of Euler characteristic to simplicial complex in any dimension. Thus, the high dimensional version of the Euler characteristic is expressed by the alternate sum of the numbers \({Cl}_{k }\left(d\right)\) of the k-cliques (which are (k-1)-simplexes) present in the network’s simplicial complex for a given value of the density threshold d.

Note that the clique algorithm, the primary function used in our code (euler—Supplementary Material 2), is an NP-complete problem, which is computationally expensive for large and/or dense networks, regardless of how you implement it (Pardalos and Xue 1994). An alternative is to fix an upper bound for the cliques’ size (Pardalos and Xue 1994; Gillis 2018). Therefore, the second function (euler_k—Supplementary Material 2) allows the user to constrain the maximum size of the cliques we are looking for. This means that we are fixing the dimension k of our simplicial complex and ignoring simplexes of dimension greater than k.

Phase transitions can provide insight into the proprieties of a ‘material’. For example, water is known for becoming steam at 100 °C. Similarly, by using TDA when comparing a patient and healthy population, one could identify these populations’ properties by studying each group’s topological phase transition profile. This strategy has already been applied for investigating group differences between controls and glioma brain networks (Santos et al. 2019) and typically developing children and children with attention-deficit/hyperactivity disorder (Gracia-Tabuenca et al. 2020). In other fields, topological phase transitions were also investigated in the S. cerevisiae and C. elegans protein interaction networks, reionisation processes, and evolving coauthorship networks (Amorim et al. 2019; Giri and Mellema 2021; Lee et al. 2021).

To investigate topological phase transitions in brain networks, we first need to visualise the Euler entropy (Fig 3 in Santos et al. 2017):

\({S}_{\upchi }\)= ln|\(\upchi \) |.when \(\upchi \) = 0 for a given value of the density of the network, the Euler entropy is singular, \({S}_{\upchi } \to \infty \). Under specific hypotheses, a topological phase transition in a complex network occurs when the Euler characteristic is null (Santos et al. 2019). This statement finds support in the behaviour of \({S}_{\upchi }\) at the thermodynamic phase transitions across various physical systems (Santos et al. 2017). In network theory, the Giant component transition is associated with network changes, from smaller connected clusters to the emergence of Giant ones (Erdős 1959). Theoretically, topological phase transitions are related to the extension of the Giant component transition for simplicial complexes (Linial and Peled 2016). Based on numerical simulations, it was also conjectured that the longest cycle is born in the phase transition vicinity (Bobrowski and Skraba 2020; Speidel et al. 2018). Phase transitions can also be visualised in Birth/Death plots (Fig. 3e) which will be discussed later in the Persistent Homology section.

Another set of topological invariants are the Betti numbers (\(\beta \)). Given that a simplicial complex is a high-dimensional structure, \({\beta }_{k}\) counts the number of k-dimensional holes in the simplicial complex. These are topological invariants that correspond, for each \(k\ge \) 0, to the number of linearly independent k-dimensional holes in the simplicial complex (Zomorodian 2005).

In Fig. 8, we show the representation of the k-dimensional holes. We give one example for each dimension. In a simplicial complex, there can be many of these k-holes and counting them provide the Betti number \(\beta \), e.g., if \({\beta }_{2}\) is equal to five, there are 5 two-dimensional holes.

Notice that for higher k or dense simplicial complexes, the calculation of the \(\beta \) becomes computationally expensive.

There are ways to estimate the \(\beta \) of a simplicial complex without calculating it directly. It is known that the \(\beta \) relate to Euler characteristics and phase transitions. The Euler characteristics of a simplicial complex can also be computed using the \(\beta \) via the following formula (Edelsbrunner and Harer 2010):where \(k\_\mathrm{max}\) is the maximum dimension that we are computing the cycles.

Furthermore, topological phase transitions are also defined as the \(\beta \) of a simplicial complex (Bobrowski and Kahle 2018). We know that \({\upbeta }_{0}\) counts the number of the connected components of a simplicial complex. Suppose we compute the Betti curves as a function of probability in stochastic models. In that case, each Betti curve passes through two distinct phases in a narrow interval: one when it first emerges and the other when it vanishes (Linial and Peled 2016). That means that, under similar assumptions as in theoretical models, if the \(\beta \) distribution is unimodal, increasing the density of edges of a brain network will lead to the appearance of \(\beta \) of a higher order. In contrast, smaller Betti numbers will disappear at the vicinity of a topological phase transition.

In Fig. 9, we illustrate this property on simplicial complexes obtained from random networks. As the probability increases and so the density of the network is higher, we find a sequence of dominant \({\beta }_{k}\) starting from k = 0, that change (i.e., k is incremented by one unity) every time a topological phase transition occurs. While the singularities of the Euler entropy \({S}_{\upchi }\) determine the transitions’ location, the crossover of the \(\beta \) characterises which kind of multidimensional hole prevails in each topological phase of the filtration.

Curvature is a TDA metric that can link the global network properties described above to local features (Weber et al. 2017; Farooq et al. 2019; Santos et al. 2019). When working with brain network data, this will allow us to compute topological invariants for the whole-brain set of vertices and understand the contribution of specific individual nodal, or subnetwork, geometric proprieties to global properties of the brain network.

Several approaches to defining a curvature for networks are available (Najman et al. 2017; Weber et al. 2017), including some already used in neuroscientific investigations (Santos et al. 2019). We will illustrate the curvature approach linked to topological phase transitions, previously introduced for complex systems in (Farooq et al. 2019; Najman et al. 2017; Wu et al. 2015).

To compute the curvature (Supplementary Material 4), filtration is used to calculate the clique participation rank (i.e., the number of \(k\)-cliques in which a vertex \(i\) participates for density d) (Sizemore et al. 2018), which we denote here by \({Cl}_{ik }\left(d\right)\). The curvature of the vertex based on the participation rank is then defined as follows:where \({Cl}_{ik}\) = 1 since each vertex \(i\) participates in a single 1-clique (the vertex itself), and \({k}_{max}\) the maximum number of vertices that are all-to-all connected in the network.

To link this nodal curvature to the network’s global properties, we use the Gauss-Bonnet theorem for networks, through which one can connect a local curvature of a network and its Euler characteristic. Conversely, by summing up all the curvatures of the network across different thresholds, one can reach the alternate sum of the numbers \(C{l}_{k}\) of k-cliques (a subgraph with k all-to-all connected vertices) present in the simplicial complex of the network for a given density threshold d ∈ [0, 1], according to the following equation:

By doing so, we also write the Euler characteristics as a sum of the curvature of all network vertices, i.e.,

We illustrate the curvature distribution for a functional brain network for densities before and after the transition in Fig. 10.

Homology is a topology branch that investigates objects’ shapes by studying their holes (or cycles). Persistent homology tracks the emergence of cycles across the evolving simplicial complexes during filtration, allowing us to recognise whether there were homology classes that “persisted” for many filtrations (time here meaning the threshold gap between the birth and death of a cycle) (Curto 2017; Giusti et al. 2016). Importantly, to compute persistent homology, we need to work with a distance matrix, the first step in the code below. We can then calculate the simplicial complex’s persistence and plot it as a barcode or a persistence diagram (Fig. 3c and e). Here we used the Gudhi package for the implementation of those steps (Maria et al. 2014). The topological phase transitions in complex networks (Amorim et al. 2019; Santos et al. 2019) can also be identified between the changes in the dimensionality of the birth/death graphs mentioned above (Fig. 3e).