Navigational bottlenecks in nonconservative diffusion dynamics on networks

1.   Introduction

Networks ^[1] represent the skeletons of complex systems ^[2], which facilitate the spread of "information" between the entities of the systems (vertices of the network) using their pairwise connections (edges) ^[3]. Here, "information" is used generically to account for any item-from electrons in a molecule to people in a city-moving across a network ^[4]. Therefore, one of the most fundamental problems in the investigation of complex networks is to understand the mechanisms behind the transmission of information across them. In a connected network, there is always a shortest path between any pair of vertices. These are paths of the minimum lengths in terms of the number of edges connecting the pairs of vertices ^[5,6,7]. There is a misunderstanding in considering that information flows in a network via shortest paths, even in systems with billions of entities like the human brain ^[8]. As clearly remarked by Goñi et al. ^[9] "a routing/navigation process implies that communication flows from a specific source to a specific target along the fastest or most direct route, which implies a global knowledge about the network topology". For most of complex systems, the sender of information is unaware of the global structure of the network used to transmit the information, which excludes the possibility that it uses the shortest path ^{[10,11,12,13,14,15,16]}. Diffusion is a navigational process which seems to be ubiquitous in nature, implying that ^[9] "communication occurs in the absence of specific targets, or that, even if targets are specified, a lack of knowledge about global network topology prevents particles or messages from taking the shortest paths".

Diffusion has been widely studied in the context of complex networks ^[17,18,19] as well as in engineering under the term "consensus dynamics" ^[20,21,22]. A characteristic signature of diffusion in graphs is its conservative nature. A dynamical process on a graph is mediated by the interactions between nodes ^[1,3]. It is said to be conservative if the total amount of diffusive material is constant on the graph at any time ^[23]. This type of process excludes those in which (ⅰ) some information is dissipated to or taken from outside the graph, (ⅱ) part of the information is annihilated/created at the vertices of the graph. In these cases, the amount of diffusive material on the graph does not remain constant in time, and these are known as nonconservative (NC) processes. There are several important examples of NC diffusive processes in complex systems ^{[24,25,26,27,28,29,30]}. Traffic in a city is frequently studied by assuming that it flows via the shortest paths between origin-destination pairs ^{[31,32,33,34]}, or by considering a conservative diffusion model ^[35,36,37]. However, the number of cars flowing through the streets (edges) of an urban street network is not necessarily the same at slightly different times, making the process NC in its nature. The reason is that some cars may "disappear"/"appear" in the street leg between two intersections due to the fact that they may park or emerge from parking in such street leg, known as "mid-link sink and sources" in traffic literature ^[38,39]. Another example frequently considered from the perspective of shortest paths and conservative diffusion is the flow of matter and energy in a food web. In this casethe nodes represent species and the directed edges represent their trophic relations (who eats who), which are the pathways over which energy and matter can flow. When one species $A$ (predator) predates another species $B$ (prey), $A$ utilizes only a portion of the material and free energy originally in $B$, which is then retained in the predator, giving rise to a non-conservative process. Such mass and energy can then be diffused across the food web in an NC diffusive way ^[40]. Another non-conservative scenario is the chemical synapses in neuronal systems where apart fromthe wiring intercellular communication, which is expected to be conservative, there is also communication in the form of a volume transmission (VT), which uses the extracellular fluid filling channels of the extracellular space and the cerebrospinal fluid filling ventricular space and sub-arachnoidal space (Figure 1(e)) ^{[26,41,42,43,44,45,46]}. More examples of NC diffusion include communication in social media like X (formerly known as Twitter) ^[27,28,29], where a user can post a message that can be read by her followers, but also (if not constrained by the user) by non-followers, all of whom can retweet such information to others. Even the transmission of packages of information via the Internet may be an NC diffusion process due to the existence of long queues at given servers, which may result in some packages being discarded, making the transmission process NC on the graph.^*

^*We remark that the process is always conservative in the physical universe, but we are referring to the case of being conservative or not on the discrete space defined by the graph.

Here, we consider navigational processes occurring in complex systems that can be modeled by NC diffusive dynamics. We then focus on understanding which are the network characteristics that may burden the navigability in this framework. Let us consider an NC diffusion dynamics reaching a steady state at a given time $t_{c}$. Then, if we start the diffusive process by concentrating all the diffusive particles at a vertex $i$, we can obtain $t_{c, i}$. Similarly, we can initialize the process at vertex $j$ and obtain $t_{c, j}$. Obviously, if $t_{c, j} > t_{c, i}$ it means that it is more difficult to reach the steady state of the diffusion when starting at vertex j than when starting at vertex $i$. If we do this for all vertices in the network, we can obtain those which are the ones producing the biggest delay in reaching the steady state. We will call these vertices "navigational bottlenecks" for obvious reasons. The identification of network bottlenecks is a foundational work for improving network traffic conditions and preventing traffic congestion ^{[47,48,49,50,51,52,53,54,55]}. However, we should stress an important problem with dealing with this matter before we can proceed. In a real-world situation, the existence of a bottleneck does not only depend on the topology of the network supporting the dynamics but also depends on the traffic allocated to the given vertices. For instance, a vertex that is identified as a navigational bottleneck in a network does not necessarily behave as a bottleneck if the traffic allocated to it is relatively small. Therefore, what we propose in this work is the identification of those vertices that have a large propensity to become navigational bottlenecks if the amount of traffic allocated to them is significantly large. Developing the previously mentioned program for identifying navigational bottlenecks implies the realization of $n$ simulations of the NC diffusion on a network of $n$ vertices, i.e., one simulation starting the process at each vertex. Therefore, what we propose here is to solve the problem analytically, such that we can define an index characterizing the propensity of every vertex to become a navigational bottleneck without the necessity of performing any simulation of the dynamics.

2.   Preliminaries

