Página 1 dos resultados de 350 itens digitais encontrados em 0.005 segundos

Spectra of weighted rooted graphs having prescribed subgraphs at some levels

Rojo, O.; Robbiano, M.; Cardoso, D.M.; Martins, E.A.
Fonte: ILAS - International Linear Algebra Society Publicador: ILAS - International Linear Algebra Society
Tipo: Artigo de Revista Científica
ENG
Relevância na Pesquisa
36.48%
Let B be a weighted generalized Bethe tree of k levels (k > 1) in which nj is the number of vertices at the level k-j+1 (1 ≤ j ≤ k). Let Δ subset {1, 2,., k-1} and F={Gj:j in Δ}, where Gj is a prescribed weighted graph on each set of children of B at the level k-j+1. In this paper, the eigenvalues of a block symmetric tridiagonal matrix of order n1+n2 +...+nk are characterized as the eigenvalues of symmetric tridiagonal matrices of order j, 1≤j≤k, easily constructed from the degrees of the vertices, the weights of the edges, and the eigenvalues of the matrices associated to the family of graphs F. These results are applied to characterize the eigenvalues of the Laplacian matrix, including their multiplicities, of the graph β(F) obtained from β and all the graphs in F={Gj:j in Δ}; and also of the signless Laplacian and adjacency matrices whenever the graphs of the family F are regular.; CIDMA; FCT; FEDER/POCI 2010; PTDC/MAT/112276/2009; Fondecyt - IC Project 11090211; Fondecyt Regular 1100072

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

Severini, Simone
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
36.37%
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.; Comment: 5 pages

Levy-Khintchine random matrices and the Poisson weighted infinite skeleton tree

Jung, Paul
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
36.4%
We study a class of Hermitian random matrices which includes and generalizes Wigner matrices, heavy-tailed random matrices, and sparse random matrices such as the adjacency matrices of Erdos-Renyi random graphs with p ~ 1/N. Our NxN random matrices have real entries which are i.i.d. up to symmetry. The distributions may depend on N, however, the sums of rows must converge in distribution; it is then well-known that the limiting distributions are infinitely divisible. We show that a limiting empirical spectral distribution (LSD) exists, and via local weak convergence of associated graphs, the LSD corresponds to the spectral measure at the root of a Poisson weighted infinite skeleton tree. This graph is formed by connecting infinitely many Poisson weighted infinite trees using a backbone structure. One example covered by the results are matrices with i.i.d. entries having infinite second moments, but normalized to be in the Gaussian domain of attraction. In this case, the limiting graph is just the positive integer line rooted at 1, and as expected, the LSD is Wigner's semi-circle law. The results also extend to self-adjoint complex matrices and also to Wishart matrices.; Comment: Several revisions. 28 pages

Algebraic Conditions for Generating Accurate Adjacency Arrays

Dibert, Karia; Jansen, Hayden; Kepner, Jeremy
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 17/10/2015
Relevância na Pesquisa
36.6%
Data processing systems impose multiple views on data as it is processed by the system. These views include spreadsheets, databases, matrices, and graphs. Associative arrays unify and simplify these different approaches into a common two-dimensional view of data. Graph construction, a fundamental operation in the data processing pipeline, is typically done by multiplying the incidence array representations of a graph, $\mathbf{E}_\mathrm{in}$ and $\mathbf{E}_\mathrm{out}$, to produce an adjacency matrix of the graph that can be processed with a variety of machine learning clustering techniques. This work focuses on establishing the mathematical criteria to ensure that the matrix product $\mathbf{E}_\mathrm{out}^\intercal\mathbf{E}_\mathrm{in}$ is the adjacency array of the graph. It will then be shown that these criteria are also necessary and sufficient for the remaining nonzero product of incidence arrays, $\mathbf{E}_\mathrm{in}^\intercal\mathbf{E}_\mathrm{out}$ to be the adjacency matrices of the reversed graph. Algebraic structures that comply with the criteria will be identified and discussed.; Comment: 2015 IEEE MIT Undergraduate Research Technology Conference

