Search

We consider weighted coupled cell networks, that is networks where the interactions between any two cells have an associated weight that is a real valued number. Weighted networks are ubiquitous in real-world applications. We consider a dynamical systems perspective by associating with each network a set of continuous dynamical systems, the ones that respect the graph structure of the network. For weighted networks it is natural for the admissible coupled cell systems to have an additive input structure. We present a characterization of the synchrony subspaces and the antisynchrony subspaces for a weighted network depending on the restrictions that are imposed in their admissible input-additive coupled cell systems. These subspaces are flow invariant by those systems and are generalized polydiagonal subspaces, that is, are characterized by conditions on the cell coordinates of the types xi = xj and/or xk = xl and/or xm = 0. The existence and identification of the synchrony and antisynchrony subspaces for a weighted network are deeply relevant from the applications and dynamics points of view. Our characterization of the synchrony and antisynchrony subspaces of a weighted network follows from our results where we give necessary and sufficient conditions for a generalized polydiagonal to be invariant by the adjacency matrix and/or the Laplacian matrix of the network. [ABSTRACT FROM AUTHOR]

Let hom(G, H) denote the number of homomorphisms from a graph G to a graph H. In this paper we study the number of homomorphisms of trees into a path, and prove that hom(Pm, Pn) ≤ hom(Tm, Pn) ≤ hom(Sm, Pn), where Tm is any tree on m vertices, and Pm and Sm denote the path and star on m vertices, respectively. This completes the study of extremal problems concerning the number of homomorphisms between trees started in the paper Graph Homomorphisms Between Trees [Electron. J. Combin., 21 (2014), 4.9] written by the authors of the current paper. [ABSTRACT FROM AUTHOR]

We propose a communication-driven mechanism for predicting triadic closure in complex networks. It is mathematically formulated on the basis of communicability distance functions that account for the quality of communication between nodes in the network. We study 25 real-world networks and show that the proposed method correctly predicts 20% of triadic closures in these networks, in contrast to the 7.6% predicted by a random mechanism. We also show that the communication-driven method outperforms the random mechanism in explaining the clustering coefficient, average path length, and average communicability. The new method also displays some interesting features with regards to optimizing communication in networks. [ABSTRACT FROM AUTHOR]

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 centralities. We show that the parameter can be "tuned" to interpolate between degree and eigenvector centralities, 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. [ABSTRACT FROM AUTHOR]

The existence of a partial quadrangle PQ(s, t, μ) is equivalent to the existence of a diamond-free strongly regular graph SRG(1 + s(t + 1)+s²t(t + 1)/μ, s(t + 1), s - 1, μ). Let S be a PQ(3, (n + 3)(n² - 1)/3, n² + n) such that for every two noncollinear points p1 and p2, there is a point q noncollinear with p1, p2, and all points collinear with both p1 and p2. In this article, we establish that S exists only for n ∈ {-2, 2, 3} and probably n = 10. [ABSTRACT FROM AUTHOR]

Approximations of matrix-valued functions of the form WT f(A)W, where A ∈ Rm×m is symmetric, W ∈ Rm×k, with m large and k ≪ m, has orthonormal columns, and f is a function, can be computed by applying a few steps of the symmetric block Lanczos method to A with initial block-vector W ∈ Rm×k. Golub and Meurant have shown that the approximants obtained in this manner may be considered block Gauss quadrature rules associated with a matrix-valued measure. This paper generalizes anti-Gauss quadrature rules, introduced by Laurie for real-valued measures, to matrix-valued measures, and shows that under suitable conditions pairs of block Gauss and block anti-Gauss rules provide upper and lower bounds for the entries of the desired matrix-valued function. Extensions to matrix-valued functions of the form WT f(A)V, where A ∈ Rm×m may be nonsymmetric, and the matrices V,W ∈ Rm×k satisfy VTW = Ik are also discussed. Approximations of the latter functions are computed by applying a few steps of the nonsymmetric block Lanczos method to A with initial block-vectors V and W. We describe applications to the evaluation of functions of a symmetric or nonsymmetric adjacency matrix for a network. Numerical examples illustrate that a combination of block Gauss and anti-Gauss quadrature rules typically provides upper and lower bounds for such problems. We introduce some new quantities that describe properties of nodes in directed or undirected networks, and demonstrate how these and other quantities can be computed inexpensively with the quadrature rules of the present paper. [ABSTRACT FROM AUTHOR]

For random graphs distributed according to a stochastic block model, we consider the inferential task of partitioning vertices into blocks using spectral techniques. Spectral partitioning using the normalized Laplacian and the adjacency matrix have both been shown to be consistent as the number of vertices tend to infinity. Importantly, both procedures require that the number of blocks and the rank of the communication probability matrix be known, even as the rest of the parameters may be unknown. In this paper, we prove that the (suitably modified) adjacency-spectral partitioning procedure, requiring only an upper bound on the rank of the communication probability matrix, is consistent. Indeed, this result demonstrates a robustness to model mis-specification; an overestimate of the rank may impose a moderate performance penalty, but the procedure is still consistent. Furthermore, we extend this procedure to the setting where adjacencies may have multiple modalities and we allow for either directed or undirected graphs. [ABSTRACT FROM AUTHOR]

We consider only simple graphs. Given two graphs G with vertices 1,…, n and H, the corona G ο H is defined as the graph obtained by taking n copies of H and for each i inserting edges between the ith vertex of G and each vertex of the ith copy of H. For a connected graph G and any r-regular graph H we provide complete information about the spectrum of G ο H using the spectrum of G and spectrum of H. Complete information about the Laplacian spectrum of G ο H is also provided even when H is not regular. A graph G is said to have the property (R) if 1/λ is an eigenvalue of G whenever λ is an eigenvalue of G. Further, if λ and 1/λ have the same multiplicity, for each eigenvalue λ, then it is said to have the property (SR). We characterize all trees with property (SR) and show that such a tree is the corona product of some tree and an isolated vertex. We supply a family of bipartite graphs with property (R). As an application we construct infinitely many pairs of nonisomorphic graphs with the same spectrum and the same Laplacian spectrum. We prove some results about the eigenvector related to the second smallest eigenvalue of the Laplacian matrix of G ο H and give an application. [ABSTRACT FROM AUTHOR]