Structure and function in flow networks

The relation between structure and function is one of the most studied topics in the theory of complex networks [1–7]. The structure is a topological representation of the interacting elements forming a network and it is rigorously described by the theory of graphs. The function is related to how the network units interact, exchange information, or dynamically evolve. It can be quantified by a variety of different approaches and methodologies, e.g., it can be quantified as a statistical description of the weights of connections of the structure of the network [1–4] disregarding any intrinsic dynamic of the nodes, or depend on the dynamics of interactions among the units.

This work deals with flow networks [8–11] that satisfy conservation laws (Kirchhoff's laws). The model for the flow network is stated in terms of resistor networks (weighted symmetric graphs), which have a source node s and a sink node t feeding the system, and a linear relationship between loads (voltages) and flows (currents)¹. The problem models a wide variety of physical phenomena, such as optimization algorithms [12–14], transport networks [14, 15], scheduling problems [16, 17], and electrical circuits [8, 9, 18]. Its solutions establish a clear relationship between the topological structure of the networks (namely, adjacency matrix and edge weights, assumed known) and the functional flows passing through nodes and edges (that are a consequence of solving the flow model). The foundation of network flow theory roots back to Kirchhoff [8], answering what are the current flows in an electrical circuit when a set of voltages is applied. The solution is then achieved by solving Kirchhoff's equations [8–11].

In this letter, we present a unified approach for the fundamental relationship between structure and function in flow networks by calculating voltages (loads) when input currents (flows) are given. The main results of this approach are the following.

First, a novel formula for the voltages in the flow network model, i.e., theVoltage-Flow (VF) problem (eq. (2)), is analytically derived. The solution (eq. (6)) is expressed in terms of the known graph's weighted Laplacian matrix eigenspace base. In particular, we show that the behaviour of the flows is not only dependent on the matrix spectra, but intrinsically connected to the eigenvectors of this matrix.

Second, we show that theequivalent resistance (also known as two-point distance resistance) formula [19] is retrieved (eq. (7)) without further assumptions from the analytical expression for the voltages induced by the single s-t pair. The equivalent resistance between any two nodes is a measure that characterises the graph's structure differently than other betweenness measures, such as degree distribution or clustering coefficient. It is shown here how it constitutes a highly useful tool to reduce the complexity of any network structure: an arbitrary topology is transformed to an effective all-to-all complete graph.

Third, using both the voltage differences and the equivalent resistance, an effective functional flow adjacency (EFFA) between any two points in the circuit is constructed (eq. (8)). These effective flows are the real measurable observables that are obtained when a probe is placed between any two nodes in the network. The EFFA matrix expresses the level of connectivity in terms of flow transmission; the functional relationship among the network components in the effective all-to-all topology. In particular, if two nodes are not directly connected, an effective current between them may still exist.

Fourth, as an application of our approach, we show how to identify the nodes that are mainly responsible for the transmission of flow, how to detect qualitatively communities of the network, and how to infer the maximal node outflow for different graph topologies and resistor distributions. This reveals topological issues that are related to the node maximum capacities in a natural manner.

The starting point for our unified approach is the calculation of voltages in a network by solving the VF problem. The VF problem is set by interpreting any graph structure as a linear resistor network circuit, which then receives an input flow I at node s and leaves at node t (a current I enters the circuit at a source and leaves at a sink). This model associates loads l_ij with potential differences ΔV_ij and flows f_ij with electrical currents I_ij. The network structure is given by a connected strict graph $\mathcal {G} = \{\mathcal {V},\,\mathcal {E}\}$ (where $\mathcal {V}$ and $\mathcal {E}$ are the sets of nodes and edges, respectively) with symmetric edge weights W_ij ≡ A_ij/R_ij for i, j = 1,..., N (N being the number of nodes in $\mathcal {V}$, A_ij the ij-th element of the adjacency matrix, and R_ij the edge's resistance).

Imposing conservation of charge (flow conservation: $\sum _{j} f_{ij} = 0$) in every node of the network, i.e., a graph where at each node the current arriving at it equals the amount leaving it (first Kirchhoff's law), the flow vector is $(\vec {F}^{(st)})_i = I\,\left ( \delta _{is} - \delta _{it} \right )$ for i = 1, ..., N, with δ_ij being the Kronecker delta. Thus, using the laws of Kirchhoff and Ohm, the net current in any node is given by

$$\begin{equation} F_i^{(st)} = I\,\left(\delta_{is} - \delta_{it}\right) = \sum_{j = 1}^N \frac{A_{ij} }{R_{ij}}\left( V_i^{(st)} - V_j^{(st)} \right)\,, \end{equation} \tag{ 1 }$$

where V^(st)_i is the voltage potential at node i given the particular s-t pair. Equation (1) is rearranged such that the VF problem is expressed in matrix form

$$\begin{equation} \mathbf{G}\,\vec{V}^{(st)} = \vec{F}^{(st)}\,, \end{equation} \tag{ 2 }$$

where the upper indexes indicate that the problem depends on the location of the s-t nodes on $\mathcal {V}$ and G is the weighted Laplacian matrix. The entries of G are

$$\begin{equation} G_{ij} = \left\lbrace \begin{array}{lcl} \sum_{k=1}^N W_{ik}, & \quad \mathrm{if} & i = j, \\ - W_{ij}, & \quad \mathrm{if} & i \neq j. \end{array} \right. \end{equation} \tag{ 3 }$$

Then, the VF solution is achieved once the voltages in each node are found from inverting G. However, the rank of G is N − 1 ($\det \left ( \mathbf {G} \right ) = \prod _{n = 0}^{N-1}\lambda _n = 0$) and direct inversion is not possible [11, 20].

The Laplacian inversion is addressed here by a different interpretation of the derivation of the generalized inverse matrix, also known as Moore-Penrose matrix [11, 19].

The eigenvalue problem for the Laplacian is given by G P = P Λ, where Λ_ij = δ_ij λ_n (n = i − 1 = 0,...,N − 1) is a diagonal matrix containing all eigenvalues and $\mathbf {P} = \{\vec {v}_0,\,\vec {v}_1,\,\ldots ,\,\vec {v}_{N-1}\}$ is the matrix whose columns are the eigenvectors of G. We prove here that to express any element of G, the only elements needed from the spectral decomposition are the non-null eigenvalues and corresponding eigenvectors. This results in the following decomposition of G:

$$\begin{equation} \mathbf{G} = \mathbf{P}_r\,\mathbf{\Lambda}_r\,\mathbf{P}_r^{T}\,, \end{equation} \tag{ 4 }$$

where T indicates transpose, $\mathbf {P}_r \in \mathbb {R}^{N\times (N-r)}$, $\mathbf {\Lambda }_r \in \mathbb {R}^{(N-r)\times (N-r)}$, and r being the number of connected components of $\mathcal {G}$, which in this letter is fixed at r = 1.

Equation (4) is derived by analyzing each Laplacian matrix entry using the full spectral decomposition. In particular, $G_{ij} = \sum _{k=1}^N P_{ik} \lambda _{k-1} P^{-1}_{kj}$, where for k = 1, λ₀ = 0, so no contribution is added to the sum. Thus, observing that the inverse of an orthogonal matrix is its transpose ($P^{-1}_{kj} = P_{jk} = \left (\vec {v}_{k-1}\right )_j$), the ij's entry of G is given by $G_{ij} = \sum _{k=2}^N \left (\vec {v}_{k-1}\right )_i\, \lambda _{k-1}\,\left (\vec {v}_{k-1}\right )_j$, which is easily extendible to various connected components making the lower bound for the summation index k = r + 1.

However, removing the null eigenspace of the spanning set of eigenvectors, the rank of the new G in eq. (4) is N and inversion can be directly performed. Consequently, each element of the generalized inverse Laplacian matrix Z_ij ≡ (G⁻¹)_ij is found from

$$\begin{equation} Z_{ij} = \sum_{n = 1}^{N-1} \left(\vec{v}_n\right)_i \frac{1}{\lambda_n} \left(\vec{v}_n\right)_j\,, \end{equation} \tag{ 5 }$$

with the new index n = k − 1 and i, j = 1,...,N. It is easy to show that $\sum _{k=1}^N G_{ik}\,Z_{kj} = \delta _{ij} - 1/N$, where the extra constant factor comes from the incompleteness of the restricted eigenspace and it cancels out when calculating voltage differences.

Returning to eq. (2), the solution for the VF problem at a given node $i\in \mathcal {V}$ is $\left ( \vec {V}^{(st)} \right )_i = \sum _{j = 1}^N Z_{ij}\,\left ( \vec {F}^{(st)} \right )_j = I\,\left ( Z_{is} - Z_{it} \right )$,

$$\begin{equation} \left( \vec{V}^{(st)} \right)_i = I\,\sum_{n = 1}^{N-1} \frac{ \left(\vec{v}_n\right)_i }{ \lambda_n } \left[\left( \vec{v}_n \right)_s - \left( \vec{v}_n \right)_t\right]\,. \end{equation} \tag{ 6 }$$

This formula is the backbone of our unified approach. It is applicable to any connected weighted graph and is extendible to many sources and sinks with different inputs and outputs as long as flow conservation is fulfilled ($\sum _i F_i^{(st)} = 0$ and F_i = 0∀ i ≠ s or t). Furthermore, it allows to derive the equation for the equivalent resistance between any two nodes, to construct the effective flows, and the later apply them to, e.g., community detection.

The derivation of the equivalent resistance ρ_ij between any two nodes [19] is done as follows. Set the source at a starting node (i = s) and the sink at an ending point (j = t), then eq. (6) provides an exact closed formula for ρ_ij in terms of eigenvalues and eigenvectors of the weighted Laplacian matrix. The reason for doing this is that the voltage difference between these two nodes gives the incoming current times the resistance between them, hence, $(\vec {V}^{(st)})_s - (\vec {V}^{(st)})_t = I\,\rho _{st}$. Therefore, using the same procedure for every pair of nodes in the graph all ρ_ij's are determined,

$$\begin{equation} \rho_{ij} = \sum_{n = 1}^{N-1} \frac{ 1 }{ \lambda_n } \left[\left( \vec{v}_n \right)_i - \left( \vec{v}_n \right)_j\right]^2\,, \end{equation} \tag{ 7 }$$

providing a solution that is independent of where the s-t pair is placed.

The matrix element ρ_ij is a measure of the structure that weighs all paths between any pair of nodes i and j. In other words, all paths between these nodes that are allowed by the adjacency structure of the graph are collapsed to one equivalent link with weight ρ_ij. The result is that a single effective link is created between i and j. The important contribution is that this quantity presents the possibility to diminish the complexity of any graph to a simpler all-to-all equivalent topology with a betweenness score given by ρ_ij.

As a working example, results of applying the solution given by eqs. (6) and (7) to a ring graph, namely C_N, of N = 16 nodes with resistors equal to one (R_ij = 1∀ i,j) and input current I = 1 are shown in fig. 1. For this network, the set of unordered eigenvalues is given by λ_n = 2 − 2 cos (2π n/N), with n = 0,...,N − 1 [20].

Zoom In Zoom Out Reset image size

The top left panel in fig. 1 shows that for the N (N − 1) = 240 possibilities of s-t pairs in C_N the maximum voltages achieved in the ring do not surpass 2 (arbitrary units). This is the maximum difference that the eigenvector coordinates can achieve in the non-normalized frame (top right panel in fig. 1), hence giving a maximum voltage difference of 4. This result shows that not only the eigenvalues of the Laplacian are important to infer the network's functional behaviour, but eigenvectors are also needed. Also, the maximum (minimum) is periodic, in the sense that the largest difference happens every time the source and sink are separated by 8 edges.

The bottom panels in fig. 1 show the voltage solutions for all the s-t pairs (left) and all equivalent resistances (right). The resulting values show the functional and structural symmetry that this simple network has. As all edge weights are unity (R_ij = 1), the equivalent resistance ρ_ij maximum can only be 4. This is easily seen when calculating it directly by means of series and parallel resistor calculations. For instance, for nodes i = 1 and j = 9 there are two parallel paths with 8 edges in series, hence: $\rho _{1,9}^{-1} = \frac {1}{8} + \frac {1}{8} \;\Rightarrow \; \rho _{1,9} = 4$, which is the same value as element ρ_1,9 in the bottom right panel of fig. 1 (found from eq. (7)).

Having the voltage difference and equivalent resistance given by eqs. (6) and (7), the third result of our unified approach is addressed: the construction of the effective edge flows, namely, ϕ^(st)_ij. We introduce these flows by finding the voltage differences among any two nodes in the effective topology given by ρ_ij. Thus, the EFFA matrix elements for each s-t configuration are given by

$$\begin{equation} \phi_{ij}^{(st)} = \frac{ 1 }{ \rho_{ij} } \left[ \left( \vec{V}^{(st)} \right)_i - \left( \vec{V}^{(st)} \right)_j \right]\,, \end{equation} \tag{ 8 }$$

where $(\vec {V}^{(st)})_i > (\vec {V}^{(st)})_j$ such that an effective current is flowing from node i to j, otherwise ϕ^(st)_ij = 0. Hence, the s-t–dependent EFFA matrix defines an effective directed network, which breaks the symmetry of the effective all-to-all topology structure given by ρ_ij. In particular, the physical current on each edge $ij\in \mathcal {E}$ of the graph is given by $I_{ij}^{(st)} = \frac { A_{ij} }{ R_{ij} }\,[ ( \vec {V}^{(st)} )_i - ( \vec {V}^{(st)} )_j ]$.

The voltage differences define a functional relationship among nodes and the equivalent resistance an effective topology structure. The introduction of the EFFA relates both structure and functional characteristics of the graph, thus, it enables to find functional hubs that might not be there in the topological structure, and detect highly connected areas (communities) in a functional way. In this sense, the s-t analysis acts similarly as how a dye does when introduced to a circulatory system of a person: it highlights a certain part of the network structure to detect what is being sought, e.g., clog blocking, arteries stiffness, etc. For example, a simple network can consist of a few nodes connected to a central hub. If this network (A) is linked by a single path to another such network (B), and the flow source is located at A and the sink is located at B, then, the functional hubs are found in the path connecting the two networks. These are the nodes that handle all the flow that is being transported from A to B, however, they are not hubs from a strict structural point of view.

The mean EFFA matrix is defined to detect statistically relevant functional observables. It is calculated by all the effective currents (eq. (8)) among the different pairs averaged over all possible realizations of source-sink pairs. Its matrix elements are

$$\begin{equation} \phi_{ij} \equiv \left\langle \phi_{ij}^{(st)} \right\rangle_{(st)} = \sum_{s = 1}^N \sum_{t = 1\,(t \neq s)}^N \frac{ \phi_{ij}^{(st)} }{N\,(N-1)}\,, \end{equation} \tag{ 9 }$$

which define a matrix that constitutes an effective structural flow quantity and is related to the equivalent resistance matrix. The EFFA matrix and its averaged counterpart for the example of the ring graph are shown in fig. 2, where the left panel shows the mean EFFA matrix and the right panel exhibits the symmetry breaking for a particular s-t pair.

Zoom In Zoom Out Reset image size

With the three quantities analytically expressed (voltages in eq. (6), equivalent resistances in eq. (7), and the effective currents in eq. (8)), we investigate² random graphs (RN) [21], small-world (SW) networks [22], scale-free (SF) topologies [23], and numerically generated clustered networks (CN) of N = 2⁹ nodes. The following conclusions constitute the application of our unified approach to these concrete topologies. In particular, the differences between the respective adjacency and effective topologies (equivalent resistance) are shown in the left and centre columns of figs. 3 and 4.

Zoom In Zoom Out Reset image size

Zoom In Zoom Out Reset image size

To study other features of the EFFA matrix that are not represented in its averaged version and to answer how the flow is effectively distributed in any given topology, the probability density function (PDF) of the effective edge flows ϕ^(st)_ij for every particular s-t is calculated. This does not only tells how diffusive or localized the transport of currents is as a function of the effective topology, but also gives the maximum flow values a particular graph can have, i.e., the maximum edge capacity.

Results show that the EFFA PDFs for RN, SW, and SF networks are roughly invariant under changes of the s-t pair. However, SW and SF networks produce more high flow magnitudes (ϕ^(st)_ij ≃ 1) than RN for a broad range of parameters (see footnote ²), hence, RNs distribute flows in a more uniform way than SF or SW networks. These observations are seen in the example shown in the right column of fig. 3.

The detection of communities is done by the analysis of the mean EFFA matrix and the equivalent resistance. In general, the application of the EFFA analysis on numerically generated CNs qualitatively exhibits the communities that the networks have. This is seen in the centre and right panels of the example exhibited in fig. 4, where the communities are spotted as dark areas, both in ρ_ij and ϕ_ij, though the contrast in the mean EFFA matrix is higher than in the equivalent resistance, implying that communities are better identified by ϕ_ij. The ϕ_ij matrix not only detects the communities but also shows that the effective flows between communities are larger than the ones within each community. Hence, the intra-edges connecting communities must have a high flow capacity as they represent the vulnerable links in the network. The removal of any of these edges generates drastic changes in the flows, leading to the isolation of communities.

The observations on flow transmission and community detection have been previously shown by doing a structural analysis of networks, e.g., in refs. [1–7]. In particular, the possibility of using voltages as a betweenness measure score is pointed out in refs. [1–3] and is related to shortest-paths and random walks. With our unified approach, and the four results that are addressed in this letter, we show the practicality of it. Moreover, the linear relationship between loads and flows, and the conservation of charge, are restrictions needed to define the flow network on top of the structure, but not for the structure itself. Thus, the flow analysis is applicable to any network structure outside the domain of flow networks as long as the graph to be analysed is connected.

An estimate of the computational time that our approach requires is as follows. To calculate the voltages one needs the eigenvectors and eigenvalues of the Laplacian matrix. This is calculated in time $\mathcal {O}(N^{\alpha })$, with α being an exponent that nowadays rounds 2 and N the number of nodes in the network. Then, if all possible source-sink pairs are analysed, the flows require $\mathcal {O}(N^3)$ to be found. This means that the algorithm is not as effective as other methods [24] but its mathematical formulas still provide great information for obtaining upper and lower bounds for currents without the need for simulations. Furthermore, community detection can be quantitatively described if other techniques are used, such as PDF analysis of the EFFA matrix elements.

Authors acknowledge the Scottish University Physics Alliance (SUPA).