Questions tagged [random-graphs]
The study of probability distributions over graphs. For example, the Erdős–Rényi model where each edge occurs independently with equal probability.
345 questions
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
2
votes
0
answers
64
views
Transversal deviation in first passage percolation
Take the lattice $\mathbb{L}^{2}=(\mathbb{Z}^{2},\mathbb{E}^{2})$ with i.i.d. $\text{U}[0,1]$ weights on the edges, and the random variable $D$ giving the maximal transversal deviation of the geodesic ...
- 640
3
votes
1
answer
108
views
Expected size of matchings in a cubic graph
Let $G$ be a random cubic graph on $n$ vertices. Let $M$ be the set of (not necessarily maximum) matchings of $G$. What is the expected size (i.e. number of edges) of an element of $M$?
In other ...
- 9,501
1
vote
1
answer
198
views
Figuring out a consistent definition for the percolation backbone
In the context of percolation, e.g., bond/site percolation, random graph connectivity in 2-3 dimensions, etc., once the percolation threshold is reached, that is the system is spanned by an infinite ...
- 649
5
votes
1
answer
222
views
Switching oriented paths in a graph
Consider an oriented graph (e.g. a finite part of the standard grid with some random orientations).
Each minute the following operation takes place: we choose uniformly randomly an ordered pair $(A,B)...
- 5,043
1
vote
1
answer
94
views
What is the expected distance between the sides of a random subgraph of the grid?
Let $G$ be the $n \times n$ grid, in which each vertex is connected to the vertices above it, below it and on either side. Let $G_p$ be the random subgraph of $G$ obtained by keeping each edge with ...
- 1,633
3
votes
1
answer
822
views
Open Problems in Random Graphs [closed]
I am a PhD student in mathematics. I'm interested in probabilistic methods in combinatorics and especially random graphs. I am looking for an open problem in this area for my PhD proposal. I know that ...
- 57
0
votes
2
answers
255
views
Random Optimization on Graphs: Minimum Cut
Consider a complete graph on $n$ vertices. To each edge, $(i,j)$, we assign a weight, $W_{ij}$, which comes from some known distribution iid. Then, we ask the following question. Among all (weighted) ...
- 1,096
7
votes
1
answer
257
views
Collecting proofs of the birth of the giant component
I want to collect different proofs of Erdös-Rényi result on the double jump of the largest connected component on $G(n,p)$ (or in $G(n,M)$.
I know the original proof of Erdös-Rényi, the proof that ...
- 1,561
3
votes
2
answers
1k
views
Non-backtracking random walk in regular (finite) graphs
I know that many things are known when dealing with random walks on a finite (or even infinite) graph: mixing time, returns to origin, etc. All is based in the use of the Markovian property of such a ...
- 1,561
3
votes
1
answer
206
views
Component properties in Euclidean graphs with distance threshold
In the context of Euclidean graphs with vertices randomly embedded in either a 2D plane (for instance square with length $L$) or in 3D (similarly, cube of side $L$), where an edge between two given ...
- 649
12
votes
3
answers
1k
views
A Modern Proof of Erdos and Renyi's 1959 Random Graph Paper?
In their paper, Erdos and Renyi consider a random graph with a fixed number of edges, as opposed to the more modern approach of adding each edge independently with probability $p$. From what I ...
- 470
2
votes
1
answer
606
views
Component size distribution in small Erdos-Renyi networks
I'm looking at $\mathcal{G}(n,p)$ (I'll call these Erdos-Renyi networks) where $n$ is, say, at most 10.
I would like to know the probability a random node is in a component of size $m$.
It's ...
- 121
0
votes
1
answer
525
views
The expected value of common neighbors on a random regular graph
Given a random $d$-regular graph on $n$ nodes, what is the expected number of common neighbors between two nodes?
I don't know if it is as simple as just assuming that each neighbor of the first node ...
- 103
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
1
vote
0
answers
61
views
$\exp(-Cn^{\epsilon})$ estimate for probability of Brouwer-Haemers condition in Erdos-Renyi-like random graph
For any $n$-vertex graph $G$, we have the inequality $\lambda_i^{L_G}\geq D_i-i+2,$ where $L_G$ denotes the Laplacian of $G$ and $\lambda_i^{L_G}$ denotes the $i^\text{th}$ largest eigenvalue and $D_i$...
- 276
1
vote
0
answers
209
views
Characterization of k-walk-equivalent graphs
Let $G=(V,E)$ be an undirected graph. A walk of length $k$ in $G$ is a sequence of vertices $v_1,v_2,\ldots,v_{k+1}$ in $V$ such that $(v_i,v_{i+1})\in E$ for each $i=1,2,\ldots,k$.
Call two graphs $...
- 493
6
votes
1
answer
304
views
Citations graphs: what is known?
There has been much research related to web graphs and social graphs.
They can be thought of as a kind of random graphs, but the point is that
they are different from the well-known Erdős–Rényi model.
...
- 24.8k
2
votes
0
answers
49
views
Size of the last non-empty $k$-core of a random graph
Given $n$ and $p$ for $G(n,p)$, how to find the distribution of the size of the non-empty $k$-core with largest $k$?
In particular, what is the probability (for any $n$ and $p$) that only $c$ ...
- 21
2
votes
1
answer
97
views
References on the structure of bond percolation on the (finite) 2D-grid in the sub-critical regime (e.g p=1/10)
Would appreciate references to the most up-to-date results for the structure of bond percolation on the (finite) 2D-grid in the sub-critical regime (e.g, $p=1/10$).
Thank you.
- 131
5
votes
2
answers
444
views
expected length of a largest cycle in regular graph
Consider a simple random regular graph $G_d(n)$ with $d=2$ (that is, I select a $2-$regular graph from the set of all $2-$regular graphs on $n$ vertices, uniformly at random).
It is clear that this ...
3
votes
1
answer
865
views
Uniform sampling of random connected graph with given number of vertices/edges
I am looking for algorithms for the exact uniform sampling of connected labelled graphs with $n$ vertices and $m$ edges. By "exact" I mean that every such graph should be generated with precisely (not ...
- 911
4
votes
2
answers
4k
views
Expected global clustering coefficient for Erdős–Rényi graph
What is the expected global clustering coefficient $\mathbb{E}[C_{GC}]$ for the Erdős–Rényi random graph (ER-graph) $\mathcal{G}(n,p)$ (expectation is over the ensemble of all ER-graphs) as $n \...
- 151
1
vote
1
answer
188
views
KPZ relation $\chi = 2 \xi -1$ in a random geometric graph
If I have $n$ points uniformly distributed on the surface of a torus, and form a graph by adding an edge between pairs whenever they are within a unit distance (induced by the Euclidean metric), I ...
- 640
6
votes
1
answer
341
views
Bounds on degrees of minors obtained by edge contractions of regular graphs
Given a connected $d$-regular graph $G=(V,E)$, generate a sequence of minors by performing only edge contractions and loop deletions (as, e.g., in Karger's algorithm) until the graph collapses to a ...
- 163
0
votes
0
answers
80
views
Not exactly directed percolation
Is the following problem known/well-studies? I'm looking for references or a name that I can look up.
I start with $N$ cell, each one divides into two cells, each one of the new cells either dies ...
- 371
2
votes
1
answer
485
views
Longest Path in a Directed Graph with Specified Number of Edges
Let $G$ be a directed graph that has $n$ nodes and is strongly connected. Define a random path as the following: Pick two vertices uniformly at random and find the shortest path going from one vertex ...
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
1
vote
0
answers
43
views
In weighed random graph where the edge weight is restricted to $[0,1]$, what are the usual assumptions of edge weight distribution?
In classic ER random graph, the edge distribution is Bernoulli. Given a weighted random graph where the edge weight is restricted in $[0,1]$, is there a canonical assumption of the weight distribution ...
- 272
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
5
votes
1
answer
531
views
What is the chromatic number of the Erdős–Rényi graph G(n,d/n) when d < 1?
What is the chromatic number of the ER graph $G(n,d/n)$, when $d < 1$ (there exist expressions for $d > 1$, but what if the graph is super sparse?). Here $n$ is the number of vertices and $d/n$ ...
- 271
1
vote
1
answer
1k
views
An explicit formula for the number of different (non isomorphic) simple graphs with $p$ vertices and $q$ edges
I would like to know if there is an explicit formula for the number of different (non isomorphic) simple graphs with a given number of vertices $p$ and edges $q$, and if yes what is it.
Trying to ...
- 29
2
votes
1
answer
261
views
Minimum dominating sets in tournaments
It is known that in any tournament with $n$ vertices, there is a dominating set of size no more than $\lceil \log_2 n\rceil$. (See Fact 2.5 here.)
What about when the tournament is chosen ...
- 1,209
6
votes
0
answers
105
views
Long loops in critical random graphs
A simple calculation seems to show that the expected number $X_k$ of loops of length $k$ in a critical Erdös-Renyi random graph $G(n,n^{-1})$ is approximately given by
$$ \mathbb{E} X_k=\frac1{2k}{e^...
13
votes
1
answer
409
views
When is the union of a graph and a random permutation thereof connected?
First things first: in what follows, a "random permutation" of a set $\Omega$ with $n$ elements does not necessarily mean an element chosen uniformly at random from $\textrm{Sym}(\Omega)$. Rather, and ...
- 20.1k
4
votes
2
answers
420
views
Conditional probability that a random spanning tree contains the edge e
Let $G$ be a connected simple graph with two distinct edges $e,f \in E(G)$. Choose a random spanning tree $T\subseteq G$, my question is whether there are any known upper bound for the following
\...
- 43
21
votes
2
answers
548
views
Do these polynomials have alternating coefficients?
In answering another MathOverflow question, I stumbled across the sequence of polynomials $Q_n(p)$ defined by the recurrence
$$Q_n(p) = 1-\sum_{k=2}^{n-1} \binom{n-2}{k-2}(1-p)^{k(n-k)}Q_k(p).$$
Thus:
...
- 44.4k
7
votes
2
answers
1k
views
Edge probability for connected Erdős–Rényi model
Consider the Erdős–Rényi model $G_{n,p}$ with corresponding probability measure $\mathbb{P}_{n,p}$. For any two vertices $x,y$, $\mathbb{P}_{n,p}[E_{x,y}]=p$, where $E_{x,y}$ is the event that there ...
- 71
1
vote
1
answer
167
views
Vertex reachability in random graph
Given $n$ vertices, one of which is $z$. Consider a uniform random tournament: Between any two vertices $x,y$, with probability $0.5$ draw an edge from $x$ to $y$; otherwise draw an edge from $y$ to $...
- 1,209
2
votes
1
answer
237
views
Subsets of a graph, maximal w.r.t. the property of inducing a subgraph with minimum degree at least $k$
Let $G=(V,E)$ be a simple undirected graph. Define an mmd$k$s in $G$ (for 'maximal minimum degree $k$ subset') to be any subset $S$ of $V$ such that
the subgraph induced by $S$ in $G$ has minimum ...
- 393
2
votes
0
answers
92
views
Erdös-Renyi Model with prescribed subgraph
In the Erdös-Rényi model for random graphs there is a lot of results stating sharp phase transitions for the probability of a random graph to contain a fixed prescribed ...
- 2,630
1
vote
0
answers
79
views
Generation of randomly looking graph coordinates
Let $G$ be some connected graph. We pick randomly $k$ distinct vertices $l_1, l_2, \cdots l_k \in V(G)$. We call them the landmarks.
We define $d(u,v)$ to be the length of the shortest path between ...
- 323
3
votes
1
answer
396
views
Threshold for appearance of a cycle
I am interested in a random graph $G\sim G(n,p)$. I know that if $p<<1/n$, then $G$ will be a forest. I happen to be interested in the boundary case where $p=c/n$, where $c<1$ is a constant....
- 2,955
8
votes
0
answers
240
views
Stepanov phase transition in random graph
Consider the classical random graph model G(n,p), with p=c/n, as proposed by Erd\"os and R\'enyi.
At this scaling, the most prominent feature is arguably the abrupt change of the topology that the ...
- 468
2
votes
1
answer
181
views
zero-one law in bipartite random model $G(n,n,p)$
Consider the binomial random graph model $G(n,p)$ with $0<p<1$. We say that $G(n,p)$ satisfies the Zero-One law if for every first order property $Q$ one has
$$\lim\limits_{n \rightarrow \infty}...
- 683
0
votes
1
answer
1k
views
Random graphs- Erdos and Renyi 1959 paper
Please refer to this link. It is Erdos and Renyi's first paper on Random Graphs (1959). I am trying to work through it.
I'm struggling with equations (16), (17) and (21).
(16)
I'm not sure why ...
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
2
votes
0
answers
220
views
mixing time of random walks on dense Erdos Renyi graphs
Is there anything known about the mixing time of a simple random walk on an Erdos-Renyi graph with parameter $\langle n,d \rangle$ where $d=n^a (0<a<1 )$. I know about Reed et al and Benjamini ...
