Evolutionary scale-free networks

The study of networks and transport in networks is of great interest for the sport-science field. For instance, the iterative process of building a team for the Olympics, which consists in evaluating the collective performance through the permutation of athletes inside the team, is a key process in maximizing the team’s performance and winning a medal. Another example includes the modeling of the communication between athletes in a team during a match, which changes with time, or the identification of the "institutional trajectories" of athletes, i.e., assessing the structures (alternatively, the coaches) which are critical in the institutional network of sport organizations. More generally, transport in complex (or scale-free) networks is relevant for various natural and artificial systems. These networks have a degree distribution that follows a power law $P(k) \sim k^{-\gamma}$ (or truncated power law), where $k$ is the node degree and $\gamma$ is an exponent. Natural and artificial systems forming such networks can be altered with time, and often exhibit properties related to the percolation phenomena, where links are lost or destroyed with time. This can illustrate the loss of information between athletes during a match (due to the adversary breaking a link between two athletes, for instance), or the loss of a path (i.e., possibility to move from one structure/coach to another) between two institutional structures (or coaches), which may endanger the sport organization at the national level. Previous studies have shown that scale-free networks are fragile and prone to collapse. This was demonstrated theoretically and for multiple dynamical real-world systems, such as (species) evolution and ecosystems, the financial sector, and social networks. The stability of such systems can be jeopardized with the removal of just one element, possibly leading to collapse.

In this hackathon, we aim at modeling a simplified version of these processes in quantum computers. The ultimate objective is to avoid the computing bottleneck of the whole process (construction of the graph + solving equation (2), and see section 2.3) that occurs when simulating large networks with millions of nodes.

Specific resources: [1, 2]

One experience can be described as follows: build a network according to a set of parameters then iteratively remove links in this network according to a predefined strategy, until a stopping condition (which stops the experience) is met. The transport dynamics inside the networks is described by the Kirchhoff’s equations. The methodology is:

Construct a random network with $N_0$ nodes, see section 2.2). In each realization of the network, randomly select a pair of source and drain nodes, at which the potential is fixed to be 1 and 0, respectively. The flux through the network satisfies conservation of mass [3]: at every node $i$ we impose $\sum_j q_{i,j} = 0$, where $q_{i,j}$ is the flux through the link connecting nodes $i$ and $j$. These fluxes are calculated as:

where $P_i$ and $P_j$ are the potentials at the nodes $i$ and $j$ respectively, and we set the unit resistance for all links. In such a setup, the system of linear Kirchhoff’s equations describing the transport in a network is:

with $\top$ denoting transposition and where $P^\top$ is the vector of $N_0 - 2$ unknown potentials, $L$ is the Laplacian matrix of $(N_0 - 2) \times (N_0 - 2)$ elements obtained after removal of two lines and two columns corresponding to the source and drain nodes (at which the potentials are fixed), and $S^\top$ is a $(N_0 - 2) \times 1$ column vector, in which each element corresponds to the total flux exiting each node $i$:

Each element of $L$ is defined as:

The system described in eq. (2) is solved for $P$ numerically using a custom routine in Matlab (see section 2.3). The distributions of potentials on nodes and fluxes in links are then obtained. In particular, we compute the total flux $Q$, that is the sum of fluxes exiting from the source node.

The constructed network evolves at discrete steps according to a pre-selected strategy. At each evolution step, we solve the system of Kirchhoff’s equations (2) and remove either the weakest link (pseudo-Darwinian strategy) or a random link (random strategy) [1]. After a link removal, we also remove “dead-end” nodes (i.e., nodes whose degree equals 1), thus requiring any existing node after an evolutionary step to have at least degree 2. Each evolution step is associated with “time” $t$, and $t_0 = 0$ being the initial time, when the evolution starts. We denote by $Q_0$ and $L_0$ the total flux and the number of links respectively at $t_0$.

We aim at estimating the time of collapse $t_c$ of the network. The evolution ends when at least one of the following conditions is met: (i) no path exists between the source and the drain (i.e., the source and drain are disconnected), (ii) the source or the drain is removed from the network, (iii) a portion of the network – a subgraph containing more than one node – is disconnected from the rest of the network. This last condition is implemented to reflect natural systems such as energy, transportation or biological networks, where it is not desirable to remove a portion of nodes from the rest of the network. The end of the simulation defines $t_c$, corresponding to a situation where the transport can no longer be maintained through the whole network.

We generally obtain a distribution of $t_c$ by running many experiences for a given set of network parameters.

The two critical steps in constructing a random network are:

A mandatory condition for establishing the Kirchhoff’s equations is that the minimum degree of each node should be at least 2 (otherwise transport cannot be achieved: a node with degree 1 cannot transport a quantity to another node).

A Matlab function submission/get_flow.m is provided to understand how the solving is performed. The input and output nodes are removed before solving the linear system (eq. 2) for the fluxes (see section 2.1). However, solving eq. 2 can get really computational, in terms of operations, as the number of equations is proportional to $N_0$, and this should be solved for each evolutionary/time step. In other words, during one experience, a network is constructed, and (eq. 2) has to be solved for each time step until $t_c$ is reached. Moreover, the number of experiences has to be repeated in order to have the distribution of $t_c$. This may create a computational bottleneck when simulating large networks (i.e., of the order $N_0 = 10^4$ nodes or larger). Not to mention that in order to measure a size-effect, multiple experiences per $N_0$ should be performed. Such that we ultimately have the total number of solving operations equals to $n \approx n_{N_0} \times n_e \times \bar{t}_c$ where $n_{N_0}$ is the number of $N_0$ to investigate, $n_e$ is the number of experiences to produce for each of these $N_0$ values, and $\bar{t}_c$ is the expected ending times value, which also relates to $N_0$ and remains unknown (it should be estimated numerically, i.e., using the simulations).

A complete code describing this process can be found at the following Git URL:

Please note that the GitHub code also contains C implementations of the prepare_linsys(netw, sized); and compute_q(netw, sized, F); subfunctions (see submission/get_flow.m function).