Let $\mathcal{G} = \left(V, E\right)$ be a simple, connected graph and let $A$ be its adjacency matrix. The degree of the vertex $i$, $k_{i}$, is the number of edges connected to that vertex in the graph. Let $A = U\Lambda U^{T}$ be the spectral decomposition of the adjacency matrix, such that $\varLambda$ is the diagonal matrix of eigenvalues of $A$ and $U$ is the orthogonal matrix of eigenvectors. In general, we designate the spectrum of a matrix $M$, $Spec\left(M\right)$ to be the set of eigenvalues of this matrix together with their multiplicities, which are represented as superscripts in parentheses. In the case of the matrix $A$ of a connected undirected graph: $Spec\left(M\right) = \left\{ \lambda_{1}, \lambda_{2}^{\left(m_{2}\right)}, \cdots, \lambda_{n}^{\left(m_{2}\right)}\right\}$, such that $\lambda_{1} > \lambda_{2}\geq\cdots\geq\lambda_{n}$ are the eigenvalues of $A$. Let $\psi_{j}$ be the eigenvector associated with the eigenvalue $\lambda_{j}$. We will designate by $\psi_{j, i}$ the $i$th entry of $\psi_{j}$. The entry $\psi_{1, i}$ is known as the eigenvector centrality of the vertex $i$, $EC_{i}$ ^[56,57,58]. The standard, conservative diffusion process on a graph represents the change of the "concentration" $C_{i}$ of items at the vertices of the graph with the pass of time, which is defined by ^[17]:

with initial condition $C\left(0\right) = C_{0}$. In this equation, $\dot{C}\left(t\right) = \left[\dot{C_{1}}\left(t\right), \ldots, \dot{C_{n}}\left(t\right)\right]^{T}$where $\dot{C}\left(t\right) = \dfrac{dC\left(t\right)}{dt}$, $C\left(t\right) = \left[C_{1}\left(t\right), \ldots, C_{n}\left(t\right)\right]^{T}$ and $\mathscr{L} = K-A$ is the graph Laplacian, with $K$ being the diagonal matrix of vertex degrees. The solution of the Cauchy problem (2.1) is given by $C\left(t\right) = e^{-t\mathscr{L}}C_{0}$, where $e^{-t\mathscr{L}}$ is the matrix exponential function of the graph Laplacian. Matrix functions of the adjacency matrix, which will frequently appear in this work, are defined by: $G: = \exp\left(A\right)$. The term $G_{i, j}$ for $i\neq j$ is known as the communicability between the two vertices, while the term $G_{ii}$ is known as the subgraph centrality of the vertex $i$. The term $EE\left(\mathcal{G}\right): = Tr\exp\left(A\right)$ is known as the Estrada index of the graph, where $Tr$ is the trace of the corresponding matrix.

The squared communicability distance between two vertices in a graph is defined as ^[59] (see also ^[60,61,62]):

which has been proved to be a Euclidean and spherical distance between the corresponding vertices in the graph.

The nonconservative (NC) diffusion process on a graph has been previously studied. In this case, the change of concentration of items at the vertices of the graph with time is described by the equation:

where $L_{\chi}: = \chi I-A$ is the Lerman-Ghosh Laplacian of the graph ^[64] (see also ^[65]), and the process has initial condition $C\left(0\right) = C_{0}$.

3.   Theoretical results

We start by proving the following result.

Theorem 1. Let $\mathcal{G}$ be a graph in which the NC diffusion (2.3) takes place. Then,

Proof. The solution of the diffusion equation is given by

which can be written as

Then, when $\chi < \lambda_{1}$ we have

which diverges as $t\rightarrow \infty$.

If $\chi = \lambda_{1}$ we have that the first term of Eq (3.3) is zero, and the rest are negative, such that

which indicates that the solution is proportional to the entries of the eigenvector $\psi_{1}$ associated with the spectral radius $\lambda_{1}$ of $A$. This eigenvector was introduced by Bonacich ^[56,57,58] as a centrality index of the vertices in a graph and it is nowadays known as the eigenvector centrality. Therefore, the current framework provides a dynamics interpretation of this centrality index in terms of the concentration reached by a vertex at the steady state of a non-conservative diffusion controlled by the Lerman-Ghosh Laplacian matrix ^[64] when $\chi = \lambda_{1}$. Because the second smallest eigenvalue of $\left(\lambda_{1}I-A\right)$ is $\lambda_{1}-\lambda_{2}$, it determines the rate of convergence of the diffusive process. Notice that if $C^{0} = \psi_{1}$, then the diffusion process is conservative because:

Finally, if $\chi > \lambda_{1}$ then,

which goes to zero as $t\rightarrow \infty$. □

Therefore, the only NC diffusion process that does not diverge is when $\chi = \lambda_{1}$. Let us then consider such a process on $G$. Let us then consider the concentration of items at a given vertex $i\in V$ when $C_{i}^{0} = 1$ and $C_{j}^{0} = 0$ for all $j\neq i$, when $t\ll\infty$, which is given by

Let us now consider such concentration at an infinitely large time. That is the following:

where $\psi_{1, i}^{2}$ is the square of $i$th entry of the eigenvector associated with $\lambda_{1}$. Notice that $\psi_{1, i}$ is the eigenvector centrality of $i$, $EC_{i},$ such that $\underset{t\rightarrow \infty}{\lim}C_{i}\left(t\right) = EC_{i}^{2}$ when $C_{i}^{0} = 1$ and $C_{j}^{0} = 0$ for all $j\neq i$.

Remark 2. Notice that when $C_{i}^{0} = 1$ and $C_{j}^{0} = 0$ for all $j\neq i$, the concentration at any node $j\neq i$ when the steady state is reached is given by

Let us then consider the following.

Definition 3. Let $G$ be a graph in which the NC diffusion (2.3) takes place with initial conditions given by $C_{i}^{0} = 1$ and $C_{j}^{0} = 0$ for all $j\neq i$. Let $\chi = \lambda_{1}.$ Then, the difference $C_{i}\left(t = 1\right)-\underset{t\rightarrow \infty}{\lim}C_{i}\left(t\right)$ accounts for how fast or slow a vertex spreads the concentration of items across the graph when all the initial concentration is at this vertex:

where $SC_{i}$ is the subgraph centrality of the vertex $i$ ^[66]. Then, because the denominator is just a normalization factor we will consider here the index

A small value of $X_{i}$ indicates that the vertex $i$ has a large capacity to deliver items from it to reach the steady-state concentration corresponding to an NC process taking place on the graph. On the other hand, a large value of this index indicates that it takes a long time for this vertex to reach such steady-state concentration. Therefore, the last vertex is a potential bottleneck in the diffusive navigational processes taking place on the graph. Therefore, we will call $X_{i}$ the navigational bottleneck index (NBI) of the vertex $i$. Notice that if comparisons between vertices in different graphs are intended, then the normalization by $\exp\left(\lambda_{1}\right)$ is necessary.

