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

## Spectra of weighted rooted graphs having prescribed subgraphs at some levels

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

Link permanente para citações:

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

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

Link permanente para citações:

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

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

Link permanente para citações:

## Algebraic Conditions for Generating Accurate Adjacency Arrays

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 17/10/2015

Relevância na Pesquisa

36.6%

#Computer Science - Databases#Computer Science - Data Structures and Algorithms#Mathematics - Rings and Algebras

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

Link permanente para citações:

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

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

Link permanente para citações:

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

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...

Link permanente para citações:

## Wreath product of matrices

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

Link permanente para citações:

## Permanental polynomials of skew adjacency matrices of oriented graphs

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.

Link permanente para citações:

## Matrices and $\alpha $-Stable Bipartite Graphs

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...

Link permanente para citações:

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

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.

Link permanente para citações:

## Determinants of adjacency matrices of graphs

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.

Link permanente para citações:

## Spectral distributions of adjacency and Laplacian matrices of random graphs

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)

Link permanente para citações:

## The minimum rank of universal adjacency matrices

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.

Link permanente para citações:

## Adjacency Matrices of Configuration Graphs

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}.

Link permanente para citações:

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

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

Link permanente para citações:

## On Adjacency Matrices and Descriptors of Signed Cycle Graphs

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

Link permanente para citações:

## Approximating the largest eigenvalue of network adjacency matrices

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

Link permanente para citações:

## The limiting distributions of large heavy Wigner and arbitrary random matrices

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...

Link permanente para citações:

## The Square of Adjacency Matrices

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.

Link permanente para citações:

## Diamond condition for commuting adjacency matrices of directed and undirected graphs

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.

Link permanente para citações: