Computation of centrality and communicability indices using generalized matrix functions

Francesca Arrigo (The University of Strathclyde)


Generalized matrix functions were first introduced by Hawkins and Ben-Israel in [5] in order to extend
the notion of a matrix function to rectangular matrices. The definition is based on replacing the Jordan
canonical form of A with its compact singular value decomposition, and evaluating the function at the
positive singular values of A, if defined.

They have appeared several times in the literature without being recognized as such. A first example
is provided in [4], where the authors address the problem of computing unctions of real skew-symmetric
matrices, in particular the evaluation of the product e^A b for a given skew-symmetric matrix A and vector
b using the Lanczos algorithm.

In [3], the authors consider the problem of detecting (approximate) directed bipartite communities in
directed graphs. Consideration of alternating walks in the underlying graph leads them to introducing a
“non-standard matrix function” of the form
f (A) = U cosh(Σ)U^T − U sinh(Σ)V^T ,
which is a “mixture” of the standard matrix function cosh( AA^T ) and the generalized matrix function
sinh ⋄ (A) = U sinh(Σ)V^T .

In this talk, after briefly reviewing the concepts of centrality, communicability, and total communi-
cability in complex networks, we describe how entries of generalized matrix functions can be used as
communicability indices in directed graphs [2]. Furthermore, we show that the action of generalized
matrix functions on a vector of all ones can be used to define certain centrality measures for nodes in di-
rected networks [1]. We then describe three computational approaches based on variants of Golub–Kahan
bidiagonalization algorithm to compute or estimate bilinear forms involving generalized matrix functions,
including entries of the generalized matrix function itself and the action of a generalized matrix function
on a vector.

Extensive numerical studies are presented to assess the effectiveness of the proposed methods.

[1] F. Arrigo and M. Benzi, Edge modification criteria for enhancing the communicability of digraphs,
SIAM J. Matrix Anal. Appl., 37(1) (2016), pp. 443–468.
[2] M. Benzi, E. Estrada, and C. Klymko, Ranking hubs and authorities using matrix functions,
Linear Algebra Appl., 438 (2013), pp. 2447–2474.
[3] J. J. Crofts, E. Estrada, D. J. Higham, and A. Taylor, Mapping directed networks, Elec-
tron. Trans. Numer. Anal., 37 (2010), pp. 337–350.
[4] N. Del Buono, L. Lopez, and R. Peluso, Computation of the exponential of large sparse skew-
symmetric matrices, SIAM J. Sci. Comput., 27 (2005), pp. 278–293.
[5] J. B. Hawkins and A. Ben–Israel, On generalized matrix functions, Linear and Multilinear Al-
gebra, 1 (1973), pp. 163–171.

Import this event to your Outlook calendar
▲ Up to the top