To gain insights about the role of graph structure in the values of $X_{i}$, we have designed the three toy graphs illustrated in Figure 3.1. The first graph, also known as an agave graph, represents two large degree vertices (hubs) that are connected to each other as well as through a series of vertices of degree two. The multiple dots indicate that the number of these vertices of degree two is arbitrary. The second graph is the same as the previous one, but in this case, the two hubs are not interconnected. The communication between the two hubs in this graph occurs only via the vertices of degree two. The third graph consists of two hubs that are not directly connected to each other but connected through paths of length three. In closing, this example has a pair of hubs communicated by a peripheral set of vertices of degree two. The difference among them resides in the fact that in the three graphs the "effective separation" between the two hubs increases from $\mathcal{G}_{1}$ to $\mathcal{G}_{3}$.

We now find the values of $X_{i}$ for the two types of vertices in the graphs in Figure 3.1 analytically.

Lemma 4. Let $\mathcal{G}_{1}$ be the graph illustrated in Figure 3.1 on $n$ vertices where $v$ is any of the two vertices of degree $n-1$ (hubs) and $w$ is any of the vertices of degree two. Let $\alpha = \sqrt{8n-15}$. Then,

and

Proof. The eigenvalues of the adjacency matrix of the agave graph $G_{1}$ are:

and the entries of the eigenvector associated with $\lambda_{j}$ for the vertex $v$ are: $\psi_{1, v}^{2} = \dfrac{1}{4}\left(1+\alpha^{-1}\right)$, $\psi_{2\leq j\leq n-2, v}^{2} = 0$, $\psi_{n-1, v}^{2} = \dfrac{1}{2}$, $\psi_{n, v}^{2} = \dfrac{\alpha-1}{4\alpha}$. Therefore,

Because, $X_{v}\left(\mathcal{G}_{1}\right) = \left(e^{A\left(\mathcal{G}_{1}\right)}\right)_{vv}-\dfrac{1}{4}\left(1+\alpha^{-1}\right)e^{1/2\left(1+\alpha\right)}$ we have

which proves the first part of the result.

Then,

where the Estrada index of an agave graph on $n$ vertices $EE\left(\mathcal{G}_{1}\right)$ is:

Then, after substitution and arrangements, we have

Finally, we have that $X_{w}\left(\mathcal{G}_{1}\right) = \left(e^{A\left(\mathcal{G}_{1}\right)}\right)_{ww}-\psi_{1, w}^{2}e^{\lambda_{1}} = \left(e^{A\left(\mathcal{G}_{1}\right)}\right)_{ww}-\dfrac{4}{\alpha\left(\alpha+1\right)}e^{1/2\left(1+\alpha\right)},$ so that we obtain the final result. □

Lemma 5. Let $\mathcal{G}_{2}$ be the graph illustrated in Figure 3.1 on $n\geq5$ vertices where $v$ is any of the two vertices of degree $n-1$ (hubs) and $w$ is any of the vertices of degree two. Let $\beta = \sqrt{2\left(n-2\right)}$. Then,

and

Proof. The graph $\mathcal{G}_{2}$ is a complete bipartite graph $K_{2, n-2},$ so the eigenvalues of its adjacency matrix are:

and $\psi_{1, v} = \dfrac{1}{2}$ such that

Because $\sum_{j = 1}^{n}\psi_{1, j}^{2} = 1$ we get $\sum_{2\leq j\leq n-1}\psi_{j}^{2} = \dfrac{1}{2},$ such that

and

For obtaining $\left(e^{A}\right)_{ww}$ we use again the trace of $\exp\left(A\right)$, such that

and

such that

□

Lemma 6. Let $\mathcal{G}_{3}$ be the graph illustrated in Figure 3.1 on $n\geq8$ vertices where $v$ is any of the two vertices of degree $n-1$ (hubs) and $w$ is any of the vertices of degree two. Let $\gamma = \sqrt{2\left(n-3\right)}$. Then,

and

Proof. The eigenvalues of the adjacency matrix of the agave graph $\mathcal{G}_{3}$ are (notice that $n$ is always even in this graph):

and $\psi_{1, v}^{2} = \dfrac{1}{4}\left(1-\dfrac{1}{\gamma}\right)$, $\psi_{1, w}^{2} = \dfrac{\gamma+1}{2\left(n-2\right)\gamma}$, $\psi_{n-1, v}^{2} = \dfrac{1}{4}\left(1+\dfrac{1}{\gamma}\right),$ $\psi_{n-1, w}^{2} = \dfrac{\gamma-1}{2\left(n-2\right)\tau}$. Therefore,

We can also write

such that

We can now obtain the values of $X_{v}\left(\mathcal{G}_{3}\right)$ and $X_{w}\left(\mathcal{G}_{3}\right)$ by subtracting $\psi_{1, v}^{2}e^{\lambda_{1}}$ and $\psi_{1, w}^{2}e^{\lambda_{1}}$ from the expressions of $\left(e^{A\left(\mathcal{G}_{3}\right)}\right)_{vv}$ and $\left(e^{A\left(\mathcal{G}_{3}\right)}\right)_{ww}$, respectively, which proves the result. □

