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.
29 questions
12
votes
1
answer
509
views
Probability of a graph procedure
We are going to build $K_n$ one edge at a time. Begin with the empty graph on $n$ vertices. Take a random permutation of the edges of $K_n$ and, one at a time, place the edges onto the graph (so, ...
- 175
5
votes
3
answers
411
views
Simple graphs with prescribed degrees as disjoint union of simple subgraphs with prescribed degrees
Consider a set $V$ of $n$ vertices, and three degree sequences $a_i$, $b_i$ and $c_i$ such that $c_i = a_i+b_i$, $i=1..n$.
Assume these degree sequences are graphical: there exist simple graphs (no ...
- 1,444
57
votes
4
answers
15k
views
Connectivity of the Erdős–Rényi random graph
It is well-known that if $\omega=\omega(n)$ is any function such that $\omega \to \infty$ as $n \to \infty$, and if $p \ge (\log{n}+\omega) / n$ then the Erdős–Rényi random graph $G(n,p)$ is ...
- 7,857
13
votes
3
answers
835
views
What fraction of n-point sets in the unit ball have diameter smaller than 1?
This question is inspired by a recent talk by Matt Kahle on random geometric complexes.
Some simple notation: let $\mathcal{B} \subset \mathbb{R}^d$ be the unit ball in $d$-dimensional Euclidean ...
- 15.5k
12
votes
3
answers
3k
views
Area Enclosed by the Convex Hull of a Set of Random Points
Consider $n$ points generated randomly and uniformly on a unit square. What is the expected value of the area (as a function of $n$) enclosed by the convex hull of the set of points?
- 123
3
votes
0
answers
107
views
Random graphs with prescibed degrees and triangles
In short: a random graph model generates (multi-)graphs with prescribed number of edges and minimal number of triangles for each vertex. Questions arise about the actual number of triangles and the ...
- 1,444
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
10
votes
1
answer
889
views
What is the theory of the random poset?
$\DeclareMathOperator\Th{Th}$The random poset is the Fraisse limit of the class of finite posets, just like the random graph is the Fraisse limit of the class of finite graphs? That is, the random ...
- 4,587
10
votes
2
answers
2k
views
Probability of Generating a Connected Graph
$N$ points are generated randomly within a unit square, with a uniform distribution.
What is the probability that the points form a connected graph, given that two points are connected if the distance ...
- 103
10
votes
4
answers
3k
views
"sparse graphs are locally tree-like"
I would like to be able to state with confidence that sparse graphs (graphs with small numbers of edges) are locally tree-like (they have few short cycles). Apparently "Sparse graphs are locally tree ...
- 101
8
votes
1
answer
447
views
Graphons and Graphs
The situation is as follows: assume we have a sequence of simple weighted graphs $(G_n)_{n\in\Bbb{N}}$. For the terminology that follows I refer to Limits of dense graph sequences by László Lovász and ...
- 81
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
6
votes
1
answer
618
views
The structure of small components in random graphs with a given degree sequence
Background and definitions
Consider a random graph on $n$ vertices with a nicely behaved degree sequence. That is, letting $d_i(n)$ denote the number of vertices of degree $i$, suppose that for all $...
- 462
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
6
votes
1
answer
571
views
How does the distribution of Erdős number evolve over time ? How to build a model to fit the real data ?
Let $E(n,t)$ be the number of mathematicians with finite positive Erdős number $n$ at time $t$. As old mathematicians leave, and new mathematicians come, how does $E(n,t)$ change over time ?
We can ...
- 2,581
5
votes
2
answers
845
views
Database of adjacency matrices on cospectral non-isomorphic graph pairs
Is there a repository of cospectral non-isomorphic graphs available somewhere?
I am looking for list of $0/1$ adjacency matrix pairs that can be input data in tools such as MATLAB.
- 13.9k
5
votes
1
answer
1k
views
How many distinct eigenvalues does a random graph have?
It is well-known that a random graph a.e. has diameter 2. It is also well-known that the number of distinct eigenvalues of a graph is at least the diameter plus one.
But what is known about the ...
- 6,962
4
votes
2
answers
207
views
Fast uniform generation of random graphs with given degree sequences - any implementation?
The paper below presents a linear-time algorithm for uniform generation of random graphs with given degree sequences [1].
This is very interesting in practice, but I found no implementation. However, ...
- 1,444
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
4
votes
1
answer
245
views
Probability of a vertex being a "degree-celebrity" in a random graph
If $G(n,p)$ is a random graph of the Erdös-Rényi model,
what is the probability that $\mathrm{deg}(v)\gt\mathrm{deg}(u)\ \forall u\in\mathrm{adj}(v)$
Please feel free to relate answers to other ...
- 13.2k
4
votes
0
answers
617
views
Expected number of components with multiple cycles in a subgraph of a square lattice
Short version
Is there an understanding of the emergence and subsequent disappearance of components with zero, one, or more cycles in a random subgraph of a square or cubic lattice, as the edge-...
- 1,414
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
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
3
votes
1
answer
192
views
Discrepancy of random bipartite graphs
This is a crosspost from MathStackExchange (original question).
Fix $k>0$ and let $X, Y$ be two vertex sets of size $n$ a positive integer (we're interested in the limit $n\to \infty$).
Define a ...
- 3,446
2
votes
1
answer
426
views
Random subgraph properties
Consider a graph $G$ of $N$ vertices and $M$ edges, and assume $G$ has typical complex network properties: it is not necessarily connected, but it has a high clustering coefficient and a giant ...
- 129
2
votes
0
answers
69
views
Are two degree sequences compatible, for random simple graph generation?
Consider a set $V$ of $n$ vertices, and three degree sequences $a_i$, $b_i$ and $c_i$ such that $c_i = a_i+b_i$, $i=1..n$.
Assume these degree sequences are graphical: there exist simple graphs (no ...
- 1,444
1
vote
0
answers
164
views
Locally "unshortable" paths in graphs
Setup: Consider a connected graph G, with diameter "d".
Informally: Trivially (by definition of diameter), taking any path $P$ any nodes $P(i) , P(i+k)$ for $k>d$ can be connected by a ...
- 24.8k
1
vote
0
answers
78
views
Canonical representation of the a probability distribution for Hammersley Clifford Theorem
I'm reading the following paper
http://www2.stat.duke.edu/~scs/Courses/Stat376/Papers/GibbsFieldEst/BesagJRSSB1974.pdf
On page 7 they give the result that
$$Q(\textbf{x}) = \sum_{1 \leq i \leq n} ...
- 903
1
vote
1
answer
152
views
Discrepancy of random bipartite graphs (2)
This question is a modification of the one asked here, which turned out to ask for something too strong to be true.
Given $k>0$ and a positive integer $n$, let $X, Y$ be two vertex sets of size $n$ ...
- 3,446