Aggregating nonnegative eigenvectors of the adjacency matrix as a measure of centrality for a directed graph

Eigenvector centrality is a popular measure that uses the principal eigenvector of the adjacency matrix to distinguish importance of nodes in a graph. To find the principal eigenvector, the power method iterating from a random initial vector is often adopted. In this article, we consider the adjacency matrix of a directed graph and choose suitable initial vectors according to strongly connected components of the graph instead so that nonnegative eigenvectors, including the principal one, can be found. Consequently, for aggregating nonnegative eigenvectors, we propose a weighted measure of centrality, called the aggregated-eigenvector centrality. Weighting each nonnegative eigenvector by the reachability of the associated strongly connected component, we can obtain a measure that follows a status hierarchy in a directed graph.     

Bigraphs versus digraphs via matrices

It was observed by Dulmage and Mendelsohn in their work on matrix reducibility that there is a one-to-one correspondence between bigraphs and digraphs determined by the utilization of the adjacency matrix. In this semiexpository paper we explore the interaction between this correspondence and a theory of matrix decomposability that is developed in several different articles. These results include: (a) a characterization of those bipartite graphs that can be labeled so that the resulting digraph is symmetric; (b) a criterion for the bigraph of a symmetric digraph to be connected; (c) a necessary and sufficient condition for a square binary matrix to be fully indecomposable in terms of its associated bigraph, and (d) matrix criteria for a digraph to be strongly, unilaterally, or weakly connected. We close with an unsolved extermal problem on the number of components of the bigraph of various orientations of a given graph. This leads to new amusing characterizations of trees and bigraphs. Dedicated to the graph-theoretic partnership of Lloyd Dulmage and Nathan Mendelsohn.     

Sharp upper and lower bounds for the spectral radius of a nonnegative irreducible matrix and its applications

In this paper, we obtain the sharp upper and lower bounds for the spectral radius of a nonnegative irreducible matrix. We also apply these bounds to various matrices associated with a graph or a digraph, obtain some new results or known results about various spectral radii, including the adjacency spectral radius, the signless Laplacian spectral radius, the distance spectral radius, the distance signless Laplacian spectral radius of a graph or a digraph.     

强连通双圈有向图的无符号拉普拉斯谱刻画

设$\overrightarrow{G}$ 是一个强连通双圈有向图, $A(\overrightarrow{G})$是其邻接矩阵.设$D(\overrightarrow{G})$ 是$\overrightarrow{G}$的顶点出度的对角矩阵, $Q(\overrightarrow{G})=D(\overrightarrow{G})+A(\overrightarrow{G})$是$\overrightarrow{G}$ 的无符号拉普拉斯矩阵. $Q(\overrightarrow{G})$的谱半径称为$\overrightarrow{G}$的无符号拉普拉斯谱半径.在这篇文章中, 确定了在所有强连通双圈有向图中达到最大或最小无符号拉普拉斯谱半径的唯一有向图. 此外,还证明了任意一个强连通双圈有向图是由它的无符号拉普拉斯谱所确定的.     

On graphs with exactly one anti-adjacency eigenvalue and beyond

The anti-adjacency matrix of a graph is constructed from the distance matrix of a graph by keeping each row and each column only the largest distances. This matrix can be interpreted as the opposite of the adjacency matrix, which is instead constructed from the distance matrix of a graph by keeping in each row and each column only the distances equal to 1. The (anti-)adjacency eigenvalues of a graph are those of its (anti-)adjacency matrix. Employing a novel technique introduced by Haemers (2019) [9], we characterize all connected graphs with exactly one positive anti-adjacency eigenvalue, which is an analog of Smith's classical result that a connected graph has exactly one positive adjacency eigenvalue iff it is a complete multipartite graph. On this basis, we identify the connected graphs with all but at most two anti-adjacency eigenvalues equal to ?2 and 0. Moreover, for the anti-adjacency matrix we determine the HL-index of graphs with exactly one positive anti-adjacency eigenvalue, where the HL-index measures how large in absolute value may be the median eigenvalues of a graph. We finally propose some problems for further study.     