To illustrate the results obtained in the previous three Lemmas we calculate here the values of the $X$ index for the two non-equivalent vertices in the three classes of graphs illustrated in Figure 3.1. We select $n = 10$ in this example. In the case of the graph $\mathcal{G}_{1}$ it is easy to see that $\underset{n\rightarrow \infty}{\lim}X_{v}\left(\mathcal{G}_{1}\right) = \dfrac{1}{2e}$ and $\underset{n\rightarrow \infty}{\lim}X_{w}\left(\mathcal{G}_{1}\right) = 1.$ The results given in Table 1 give $X_{v}\left(\mathcal{G}_{1}\right)\approx0.19$ and $X_{w}\left(\mathcal{G}_{1}\right)\approx0.88$, which are close to the limit values. However, the most interesting thing here is that, as predicted, the vertex $w$, which is the one of degree two, is the one having the largest capacity to create a navigational bottleneck in the graph. This is corroborated by the fact that time $t_{c}\left(w\right)$ needed to reach the steady state, i.e., $\left(u_{i}\left(t\right)-u_{j}\left(t\right)\right)\leq10^{-4}$ for all $i, j\in V$, when the initial concentration is located at the vertex $w$ is bigger than that when the concentration is located at the vertex $v$, $t_{c}\left(v\right)$. That is, reaching the steady state of a nonconservative diffusion in $G_{1}$ is harder if the initial concentration is located at the vertex $w$ than at the vertex $v$, exactly as predicted by the index $X$. The situation is similar for the graph $\mathcal{G}_{2}$ where $\underset{n\rightarrow \infty}{\lim}X_{v}\left(\mathcal{G}_{2}\right) = \dfrac{1}{2}$ and $\underset{n\rightarrow \infty}{\lim}X_{w}\left(\mathcal{G}_{2}\right) = 1$. Here again $t_{c}\left(w\right) > t_{c}\left(v\right)$ indicating that the vertices of degree two are potential navigational bottlenecks relative to vertex $w$ (see Table 1). The graph $\mathcal{G}_{3}$ is, however, an example where the hubs are the potential navigational bottlenecks for a nonconservative diffusion. In this case $X_{v}\left(\mathcal{G}_{3}\right) > X_{w}\left(\mathcal{G}_{3}\right)$, indicating that the vertex with the largest degree inhibits the spread of concentration across the vertices of the graph more than the vertex $w$. In fact, we can observe that indeed $t_{c}\left(v\right) > t_{c}\left(w\right)$, confirming that this hub as the navigational bottleneck of the graph.

The previous example teaches us that such generalizations as "the hubs facilitate/inhibit" the dynamical spread of "information" across a network are not necessarily correct and they depend on the topological position of the hubs in the graph. For instance, when the hubs are directly connected or very close to each other, like in the cases of graphs $\mathcal{G}_{1}$ and $\mathcal{G}_{2}$, they have the capacity of spreading a lot of information between each other, avoiding the creation of a potential navigational bottleneck at them. However, if the hubs are not close together but separated by relatively large paths, like in the case of graph $\mathcal{G}_{3}$, they lose this capacity of alleviating the traffic by sending information among them. In this case they become navigational bottlenecks, inhibiting the spread of information between vertices in the graph.

4.   The geometry of navigational bottlenecks

Definition 7. Let $\tilde{\varLambda}$ be the $\left(n-1\right)\times\left(n-1\right)$ diagonal matrix obtained by removing the row and column of $\varLambda$ corresponding to $\lambda_{1}$ and let $\tilde{U}$ be the $\left(n\right)\times\left(n-1\right)$ matrix resulting from removing the column of $U$ corresponding to $\psi_{1}.$ Let us define the matrix $\tilde{G} = \tilde{U}e^{\tilde{\varLambda}}\tilde{U}^{T}$.

Lemma 8. The matrix $\tilde{G}$ is positive semidefinite.

Proof. Let $z$ be a nonzero column vector of length $n$. Then,

where $\lambda_{j}$ is an eigenvalue of $A$ and $\psi_{ju}$ is the $u$th entry of the eigenvector corresponding to $\lambda_{j}$. The term in parentheses is zero if and only if $z = \psi_{1}$, where $\psi_{1}$ is the eigenvector associated with the spectral radius of $A$. Because the eigenvectors are orthogonalized it happens that $\psi_{1}^{T}\psi_{j} = 0$ for all $j\geq2$, which proves the result. □

Remark 9. It is easy to realize that $\tilde{G}_{uu} = X_{u}.$ That is,

Also notice that $\tilde{U}e^{\tilde{\varLambda}}\tilde{U}^{T}\neq e^{\tilde{U}\tilde{\varLambda}\tilde{U}^{T}} = e^{\tilde{A}},$ where $\tilde{A}: = \tilde{U}\tilde{\varLambda}\tilde{U}^{T}$.

Let us now interpret the term $\tilde{G}_{uv}$. As we have seen in Remark 2, $\underset{t\rightarrow \infty}{\lim}C_{v}\left(t\right) = \psi_{1, u}\psi_{1, v}$, which is the amount of items diffused to vertex $v$ when the initial concentration is completely localized at vertex $u$ in the NC diffusion that we are considering in this work. If we obtain the concentration $C_{v}\left(t = 1\right)$ under the same conditions, we obtain:

where $G_{uv}$ is the communicability function ^[67,68] between the two vertices. Therefore,

which means that $\tilde{G}_{uv}$ is proportional to the amount of items diffused from $u$ to $v$ at an early time of the process minus the amount that arrives at $v$ at the steady state. In other words, it is a measure of the rate of transfer from $u$ to $v$ when the whole initial concentration is at the first vertex. The largest $\tilde{G}_{uv}$ indicates a larger capacity for delivering items from the two vertices (due to the non-directionality of the graphs) as the NC diffusion evolves. We now have the following.

Definition 10. Let $\tilde{G}$ be defined as before, and let us define

Notice that while $\tilde{G}_{uu}$ and $\tilde{G}_{vv}$ give the capacity of the vertices to create navigational bottlenecks, the term $\tilde{G}_{uv}$ is a measure of how good transmission exists between the two vertices. Thus, a large value of $Y_{uv}$ indicates that items can easily get trapped at the vertices $u$ and $v$ because both vertices are potential navigational bottlenecks and they do not have a large capacity of diffusing the items among them. A relatively low value of this measure indicates a good capacity for delivering the items between the two vertices at an early time of the NC process, such that there would not be a bottleneck among them. We now prove the following result.

Lemma 11. $Y_{uv}$ is a squared Euclidean distance between the vertices $u$ and $v$ of $G$.

Proof. Let us write

which proves that $Y_{uv}\geq0$ as required for a distance.

Let us now define $\tilde{\varphi}_{u}: = \left[\psi_{2, v}, \ldots, \psi_{n, v}\right]^{T},$ such that we can write

Then, because $e^{\tilde{\varLambda}}$ is positive definite we can find its square root and express:

Finally, by defining $\tilde{x}_{u}: = e^{\tilde{\varLambda}/2}\tilde{\varphi}_{u}$ we have

□

