Speaker
Description
Multilayer networks are often used to model systems where entities are connected in multiple ways simultaneously, capturing the complexity of real-world relationships better than traditional single-layer networks [1]. The dynamical evolution of a complex system over time can be described through a particular interlayer structure. The extent to which properties of evolving networks can be represented by a multilayer has been thoroughly examined in the literature ([2,3]).
The key idea of our project stems from the application of complex network theory to the
analysis of a zonal water system, in this case the water distribution network
of the Emilia Romagna region. The ability of water networked systems to
continue to supply water when components are damaged or fail is a central
topic in the water system design and analysis. This feature of water systems is
related to the connectivity of the internal components of the system (pipes and
reserves). In this particular case, we
assumed the network to be undirected, which implies its adjacency matrix to
be symmetric.
One important feature of our data set is a detailed account of all the pipe
breakages in the water system over the course of time, from a few hours up to many months. To appropriately track the phenomenon, we propose to model breakages as low-rank modifications of the edge adjacency matrix of a water network within a time-aware block influence matrix.
Let $\{G_\ell\}_{\ell=1\dots L}$ be a sequence of discrete time evolving graphs, $G_\ell=(V,E_\ell)$, where, for each $\ell$, $V$ are the vertices and $E_\ell$ are the edges, while $L$ is the number of time units. The composition of edges changes with time. Let $A_\ell$ be edge adjacency matrix of each $G_\ell$ and let $N$ be the number of edges of the full network, so that $A_\ell$ is $N\times N$. To strengthen the impact of the edge modification in time, by also keeping track of this network change in the upper diagonal block as follows:
$$
{\cal M}=
\begin{pmatrix}
A_1&W_1&0&\dots&0\\
0& A_2&W_2&\dots&0 \\
0 & 0&A_3 & \ddots&\vdots \\
\vdots & \vdots&\dots & \ddots&W_{L-1} \\
0 & 0 &\dots&\dots& A_L
\end{pmatrix}
\in \mathbb{R}^{NL\times NL} ,
$$
where $W_\ell=A_{\ell+1}-A_\ell$, $\ell=1, \ldots, L-1$. If the graph loses one or more edges at time $\ell$ (i.e. one or more pipes break), the corresponding nodes in the edge adjacency matrix will be removed, and thus $W_\ell$ will represent the rows and columns associated with the removed nodes. The chosen centrality measure is the Katz centrality $c=(I-\alpha {\cal M})^{-1}{ 1}$, with $\alpha<\frac{1}{\max_{\ell}\rho(A_\ell)}$ and ${1}\in\mathbb{R}^{NL}$ the vector of all ones [4]. Reshape the vector $ c$ as a matrix $C$ of size $N\times L$, and consider the index $i$ at time $\ell$, that is:
$ C(i,\ell)=e_{(\ell-1)N+i}^T { c}=e_{(\ell-1)N+i}^T
(I-\alpha {\cal M})^{-1}{1},$
where $e_k$ is the $k$th column of the identity matrix of size $NL$.
$C(i,\ell)$ is the Katz index related to the node $i$ at time $\ell$.
The $\textit{Katz marginal centrality}$ is the mean of all Katz centrality values of edge $i$ over all time layers, that is
$$
KMN(i)=\frac{1}{L}\sum_{\ell=1}^L { C}(i,\ell).
$$
In order to recover the marginal Katz centralities, the computation of the vector $ c$ is required.
For very large networks, for each edge $i$ the KMN index could be obtained by only *approximately* solving the large linear system of size $NL\times NL$. To do so, we could employ well established computational methods such as BICGstab [5]. However, we can make use of the special structure of the inverse matrix to gain some computational advance.
Let $K(A_\ell)=(I-\alpha A_\ell)^{-1}$, for $\ell=1,\dots,L$.
For instance, for $L=4$, the block structure of the matrix $K(\mathcal{M})=(I-\alpha \mathcal{M})^{-1}$ is:
$$
{\scriptsize
K({\mathcal{M}})=
\begin{bmatrix}
K(A_1)&K(A_2)-K(A_1)&K(A_1)W_1(K(A_3)-K(A_2))&(K(A_2)-K(A_1))W_1(K(A_4)-K(A_3))\\
0&K(A_2)&K(A_3)-K(A_2)&K(A_2)W_2(K(A_4)-K(A_3)) \\
0&0&K(A_3) & K(A_4)-K(A_3)\\
0&0&0&K(A_4)
\end{bmatrix}.}
$$
By a truncation of the matrix at the first super-diagonal block, we can solve the linear system by solving $L-1$ linear systems in parallel on the diagonal blocks of the matrix. We provide theoretical results on the
decay of the off-diagonal entries that justify this truncation.
References
1.Kivela, M., Arenas, A., Barthelemy, M., Gleeson, J. P., Moreno, Y., & Porter, M. A. (2014). Multilayer networks. Journal of Complex Networks, 2(3), 203–271. https://doi.org/10.1093/comnet/cnu016
2.Fenu, C., & Higham, D. J. (2017). Block Matrix Formulations for Evolving Networks. SIAM Journal on Matrix Analysis and Applications, 38(2), 343–360. https://doi.org/10.1137/16m1076988
3.Bergermann, K., & Stoll, M. (2022). Fast computation of matrix function-based centrality measures for layer-coupled multiplex networks. Physical Review E, 105(3). https://doi.org/10.1103/physreve.105.034305
4.Katz, L. (1953). A New Status Index Derived from Sociometric Analysis.
Psychometrika, 18(1), 39–43. https://doi.org/10.1007/bf02289026
5.van der Vorst, H. A. (1992). Bi-CGSTAB: A Fast and Smoothly Converging Variant of Bi-CG for the Solution of Nonsymmetric Linear Systems. SIAM Journal on Scientific and Statistical Computing, 13(2), 631–644. https://doi.org/10.1137/0913035
6.Taylor, D., Myers, S. A., Clauset, A., Porter, M. A., & Mucha, P. J. (2017). Eigenvector-Based Centrality Measures for Temporal Networks. Multiscale Modeling & Simulation, 15(1), 537–574. https://doi.org/10.1137/16m1066142
