Michele Benzi

Michele Benzi, Christine Klymko

We examine a node centrality measure based on the notion of total communicability, defined in terms of the row sums of the exponential of the adjacency matrix of the network. We argue that this is a natural metric for ranking nodes in a network, and we point out that it can be computed very rapidly even in the case of large networks. Furthermore, we propose the total sum of node communicabilities as a useful measure of network connectivity. Extensive numerical studies are conducted in order to compare this centrality measure with the closely related ones of subgraph centrality [E. Estrada and J. A. Rodriguez-Velazquez, Phys. Rev. E, 71 (2005), 056103] and Katz centrality [L. Katz, Psychometrica, 18 (1953), pp. 39-43]. Both synthetic and real-world networks are used in the computations.

Michele Benzi, Paola Boito, Nader Razouk

Motivated by applications in quantum chemistry and solid state physics, we apply general results from approximation theory and matrix analysis to the study of the decay properties of spectral projectors associated with large and sparse Hermitian matrices. Our theory leads to a rigorous proof of the exponential off-diagonal decay ("nearsightedness") for the density matrix of gapped systems at zero electronic temperature in both orthogonal and non-orthogonal representations, thus providing a firm theoretical basis for the possibility of linear scaling methods in electronic structure calculations for non-metallic systems. We further discuss the case of density matrices for metallic systems at positive electronic temperature. A few other possible applications are also discussed.

Michele Benzi, Valeria Simoncini

We consider the numerical approximation of $f({\cal A})b$ where $b\in{\mathbb R}^{N}$ and $\cal A$ is the sum of Kronecker products, that is ${\cal A}=M_2 \otimes I + I \otimes M_1\in{\mathbb R}^{N\times N}$. Here $f$ is a regular function such that $f({\cal A})$ is well defined. We derive a computational strategy that significantly lowers the memory requirements and computational efforts of the standard approximations, with special emphasis on the exponential function, for which the new procedure becomes particularly advantageous. Our findings are illustrated by numerical experiments with typical functions used in applications.

Francesca Arrigo, Michele Benzi, Caterina Fenu

We develop numerical algorithms for the efficient evaluation of quantities associated with generalized matrix functions [J. B. Hawkins and A. Ben-Israel, Linear and Multilinear Algebra 1(2), 1973, pp. 163-171]. Our algorithms are based on Gaussian quadrature and Golub--Kahan bidiagonalization. Block variants are also investigated. Numerical experiments are performed to illustrate the effectiveness and efficiency of our techniques in computing generalized matrix functions arising in the analysis of networks.

Francesca Arrigo, Michele Benzi

We introduce new broadcast and receive communicability indices that can be used as global measures of how effectively information is spread in a directed network. Furthermore, we describe fast and effective criteria for the selection of edges to be added to (or deleted from) a given directed network so as to enhance these network communicability measures. Numerical experiments illustrate the effectiveness of the proposed techniques.

Michele Benzi, Valeria Simoncini

We present decay bounds for a broad class of Hermitian matrix functions where the matrix argument is banded or a Kronecker sum of banded matrices. Besides being significantly tighter than previous estimates, the new bounds closely capture the actual (non-monotonic) decay behavior of the entries of functions of matrices with Kronecker sum structure. We also discuss extensions to more general sparse matrices.

Michele Benzi, Marco Feder, Luca Heltai et al.

We present a novel augmented Lagrangian (AL) preconditioner for the solution of linear systems arising from finite element discretizations of elliptic interface problems with jump coefficients. The method is based on the Fictitious Domain with Distributed Lagrange Multipliers formulation and it is designed to improve the convergence of the Flexible Generalized Minimal Residual (FGMRES) method in the presence of large coefficient jumps. To reduce the computational cost, we also introduce a cheaper block-triangular variant of the preconditioner. We prove eigenvalue clustering for the ideal AL preconditioner and study the limiting behavior of the spectrum for the modified variant in terms of parameters and the size of the jumps. Numerical experiments on different immersed geometries confirm mesh-independent iteration counts and robustness over large coefficient jumps, with substantial reductions in wall-clock time for the modified approach.

Francesca Arrigo, Michele Benzi

The total communicability of a network (or graph) is defined as the sum of the entries in the exponential of the adjacency matrix of the network, possibly normalized by the number of nodes. This quantity offers a good measure of how easily information spreads across the network, and can be useful in the design of networks having certain desirable properties. The total communicability can be computed quickly even for large networks using techniques based on the Lanczos algorithm. In this work we introduce some heuristics that can be used to add, delete, or rewire a limited number of edges in a given sparse network so that the modified network has a large total communicability. To this end, we introduce new edge centrality measures which can be used to guide in the selection of edges to be added or removed. Moreover, we show experimentally that the total communicability provides an effective and easily computable measure of how "well-connected" a sparse network is.

Michele Benzi, Christine Klymko

We consider a broad class of walk-based, parameterized node centrality measures for network analysis. These measures are expressed in terms of functions of the adjacency matrix and generalize various well-known centrality indices, including Katz and subgraph centrality. We show that the parameter can be "tuned" to interpolate between degree and eigenvector centrality, which appear as limiting cases. Our analysis helps explain certain correlations often observed between the rankings obtained using different centrality measures, and provides some guidance for the tuning of parameters. We also highlight the roles played by the spectral gap of the adjacency matrix and by the number of triangles in the network. Our analysis covers both undirected and directed networks, including weighted ones. A brief discussion of PageRank is also given.