A random graph is a graph 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$.

learn more… | top users | synonyms

0
votes
2answers
44 views

Probability spaces over graphs: which area has focus on them?

Suppose a simple graph $G$. Now consider probability space $G(v;p)$ where $0\leq p\leq 1$ and $v$ vertices. I want to calculate globally-determined properties of $G(v;p)$ such as connectivity and ...
0
votes
0answers
40 views

Boolean function analysis on random graphs?

Random graphs have some properties that are determined in some random way such as edge probabilities in the interval $[0,1]$. Ryan O'Donnell's book "Analysis of Boolean Functions" (2014) has analysis ...
0
votes
0answers
27 views

Probability of a given deterministic graph containing a k-clique

I want to approximate the properties of a given, deterministic, undirected Graph $G$ without multiple edges. To be precise: I want to know the probability $P$ that $G$ with $n$ edges and $z$ ...
3
votes
0answers
78 views

Trace of power of random matrix / sum of random variables with semicircle distribution

I want to calculate the expectation value for the trace of the $m$-th power of the $n\times n$ adjacency matrix $A$ of a large Erdos-Renyi random graph (without self-coupling, i.e., all diagonal ...
0
votes
1answer
33 views

Probability of at least one triangle in Erdos-Renyi graph

Cross-posting here as I didn't get a satisfactory solution on cv. This is a well-known problem in random graph theory, where we show that if $X$ is the number of triangles in $G(V,E,p)$ with ...
2
votes
1answer
21 views

Random Geometric Graph in unit disk

According to the Wikipedia article, to define a random geometric graph, one needs a metric space. In the examples they give for 2D random geometric graphs, they say that "an RGG can be constructed ...
1
vote
1answer
68 views

What is the expected number of of $k$-tuples of vertices such that all edges between the vertices have the same colour?

Consider the complete graph $K_n$ and suppose we colour each edge of $K_n$ red or blue with equal probability. For every $k$, $1\leq k \leq n$, give a formula for the expected number of $k$-tuples ...
-1
votes
0answers
23 views

How to find the graph (network) is even or uneven graph?

I want to split one Graph into two mutually exclusive subgraphs by applying following structural condition: even versus uneven allocation of nodes into two mutually exclusive groups. but i don't ...
0
votes
1answer
26 views

What is the official name for the ratio of edges to nodes in a connected graph?

In my context, the nodes are code elements and the edges are "dependencies". So I am using the term "dependency density" to refer to the ratio of edges/nodes. Is there an official term for this ratio ...
3
votes
0answers
39 views

How to formalize this statement about $G_{n,p}$ and $G_{n,m}$?

I'm reading a proof of the following Thereom: If $m/n \to \infty$ then $G_{n,m}$ contains a triangle wit high probability. The first line of the proof states: Because having a triangle is ...
1
vote
2answers
42 views

Probability $u, v$ are connected in a random graph model

There is a random graph problem. Given an undirected graph $G(V,E)$ associated with $p_{uv}$ to denote the probability there is an edge between $u$ and $v$ ($p_{uv}$ are independent, maybe different ...
1
vote
0answers
20 views

Step in using Stirling's formula to get an upper bound

I'm having trouble seeing why the following holds. Given the conditions that $N=\binom{n}{2}$ and $m$ is a function of $n$ such that $N-m \to \infty$ as $n \to \infty$, why is it that $$(1+o(1)) ...
0
votes
0answers
25 views

The number of vertices in cycles in $D(n, p=c/n)$ is bounded in probability

Let $c \in (0,1)$ and let $D(n,p=c/n)$ be a random directed graph. Prove that the number of vertices in cycles in $D(n,p)$ is bounded in probability. That is, for any $\delta = \delta_n \rightarrow ...
1
vote
0answers
17 views

Confused about this notation about random graphs in Bollobas' book

After Theorem 2.1 on page 26 (second edition) he states Note that the arugment above shows that if $Q$ is a nontrivial monotone increasing property then $$P_{p_2}(Q) \ge P_{p_1}(Q) + \{1 - ...
1
vote
1answer
29 views

Number of distinct vertices in a random walk on a graph

Let $G$ be a graph on $n$ vertices. Is it possible to calculate the expected number of distinct vertices seen in a simple random walk of length, say, $k < n$? Moreover, how is this affected when ...
1
vote
1answer
42 views

Probability of at least one isolated clique forming

Is there any "famous" random graph model in which the probability of at least one isolated clique forming is monotonic in the parameters? For instance, are any results known in this matter for the ...
-1
votes
1answer
37 views

Asymptotic enumeration of regular graphs

I have been following a few papers on the asymptotic enumeration of $r$-regular graphs of $n$ vertices, $L_r$. According to Random Graphs, $L_r = L_n \sim \sqrt{2} e^{- \frac{\left(r^2 - ...
0
votes
1answer
46 views

Random graph problem

I'm trying to analyze a network algorithm to get a latency probability distribution. One of the steps is to "calculate the probability distribution of the number of updated nodes in a single hop of a ...
1
vote
1answer
69 views

The expected number of triangles in Erdos-Renyi graph : why wrong derivation also works?

So I know how to correctly calculate the expected number of triangles in the Erdos-Renyi graph using linearity of the expectation value operator (See this for example). However, now consider a "wrong" ...
1
vote
1answer
20 views

Average node degree k in a geometric random graph is $\frac{\Pi r^2n}{l^2}$

The paper "Small-Worlds: Strong Clustering in Wireless Networks" (http://arxiv.org/pdf/0706.1063.pdf) is indicating empirically that the average node degree $<k>$ is (or can be approximated by) ...
1
vote
0answers
22 views

The Laplacian spectra of random graph $G(n,m)$ and $G(n,m+k)$

I am currently doing some work related to the eigenvalues of the Laplacian of a graph. Define $\sigma_i=\frac{\lambda_i}{\lambda_2}$, where $0=\lambda_1<\lambda_2\leq\cdots\leq \lambda_N$ is the ...
0
votes
0answers
23 views

Probability of maximum degree in On random graphs I by Erdos

In The Maximum Degree of a Random Graph by RIORDAN et al., the authors commented that the study of the distribution of the maximum degree $d^{max}(G)$ of a random graph $G$ was started by Erdos and ...
0
votes
1answer
31 views

Confused with the power set of an integer

I am going through The Maximum Degree of a Random Graph by RIORDAN et al. On the second page, the notation $\mathbb{P}(\mathcal{D})$ is used which I assume the power set of the set $\mathcal{D}$. ...
0
votes
0answers
11 views

The random graph quantity $S(n: K, L)$

I am going through Degree sequences of random graphs by Béla Bollobás. On page $3$ the author introduces the quantity $S(n: K, L)$ without any explanation. Could anyone please help me in ...
0
votes
1answer
23 views

Calculating the probability of a graph being Erdos-Renyi

Given an undirected, unweighted graph with |V| = 11 and |E|= 19 and given probability p=0.5 I have to calculate the probability of the graph being generated using the Erdos-Renyi Model. I applied the ...
0
votes
2answers
50 views

threshold for random 2-sat

I'm looking at notes on the threshold for random 2-sat which is given as $r_{2}^{*}=1$. In the first part of proving the threshold they claim that a 2-sat formula is satisfiable if and only if the ...
0
votes
0answers
37 views

Show With High Probability $G_{n, p}$ has an induced path of length $(\log(n))^{1/2}$

The problem on which I am working states: Let the probability $p = d/n$ where $d > 1$. Show that with high probability, $G_{n, p}$ contains an induced path of length $(\log(n))^{1/2}$. My ...
2
votes
3answers
54 views

Finding the limit of ${n-1 \choose k}p^k(1-p)^{n-1-k}$ as $n$ goes to infinity

On this Wikipedia page on random graphs, they compute this limit to be $$\lim_{n\to\infty}\binom{n-1}kp^k(1-p)^{n-1-k}=\frac{(np)^ke^{-np}}{k!}$$ with $np$ constant. Any hints on how to get that? ...
3
votes
2answers
118 views

Show With High Probability, No Vertex Belongs to More than One Triangle

I am working on a random graphs problem, which is stated as follows: Suppose that $p = d/n$, where $d$ is constant. Prove that with high probability (w.h.p.), no vertex belongs to more than one ...
2
votes
0answers
47 views

Are the vertices of a Voronoi diagram obtained from a Sierpinski attractor also a kind of attractor?

Trying to understand how the Voronoi Diagrams work I did a test generating the Voronoi diagram of the points obtained from The Chaos Game algorithm when it is applied to a $3$-gon. The result is a set ...
1
vote
2answers
38 views

Ensure a graph approximates an Erdős-Renyi random graph even as nodes are added

Suppose we have a graph $G$ where the number of nodes increases over time, e.g. whenever the mean number of edges per node exceeds some value (which may be a function of the number of nodes). What is ...
0
votes
1answer
59 views

Sparse sequence of random graphs

I have the following definition for sparse random graphs: In the lecture it was said that actually this type of graphs have a lot of "hubs", i.e. a lot of vertices of high degree. But this is ...
2
votes
1answer
85 views

Max matching size in a random graph

Consider the random graph $G(n,\frac{1}{n})$. I'm trying to estimate the size of the maximum matching in $G$. If we look at one vertex, the expected value of its degree is $\frac{n-1}{n}$ so it ...
1
vote
1answer
20 views

Random graph application

Hi am looking at the theorem 1.1 but I can't come to that distribution. Can someone tell me how does this factor comes in the distribution of $D_n^*$? That sounds trivial but I cannot get it. ...
0
votes
1answer
28 views

Random Graph - lower bound in the number of edges going out from a subset of vertices

I need to proof the following: Show that exist a costant $c=c(p)>0$ (with p the probability in the random graph) such that for a subset $X\subset V(G)$ with G a random graph G(n,p) and with ...
1
vote
2answers
42 views

Is it possible to construct the Rado Graph as a countably infinite graph with non-constant edge probabilities?

Let's say we have a countably infinite set $V$ of vertices and a map $f:V\times{V}\to{(0,1)}$ that assigns to each pair $(i,j)$ of vertices an edge with probability $f(i,j) = p$. I believe that if ...
1
vote
0answers
24 views

One proof in Random graph Bela Bollobas about Hamiltonian Cycles

In Random Graph 2001 (Bela Bollobas), P209, the proof for lemma 8.7, it says that $\sum_{u=u_0-1}^{u_1}\sum_{w=1}^{\llcorner(\gamma - 1)u\lrcorner}(\log n)^w (\frac{e}{u})^u(\frac{eu}{w})^wn^{\gamma ...
-2
votes
1answer
79 views

Random graph of $4$ vertices is triangle-free

Consider an undirected random graph $G$ of $4$ vertices. The probability that there is an edge between a pair of vertices is $\frac{1}{2}$. What is the probability that $G$ is triangle-free? Thank ...
1
vote
1answer
87 views

Random graph is simple cycle or tree

Consider an undirected random graph $G$ of $n$ vertices. The probability that there is an edge between a pair of vertices is $p$. What is the probability that $G$ is simple cycle of $n$ vertices or ...
0
votes
1answer
26 views

Stochastic domination of the cluster size

I have troubles understanding the main idea used to prove the following theorem, which should be a coupling argument. My question refers to the following notes, at page 125. ...
1
vote
0answers
38 views

Expected number of vertex-pairs without any simple path in between

Consider a random undirected graph $G(n, p)$, with $n$ vertices and each edge is added independently with probability $p$. The goal is to find the expected number of vertex-pairs without any simple ...
0
votes
1answer
62 views

Expected degree of a vertex in a random network

In the paper "Finding and evaluating community structure in networks" by M. E. J. Newman and M. Girvan section 5a, when they construct random communities as a network, they state: Edges were ...
0
votes
1answer
34 views

CLT version for $ER_n(p)$ graphs

We defined the Erdôs- Rényi graph as follows: $ER_n(P)$ is the random graph with vertex set $[n]$ where each pair $\{u,v\}$ of vertices is added to the edges set $E$ independently with probability ...
1
vote
1answer
37 views

How can classical random graph theory be applied to real world networks?

In real world networks, we have no further information about the structure of the networks. For example, in the Facebook network, we assume each one has some known particular probabilities to ...
0
votes
0answers
21 views

About the Alon-Krivilevich-Vu result on concentration of eigenvalues of random matrices.

I am looking at the statement in theorem 5.4 in these notes, http://www.math.ucla.edu/~nickcook/talagrand.pdf I had a few questions about the statement of this theorem, Can someone kindly clarify ...
1
vote
0answers
33 views

Branching process - generating function

I report our definition of a branching process. Let $X$ be a random variable with $\mathbb{P}[X=j]=p_j$ and $(X_{n,i})_{n,i\geq 1}$ i.i.d. random variables with $X_{n,i}\overset{\mathcal{L}}{=}X$. ...
1
vote
2answers
121 views

Expected number of isolated vertices for random graph G(n, N)

For a random graph G(n,p), I can understand how to calculate the E(X) where X is the number of isolated vertices. However, in the case of fixed N edges (N = cn), I am not sure how to proceed in the ...
0
votes
0answers
24 views

Why is there an extra power of of g in this integral?

I'm trying to understand this paper: Betweenness Centrality in Large Networks. They are looking at the distribution of $g$ (betweenness centrality) and $k$ (degree centrality) in large graphs. They ...
0
votes
1answer
35 views

Probability that a random graph on countably many vertices is connected

Fix $0 < p < 1$ and let $G$ be a random graph on elements $\mathbb{N}$ where for $n,m \in \mathbb{N}$, the probability that there is an edge between $n$ and $m$ will $p$. What is the probability ...
1
vote
1answer
69 views

probability of having cycle in a random directed graph with a given in-degree distribution

Consider directed graph $G \left(V, E\right)$. Let random variable $N$ be the in-degree of a vertex. We assume that in-degree values are i.i.d random variables with PMF $f_N(n)$. 1- What is the ...