Investigating Randomly Generated Adjacency Matrices For Their Use In Modeling Wireless Topologies

Bhanage, Gautam; Kaul, Sanjit
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 16/04/2013
Relevância na Pesquisa
46.65%
Generation of realistic topologies plays an important role in determining the accuracy and validity of simulation studies. This study presents a discussion to justify why, and how often randomly generated adjacency matrices may not not conform to wireless topologies in the physical world. Specifically, it shows through analysis and random trials that, more than 90% of times, a randomly generated adjacency matrix will not conform to a valid wireless topology, when it has more than 3 nodes. By showing that node triplets in the adjacency graph need to adhere to rules of a geometric vector space, the study shows that the number of randomly chosen node triplets failing consistency checks grow at the order of O(base^3), where base is the granularity of the distance metric. Further, the study models and presents a probability estimate with which any randomly generated adjacency matrix would fail realization. This information could be used to design simpler algorithms for generating k-connected wireless topologies.; Comment: 3 pages, 4 figures

Cobweb Posets and KoDAG Digraphs are Representing Natural Join of Relations, their diBigraphs and the Corresponding Adjacency Matrices

Kwasniewski, A. K.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
46.6%
Natural join of $di-bigraphs$ that is directed biparted graphs and their corresponding adjacency matrices is defined and then applied to investigate the so called cobweb posets and their $Hasse$ digraphs called $KoDAGs$. $KoDAGs$ are special orderable directed acyclic graphs which are cover relation digraphs of cobweb posets introduced by the author few years ago. $KoDAGs$ appear to be distinguished family of $Ferrers$ digraphs which are natural join of a corresponding ordering chain of one direction directed cliques called $di-bicliques$. These digraphs serve to represent faithfully corresponding relations of arbitrary arity so that all relations of arbitrary arity are their subrelations. Being this $chain -way$ complete if compared with kompletne $Kuratowski$ bipartite graphs their $DAG$ denotation is accompanied with the letter $K$ in front of descriptive abbreviation $oDAG$. The way to join bipartite digraphs of binary into $multi-ary$ relations is the natural join operation either on relations or their digraph representatives. This natural join operation is denoted here by $\os$ symbol deliberately referring to the direct sum $\oplus$ of adjacency matrices as it becomes the case for disjoint $di-bigraphs$.; Comment: 19 pages, 7 figures...

Wreath product of matrices

D'Angeli, Daniele; Donno, Alfredo
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 09/07/2015
Relevância na Pesquisa
36.48%
We introduce a new matrix product, that we call the wreath product of matrices. The name is inspired by the analogous product for graphs, and the following important correspondence is proven: the wreath product of the adjacency matrices of two graphs provides the adjacency matrix of the wreath product of the graphs. This correspondence is exploited in order to study the spectral properties of the famous Lamplighter random walk: the spectrum is explicitly determined for the "Walk or switch" model on a complete graph of any size, with two lamp colors. The investigation of the spectrum of the matrix wreath product is actually developed for the more general case where the second factor is a circulant matrix. Finally, an application to the study of generalized Sylvester matrix equations is treated.; Comment: 25 pages

Permanental polynomials of skew adjacency matrices of oriented graphs

Liu, Shunyi; Zhang, Heping
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 10/09/2014
Relevância na Pesquisa
46.52%
Let $G^\sigma$ be an orientation of a simple graph $G$ and $A_s(G^\sigma)$ the skew adjacency matrix of $G^\sigma$. In this paper, the permanental polynomial of $A_s(G^\sigma)$ is investigated. All the coefficients of the permanental polynomial of $A_s(G^\sigma)$ are presented in terms of $G^\sigma$, and it is proved that the skew adjacency matrices of a graph $G$ all have the same permanental polynomial if and only if $G$ has no even cycles. Moreover, the relationship between $S_p(G^\sigma)$ and $S_p(G)$ is studied, where $S_p(G^\sigma)$ and $S_p(G)$ denote respectively the per-spectrum of $G^\sigma$ and $G$. In particular, (i) $S_p(G^\sigma)$ = $iS_p(G)$ for some orientation $G^\sigma$ if and only if $G$ is bipartite, (ii) $S_p(G^\sigma)$ = $iS_p(G)$ for any orientation $G^\sigma$ if and only if $G$ is a forest, where $i^2$ = -1.

Matrices and $\alpha $-Stable Bipartite Graphs

Levit, Vadim E.; Mandrescu, Eugen
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 15/12/1999
Relevância na Pesquisa
36.68%
A square (0,1)-matrix X of order n > 0 is called fully indecomposable if there exists no integer k with 0 < k < n, such that X has a k by n-k zero submatrix. A stable set of a graph G is a subset of pairwise nonadjacent vertices. The stability number of G, denoted by $\alpha (G)$, is the cardinality of a maximum stable set in G. A graph is called $\alpha $-stable if its stability number remains the same upon both the deletion and the addition of any edge. We show that a connected bipartite graph has exactly two maximum stable sets that partition its vertex set if and only if its reduced adjacency matrix is fully indecomposable. We also describe a decomposition structure of $\alpha $-stable bipartite graphs in terms of their reduced adjacency matrices. On the base of these findings we obtain both new proofs for a number of well-known theorems on the structure of matrices due to Brualdi, Marcus and Minc, Dulmage and Mendelsohn, and some generalizations of these statements. Several new results on $\alpha $-stable bipartite graphs and their corresponding reduced adjacency matrices are presented, as well. Two kinds of matrix product are also considered (namely, Boolean product and Kronecker product), and their corresponding graph operations. As a consequence...

Network inference and community detection, based on covariance matrices, correlations and test statistics from arbitrary distributions

Bartlett, Thomas E.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
36.53%
In this paper we propose methodology for inference of binary adjacency matrices from various measures of the strength of association between pairs of network nodes, or more generally pairs of variables. This strength of association can be quantified by sample covariance and correlation matrices, and more generally by test-statistics and hypothesis test p-values from arbitrary distributions. Binary adjacency matrices inferred in this way are then ideal for community detection, for example by block-modelling. The proposed methodology is applicable to large high-dimensional data-sets and is based on computationally efficient algorithms: we illustrate its utility in a range of contexts including biological and social/communication networks.

Determinants of adjacency matrices of graphs

Abdollahi, Alireza
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 23/08/2009
Relevância na Pesquisa
46.4%
We study the set of all determinants of adjacency matrices of graphs with a given number of vertices.

Spectral distributions of adjacency and Laplacian matrices of random graphs

Ding, Xue; Jiang, Tiefeng
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 11/11/2010
Relevância na Pesquisa
36.78%
In this paper, we investigate the spectral properties of the adjacency and the Laplacian matrices of random graphs. We prove that: (i) the law of large numbers for the spectral norms and the largest eigenvalues of the adjacency and the Laplacian matrices; (ii) under some further independent conditions, the normalized largest eigenvalues of the Laplacian matrices are dense in a compact interval almost surely; (iii) the empirical distributions of the eigenvalues of the Laplacian matrices converge weakly to the free convolution of the standard Gaussian distribution and the Wigner's semi-circular law; (iv) the empirical distributions of the eigenvalues of the adjacency matrices converge weakly to the Wigner's semi-circular law.; Comment: Published in at http://dx.doi.org/10.1214/10-AAP677 the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)

The minimum rank of universal adjacency matrices