Eigenspectral Analysis of Hermitian Adjacency Matrices for the Analysis of Group Substructures

In this paper we propose the use of the eigensystem of complex adjacency matrices to analyze the structure of asymmetric directed weighted communication.

The use of complex Hermitian adjacency matrices allows to store more data relevant to asymmetric communication, and extends the interpretation of the resulting eigensystem beyond the principal eigenpair. This is based on the fact, that the adjacency matrix is transformed into a linear self-adjoint operator in Hilbert space.

Subgroups of members, or nodes of a communication network can be characterised by the eigensubspaces of the complex Hermitian adjacency matrix. Their relative ‘traffic-level’ is represented by the eigenvalue of the subspace, and their members are represented by the eigenvector components. Since eigenvectors belonging to distinct eigenvalues are orthogonal the subgroups can be viewed as independent with respect to the communication behavior of the relevant members of each subgroup.

As an example for this kind of analysis the EIES data set is used. The substructures and communication patterns within this data set are described.     

A vector space approach to the road coloring problem

Let G be a strongly connected, aperiodic, two-out digraph with adjacency matrix A. Suppose A = R + B are coloring matrices: that is, matrices that represent the functions induced by an edge-coloring of G. We introduce a matrix Δ = 1/2 (R − B) and investigate its properties. A number of useful conditions involving Δ which either are equivalent to or imply a solution to the road coloring problem are derived.     

Line digraphs and the Moore-Penrose inverse

Various characterizations of line digraphs and of Boolean matrices possessing a Moore-Penrose inverse are used to show that a square Boolean matrix has a Moore-Penrose inverse if and only if it is the adjacency matrix of a line digraph. A similar relationship between a nonsquare Boolean matrix and a bipartite graph is also given.     

Ranking hubs and authorities using matrix functions

The notions of subgraph centrality and communicability, based on the exponential of the adjacency matrix of the underlying graph, have been effectively used in the analysis of undirected networks. In this paper we propose an extension of these measures to directed networks, and we apply them to the problem of ranking hubs and authorities. The extension is achieved by bipartization, i.e., the directed network is mapped onto a bipartite undirected network with twice as many nodes in order to obtain a network with a symmetric adjacency matrix. We explicitly determine the exponential of this adjacency matrix in terms of the adjacency matrix of the original, directed network, and we give an interpretation of centrality and communicability in this new context, leading to a technique for ranking hubs and authorities. The matrix exponential method for computing hubs and authorities is compared to the well known HITS algorithm, both on small artificial examples and on more realistic real-world networks. A few other ranking algorithms are also discussed and compared with our technique. The use of Gaussian quadrature rules for calculating hub and authority scores is discussed.     

From Affiliation Matrices to Adjacency Matrices: Methods and Techniques for the Analysis of Centrality

In the analysis of 2-mode networks, the transition from affiliation matrices to adjacency matrices formalizes the information on overall actors' participation in the occasions, in a way that does not allow to exploit the whole amount of information in some analysis, such as centrality. In this article, I propose a procedure for the calculation of a different and more informative adjacency matrix; moreover, I propose an adaptation for Freeman centrality indices; this adaptation accounts for the different organization of the information on the intersubset ties, which allows the computation of centrality using all the available information. Finally, I empirically illustrate the introduced procedures, and the information they allow to retrieve, analyzing a real 2-mode network known in the literature.     

Arc transitive covering digraphs and their eigenvalues

We prove that every finite regular digraph has an arc-transitive covering digraph (whose arcs are equivalent under automorphisms) and every finite regular graph has a 2-arc-transitive covering graph. As a corollary, we sharpen C. D. Godsil's results on eigenvalues and minimum polynomials of vertex-transitive graphs and digraphs. Using Godsil's results, we prove, that given an integral matrix A there exists an arc-transitive digraph X such that the minimum polynomial of A divides that of X. It follows that there exist arc-transitive digraphs with nondiagonalizable adjacency matrices, answering a problem by P. J. Cameron. For symmetric matrices A, we construct a 2-arc-transitive graphs X.     

