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.
816
questions
0
votes
1
answer
54
views
Average Distance Between Two Nodes In An Unweighted Tree
Given a random unweighted tree with $n$ vertices, what would be an average minimal distance between two of its vertices?
To put it in a more formal way, let's denote the set of all trees with $n$ ...
2
votes
1
answer
85
views
Probability / Graph Theory / Optimization Problem
I have a problem involving a random graph $G$ with a set of nodes $n_1, n_2, ..., n_k$. A priori, we know approximately the probabilities $p_{ij} ( =p_{ji} )$ that an edge $e_{ij}$ exists between ...
- 21
1
vote
0
answers
42
views
Probability of number of $m$-walks in graph to be $l$
I'm considering this question: if a directed graph with adjacency matrix A satisfy that $P(a_{i,j}=1)=P(a_{i,j}=0)=0.5$ and $a_{i,i}=0$ for any i, j in ${1,...,n}$, where $n$ is the number of the ...
- 41
0
votes
1
answer
48
views
Concentration inequality on graphs
Suppose we consider the graph $G_n$ with $n$ vertices and $nd$ edges, where we choose every
edges $E_1,...,E_{dn}$ uniformly at random from the total set of $n \choose 2$
edges, independently for ...
- 629
1
vote
1
answer
50
views
A graph with bounded degree has typical distance at least $(1-\varepsilon)\log n/\log d_{\max}$ with high probability
Let $(G_n)_{n \geq 1}$ be a graph sequence that has a bounded degree, i.e., $\max_{v \in [n]}d_v = d_{\max} \leq K$ and $G_n$ is connected for every $n \geq 1$. Let $[n]$ be the set of vertices of $...
- 801
0
votes
0
answers
55
views
What is the stablished value for the modularity of the Karate Club?
The question speaks for itself. In the literature, we find that the karate club graph has a modularity value of 0.42. A python library to compute the modularity is networkx. To obtain the modularity ...
- 9
10
votes
1
answer
280
views
Friendship Paradox and the Euler-Mascheroni constant
The friendship paradox is the phenomenon that most people have fewer friends than their friends have, on average. It can be explained as a form of sampling bias in which people with more friends are ...
- 734
0
votes
0
answers
48
views
Random graphs: Show that $\mathbb{P}\bigg[ \mathrm{diam} \biggl(G \biggl(n,\sqrt{\frac{2\log(n)+h}{n}} \biggr)\biggr) > 2 \biggr] = \mathcal{o}(1)$
Let $diam(G)$ denote the diameter of a graph $G$; i.e.
$$\mathrm{diam}(G) := \max_{ { i,j} \in \binom{[n]}{2}} d(i, j)$$
, where $d(i,j)$ denotes the length of the shortest path between the vertices $...
- 3,564
1
vote
0
answers
21
views
Component Analysis in the Subcritical Hypergraph
Let $H_k(n,p)$ be the random $k$-uniform hypergraph on $n$ vertices, where each hyperedge $E\subseteq\{1,\dots,n\}$, $|E|=k$, is included independently with probability $p$. Further, let $d=\binom{n-1}...
- 2,862
5
votes
1
answer
62
views
Law of large numbers for the number of connected components in a random graph
A network evolves similarly to the Preferential Attachment model, with some
important modification. The network starts at time $t = 1$ with one isolated vertex. At any step
$t ≥ 2$, a new vertex, $v_t$...
- 801
0
votes
1
answer
63
views
Percolation theory: Proving that the critical probability is a non decreasing function of the dimension
While I was reading Introduction to Bernoulli Percolation by Duminil-Copin (https://www.ihes.fr/~duminil/publi/2017percolation.pdf), I got stuck with the proof of the following part of the proof of ...
- 43
2
votes
0
answers
23
views
Infinite Maze of Squares with Random Thin Walls: Bounded?
A finite maze is generated as follows: A N×N grid of squares, where N is odd, and each border between two squares, or between a square and the outside of the N×N grid, has a p% chance of being a wall. ...
- 201
0
votes
0
answers
11
views
Are there recent review papers on random digraph models?
I am developing interest in random digraphs. I would like to have a quick survey of the history, concepts and latest developments in random digraph models. Is there some comprehensive contemporary ...
0
votes
1
answer
67
views
Prove that a graph has a vertex of specific degree with high probability
Let $ G_{n,p} $ be a graph with n vertrices, such that each possible edge has a probability of $p$ to exist (there are $ \binom{n}{2} $ possible edges, each one appears in the graph with probability $...
- 3,635
1
vote
1
answer
63
views
High probability of $\sqrt{\log n}$ degree in random graph [duplicate]
I’m stuck on a problem I’ve found in a book on random graphs. Appreciate any help:
Let $G_{n,p}$ be a random graph with $p=\frac{c}{n}$ for some positive $c$.
Show that with high probability there is ...
- 46
0
votes
0
answers
8
views
Trying to formally understand consistency of parameter estimation for random graph models?
Let $G$ be a set of graphs on $n$ nodes with an underlying probability distribution $P: G\rightarrow [0,1]$. The distribution is exchangeable i.e. isomorphic graphs have the same probability.
I also ...
- 1,697
1
vote
1
answer
75
views
Limit probability for a random graph to have an isolated edge
Let $G(n,p)$ be the random graph, a.k.a Erdos-Renyi graph. Show that
$$\mathbb{P}[G(n,p) \text{ contains an isolated edge }] \xrightarrow{n \rightarrow \infty} \begin{cases} 0 \text{ if $p = (1+\...
- 3,564
0
votes
1
answer
26
views
Link probability Barabási-Albert Model
I am interested in a formula that describes the probability that nodes i < j < k of a BA model of size n (that have been added, respectively, at time i < j < k) are such that there is a ...
- 121
2
votes
1
answer
37
views
Random graphs: $p \mapsto \mathbb{P}[G(n,p) \text{ has property } P]$ is a decreasing function for hereditary properties
Definition: A graph $G$ has a herditary property $P$ if for every graph $G$ that
has property $P$, every spanning subgraph of $G$ (i.e. every subgraph on the same
vertex set as $G)$ also has property $...
- 3,564
1
vote
0
answers
31
views
How to construct a sequence of expander graphs with strictly decreasing Cheeger constants?
Let $c > 0$ be a real number. Let's say that a graph is a $c$-expander if its Cheeger constant is at least $c$. I am interested in knowing whether the following construction exists. Any references ...
- 11
1
vote
0
answers
11
views
Name for a vertex, edge, or path that is part of a cycle
I am interested in the fraction of vertices, edges, and paths that are part of a cycle in a random graph (for paths, all edges should be part of a cycle).
To better search the literature, is there ...
- 141
0
votes
1
answer
28
views
Why $\mathbb{P}(\text{vertex $1$ is part of a triangle}) \to 0$ in an Erdös-Rényi graph, as $n \to \infty$?
Let $G(n, \lambda/n)$ be an Erdös-Rényi random graph. I need to show that
$$\lim_{n\to\infty}\mathbb{P}(\text{vertex $1$ is part of a triangle}) = 0.$$
(This post also asks a similar question as mine)
...
- 801
0
votes
0
answers
36
views
Is there a way to construct a bipartite $c$-expander graph, for a given $c >0$?
Suppose that $c > 0$ is a real number. Suppose that we are given integers $n > 0$ and $m > 0$. There are many bipartite graphs $G = (L, R, E)$ with $|L| = |R| = n$ vertices on each side and $|...
- 1
0
votes
1
answer
36
views
Converting a deterministic graph into random graph
When we build a random graph model, we start from an empty graph of $n$ nodes and add $m$ edges or generate a graph with edge probability $p$.
What happens if we start from an arbitrary graph instead ...
- 73
0
votes
1
answer
36
views
Optimize distances between vertices in graph theory
So imagine that I have a weighted graph with some random values ranging between $1$ and $20$, where this integer represents the amount of time required to travel to the node/vertex.
I wanted to know, ...
- 23
0
votes
1
answer
128
views
What is the expected number of paths with length $k$ in Erdős–Rényi random graph?
Consider the Erdős–Rényi random graph. Suppose the graph has $n$ vertices, and two vertices are connected with probability $\lambda/n$,independently. Denote such graph as $G(n, \lambda/n)$.
Let $N_k$ ...
- 801
0
votes
0
answers
28
views
What is the probability that a random graph is connected with at-least one spanning tree?
Consider a random graph $G(n,p)$ with finite $n$. What is the probability that there is at-least one spanning tree.
I know that the expected number of spanning trees is $p^{(n-1)}n^{(n-2)}$. But how ...
- 73
2
votes
1
answer
77
views
Proof that if $np - \log n \rightarrow c$ the probability that $G(n,p)$ is connected goes to $e^{-e^{-c}}$ using Janson's inequalities
I am interested in showing that in the Erdõs-Rényi random graph $G(n,p)$ for $p = p(n)$ satisfying $np - \log n \rightarrow c \in \mathbb{R}$ the probability of $G(n,p)$ being connected goes to $e^{-e^...
- 77
3
votes
1
answer
57
views
Proof of Theorem 7.3 from Bela Bollobas' Random Graphs
I'm trying to figure out a certain bound in a proof of theorem of connectivity of random graphs. This is from a book of Bela Bollobas titled Random Graphs.
What is the probability that for some $r$, $...
- 321
0
votes
1
answer
37
views
Probability that two vertices are connected in a configuration model
Let CM$_n(\boldsymbol{d})$ $(n \gg 4)$ denotes a configuration model with $n$ vertices and degree sequence $\boldsymbol{d}$. Let $l_n$ be the total number of half-edges. Here, two vertices are ...
- 801
2
votes
0
answers
91
views
Network that takes the form of a set of disjoint clusters or communities.
Consider the following simple and rather unrealistic mathematical model of a network. Each of $n$ nodes belongs to one of several groups. The $m$-th group has $n_m$ nodes and each node in that group ...
- 769
0
votes
0
answers
28
views
what is the three-point degree correlation of an uncorrelated network?
Consider a simple uncorrelated network of size $N$. I am trying to figure out what the three-point correlation of its degree distribution is. The hard part (to me) is to find the the probability of ...
- 53
0
votes
0
answers
25
views
Existence of a pair of isomorphic subgraphs in a given graph with large number of edges
I am trying to show that a graph $G$ with $n$-vertices and $pn^2$ edges ($n\geqslant10$, and $p\geqslant10/n$) contains two vertex-disjoint and isomorphic subgraphs with at least $ap^2n^2$ edges, ...
- 175
3
votes
1
answer
89
views
When other components appear in Erdos-Renyi random graph model
In the evolution of Erdos-Renyi random graph, denoted by $G(n,p)$ with average degree $c=n \cdot p$, I am interested in appearance of other components in supercritical regime ($c>1$).
I know that ...
0
votes
0
answers
37
views
Connectivity bounds for random regular fixed degree graphs with edge deletions
Let $G = (V, E)$ be a very large random graph of fixed degree (in my case, 3) , i.e., a regular graph. Let $\epsilon_i$ be independent Bernoulli random variables, s.t. $\epsilon_i \sim f(n)$ where $n$ ...
- 95
0
votes
1
answer
28
views
Expected Trail Length
I live on a node in a countably infinite connected graph where of finite maximum degree. I want to take a trip. The roads are given by independently and identically selecting edges from the graph. I ...
- 1,944
0
votes
0
answers
58
views
Edge Probability of Erdos Renyi random graph
Given a graph $G(n,p)$ modeled by random graph model, is there any way to find $p$ when number of nodes $n$, number of edges $m$, degrees associated with each node and the total degree, probability ...
- 73
1
vote
1
answer
52
views
Constructing uniformly random permutation by coin flippings
Let $R \subseteq \{1 \dots n\}^2$ be a variable of strict partial order on $n$ elements. Initially, $R_0 := \emptyset$. The goal is to gradually and randomly enlarge R, so that R end up being a ...
- 125
0
votes
1
answer
25
views
How to prove that $ P(\alpha(G)\ge k)\le \binom{n}{k}q^{\binom{k}{2}} $?
Let $G\in \mathcal{G}(n,p)$ be a Erdos-Renyi random graph. Let $\alpha(G)$ be the maximal number of the independent set of $G$. Here is a Lemma as follows.
For all integers $n\ge k\ge 2$, the ...
- 934
0
votes
1
answer
38
views
How to get the following inequality: $ E[X]\le n^k p^k? $ for a Erdos-Renyi random graph?
Let $G\in \mathcal{G}(n,p)$ be a Erdos-Renyi random graph. Let $X_k$ be a random variable that the number of cycles in $G$ that are length $k$. How to get the following inequality:
$$
E[X_k]\le n^k p^...
- 934
1
vote
1
answer
86
views
One question about the proof of there is a graph $G$ with girth $g(G)>k$ (that is the length of the shortest cycle in graph $G$) and $\chi(G)>k$
In Diestel's Graph Theory, I try to figure out the proof of Theorem 11.2.2 on page 301:
given any positive integer $k$, there is a graph $G$ with girth $g(G)>k$ (that is the length of the shortest ...
- 934
1
vote
1
answer
30
views
Connectivity of random regular multigraphs
For even integers $n$ and integers $3\le r < n$, is it true that a random $r$-regular multigraph on $n$ labelled vertices, obtained as the union of $r$ independent uniformly random perfect ...
0
votes
0
answers
32
views
Connectivity of random collections of cubes
Imagine a cube $100\times100\times100$, a million little cubes. We randomly pick half of them to be red, half to be blue. Define "connected" to mean, two red cubes sharing a face. (You could ...
- 101
1
vote
1
answer
91
views
One question about the probabilistic method proof of the any large girth number and chromatic number on a graph.
In Diestel's Graph Theory, I try to figure out the proof of Theorem 11.2.2 on page 301:
given any positive integer $k$, there is a graph $G$ with girth $g(G)>k$ (that is the length of the shortest ...
- 934
0
votes
0
answers
35
views
Number of spanning trees in a random connected graph
Let us consider a graph $G$ with n nodes and m edges formed by Erdos Renyi random graph model $G(m,n)$. How do we find the number of spanning trees?
Follow up question, how do we find the number of ...
- 73
0
votes
0
answers
16
views
Recursive formula for estimating the mean number of second neighbors in a network reachable with two paths.
In the iLCD algorithm the EMSN (Estimation of the mean number of second neighbors) and the EMRSN (Estimation of the mean number of robust second neighbors) are approximated.
These values represent, ...
- 1
1
vote
1
answer
37
views
equivalence of random hypergraph models
On Wikipedia it says that for any monotone graph property $P$, the two statements
"$G(n,p)$ has property $P$ with high probability" and "$G(n, p\binom{n}{2})$ has Property $P$ with ...
- 13
1
vote
1
answer
54
views
Second Largest Eigenvalue of graphs without C4
Given a $d$-regular graph, let $\lambda = \max(|\lambda_2|,|\lambda_n|) $ where $\lambda_i$ are the eigenvalues of its adjacency matrix.
Can we show that this value is at most $o(d)$ if the graph is $...
- 35
2
votes
2
answers
74
views
Doubt about probabilistic argument on Wikipedia
In this wikipedia page, a claimed proof of the following statement is sketched out: Given positive integers $g$ and $k$, there exists a graph $G$ containing only cycles of length at least $g$, such ...
- 151
4
votes
3
answers
76
views
When the mean of a non-negative, integer-valued random variable goes to zero, does this imply anything about the other raw moments?
When the mean of a non-negative, integer-valued random variable $X_n$, for example counting paths in a random graph on $n$ vertices between two fixed vertices, goes to zero,
$$\lim_{n \to \infty}\...
- 2,695