Ahmadi, Bahman; Alinaghipour, Fatemeh; Fallat, Shaun M.; Fan, Yi-Zheng; Meagher, Karen; Nasserasr, Shahla
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 07/12/2011
Relevância na Pesquisa
36.4%
In this paper we introduce a new parameter for a graph called the {\it minimum universal rank}. This parameter is similar to the minimum rank of a graph. For a graph $G$ the minimum universal rank of $G$ is the minimum rank over all matrices of the form \[ U(\alpha, \beta, \gamma, \delta) = \alpha A + \beta I + \gamma J + \delta D \] where $A$ is the adjacency matrix of $G$, $J$ is the all ones matrix and $D$ is the matrix with the degrees of the vertices in the main diagonal, and $\alpha\neq 0, \beta, \gamma, \delta$ are scalars. Bounds for general graphs based on known graph parameters are given, as is a formula for the minimum universal rank for regular graphs based on the multiplicity of the eigenvalues of $A$. The exact value of the minimum universal rank of some families of graphs are determined, including complete graphs, complete bipartite graph, paths and cycles. Bounds on the minimum universal rank of a graph obtained by deleting a single vertex are established. It is shown that the minimum universal rank is not monotone on induced subgraphs, but bounds based on certain induced subgraphs, including bounds on the union of two graphs, are given. Finally we characterize all graphs with minimum universal rank equal to 0 and to 1.

Adjacency Matrices of Configuration Graphs