On the critical ideals of graphs

We introduce some determinantal ideals of the generalized Laplacian matrix associated to a digraph G, that we call critical ideals of G. Critical ideals generalize the critical group and the characteristic polynomials of the adjacency and Laplacian matrices of a digraph. The main results of this article are the determination of some minimal generator sets and the reduced Gröbner basis for the critical ideals of the complete graphs, the cycles and the paths. Also, we establish a bound between the number of trivial critical ideals and the stability and clique numbers of a graph.     

On the structure of the adjacency matrix of the line digraph of a regular digraph

We show that the adjacency matrix M of the line digraph of a d-regular digraph D on n vertices can be written as M=AB, where the matrix A is the Kronecker product of the all-ones matrix of dimension d with the identity matrix of dimension n and the matrix B is the direct sum of the adjacency matrices of the factors in a dicycle factorization of D.     

Partly zero eigenvectors

This paper is concerned with the forced presence or absence of zero components in an eigenvector. Relative to a fixed matrix Awith eigenvalue λ, we characterize the strictly nonzero part of a partly zero eigenvector associated with λ. We also give a sufficient condition for a fixed matrix to have a partly zero eigenvector, and discuss several examples in which a matrix has one or more partly zero eigenvectors. Our main results, however, are qualitative in nature. We associate a zero/nonzero pattern class of matrices with a digraph, and characterize the set of pattern classes which requires all eigenvectors to be strictly nonzero. A sufficient condition is also given that identifies the components of a partly zero eigenvector which may be nonzero.     

Robustifying principal component analysis with spatial sign vectors

In this paper, we apply orthogonally equivariant spatial sign covariance matrices as well as their affine equivariant counterparts in principal component analysis. The influence functions and asymptotic covariance matrices of eigenvectors based on robust covariance estimators are derived in order to compare the robustness and efficiency properties. We show in particular that the estimators that use pairwise differences of the observed data have very good efficiency properties, providing practical robust alternatives to classical sample covariance matrix based methods.     

Hoffman polynomials of nonnegative irreducible matrices and strongly connected digraphs

For a nonnegative n × n matrix A, we find that there is a polynomial f(x)∈R[x] such that f(A) is a positive matrix of rank one if and only if A is irreducible. Furthermore, we show that the lowest degree such polynomial f(x) with tr f(A) = n is unique. Thus, generalizing the well-known definition of the Hoffman polynomial of a strongly connected regular digraph, for any irreducible nonnegative n × n matrix A, we are led to define its Hoffman polynomial to be the polynomial f(x) of minimum degree satisfying that f(A) is positive and has rank 1 and trace n. The Hoffman polynomial of a strongly connected digraph is defined to be the Hoffman polynomial of its adjacency matrix. We collect in this paper some basic results and open problems related to the concept of Hoffman polynomials.     

Quadrature rule-based bounds for functions of adjacency matrices

Bounds for entries of matrix functions based on Gauss-type quadrature rules are applied to adjacency matrices associated with graphs. This technique allows to develop inexpensive and accurate upper and lower bounds for certain quantities (Estrada index, subgraph centrality, communicability) that describe properties of networks.     

On some properties of the Laplacian matrix revealed by the RCM algorithm

In this paper we present some theoretical results about the irreducibility of the Laplacian matrix ordered by the Reverse Cuthill-McKee (RCM) algorithm. We consider undirected graphs with no loops consisting of some connected components. RCM is a well-known scheme for numbering the nodes of a network in such a way that the corresponding adjacency matrix has a narrow bandwidth. Inspired by some properties of the eigenvectors of a Laplacian matrix, we derive some properties based on row sums of a Laplacian matrix that was reordered by the RCM algorithm. One of the theoretical results serves as a basis for writing an easy MATLAB code to detect connected components, by using the function “symrcm” of MATLAB. Some examples illustrate the theoretical results.