Binary Generative Network Models

Historical Background

[ Leave blank for now ]

The Binary Generative Network Model

The binary generative network model (henceforth, GNM) is a model which, through the iteration addition of edge to a network, is able to generate networks which have significant topological similarity to real brain networks. The nodes in the GNM represent individual brain regions within a parcellation. The pattern of connectivity between these regions is represented by an adjacency matrix, $A_{ij}$.

The core of the GNM is very simple. The model begins with a seed adjacency matrix, $A_{ij}$, which can be either empty (zeros everywhere) or already contain some connections. At each step of the algorithm, we compute a likelihood that each currently unconnected pair of nodes will form a connection. We then sample a pair of nodes randomly according to this distribution. An edge is then added between the sampled nodes. This cycle then repeats, with edges being added one-by-one until one-by-one until a desired total number of connections is reached. Importantly, at each step the current pattern of connectivity present within the network influences the likelihood of connections between nodes, allowing for complex feedback loops.

Within a GNM, the likelihood of a connection forming at each step depends on both the distance and affinity between the nodes. Distance captures spatial constraints on wiring, and in general the further two nodes are physically separated from each other the less likely a connection is to form between them. The influence of distance on wiring probabilities is controlled through a parameter $\eta$. Affinity captures non-spatial topological factors that influence connection formation. As discussed below, there are many different methods for computing the affinity matrix, denoted $K$, each giving rise to different growth dynamics and final network structures. The influence of affinity on wiring probabilities is controlled through a parameter $\gamma$.

Because the sampling of edges is performed at random, GNMs are fundamentally stochastic: running the model for the same set of parameters ($\eta, \gamma$) repeatedly can result in very different final networks. In general, there is no way for us to say the probability that a particular network will be generated via the GNM under some set of parameters; instead, we typically explore model outputs by running many copies of the model for the same parameters ($\eta, \gamma$) to examine the distribution of networks the model produces for that parameter set. By comparing these distributions across different parameter pairs, we can find the set of parameters which gives produces networks which most often have the same topological properties found in real brain networks.

Computing Wiring Probabilities

At each step of the GNM, we must compute wiring probabilities $P_{ij}$ that each pair of currently unconnected nodes will form a connection. We begin by computing unnormalised wiring probabilities using both the distance and affinity matrices, $D$ and $K$ as follows.

The distance matrix $D$ measures the physical separation in space between nodes; $D_{ij}$ is equal to the distance between nodes $i$ and $j$. From the distance matrix, we obtain a distance transform $d_{ij}$ dependent on both the parameter $\eta$ and on the distance relationship type. When the distance relationship type is exponential, the distance transform is computed as $d_{ij} = \exp( \eta D_{ij} )$. When the distance relationship type is powerlaw, the distance transform is computed as $d_{ij} = D^{\eta}$. Similarly, from the affinity matrix $K_{ij}$ we obtain an affinity transform $k_{ij}$ using parameter $\gamma$. When the affinity relationship type is exponential, the affinity transform is $k_{ij} = \exp( \gamma K_{ij} )$; when the affinity relationship type is powerlaw, the affinity transform is $k_{ij} = K_{ij}^\gamma$.

To combine the geometric information contained in the distance transform, $d_{ij}$, with the non-geometric, topological information contained in the affinity transform, $k_{ij}$, we multiply these together to produce unnormalised wiring probabilities, $$ \tilde{P}{ij} = d{ij} \times k_{ij}. $$ Several important constraints are then applied to these unnormalised probabilities. Existing edges have their probabilities set to zero, since we can only add new edges between nodes not already connected. This can be accomplished by multiplying the unnormalised probabilities by $(1 - A_{ij})$, which is $0$ when $i$ and $j$ are adjacent ($A_{ij} = 1$) and $1$ when they are not currently connected ($A_{ij} = 0$). Since nodes cannot form edges to themselves (i.e., self-connections are prohibited), we set the diagonal terms to $0$, $\tilde{P}_{ii} = 0$. Finally, we normalised the probabilities by dividing by their sum to ensure the sum of the normalised probabilities is $1$.

After sampling from the normalised probabilities and adding the selected connection to the network, the process iterates. The affinity matrix is recomputed based on the updated adjacency matrix, new unnormalised and normalised wiring probabilities are calculated, and sampling continues. This iteration continues until the desired number of edges is reached.

Input: (Possibly empty) seed adjacency matrix, $A_{ij}$

For number of binary updates do:

Compute affinity matrix $K_{ij}$ from current adjacency matrix $A_{ij}$
Compute distance transform $d_{ij} = D_{ij}^\eta$ if distance relationship type is powerlaw and $d_{ij} = \exp( \eta D_{ij} )$ if the distance relationship type is exponential.
Compute affinity transform $k_{ij} = K_{ij}^\gamma$ if affinity relationship type is powerlaw and $k_{ij} = \exp( \gamma K_{ij})$ if the affinity relationship type is exponential.
Compute unnormalised connection probabilities as the product of the distance and affinity transforms: $$\tilde{P}_{ij} \gets k_{ij} \times d_{ij} $$
Set probability of already present edges to zero: $\tilde{P}_{ij} \gets (1 - A_{ij}) \tilde{P}_{ij}$
Set probability of self-connections to zero: $\tilde{P}_{ii} \gets 0$
Normalise wiring probabilities: $$P_{ij} \gets \frac{\tilde{P}_{ij}}{ \sum_{ab} \tilde{P}_{ab} }$$
Sample edge $(i,j)$ with probability $P_{ij}$
Add edge to the adjacency matrix: $A_{ij} \gets 1$ and $A_{ji} \gets 1$

