# Questions tagged [random-graphs]

A random graph is a graph - a set of vertices and edges - that is chosen according to some probability distribution. In the most common model, $G_{n, p}$, a graph has $n$ vertices, and edges are present independently with probability $p$. Use (graphing-functions) instead if your question is about graphing or plotting functions.

611 questions
Filter by
Sorted by
Tagged with
24 views

25 views

### Model Epidemic Random Graph

I'm reading on random graphs and understand that they can be used to model disease spread (seems particularly germane at the moment). The papers I've found so far are focused on quite complex models. ...
27 views

### Number of triangles in a random graph.

Let G be the random graph $G\left(n,\frac{\log(n)}n\right)$, i.e. the graph on $n$ vertices with each edge independently having probability $\frac{\log(n)}n$ of being in the graph. I wrote a program ...
72 views

### zero-one-law in percolation theory

I am currently working on a paper by Lyons from 1990 which can be found at https://projecteuclid.org/download/pdf_1/euclid.aop/1176990730. In chapter 6 Percolation (page 951, 21 respectively) the ...
24 views

### A graph $G(n,p)$ has $\Omega(k^2)$ edges of a special type, $k \in \mathbb{Z}^+$. If $p = \omega(k^{-2})$, then w.h.p. one of the edges is in $G$.

Why is it so? I know that the probability that none of those edges appears in the graph is $(1-p)^{k^2}$, but not sure how to continue with the reasoning.
18 views

### Hiting line in a 2D plane in a 1m radius with shortest walk

Imagine you where in a 2d plane and the place is so dark that you can't see anything. In a 1 meter radius around you, there is a rope (straight line). What would the shortest walk be for hitting that ...
18 views

### Construct a subgraph of the complete graph with a fixed distribution of valences

Suppose that I want to find a "well connected" large random graph where the distribution of the valences follow a fixed distribution. Is there a smart way to construct such a graph? More ...
37 views

### Expected value of random walk over signed network

A connected weighted graph $G(V,E,W)$ is give, where $w_{uv}$ corresponds to the probability to jump from node $u$ to node $v$. Also, a function $l$ maps nodes with positive and negative labels, where ...
29 views

### For $G \sim G(n, 0.5)$, $I$ a $k$-set of vertices, and event $E_I = \{G[I] \cong K_k \text{ or } K_k^c \}$, how many events does $E_I$ depend on?

The note in my lecture says that $E_I$ is independent of all events with disjoint edge-sets, and so it depends on at most ${k \choose 2}\left({{n-2}\choose {k-2}}-1\right)$ other events. I don't ...
37 views

### Lines randomly drawn on a page.

Suppose I have a $m \times m$ sheet of paper. Now suppose I draw a line of length $L$. The center of the line must lie within the piece of paper, and the orientation of the line is randomly chosen ...
31 views

### Let $\varepsilon > 0$ be fixed. Then the random graph $G(n,m=(1+\varepsilon))$ is a.a.s not planar.

The exact question is in the title. I understand that I somehow need to find a graph with $K_{3,3}$ or $K_5$ as a minor, but I don't really know how. I got that having $K_5$ as a minor is equivalent ...
16 views

### Stochastic Block Models regimes and topology

Hi I'm trying to understand how regimes and thresholds of Erdős–Rényi model are valid in symmetric stochastic block model. In Erdős–Rényi model $G(n,p)$ each edge is drawn independently with ...
18 views

### Average shortest path and diameter in Poisson-Delaunay graphs

For a given set of $N$ random points, distributed uniformly on a unit square, I construct its Delaunay triangulation. Taking the triangulation as an unweighted graph, I need to know the expected ...
39 views

### How many 2-hop neighbors in ER network?

An ER network is a graph $G=(V,E)=\mathcal{G} (n, p)$, where there're $n$ nodes and for each two nodes $i,j\in V$, the edge $(i,j)$ has the probability $p$ of being present in $E$ and $(1-p)$ of being ...
19 views

### Probability that a node loses an edge in the Barabási-Albert (BA) model with removal of edges

I'm following the book Networks by Mark Newman. He considers an extension to the BA model where edges are removed uniformly at random. He computes the probability that a particular node $i$ loses an ...
47 views

### Number of edges of a random connected undirected graph created by a random walk

Consider the following algorithm that generates a random connected undirected graph with $n$ vertices. Choose a random starting vertex and perform a random walk as follows. At each step $i$ of the ...
47 views

9 views

### Lemma about bounding the weight of a half edge in a random graph

I have a couple of questions about Lemma $11$, page $949$ here. The lemma needs some background about construction of a tree which is described in section $6.2$, right above the lemma in page $948$. ...
44 views

### Expected number of isolated vertices in a random graph.

I'd like to find the expected number of isolated vertices in the random graph $G=(V,E)$, where $V=\{1,\ldots,n\}$, constructed choosing uniformly at random $m$ edges out of the $\binom{n}{2}$ possible ...
34 views

### In a connected random graph, when the degree of each node is at least 2？

In random graphs, we know while $p>ln(n)/n$, the graph is connected. In a connected graph, I want to know when the degree of each node is at least 2 ? If $X$ is ${B(n,p)}$ $n\to+\infty$ When $p$ ...
14 views

### Adjacency spectra of a graph interpretation

I'm not a mathematician and I have a question about spectral graph theory. Is it possible to conclude that we have a fully connected network, if an adjacency spectra of a graph is continuous with no ...
66 views

### Given a set of $n$ random variables, such that each $k_n$ of them are indepedent, can we say something “global” about their independence?

I'm thinking about a certain problem regarding the existance of structures in random graphs, and somwhow it comes down (after some simplifications) to the following probabilistic problem. Assume we ...
20 views

### Average path length in random DAG

Suppose I have a random directed acyclic graph (DAG). By random I mean that edges are drawn uniformly at random so that the adjacency matrix is lower triangular with i.i.d. entries. Is there any ...
49 views

In a random graph $G(n, m)$, there are $n$ vertexes and $m$ edges, the degree mean is $k$. $G$ is connected, i.e., $m>\frac{1}{2}n\ln(n)$, $n\to +\infty$ Broadcasting process: round 0: A vertex ...
24 views

### Constructing a large balanced bipartition of $G(2n,1/2)$ with high probability

Consider the random graph $G(2n,1/2)$. After picking each edge uniformly and independently with probability $1/2$ suppose that we have exactly $m$ edges in total (note: $m$ is not fixed!). Prove that ...
34 views

### Clustering number on ring lattice

I have seen in several places a useful formula that let us calculates the clustering number of regular ring lattice graphs with even degree but I have not found a convincing proof of it. Concretely, ...
17 views

### For $X,Y,$ RVs on $\{0,1\}^V$, does $P(v \in X) \geq P(v \in Y)$ for every $v \in V$ imply that X stochastically dominates Y?

More specifically, for an infinite graph $G = (V,E)$, and random variables $X,Y$ taking values on the subsets of $V$: Suppose that, for every $v \in V$, \mathsf{P}(v \in X) \geq \mathsf{P}(v \in Y)...
### Edge density in subgraphs of an Erdos-Renyi graph $G(n,p)$
Given an Erdos-Renyi random graph $G\sim G(n,p)$, I want to estimate the probability that all the subgraphs of $G$ (that are not too small, say subgraphs on $m>\epsilon n$ vertices) have edge ...