All Questions
Tagged with random-graphs random-matrices
18 questions
1
vote
0
answers
54
views
Controlling quantity related to Laplacian pseudo-inverse of Erdős–Rényi graph
Consider an $n$-node undirected graph $G = (V, E)$ equipped with weights $W$. Let $L$ be the weighted graph Laplacian matrix, i.e. $L_{ij} = -W_{(i,j)}$ for $(i,j)\in E$ and $L_{ii} = \sum_{j:(i,j)\in ...
- 11
10
votes
1
answer
492
views
(Asymmetric) matrix power series in closed form: $\sum_{i=0}^{\infty} A^i \left(A^i\right)^{\top}={?}$
Let $A\in \mathbb{S}^{N\times N}$ be a symmetric, real and stable matrix, i.e., $\rho(A)<1$, where $\rho(A)$ stands for the spectral radius of $A$. Then, $$\sum\limits_{i=0}^{\infty} A^{2i}=\left( ...
- 767
2
votes
1
answer
128
views
Are the eigenvalues of the 1D lattice with random weights known?
Consider the adjacency matrix $\mathbf{A}$ of a one dimensional lattice of size $N$. That is, $A$ is a $N\times N$ matrix with $A_{ij}=1$ if vertex $i$ adjacent to vertex $j$ (there exists an edge ...
- 274
1
vote
1
answer
286
views
Bound on $i$th largest eigenvalue in a large Erdos-Renyi graphs
Typical magnitude of $i$th largest eigenvalue of an Erdos-Renyi random graph seems to decay at least exponentially with $i$. Is there an analytic expression for the constant in the exponent, or a nice ...
- 2,442
2
votes
1
answer
900
views
Asymptotically tight concentration of norms of subgaussian random vectors with independent coordinates, as the dimension $n \to \infty?$
Let $X=(X_1 \dots X_n)\in \mathbb{R}^n,$ be a subgaussian random vector so that $X_i$'s are independent, $\mathbb{E}X_i = 0, \mathbb{E}X_i^2=1.$ Before we pose our question, let's state the following:
...
- 1,465
1
vote
1
answer
104
views
Limit of normalized sum of Dirac measures at first $\lfloor p/2\rfloor$ eigenvalues of the sample covariance matrix, with Marcenko-Pastur assumptions?
Let $\lfloor{*}\rfloor$ denotes the nearest integer $\le *$. I'm asking myself the question what's the limit of the part of the empirical spectral distribution corresponding to the first $\lfloor{p/2}...
- 1,465
2
votes
2
answers
536
views
Modularity in a graph -- derivation of modularity score
Background
I am currently reading "Modularity and community structure in networks" (2006) by Newman [1].
In it, he derives a score for the modularity of a graph ...
- 121
5
votes
1
answer
680
views
What is the Essential Difference Between Random Matrices and Random Graphs?
I have the impression, that random graphs and random matrices seem to be perceived and treated as separate areas of interest; I'm not an expert in either of the subjects, so maybe my impression is ...
- 13.2k
2
votes
0
answers
64
views
Largest eigenvalue of two types of slightly different random matrices
Consider two types of slightly different $n \times n$ symmetric random matrices $X$. The diagonal elements of $X$ are fixed as $1$. Suppose $\frac{k}{n} \to \alpha$ for some constant $\alpha\in(0,1)$.
...
- 272
4
votes
1
answer
412
views
Distribution of eigenvectors and eigenvalues for random, symmetric matrix
Consider two simple, undirected graphs with adjacency matrices ${\bf A}$ and ${\bf A'}$. Let ${\bf P} = {\bf A'} - {\bf A}$. Thus, ${\bf P}$ is symmetric and always 0 along the diagonal.
Let $f({\bf ...
- 43
3
votes
2
answers
579
views
Largest eigenvalue of the adjacency matrix of weighted random graph
I find the theorem for largest eigenvalue of the adjacency matrix of ER random graph in here https://arxiv.org/pdf/math/0106066.pdf. The adjacency matrix is a symmetric random matrix s.t. diagonal ...
- 272
3
votes
0
answers
151
views
Largest eigenvalue divided by $n$
Let $X$ be an $n\times n$ symmetric random matrix whose diagonal is fixed as $1$, and every element in the upper triangle (excluding the diagonal) is drawn from Bernoulli($p$). The elements in the ...
- 272
3
votes
0
answers
77
views
Eigenvalue Spectrum density for a simple non-iid matrices
As a part of research, I am studying the eigenvalues spectrum of adjacency matrices. My adjacency matrices are symmetrical. However, their elements are following multivariate gaussian distribution. ...
- 31
3
votes
1
answer
338
views
Modularity in a graph - definition of the random component
This question concerns the definition of modularity in a graph.
Consider a simple, undirected, unweighted graph $G$ with vertices in set $V$ and edges in set $E$ . Between any two vertices there is ...
- 31
6
votes
1
answer
200
views
Modification of matching
Suppose i have an $n \times n$ random bipartite graph and suppose that i repeat the following process $n$ times. At the start (stage 1) each edge is selected independently with probability $p(n)$, and ...
- 903
8
votes
2
answers
2k
views
Statistics of strongly connected components in random directed graphs
I'm interested in the statistics of strongly connected components in random directed graphs. However, I'm unable to find any results on this, partly because I don't know the terminology to search for.
...
- 1,344
8
votes
2
answers
702
views
limiting empirical spectral distribution of the Laplacian matrix on an Erdos-Renyi graph?
Let $G$ be an Erdos-Renyi random graph (i.e. an edge ($ij$) exists with probability $0 < p < 1$ and all edges are independent). Let $L$ be the Laplacian matrix of this graph (i.e $L=D-A$, where $...
6
votes
0
answers
302
views
Behavior of eigenspaces of adjacency matrices of random graphs (not via perturbation theory)
For the sake of discussion, let us say that we have the adjacency matrix $A$ of a graph, on $n$ nodes, from a stochastic block model with 2 blocks. Another name for this (usually used in computer ...
- 1,731