Speaker
Description
Complex systems of interacting components are often modeled by a graph consisting of a set of nodes and edges, where each edge is equipped with a positive weight. Examples of such graphs include transportation networks, such as road and airline networks; see, e.g., [1,2]. Assume that the network is undirected and connected, which implies that the associated adjacency matrix $A$ is symmetric, irreducible, and nonnegative, while the associated graph Laplacian matrix $L=D-A$, with $D$ being the degree matrix, is symmetric, positive semidefinite, and has a one-dimensional null space. Two spectral quantities are particularly significant in network analysis: the spectral radius $\rho$ of $A$, known as the Perron value, and the second smallest eigenvalue $\mu$ of $L$, referred to as the Fiedler value. Specifically, the unique eigenvector of unit Euclidean norm with positive entries associated with $\rho$, i.e., the Perron vector, is used for node ranking, while the eigenvector of unit norm associated with $\mu$, i.e., the Fiedler vector, is used to infer a natural bipartition of the graph based on the signs of its entries; see, e.g., [3,4,5,6]. One can estimate the change of the Perron and Fiedler values for a connected network when the weight of an edge is perturbed by analyzing relevant entries of the Perron and Fiedler vectors. This is helpful for identifying edges whose weight perturbation causes the largest change in $\rho$ and $\mu$. For such structured perturbation analysis to be reliable, it is also important that the Perron and Fiedler vectors are not overly sensitive to perturbations. Applications of the perturbation analysis include the identification of edges that are critical for the structural robustness of the network.
References
-
Estrada, E.: The Structure of Complex Networks: Theory and Applications, https://doi.org/10.1093/acprof:oso/9780199591756.001.0001, (2011).
-
Newman, M.E.J.: Networks: An Introduction, https://doi.org/10.1093/acprof:oso/9780199206650.001.0001, (2010).
-
Berman, A., Plemmons, R.J.: Nonnegative matrices in the mathematical sciences, https://epubs.siam.org/doi/book/10.1137/1.9781611971262, (1994).
-
Bonacich, P.: Power and centrality: a family of measures, https://doi.org/10.1086/228631, (1987).
-
Fiedler, M.: Algebraic connectivity of Graphs, https://eudml.org/doc/12723, (1973).
-
Fiedler, M.: A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory, https://eudml.org/doc/12900, (1975).
