Eigenvector-based centrality measures are among the most popular centrality measures in network science. The underlying idea is intuitive and the mathematical description is extremely simple in the framework of standard, mono-layer networks. Moreover, several efficient computational tools are available for their computation. Moving up in dimensionality, several efforts have been made in the past to describe an eigenvector-based centrality measure that generalizes the Bonacich index to the case of multiplex networks. In this work, we propose a new definition of eigenvector centrality that relies on the Perron eigenvector of a multi-homogeneous map defined in terms of the tensor describing the network. We prove that existence and uniqueness of such centrality are guaranteed under very mild assumptions on the multiplex network. Extensive numerical studies are proposed to test the newly introduced centrality measure and to compare it to other existing eigenvector-based centralities.
1 January 2016 in SIAM Journal on Scientific Computing
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 qu...
The theory of zeta functions provides an expression for the generating function of non-backtracking walk counts on a directed network. We show how this expression can be used to produce a centrality measure that eliminates backtracking walks at no cost. We also show that the radius of convergence of the generating function is related to the spectrum of a three-by-three block matrix involving the original adjacency matrix. This gives a means to choose appropriate values of the attenuation parameter. We find that three important additional benefits arise when we use this technique to eliminate traversals around the network on the grounds that they are unlikely to be of relevance. First, we obtain a larger range of choices for the attenuation parameter. Second, a natural approach for determining a suitable parameter range is invariant under the removal of certain types of nodes, so we can gain computational efficiencies through reducing the dimension of the resulting eigenvalue problem. Third, the dimension of the linear system defining the centrality measures may be reduced in the same manner. We show that the new centrality measure may be interpreted as standard Katz on a modified network, where self loops are added, and where non-reciprocal edges are augmented with negative weights. We also give a multilayer interpretation, where negatively weighted walks between layers compensate for backtracking walks on the only non-empty layer. Studying the limit as the attenuation parameter approaches its upper bound also allows us to propose a generalization of eigenvector-based non-backtracking centrality measure to this directed network setting. In this context, we find that the two-by-two block matrix arising in previous studies focused on undirected networks must be extended to a new three-by-three block structure to allow for directed edges. We illustrate the centrality measure on a synthetic network, where it is shown to eliminate a localization effect present in standard Katz centrality. Finally, we give results for real networks.
1 January 2016 in SIAM Journal on Matrix Analysis and Applications
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.
1 January 2021 in SIAM Journal on Matrix Analysis and Applications
We describe a complete theory for walk-based centrality indices in complex networks defined in terms of Mittag--Leffler functions. This overarching theory includes as special cases well-known centr...
1 January 2016 in SIAM Journal on Matrix Analysis and Applications
We develop numerical algorithms for the efficient evaluation of quantities associated with generalized matrix functions [J. B. Hawkins and A. Ben-Israel, Linear Multilinear Algebra, 1 (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.