Theorem 12. Let $G_{1}$ be the graph described in Figure 3.1 on $n$ vertices in which the vertices $v$ and $v'$ are the two ones with degree $n-1$ and the vertices $u$ and $u'$ are any two of the vertices of degree two. Then,

Proof. We have proved before that the eigenvalues of $A\left(G_{1}\right)$ are:

with $\alpha: = \sqrt{8n-15}.$ Let $\varphi_{i} = \left[\psi_{1, i}, \psi_{2, i}, \ldots, \psi_{n, i}\right]^{T}.$ Then,

where $0_{n-3}$ is a column of zeros of length $n-3$ and $\varrho{}_{n-3}$ is a vector of length $n-3$ giving a different value for the different $u$ vertices of $A_{n}$. By using this information it is straightforward to obtain:

We then obtain $Y_{vv'}\left(\mathcal{G}_{1}\right) = 2\tilde{G}_{vv}\left(\mathcal{G}_{1}\right)-2\tilde{G}_{vv'}\left(\mathcal{G}_{1}\right)$, $Y_{uu'}\left(\mathcal{G}_{1}\right) = 2\tilde{G}_{uu}\left(\mathcal{G}_{1}\right)-2\tilde{G}_{uu}\left(\mathcal{G}_{1}\right)$, and $Y_{uv}\left(\mathcal{G}_{1}\right) = \tilde{G}_{uu}\left(\mathcal{G}_{1}\right)+\tilde{G}_{vv}\left(\mathcal{G}_{1}\right)-2\tilde{G}_{uv}\left(\mathcal{G}_{1}\right)$, by substitution and further algebraic simplification to prove the result. □

Theorem 13. Let $\mathcal{G}_{2}$ be the graph described in Figure 3.1 on $n$ vertices in which the vertices $v$ and $v'$ are the two ones with degree $n-1$ and the vertices $u$ and $u'$ are any two of the vertices of degree two. Then,

Proof. We start by finding $Y_{v, v'}\left(\mathcal{G}_{2}\right) = 2\tilde{G}_{vv}\left(\mathcal{G}_{2}\right)-2\tilde{G}_{vv'}\left(\mathcal{G}_{2}\right)$ for which we have to find the second term. That is,

Therefore, $Y_{v, v'}\left(\mathcal{G}_{2}\right) = 2\left(\dfrac{1}{4}e^{-\beta}+\dfrac{1}{2}\right)-2\left(\dfrac{1}{4}e^{-\beta}-\dfrac{1}{2}\right),$ which proves this part of the result.

Similarly, for $Y_{w, w'}\left(\mathcal{G}_{2}\right) = 2\tilde{G}_{ww}\left(\mathcal{G}_{2}\right)-2\tilde{G}_{ww'}\left(\mathcal{G}_{2}\right)$ we find

which by considering that $\sum_{2\leq j\leq n-1}\psi_{j, w}\psi_{j, w'} = -2\psi_{1, w}^{2}$ give $\tilde{G}_{ww'}\left(\mathcal{G}_{2}\right) = \dfrac{e^{-\beta}}{\beta^{2}}-\dfrac{1}{n-2}.$ Therefore, $Y_{w, w'}\left(\mathcal{G}_{2}\right) = \dfrac{e^{-\beta}}{n-2}+2\dfrac{n-3}{n-2}-\dfrac{e^{-\beta}}{n-2}+\dfrac{2}{n-2},$ which proves this part of the result.

Finally, we have $Y_{v, w}\left(\mathcal{G}_{2}\right) = \tilde{G}_{vv}\left(\mathcal{G}_{2}\right)+\tilde{G}_{ww}\left(\mathcal{G}_{2}\right)-2\tilde{G}_{vw}\left(\mathcal{G}_{2}\right)$ for which we find first

such that $Y_{v, w}\left(\mathcal{G}_{2}\right) = \dfrac{e^{-\beta}}{4}+\dfrac{1}{2}+\dfrac{e^{-\beta}}{\beta^{2}}+\dfrac{n-3}{n-2}+\dfrac{2e^{-\beta}}{2\beta}$, which, after simplifications, reduces to the final result. □

The most important consequence of the previous two results is the fact that the distance between the two hubs in $\mathcal{G}_{1}$ and $\mathcal{G}_{2}$ is constant and independent of the size of the graphs. That is, $Y_{v, v'}\left(\mathcal{G}_{1}\right) = \dfrac{2}{e}\approx0.7358$ and $Y_{v, v'}\left(\mathcal{G}_{2}\right) = 2$, which indicates that in $\mathcal{G}_{1}$, where the hubs are connected, the communication is very good and the $Y$-distance is smaller than the shortest path between the two hubs. In the case of $\mathcal{G}_{2}$, where the two hubs are separated at distance two, the communication between them is still good, but in this case the $Y$-distance is identical to the shortest path. To further investigate this phenomenon, we prove the following result for $Y_{v, v'}\left(\mathcal{G}_{3}\right).$ In this graph, there are six different distances between pairs of vertices, so we will focus only on the $Y$-distance between the two hubs.

Theorem 14. Let $\mathcal{G}_{3}$ be the graph described in Figure 3.1 on $n$ vertices in which the vertices $v$ and $v'$ are the two ones with degree $n-1$ and the vertices $u$ and $u'$ are any two of the vertices of degree two. Then,

where $\gamma = \sqrt{2n-3}$.

Proof. The $Y$-distance between the two hubs in $G_{3}$ is $Y_{v, v'}\left(G_{3}\right) = 2X_{v, v}\left(G_{3}\right)-2X_{v, v'}\left(G_{3}\right).$ Thus, we have to obtain $X_{v, v'}\left(G_{3}\right)$ as:

Then, by using $X_{v}\left(\mathcal{G}_{3}\right) = \dfrac{e^{\gamma}\left(\gamma+1\right)+e\left(\gamma+1\right)+\tau-1}{4\gamma}e^{-1/2\left(\gamma+1\right)}$ from Lemma 6, after some algebraic work, we obtain the result. □

Remark 15. The previous results help us to interpret the differences in the propensities to create navigational bottlenecks of vertices in the graphs $\mathcal{G}_{1},$ $\mathcal{G}_{2}$ and $\mathcal{G}_{3}$. Let us consider $n = 10$ for an example. In this case $Y_{v, v'}\left(\mathcal{G}_{1}\right)\approx0.7359$, $Y_{v, v'}\left(\mathcal{G}_{2}\right) = 2$, and $Y_{v, v'}\left(\mathcal{G}_{3}\right)\approx5.9807$. Notice that the shortest path distances between these two vertices are one, two, and three, respectively. However, while the $Y$-distance between the two hubs remains constant in $\mathcal{G}_{1},$ and $\mathcal{G}_{2}$, it grows very quickly with size in $\mathcal{G}_{3}$. This indicates that if we allocate a diffusive particle at the vertex $v$ in $\mathcal{G}_{1}$ or $\mathcal{G}_{2}$, in a situation where the graph is susceptible to jamming due to its capacity, this vertex still has a large capacity for spreading this particle to the other hub, $v'$, avoiding the creation of a navigational bottleneck at $v$. This is the reason why in $\mathcal{G}_{1},$ and $\mathcal{G}_{2}$, the propensity to be a navigational bottleneck is higher in vertex $w$ than in vertex $v$. However, when we consider the graph $\mathcal{G}_{3}$, the large value of $Y_{v, v'}\left(\mathcal{G}_{3}\right)$ indicates that the capacity of vertex $v$ to spread a diffusive particle to the other hub is very much diminished. Therefore, the hubs have a larger propensity to be navigational bottlenecks in $\mathcal{G}_{3}$ than in $\mathcal{G}_{1}$ or $\mathcal{G}_{2}$, and consequently, as we have proven analytically, it has a higher propensity to be a bottleneck than the vertex $w$.

5.   Navigational bottlenecks and real-world networks

5.1.   How to use the concept of navigational bottleneck?

Every time a new index characterizing a topological property of networks or their parts is introduced, it is desirable to confront it with real-world situations that help us understand how to use it in an appropriate way. In this subsection, we confront the index $X$ with the problem of traffic congestion in a real-world network. Unfortunately, there is no experimental data about congestion in networks apart from those related to the problem of urban traffic in cities. This particular problem is very complex, and many approaches exist in the literature to tackle it ^{[47,48,49,50,51,52,53,54,55]}. In one of these papers, Samani et al. ^[69] have combined data-driven approaches with mathematical modeling to estimate the non-congestion probability of every street in the city of Sioux Falls in South Dakota, USA. The network is formed by 24 street intersections which form the vertices of the graph and 38 streets forming its edges. The authors also provide the origin-destination travel demand $D_{ij}$ and calculated the non-congestion probability $P_{ij}$ for every street connecting intersections $i$ and $j$. The representation of the network can be seen in Figure 5.1.

Our current approach is based on the propensity of intersections, more than streets, to get congested if we allocate a significant amount of diffusive particles to them. Therefore, we start by converting the data produced by Samani et al. ^[69] into information reliable to be compared with the $X$ index. First, we compute the global demand $D_{i}$ at intersection $i$ as: $D_{i} = \sum_{j}D_{ij}$. We also obtained the average probability of observing congestion at the streets intersecting at $i$ as $P_{i} = \dfrac{1}{k}\sum_{j = 1}^{k}P_{ij}$. We then consider that an intersection has a low probability of congestion if $P_{i} < 0.333$ and it has a high probability of congestion otherwise. We found that nine intersections are classified as low congestion, with an average probability equal to 0.125, with only two values over 0.2. On the other hand, there are 15 intersections of high congestion in this city. The average probability of of these 15 intersections is 0.567, of which there are five intersections with a probability higher than 0.5.

In Figure 5.2, we plot the values of the global demand of every intersection versus their $X$ indices. Every intersection is then drawn in the $x, y$-plane as a point with size and color proportional to its average congestion probability. A linear discriminant analysis (LDA) clearly separates the two groups of intersections, leaving only four ones incorrectly classified, i.e., a classification accuracy of 83.3%. As can be seen in Figure 5.2, the intersections with relatively low values of $X$ display a low probability of congestion particularly when their traffic demand is also low. On the other hand, the intersections with relatively large values of $X$ tend to have a larger congestion probability, particularly if they have a relatively large traffic demand.

The important message of this exercise is that the $X$ index identifies the vertices in a graph that have a large propensity to get congested if (and this is a very important if) the amount of diffusive particles allocated at that vertex is significantly large. Therefore, in a real-world situation, like the study of urban traffic congestion, this index should be used accompanied by indicators of the demand of traffic at the corresponding vertices. The $X$ itself teaches us about the topological propensity of a vertex to get congested, but such congestion will depend on the amount of traffic allocated to it. Let us illustrate this point with an example. The intersection number 3 in Sioux Falls has a large value of $X$, i.e., it has the third largest value of this index in this network. However, the traffic data indicates that this intersection has a congestion probability of 0.0033. The reason is not that the index $X$ fails when identifying this intersection as one with large propensity of getting congested but that the traffic demand on it is extremely low, i.e., the lowest in the whole network. On the other extreme, we have the intersection 10, which has the highest demand in the whole network. However, it has only the fifth-highest congestion probability, mainly because, as identified by the $X$ index, it has a large capacity to deliver traffic across the network, i.e., it has a relatively low value of the $X$ index.

As a final proof of concept we ask whether the $X$ index, which characterizes the propensity of a vertex to get congested, somehow reflects the different capacities of the edges to get congested, which is what is really measured by $P_{ij}$ in Samani et al. ^[69]. For this, we selected the vertex 8 which is the one having the largest value of $X,$ i.e., $X_{8}\approx3.2545$. We then change the "length" of the edges which are incident with this vertex in the network. That is, instead of having $A\left(8, i\right) = A\left(i, 8\right) = 1$ in the adjacency matrix, we change this values to $A\left(8, i\right) = A\left(i, 8\right) = 1/2$. This is equivalent to reduce the length of the corresponding street, increasing its capacity to deliver traffic to its nearest intersection. Samani et al. ^[69] performed a similar exercise by increasing the width of streets, which is mathematically equivalent to what we are doing here. After dropping the value of the edge $\left\{ 8, 6\right\}$ to 0.5 we obtain $X_{8}\left(\mathcal{G}-\left\{ 8, 6\right\} \right) = 2.7989$. Doing the same for the rest of edges incident with vertex 8 we get: $X_{8}\left(\mathcal{G}-\left\{ 8, 7\right\} \right) = 2.8483$, $X_{8}\left(\mathcal{G}-\left\{ 8, 9\right\} \right) = 2.9412$, and $X_{8}\left(\mathcal{G}-\left\{ 8, 16\right\} \right) = 3.0689$. These results indicate that the edge contributing the most to the high value of $X_{8}$ corresponds to the street $\left\{ 8, 6\right\}$ which is the one having the highest probability of congestion of all the streets in the city according to the results of Samani et al. ^[69]. It is followed by street $\left\{ 8, 7\right\}$ which is the one having the second highest congestion probability among all streets incident to intersection 8. Therefore, this experiment reveals that the topological indication about the potential congestion of vertices in a network as developed here matches some of the situations observed in the real-world, so it can be used in the subsequent analysis of complex systems.

5.2.   Applications in the context of complex systems

We will start this section by studying three types of real-world networks (see ^[1] for more details about these networks). The first example is the representation of the airport transportation network of US, where the 332 vertices represent the airports in the continental USA, Alaska, and overseas places, and the 2,126 edges represent the existence of connecting flights between the airports. The hubs of the USA air transportation network are: Chicago O'Hare Int. (degree 139), Dallas/Fort Worth (degree 118), Hartsfield-Jackson Atlanta International Airport (degree 101), Pittsburg Int. (degree 94) and Lambert-St. Louis Int. (degree 94). All these airports are directly connected to each other forming a clique in the network. There are, of course, many other airports connected to pairs of these hubs, forming a structure similar to the one of the graph $\mathcal{G}_{1}$ in Figure 3.1. In the second class, we include the neuronal network of C. elegans, where 277 neurons of this worm are represented as vertices, and its 1,918 synaptic connections are accounted by means of edges. The top five hubs in this network represent the neurons AVAL (degree 76), AVAR (degree 74), AVER (degree 54), AVDR (degree 53), AVBR (degree 52), AVEL (degree 52) and PVCR (degree 52). The mean separation between these hubs is 1.28, with 6 pairs that are connected only via a path of length 2. We can consider these networks as examples of the class represented by the toy graph $\mathcal{G}_{2}$ in Figure 3.1. Finally, the third class is formed by two urban street networks representing the central area of São Paulo city and downtown Atlanta, which are illustrated in Figure 5.3. The nodes represent intersections and endpoints, while the edges represent the roads and streets. We obtain all data via the Python module OSMNx ^[63]. The obtained graph is simplified to undirected, unweighted, and without self-loops. The hubs in the urban street networks are intersections having connections to 6 or 5 other vertices. In the case of the city of São Paulo, the average separation between every pair of hubs is 19.3, and in the case of the city of Atlanta, it is 20.6. Every pair of hubs is separated by very long paths in these cities, which is similar to what happens in the case of the graph $\mathcal{G}_{3}$ in Figure 3.1.

We start our analysis by considering the network representing the US airport system. In Figure 5.4(a), we illustrate the network of US airports representing them with sizes proportional to their $X_{i}$ values. The top ten airports in this ranking are (their degrees are in parenthesis): Salt Lake City Intl. (59); Portland Intl. (41); Stapleton Intl. (85); Raleigh-Durham Intl. (50); Seattle-Tacoma Intl. (57); Ontario Intl. (23); Sacramento Metropolitan (23); San Francisco Intl. (68); Metropolitan Oakland Intl. (20); Phoenix Sky Harbor Intl. (60). Therefore, the average degree of these airports is 48.6, and they do not include the main hubs of the network, although they are in the top 50 most connected airports. This confirms our previous hypothesis that this network behaves similarly to the one represented by the graph $\mathcal{G}_{1}$ in Figure 3.1. Let us consider the airport of Salt Lake City Int.; which is the one showing the highest $X$ index. When we consider the distance $Y_{uv}$ which measures the quality of communication when there is a jam at the corresponding airport, the closest airports from Salt Lake City are Stapleton Intl.; Portland Intl.; Seattle-Tacoma Intl.; Ontario Intl.; San Francisco Intl.; Phoenix Sky Harbor Intl.; Sacramento Metropolitan.; Metropolitan Oakland Intl.; San Diego Intl.; Lindbergh Fld; San Jose Intl. All of which have direct flights to Salt Lake City and are also surrounding a relatively close area to that airport as can be seen in Figure 5.4(b). On the contrary, the most distant airports are: Raleigh-Durham Intl.; La Guardia; Washington National; Charlotte Douglas Intl.; Newark Intl; Bradley Intl.; Baltimore-Washington Intl.; Palm Beach Intl.; Fort Lauderdale Hollywood Intl.; Philadelphia Intl. All of them are on the east coast of the USA. Contrastingly, in normal conditions, as measured by the communicability distances $\xi_{uv}$, the airports which are better communication with the one of Salt Lake City are: General Mitchell Intl.; Louis Armstrong New Orleans International Airport; Fort Lauderdale-Hollywood Intl; Kansas City Intl; Raleigh-Durham Intl; Port Columbus Intl; Seattle-Tacoma Intl. Those in poor communication with it are mainly airports in Alaska or in the Pacific: Tuntutuliak; Kongiganak; Kwigillingok; Napaskiak; Napakiak; Eek; Quinhagak; West Tinian. Consequently, the current results indicate that in a situation of navigational vulnerability the airport of Salt Lake City represents a potential bottleneck, which will stay well communicated only with those nearby it and will dramatically diminish its communicability with those on the East Coast of the US.

We now investigate the network which resembles the graph $\mathcal{G}_{2}$ Figure 3.1. In Figure 5.5(a), we illustrate the values of $X$ for every neuron in C. elegans representing them proportionally to the color and size of the vertices of the neuronal network. The average degree of the neurons in the top ten of the $X$ ranking is 24.1. The two neurons identified with the highest propensity to become navigability bottlenecks are Ring Interneuron A Right (RIAR) (degree 35) and Ring Interneuron A Left (RIAL) (degree 30), which are located on the head of the worm and form part of the "second layer" interneurons in the process of integration of information from the outside world and the inner state of the animal, which then leads to a behavioral response. None of the neurons with the largest values of the $X$ index is among the main hubs of this network, as we would expect from its resemblance to the toy model provided by the graph $\mathcal{G}_{2}$ in Figure 3.1. In panel (b), we illustrate again the communicability distance from the RIAR neuron (very similar results for RIAL) to the rest of the neurons. The shortest communicability distances between RIAL and RIAR are with the neurons located in the lateral ganglia of the head (ASHL, AIZD), the head (RMGL), left lumbar ganglia (PQR) and retrovesicular ganglion of head (AVF). They have a variety of functions, like the main nociceptor being a center of hub-and-spoke circuit, and integration of information, among others. The longest communicability distance is with command interneurons AVAR, AVAL, AVBR and AVBL, all located in the lateral ganglia of the head. When considering the $Y$-distance (see panel (c) of Figure 5.5) the largest proximity is to neurons located in the head, such as RIH, RMDR, and RMDL, as well as among themselves, i.e., a short distance between RIAL and RIAR. The neurons of the group RMD regulate the spontaneous foraging movements in the worm. On the other hand, the longest $Y$-distances are with neurons located in the tail or lumbar ganglion, such as PVCR, PVCL, PVNR, PVNL, or in the lateral ganglia of the head (AVDR and AVDL), which are all command interneurons. These results point out the possibility that certain navigational bottlenecks at the RIA neurons, which are involved in processing information from outside, limit their diffusive communication only to neurons located in the head and affect more significantly the communication with farthest away neurons which are involved in locomotion.

We now consider the two urban street networks described before. The plots in Figure 5.6 illustrate the $X$ indices associated with each node in the urban street networks in both cities. We point to the vertices with the two highest $X$, which are marked as $A$ and $B$, respectively. As we have mentioned before, the urban street networks have the largest degrees of 6 or 5, which are separated by about 20 streets as average from each other. This is a characteristic feature of the graphs of the class of $G_{3}$ in Figure 3.1. Therefore, it is expected that the intersections with the largest values of $X$ are those with the largest degree. Indeed, in the city of Atlanta, the vertices marked as $A$ and $B$ both have degree 6, and in São Paulo they have degrees 5 and 6.

The separation between the two vertices with the largest $X$ values, which coincide with the hubs in both urban street networks, is of 24 street legs in Atlanta and 20 in São Paulo. In Atlanta there are 31 different paths of 25 street legs which connect both hubs (see Figure 5.7(a)) and in São Paulo there are 37 paths of length 21 between the vertices $A$ and $B$ as illustrated in Figure 5.7(b). Therefore, the two urban street networks studied here, which can be thought of as representatives of their class of networks, correspond to the class of networks in which the hubs are separated by a relatively large shortest path distance, for which the graph $G_{3}$ in Figure 3.1 serves as a toy model.

Finally, to understand the reasons why the intersections $A$ and $B$ are the ones with the highest risk of becoming navigational bottlenecks in the cities of Atlanta and São Paulo we investigate the $Y$-distances from these intersections to the rest of the vertices in their respective urban street networks. The results are illustrated in Figure 5.8. As can be seen in the figure, the $Y$-distance from the intersections $A$ and $B$ in both cities is significant only to a close neighborhood of these vertices and not to any intersection relatively distant from them. If we remember what we observed for the toy graph $G_{3}$ in Figure 3.1, the $Y$-distance between the two hubs in this graph was significantly larger than the shortest path distance connecting them. That is, the two hubs were in poor communication. This resulted in the fact that if one of the hubs is jammed, it loses its capacity to deliver traffic to the other one, increasing the probability of remaining jammed. This is exactly what happens in the intersections $A$ and $B,$ whose $Y$-distance is extremely large in these two cities, as can be seen in the plots of Figure 5.8. It is remarkable to realize that in Atlanta, the intersection $A$ connects six roads categorized as two avenues, three boulevards, and one residential, and the intersection $B$ has a traffic light and connects six roads, categorized as an avenue link, three boulevards, and a road that connects neighborhoods. In the case of São Paulo the intersection $A$ has six roads connecting it, one of which is a link to one of the most critical avenues in the city, while the other five interconnect neighborhoods. The intersection $B$ connects five roads, two of them are avenues; one links to an avenue, and two others connect neighborhoods.

6.   Conclusions

The networked structure of complex systems facilitates the spread of information between the entities that compose the system. Therefore, detecting potential bottlenecks inhibiting the information spreading in these networks is of great practical relevance for the study of complex systems. Additionally, the problem is far from trivial if approached from a structure-dynamics perspective. That is, we are interested in finding vertices and edges that potentially inhibit information spreading by analyzing the network structure without the necessity of performing intensive simulations of the dynamics of interest. For that purpose we have obtained a first principles connection between the NC diffusion on a network and functions of the adjacency matrix representing their structure. In this way we measure the capacity of every vertex in a network to spread the diffusive particles across the network in a short time. This approach allows one to identify those vertices which are potential navigational bottlenecks due to their diminished capacity to spread information through the network. We have shown here how this approach can be used to study analytically the problem using algebraic graph-theoretic approaches gaining many insights about the different situations in which a vertex can be a potential navigational bottleneck. More interestingly, our approach connects this topic with that of Euclidean distance matrix analysis creating a mathematical framework for the analysis of navigational bottlenecks in networks. Our results are confirmed by studying several real-world networks, such as a neuronal system, an air transportation network and two urban street networks. All in all, the current approach represents a step-forward in our understanding of the structure-dynamics relations in complex networks, which is one of the foundational goals of this discipline.

Author contributions

Ernesto Estrada: Conceptualization, formal analysis, proofs and theorems, writing, methodology, applications, review, and validation; Giovanni Soares: Conceptualization, writing, methodology, simulations, cities applications, review, editing, and validation. All authors have read and approved the final version of the manuscript for publication.

Use of AI tools declaration

The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgments

EE acknowledges funding from Ministerio de Ciencia e Innovacion, Agencia Estatal de Investigacion Program for Units of Excellences Maria de Maeztu (CEX2021−001164-M/10.13039/501100011033).

GGS acknowledges the funding of projects 446053/2023-6 and 140196/2022-6 CNPq (Brazil) and CAPES-PRINT project 88887.900891/2023-00.

Conflict of interest

All authors declare no conflicts of interest in this paper.