Glossary of terms

Adjacent

Two nodes within a graph are said to be adjacent if there is an edge between them.

Adjacency matrix, \(A\)

A matrix representation of a network. \(A_{ij} = A_{ji} = 1\) when node \(i\) is adjacent to node \(j\) (i.e., when there is an edge between \(i\) and \(j\)), and \(A_{ij} = A_{ji} = 0\) when they are not adjacent (i.e., no such edge exists). Note that the adjacency matrices are symmetric.

Affinity matrix, \(K\)

Matrix capturing non-geometric factors influencing the likelihood that nodes form an edge between them. Computed using a generative rule.

Affinity transform, \(k\)

Parametrised transform of the affinity matrix which effects the wiring probabilities. When the affinity relationship type is powerlaw, the affinity transform is \(k_{ij} = K_{ij}^\gamma\); when the affinity relationship type is exponential, the affinity transform is \(k_{ij} = \exp( \gamma K_{ij} )\). The affinity transform is multiplied by the distance transform and the heterochronous transform to obtain (unnormalised) wiring probabilities.

Alpha, \(\alpha\)

Parameter of the weighted GNM. Controls the size of the update on the weights of the network at each weighted update step; equivalent to the learning rate on the weight optimisation criteron (i.e., the loss), \(L\). The update performed at each step is \(W_{ij} \gets W_{ij} - \alpha \frac{\partial L}{\partial W_{ij}}\).

Betweenness Centrality

A way of measuring the importance of a node for communication flow through a network. For binary networks, the betweenness centrality of a node \(a\) is computed by first looking at all other pairs of nodes in the network which are connected to one another, \(b\) and \(c\). For each pair of other connected nodes, \(b\) and \(c\), we compute the fraction of shortest paths between \(b\) and \(c\) which pass through \(a\); for example, if all shortest paths between \(b\) and \(c\) go through \(a\) this is \(1\), and if none of the shortest paths go through \(a\) then this is \(0\). We then sum this fraction over all these pairs to compute the betweenness centrality of \(a\).

Binary Generative Network Model

The standard generative network model. This model generates graphs representing connectivity between brain regions by iteratively adding edges. At each iteration, the (unnormalised) wiring probability is computed by multiplying the distance transform and the affinity transform. We then sample from these wiring probabilities to choose which edge to add.

Characteristic path length

The average shortest path length within a graph. To compute characteristic path length, we consider all pairs of nodes within the graph \(a\), \(b\), and compute the shortest path length between \(a\) and \(b\). We then average over these pairs to get the characteristic path length of the graph.

Clustering coefficient

Measure of local clustering in a network. The clustering coefficient of a node \(a\) is equal to the proportion of neighbours of \(a\) which are neighbours with each other. The clustering coefficient of a network is the average clustering coefficient of all the nodes in that network.

Communicability

A measure of the total influence that one node has on another. Given a weight matrix \(W\), to compute the communicability we begin by computing normalised weights \(\hat{W}\) via \(\hat{W}_{ij} = \frac{W_{ij}}{\sqrt{s_i s_j}}\) where \(s_i\) and \(s_j\) are the node strengths of \(i\) and \(j\) respectively. The communicability is then the matrix exponential of \(\hat{W}\), \(C = \exp(\hat{W}) = I + \frac{1}{1!} \hat{W} + \frac{1}{2!} \hat{W}^2 + \frac{1}{3!} \hat{W}^3 + \dots\).

Connected

Two nodes within a network are said to be connected if there is any path which joins them, i.e., any sequence of nodes which begins with one node and ends with the other, such that each node in the sequence is adjacent to both the nodes before and after. For example, if \(a\) and \(b\) are neighbours and \(b\) and \(c\) are neighbours, then \(a\) and \(c\) are connected via the path \(a,b,c\).

Correlation

Take a pair of networks with the same set of \(N\) nodes, but different edges. Consider some nodal property, such as clustering coefficient or betweenness centrality. Then if we denote that property for node \(i\) in the first network by \(X_i\), and for node \(i\) in the second network by \(Y_i\), the correlation of that graph property between the networks is \(\(\rho = \frac{ \sum_i (X_i - \bar{X})(Y_i - \bar{Y}) }{ \sqrt{ ( \sum_i (X_i - \bar{X})^2 )( \sum_i (Y_i - \bar{Y})^2 ) } },\)\) where \(\bar{X} = \frac{1}{N} \sum_i X_i\) and \(\bar{Y} = \frac{1}{N} \sum_i Y_i\) are the average nodal properties for each of the two networks.

Cumulative distribution function

For a graph property, the cumulative distribution function at a point is the fraction of values of that graph property less than that point.

Degree

The number of edges attached to a node; equal to the number of neighbours the node has.

Density

The fraction of possible edges in a network which are actually present. Equal to the number of edges divided by \(N(N-1)/2\).

Distance Matrix, \(D\)

Matrix storing the physical distances between nodes in the network. \(D_{ij}\) gives the distance in space between nodes \(i\) and \(j\).

Distance transform, \(d\)

