Search results for "adjacency matrix"
showing 7 items of 27 documents
A Graph-Theoretical Approach to Calculate Vibrational Energies of Atomic and Subatomic Systems
2012
One of the challenges still pending in string theory and other particle physics related fields is the accurate prediction of the masses of the elementary particles defined in the standard model. In this paper an original algorithm to assign graphs to each of these particles is proposed. Based on this mapping, we demonstrate that certain indices associated with the topology of the graph (graph theoretical indices) are very effective in predicting the masses of the particles. Specifically, the spectral moments of the graph adjacency matrix weighted by edge degrees play a key role in the excellent correlations found. Moreover, the same topological pattern is found in other well known quantum s…
Quantum Lower Bound for Graph Collision Implies Lower Bound for Triangle Detection
2015
We show that an improvement to the best known quantum lower bound for GRAPH-COLLISION problem implies an improvement to the best known lower bound for TRIANGLE problem in the quantum query complexity model. In GRAPH-COLLISION we are given free access to a graph $(V,E)$ and access to a function $f:V\rightarrow \{0,1\}$ as a black box. We are asked to determine if there exist $(u,v) \in E$, such that $f(u)=f(v)=1$. In TRIANGLE we have a black box access to an adjacency matrix of a graph and we have to determine if the graph contains a triangle. For both of these problems the known lower bounds are trivial ($\Omega(\sqrt{n})$ and $\Omega(n)$, respectively) and there is no known matching upper …
Structure of eigenvectors of random regular digraphs
2018
Let $d$ and $n$ be integers satisfying $C\leq d\leq \exp(c\sqrt{\ln n})$ for some universal constants $c, C>0$, and let $z\in \mathbb{C}$. Denote by $M$ the adjacency matrix of a random $d$-regular directed graph on $n$ vertices. In this paper, we study the structure of the kernel of submatrices of $M-z\,{\rm Id}$, formed by removing a subset of rows. We show that with large probability the kernel consists of two non-intersecting types of vectors, which we call very steep and gradual with many levels. As a corollary, we show, in particular, that every eigenvector of $M$, except for constant multiples of $(1,1,\dots,1)$, possesses a weak delocalization property: its level sets have cardin…
Graph recursive least squares filter for topology inference in causal data processes
2017
In this paper, we introduce the concept of recursive least squares graph filters for online topology inference in data networks that are modelled as Causal Graph Processes (CGP). A Causal Graph Process (CGP) is an auto regressive process in the time series associated to different variables, and whose coefficients are the so-called graph filters, which are matrix polynomials with different orders of the graph adjacency matrix. Given the time series of data at different variables, the goal is to estimate these graph filters, hence the associated underlying adjacency matrix. Previously proposed algorithms have focused on a batch approach, assuming implicitly stationarity of the CGP. We propose…
Spectral moments of the edge adjacency matrix in molecular graphs. 3. Molecules containing cycles
1998
A substructural approach to quantitative structure−property relationships based on the spectral moments of the edge adjacency matrix is extended to molecules containing cycles. Spectral moments are expressed as linear combinations of structural fragments of any kind of nonweighted graphs. The boiling points of a series of 80 cycloalkanes was well-described by the present approach. The predictive power of the model was proved by using a test set of another 26 compounds. An equation that expresses the contribution of the different fragments of the molecules to the boiling point was obtained.
The rank of random regular digraphs of constant degree
2018
Abstract Let d be a (large) integer. Given n ≥ 2 d , let A n be the adjacency matrix of a random directed d -regular graph on n vertices, with the uniform distribution. We show that the rank of A n is at least n − 1 with probability going to one as n grows to infinity. The proof combines the well known method of simple switchings and a recent result of the authors on delocalization of eigenvectors of A n .
The smallest singular value of a shifted $d$-regular random square matrix
2017
We derive a lower bound on the smallest singular value of a random d-regular matrix, that is, the adjacency matrix of a random d-regular directed graph. Specifically, let $$C_1<d< c n/\log ^2 n$$ and let $$\mathcal {M}_{n,d}$$ be the set of all $$n\times n$$ square matrices with 0 / 1 entries, such that each row and each column of every matrix in $$\mathcal {M}_{n,d}$$ has exactly d ones. Let M be a random matrix uniformly distributed on $$\mathcal {M}_{n,d}$$ . Then the smallest singular value $$s_{n} (M)$$ of M is greater than $$n^{-6}$$ with probability at least $$1-C_2\log ^2 d/\sqrt{d}$$ , where c, $$C_1$$ , and $$C_2$$ are absolute positive constants independent of any other parameter…