Abreu, M.; Funk, M.; Labbate, D.; Napolitano, V.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 04/02/2010
Relevância na Pesquisa
36.53%
In 1960, Hoffman and Singleton \cite{HS60} solved a celebrated equation for square matrices of order $n$, which can be written as $$ (\kappa - 1) I_n + J_n - A A^{\rm T} = A$$ where $I_n$, $J_n$, and $A$ are the identity matrix, the all one matrix, and a $(0,1)$--matrix with all row and column sums equal to $\kappa$, respectively. If $A$ is an incidence matrix of some configuration $\cal C$ of type $n_\kappa$, then the left-hand side $\Theta(A):= (\kappa - 1)I_n + J_n - A A^{\rm T}$ is an adjacency matrix of the non--collinearity graph $\Gamma$ of $\cal C$. In certain situations, $\Theta(A)$ is also an incidence matrix of some $n_\kappa$ configuration, namely the neighbourhood geometry of $\Gamma$ introduced by Lef\`evre-Percsy, Percsy, and Leemans \cite{LPPL}. The matrix operator $\Theta$ can be reiterated and we pose the problem of solving the generalised Hoffman--Singleton equation $\Theta^m(A)=A$. In particular, we classify all $(0,1)$--matrices $M$ with all row and column sums equal to $\kappa$, for $\kappa = 3,4$, which are solutions of this equation. As a by--product, we obtain characterisations for incidence matrices of the configuration $10_3F$ in Kantor's list \cite{Kantor} and the $17_4$ configuration $#1971$ in Betten and Betten's list \cite{BB99}.

Lower Bound on the Chromatic Number by Spectra of Weighted Adjacency Matrices

Wocjan, Pawel; Janzing, Dominik; Beth, Thomas
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 21/12/2001
Relevância na Pesquisa
46.65%
A lower bound on the chromatic number of a graph is derived by majorization of spectra of weighted adjacency matrices. These matrices are given by Hadamard products of the adjacency matrix and arbitrary Hermitian matrices.; Comment: 6 pages

On Adjacency Matrices and Descriptors of Signed Cycle Graphs

Mathai, A. M.; Zaslavsky, Thomas
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 12/03/2013
Relevância na Pesquisa
46.48%
This paper deals with adjacency matrices of signed cycle graphs and chemical descriptors based on them. The eigenvalues and eigenvectors of the matrices are calculated and their efficacy in classifying different signed cycles is determined. The efficacy of some numerical indices is also examined.; Comment: 15 pp. Submitted

Approximating the largest eigenvalue of network adjacency matrices

Restrepo, Juan G.; Ott, Edward; Hunt, Brian R.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 30/05/2007
Relevância na Pesquisa
46.52%
The largest eigenvalue of the adjacency matrix of a network plays an important role in several network processes (e.g., synchronization of oscillators, percolation on directed networks, linear stability of equilibria of network coupled systems, etc.). In this paper we develop approximations to the largest eigenvalue of adjacency matrices and discuss the relationships between these approximations. Numerical experiments on simulated networks are used to test our results.; Comment: 7 pages, 4 figures

The limiting distributions of large heavy Wigner and arbitrary random matrices

Male, Camille
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 11/09/2012
Relevância na Pesquisa
36.42%
The model of heavy Wigner matrices generalizes the classical ensemble of Wigner matrices: the sub-diagonal entries are independent, identically distributed along to and out of the diagonal, and the moments its entries are of order 1/N, where N is the size of the matrices. Adjacency matrices of Erd\"os-Renyi sparse graphs and matrices with properly truncated heavy tailed entries are examples of heavy Wigner matrices. We consider a family X_N of independent heavy Wigner matrices and a family Y_N of arbitrary random matrices, independent of X_N, with a technical condition (e.g. the matrices of Y_N are deterministic and uniformly bounded in operator norm, or are deterministic diagonal). We characterize the possible limiting joint *-distributions of (X_N,Y_N) in the sense of free probability. We find that they depend on more than the *-distribution of Y_N. We use the notion of distributions of traffics and their free product to quantify the information needed on Y_N and to infer the limiting distribution of (X_N,Y_N). We give an explicit combinatorial formula for joint moments of heavy Wigner and independent random matrices. When the matrices of Y_N are diagonal, we give recursion formulas for these moments. We deduce a new characterization of the limiting eigenvalues distribution of a single heavy Wigner.; Comment: 37 pages...

The Square of Adjacency Matrices

Kranda, Dan
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 12/07/2012
Relevância na Pesquisa
36.45%
It can be shown that any symmetric $(0,1)$-matrix $A$ with $\tr A = 0$ can be interpreted as the adjacency matrix of a simple, finite graph. The square of an adjacency matrix $A^2=(s_{ij})$ has the property that $s_{ij}$ represents the number of walks of length two from vertex $i$ to vertex $j$. With this information, the motivating question behind this paper was to determine what conditions on a matrix $S$ are needed to have $S=A(G)^2$ for some graph $G$. Structural results imposed by the matrix $S$ include detecting bipartiteness or connectedness and counting four cycles. Row and column sums are examined as well as the problem of multiple nonisomorphic graphs with the same adjacency matrix squared.

Diamond condition for commuting adjacency matrices of directed and undirected graphs

Dini, Paolo; Nehaniv, Chrystopher L.
Fonte: The FP7 European Network of Excellence in Internet Science Publicador: The FP7 European Network of Excellence in Internet Science
Tipo: Book Section; NonPeerReviewed Formato: application/pdf
Publicado em /04/2013 EN; EN
Relevância na Pesquisa
46.84%
In the context of the stability analysis of interdependent networks through the eigenvalue evaluation of their adjacency matrices, we characterize algebraically and also geometrically necessary and sufficient conditions for the adjacency matrices of directed and undirected graphs to commute. We also discuss the problem of communicating the concepts, the theorems, and the results to a non-mathematical audience, and more generally across different disciplinary domains, as one of the fundamental challenges faced by the Internet Science community. Thus, the paper provides much more background, discussion, and detail than would normally be found in a purely mathematical publication, for which the proof of the diamond condition would require only a few lines. Graphical visualization, examples, discussion of important steps in the proof and of the diamond condition itself as it applies to graphs whose adjacency matrices commute are provided. The paper also discusses interdependent graphs and applies the results on commuting adjacency matrices to study when the interconnection matrix encoding links between two disjoint graphs commutes with the adjacency matrix of the disjoint union of the two graphs. Expected applications are in the design and analysis of interdependent networks.