Parametrised transform of the distance matrix which effects the wiring probabilities. When the distance relationship type is powerlaw, the distance transform is \(d_{ij} = D_{ij}^\eta\); when the distance relationship type is exponential, the distance transform is \(d_{ij} = \exp( \eta D_{ij} )\). The distance transform is multiplied by the affinity transform to obtain (unnormalised) wiring probabilities.

Distribution

The collection of values taken by a graph property across the network. For example, the distribution of clustering coefficients is the collection of clustering coefficient values of each node within the network; the edge length distribution is the collection of edge lengths of each edge within the network.

Edge

Direct connection between two nodes in a graph.

Edge length

The distance between nodes connected by a single edge. For example, if \(i\) and \(j\) are neighbours, the edge length between nodes \(i\) and \(j\) is \(D_{ij}\), where \(D\) is the distance matrix. Note that edge length depends on the physical position of nodes in space, and not (only) on the topological properties of the graph.

Eta, \(\eta\)

A parameter of the binary GNM. \(\eta\) controls the influence of the distance matrix \(D_{ij}\) on wiring probabilities. When the relationship type is powerlaw, the distance transform is \(d_{ij} = D_{ij}^\eta\); when the relationship type is exponential, the distance transform is \(d_{ij} = \exp( \eta D_{ij} )\).

Evaluation criterion

Method of measuring the similarity between two adjacency matrices or two weight matrices. For example, the maximum of a KS distance between graph measures for each of the graphs.

Exponential relationship type

Method of determining the distance, affinity, and heterochronicity transforms from their respective matrices. Under the exponential relationship type, the distance transform is \(d_{ij} = \exp( \eta D_{ij} )\), the affinity transform is \(k_{ij} = \exp( \gamma K_{ij} )\), and the heterochronicity transform is \(h_{ij} = \exp( \lambda H_{ij} )\).

Functional connectivity

Connectivity between brain regions determined by the statistical relationships between the activities in the different regions. cf. structural connectivity

Gamma, \(\gamma\)

A parameter of the binary GNM. \(\gamma\) controls the influence of the affinity matrix \(K_{ij}\) on wiring probabilities. When the affinity relationship type is powerlaw, the affinity transform is \(K_{ij}^\gamma\); when the affinity relationship type is exponential, the affinity transform is \(\exp( \gamma K_{ij} )\).

Generative rule

Method for computing the affinity matrix \(K\) from the adjacency matrix \(A\).

Graph

Synonym for network. A set of nodes with connections between them. Graphs can be either weighted or unweighted. Unweighted graphs are described by an adjacency matrix, \(A\), while weighted graphs are described via a weight matrix, \(W\).

Heterochronicity

The influence of time on wiring probabilities.

Heterochronicity Matrix, \(H\)

A matrix specifying how time influences wiring probabilities. If \(H_{ij}\) is large on a particular time-step, it increases the probability of a connection between nodes \(i\) and \(j\) being made on that time-step, assuming no connection already exists.

Heterochronicity transform, \(h\)

Parametrised transform of the heterochronous matrix which effects the wiring probabilities. When the heterochronous relationship type is powerlaw, the heterochronous transform is \(h_{ij} = H_{ij}^\lambda\); when the heterochronous relationship type is exponential, the heterochronous transform is \(h_{ij} = \exp( \lambda H_{ij} )\). In the heterochronous GNM, the (unnormalised) wiring probabilities are obtained by multiplying not just the distance transform and the affinity transform, but additionally the heterochronous transform.

Heterochronous Generative Network model

Modification of the GNM which allows for heterochronicity in the growth of the network. In the heterochronous GNM, the wiring probabilities depend not just on the distance matrix and the current affinity matrix, but also on a heterochronous matrix which varies from step to step, making the formation of some connections more or less likely on some steps.

Homophily

Any method of computing the affinity matrix which assigns a higher affinity between pairs of nodes which have a similar connection profile. This includes both the Matching Index and Neighbours generative rules.

Kolmogorov-Smirnov (KS) distance

A way of measuring how different two distributions are, by taking the maximum difference between their cumulative distribution functions.

Lambdah, \(\lambda\)

A parameter of the heterochronous binary GNM. \(\lambda\) controls the influence of the heterochronous matrix \(H_{ij}\) on wiring probabilities. When the heterochronous relationship type is powerlaw, the heterochronous transform is \(H_{ij}^\lambda\); when the affinity relationship type is exponential, the affinity transform is \(\exp( \lambda H_{ij} )\).

Loss, \(L\)

Synonym for weight optimisation criterion. For the weighted GNM, an update is performed at each step which performs gradient descent on the loss with learning rate \(\alpha\).

Matching Index

A homophily generative rule in which \(K_{ij}\) is equal to the number of neighbours shared by \(i\) and \(j\), divided by the total number of nodes which are neighbours of either \(i\) or \(j\).

Neighbour

Two nodes in a graph are said to be neighbours if there is an edge between them. In other words, \(i\) and \(j\) are neighbours if and only if \(A_{ij} = 1\).

Neighbours generative rule

A homophily generative rule in which \(K_{ij}\) is equal to the number of neighbours shared by \(i\) and \(j\), i.e., \(K_{ij} = \sum_k A_{ik} A_{jk}\). Under this rule, \(K_{ij}\) is larger the more neighbours \(i\) and \(j\) have in common.