End for

Return: Adjacency matrix $A_{ij}$

Computing the Affinity Matrix

The affinity matrix $K_{ij}$ captures an arbitrary non-geometric factor influencing the likelihood that nodes form edges between them, depending on the current pattern of connectivity in the network. Different generative rules provide various methods for computing the affinity matrix $K$ on the basis of the adjacency matrix $A$. There are three main classes of generative rules implemented within the toolbox - degree-based rules, clustering-based rules, and homphily rules.

Degree-based rules are built off the degree of each node, $s_i$ (defined as the number of neighbours of node $i$). The degree difference method compute $K_{ij} = |s_i - s_j|$, and thereby assigns a higher affinity to connections between nodes which currently have similar degree. The degree minimum method computes $K_{ij} = \min(s_i, s_j)$, and so assigns a higher affinity to connections into nodes which currently have a high degree. Within the degree class we also have degree maximum, average, and product methods. See the table below for definitions of these. Clustering-based rules are computed via analogous formulae, except using the clustering coefficients $c_i$ instead of the degrees.

Homophily rules instead assign a higher affinity to conenctions between nodes that already have a similar connection profile. There are two homophily rules implemented within the toolbox: Neighbours and Matching Index. Neighbours computes the affinity as the number of neighbours shared between two nodes. Accordingly, when two nodes share a large number of neighbours, they will have a high affinity. Note that neighbours will, in general, assign a higher affinity to connections into nodes which have high degree, since having a high number of neighbours means that you will be more likely to share those neighbours with any other node. Matching Index controls for this by instead computing the affinity between $i$ and $j$ as the fraction of nodes connected to either $i$ or $j$ which are connected to both $i$ and $j$. See the table below for a precise definition.

Rule type	Rule name	$K_{ij}$	Notes
Degree rules	Degree average	$\frac{s_i + s_j}{2}$	The degree of node $i$ is the total number of neighbours of $i$, $$s_i = \sum_j A_{ij}$$
	Degree difference	$\|s_i - s_j\|$
	Degree maximum	$\max(s_i,s_j)$
	Degree minimum	$\min(s_i,s_j)$
	Degree product	$s_i \times s_j$
Clustering rules	Clustering average	$\frac{c_i + c_j}{2}$	The clustering coefficient $c_i$ is the proportion of $i$'s neighbours which are neighbours of each other, $$c_i = \frac{\left[ A^3 \right]_{ii} }{ s_i(s_i -1) }$$
	Clustering difference	$\|c_i - c_j\|$
	Clustering maximum	$\max(c_i,c_j)$
	Clustering minimum	$\min(c_i,c_j)$
	Clustering product	$c_i \times c_j$
Homophily rules	Matching Index	$\frac{ \sum_m A_{im}A_{mj} }{\sum_m \max(A_{im},A_{mj})}$	The number of neighbours $i$ and $j$ have in common, divided by the total number of nodes connected to either node.
Homophily rules	Neighbours	$\sum_m A_{im}A_{mj}$	The number of neighbours $i$ and $j$ have in common.
Geometric rule	Geometric	$1$	Distance factor only contributes to wiring probabilities.

Applications of GNMs

[ Leave blank for now ]

Rule type	Rule name	\(K_{ij}\)	Notes
Degree rules	Degree average	\(\frac{s_i + s_j}{2}\)	The degree of node \(i\) is the total number of neighbours of \(i\), $$s_i = \sum_j A_{ij}$$
	Degree difference	\(\|s_i - s_j\|\)
	Degree maximum	\(\max(s_i,s_j)\)
	Degree minimum	\(\min(s_i,s_j)\)
	Degree product	\(s_i \times s_j\)
Clustering rules	Clustering average	\(\frac{c_i + c_j}{2}\)	The clustering coefficient \(c_i\) is the proportion of \(i\)'s neighbours which are neighbours of each other, $$c_i = \frac{\left[ A^3 \right]_{ii} }{ s_i(s_i -1) }$$
	Clustering difference	\(\|c_i - c_j\|\)
	Clustering maximum	\(\max(c_i,c_j)\)
	Clustering minimum	\(\min(c_i,c_j)\)
	Clustering product	\(c_i \times c_j\)
Homophily rules	Matching Index	\(\frac{ \sum_m A_{im}A_{mj} }{\sum_m \max(A_{im},A_{mj})}\)	The number of neighbours \(i\) and \(j\) have in common, divided by the total number of nodes connected to either node.
Homophily rules	Neighbours	\(\sum_m A_{im}A_{mj}\)	The number of neighbours \(i\) and \(j\) have in common.
Geometric rule	Geometric	\(1\)	Distance factor only contributes to wiring probabilities.