Network

Synonym for graph. A set of nodes with edges between them.

Node

A point within a network. Within a parcellation, each node is a distinct region of the brain.

Node strength, \(s\)

The sum of the weights of the edges attached to a node. The node strength of node \(i\) is given by \(\sum_j W_{ij}\). When the weight matrix is binary, the node strength is equal to the degree of a node.

Omega, \(\omega\)

A parameter of the weighted GNM, used to parametrise various loss functions for the weight optimisation criteria.

(weight) optimisation criterion, \(L\)

Loss function used to update the weight matrix in the weighted GNM. At each update step for the weighted GNM, the weights are updated by performing gradient descent on the weight optimisation criterion \(L\) with learning rates \(\alpha\), \(W_{ij} \gets W_{ij} - \alpha \frac{\partial L}{\partial W_{ij}}\).

Parcellation

A division of part of the brain, typically the cortical surface, into distinct nodes. Parcellations can be performed on the basis of the connectivity profile between regions or the cytoarchitectural properties of each region.

Path

A sequence of nodes in a graph such that each node is connected to the nodes before and after in the sequence, and no node is repeated. For example, \(a,b,c\) is a path if \(a\) and \(b\) are connected and \(b\) and \(c\) are connected. Paths can also be described by the sequence of edges traversed, e.g., \((a,b),(b,c)\).

Path length

The number of edges found in a path. For example, if \(a\) and \(b\) are neighbours then the path \(a,b\) has length \(1\); if \(a\) and \(b\) are neighbours and \(b\) and \(c\) are neighbours, then \(a,b,c\) has length \(2\), etc. Note that path length is a purely topological property, in the sense that it is agnostic to the physical position of nodes in space or the physical distance between them; it is computed solely on the basis of the presence or absence of edges between nodes.

Powerlaw relationship type

Method of determining the distance, affinity, and heterochronicity transforms from their respective matrices. Under the powerlaw relationship, the distance transform is \(d_{ij} = D^{\eta}_{ij}\), the affinity transform is \(k_{ij} = K_{ij}^{\gamma}\), and the heterochronicity transform is \(h_{ij} = H_{ij}^{\lambda}\).

Shortest path

For any two nodes, a shortest path between those nodes is a path which has smallest path length. For example, if \(a\), \(b\), and \(c\) are all connected to one another, then both \(a,c\) and \(a,b,c\) are paths between \(a\) and \(c\), but only \(a,c\) would be a shortest path. Note that there can be multiple shortest paths between nodes. If two nodes are unconnected, then the length of the shortest path between them is taken to be infinite.

Small worldness

A network has high small worldness when it displays high clustering but low characteristic path length. To compute the small worldness of a binary network, we compute the (average) clustering coefficient of the network, \(C\), and the characteristic path length, \(\ell\). We then construct a "control" network which has the same number of nodes and edges, but the edges are placed at random, and compute the same quantities for the control network, \(C_{\rm control}, \ell_{\rm control}\). The small worldness of the network is then \(\frac{C/C_{\rm control}}{\ell/\ell_{\rm control}}\).

Structural connectivity

The pattern of connections made between regions of the brain by white matter tracts. cf. functional connectivity.

Symmetric

A matrix \(M\) is symmetric when \(M_{ij} = M_{ji}\) for all pairs of nodes \(i\) and \(j\). Distance, affinity, and heterochronicity matrices (and their transforms) are all symmetric matrices.

Topology

Topological properties of a graph are those properties that depend only on the pattern of connectivity within the graph, but not on the location of nodes within physical space. cf. topographical properties.

Topography

Topographical properties of a graph are those properties which depend on the physical position of nodes within space and the spatial relationships between them. cf. topological properties.

Transform

A parametrised modification of an original matrix, denoted by a lowercase. For example, the exponential transform of the distance matrix, \(D_{ij}\), is \(d_{ij} = \exp( \eta D_{ij})\), with \(\eta\) parametrising the transform.

Vertex

Synonym for node.

Weighted Generative Network Model

Variant of the Generative Network Model which generates weighted networks.

Weight matrix, \(W\)

Matrix representing a weighted graph. \(W_{ij}\) gives the strength of the connection between \(i\) and \(j\), with \(W_{ij} = 0\) if no connection is present between \(i\) and \(j\).

Wiring probabilities, \(P_{ij}\)

The probability that, at a particular time step of the binary GNM, two nodes connect to one another. Wiring probabilities are obtained by first multiplying the distance and affinity transforms to obtain unnormalised probabilities, \(\tilde{P}_{ij} = d_{ij} \times k_{ij}\). We then set the probability of existing connections and self-connections to zero: \(\tilde{P}_{ij} \gets 0\) if \(A_{ij} = 1\), and \(\tilde{P}_{ii} \gets 0\). The unnormalised probabilities are then divided by their sum to get a probability distribution over all potential new connections, \(P_{ij} = \frac{ \tilde{P}_{ij} }{ \sum_{ab} \tilde{P}_{ab} }\).