Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

7
votes
1answer
542 views

The probability of having a perfect matching in a bipartite graph

Say we have a bipartite graph $G$ with two sets, $\{x_1,\dotsc,x_n\}$ and $\{y_1,\dotsc,y_n\}$. For each pair $xy$, there is an edge with probability $p$. Then, what is the probability of having a ...
2
votes
0answers
199 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 ...
6
votes
1answer
1k views

Expectation number of cycles in a Erdős–Rényi random directed graph $G(n,p)$

Let $G \sim G(n,p)$ be a directed Erdős–Rényi random graph with $n$ vertices and the probability $p$ that there is a directed edge between any two ordered pairs of vertices. What is the expected ...
3
votes
1answer
7k views

Expected number of triangles in a random graph of size $n$

Consider the set $V = \{1,2,\ldots,n\}$ and let $p$ be a real number with $0<p<1$. We construct a graph $G=(V,E)$ with vertex set $V$, whose edge set $E$ is determined by the following random ...
2
votes
2answers
135 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 ...
3
votes
1answer
159 views

Probability of having a girlfriend in a school with groups

A school has $r$ groups. Each group has $n$ girls and $n$ boys. Any boy and girl know each other with probability $p$ if they belong to the same group, and with probability $q$ if they belong to ...
2
votes
1answer
211 views

Expected number of edges: does $\sum\limits_{k=1}^m k \binom{m}{k} p^k (1-p)^{m-k} = mp$

Find the expected number of edges in $G \in \mathcal G(n,p)$. Method $1$: Let $\binom{n}{2} = m$. The probability that any set of edges $|X| = k$ is the set of edges in $G$ is $p^k (1-p)^{m-k}$. So ...
1
vote
2answers
251 views

How many paths of length 2 in a general random graph?

Suppose you have several random graphs. Each one has $n$ nodes, connected among them with probability $p$. There are $r$ random graphs. Now, each node is connected to nodes of another random graph ...
12
votes
1answer
691 views

Probability that a random graph is planar

I've been attempting to solve the following challenge problem from a combinatorics class but am getting absolutely nowhere. Prove: For sufficiently large $n$, the probability a random graph $G=(V,E)...
10
votes
1answer
674 views

What is the probability that a random $n\times n$ bipartite graph has an isolated vertex?

By a random $n\times n$ bipartite graph, I mean a random bipartite graph on two vertex classes of size $n$, with the edges added independently, each with probability $p$. I want to find the ...
6
votes
3answers
200 views

Show $y = \sum_{k=1}^\infty \frac{k^{k-1}}{k!} x^k$ satisfies $ye^{-y} = x$.

My question is literally the title: Show $y = \sum_{k=1}^\infty \frac{k^{k-1}}{k!} x^k$ satisfies $ye^{-y} = x$. Here's a little motivation for the question. If you don't care about motivation, ...
7
votes
1answer
436 views

Probability of two vertices to be connected in G(n,p)

Let $G(n,p)$ be an Erdős–Rényi graph on $n$ vertices. Is there an explicit expression for the probability $P_{n,p}(u,v)$ that two fixed (distinct) vertices $u,v$ lie in the same connected component of ...
5
votes
0answers
997 views

What can be said about the number of connected components of $G(n,p)$ random graphs?

By a $G(n,p)$ graph we mean a graph on $n$ vertices, all possible edges are independently included randomly with probability $p$. What can be said about the number of connected components? For ...
2
votes
0answers
90 views

Indicator function for a vertex-induced random subgraph of $G$?

I am trying to find polynomial, indicator function or sometimes called structure function to express whether a vertex-induced random subgraph $H$ of $G$ is connected or not. The polynomial $\phi(G')$ ...
7
votes
5answers
260 views

asymptotics of the expected number of edges of a random acyclic digraph with indegree and outdegree at most one

A recent discussion, which may be found here, examined the problem of counting the number of acyclic digraphs on $n$ labelled nodes and having $k$ edges and indegree and outdegree at most one. It was ...
6
votes
2answers
604 views

Probability that an undirected graph has cycles

If we know the probability $P$ that there exists an edge between two vertices of an undirected graph, let's say $P= 1/v$, where $v$ is the number of vertices in the graph, what is the probability ...
2
votes
0answers
290 views

Probability of having a path of a given length in a random graph

Suppose $G=\langle V,E \rangle$ is a directed graph consisting of $n\in \mathbb{N}$ vertices. Vertex $v_i \in V$ has an edge to vertex $v_j \in V$ with a probability of $P(i, j) = f(|i-j|)$ where $f$ ...
2
votes
1answer
108 views

Creating a uniform distribution on the set of all $r$-regular graphs on $n$ vertices.

On pg 5 of Janson's paper Random Regular Graphs: Asymptotic Distributions and Contiguity the following is mentioned: Given $r$ and a vertex set $V$ with $n$ elements (with $rn$ even), define a ...
1
vote
2answers
2k views

What is the expected size of the largest strongly connected component of a graph?

Given a directed graph with n vertices and the probability of any edge existing being p, what is the size of the largest strongly connected component in the graph? What if its undirected graph? Can we ...
4
votes
3answers
2k views

Probability of a graph having at least 1 k-clique

I need to estimate the probability $P(\text{Graph G has at least 1 k-clique})$, any precision will do. I know the edge probability, say $p$, so the average number of the edges, $EK$, is $pm(m - 1)/2$, ...
3
votes
1answer
751 views

Probability that exists at least an edge in the configuration model

In this period, I am studying some topics on random networks to understand the modularity optimization used in community detection. In particular, I am trying to understand a model called ...
1
vote
1answer
1k views

Cover Time for Random Walk on a cycle

I'm trying to find the expected time to cover all $N$ nodes on an undirected cycle graph, starting from a given node $k$. The probabilities of moving clockwise and anticlockwise are $\frac{1}{2}$ each....
1
vote
1answer
693 views

estimate value of maximum cut in graph by random sampling

I have an unweighted, undirected graph G=(V,E) from which I am sampling a set S of $\frac{kn}{ε^2}$ edges uniformly at random, where k is constant and ε is a variable parameter. From this set S I want ...
1
vote
2answers
68 views

Probability of not having a path between two certain nodes, in a random graph

Suppose we construct an Erdős–Rényi graph $G(n, p)$. Fix two nodes $u$ and $v$. What is the probability that there is no path connecting the two nodes? My take: I tried to model the problem as $P(...
1
vote
1answer
285 views

does a power law degree distribution imply graphs are sparse?

Lets say I have a random variable with values in the space of square binary matrices from which I can sample (adjacency matrices of) graphs, and lets say that the resulting graphs have a power law ...
0
votes
0answers
287 views

Estimate value of maximum cut in graph using Chernoff and union bounds

I read this: estimate value of maximum cut in graph by random sampling but I didn't understand how to solve my problem that is very similar. My problem is let $G(V, E)$ be an unweighted and ...
0
votes
0answers
77 views

Arbitrary vs. random subsets: computing probabilities

Let $G=([n],E)$ be a graph having minimum degree $\delta(G) \geq (1-\delta) n$. For some $q=q(n)$, let $G_q=([n], E_q)$ be the random subgraph of $G$ obtained by deleting each edge independently with ...
0
votes
0answers
327 views

Sample Code to Generate Points on the Rim of a Randomly Rotated Cone : What's Going On Here?

Related to this question: https://math.stackexchange.com/questions/407897/randomly-generate-point-on-shell-from-3-points-2-angles-with-uniform-angle-dis I'm trying to reverse engineer the math-...
0
votes
0answers
698 views

Creating Barabási–Albert(BA) graph with spacific node and edgs

I am trying to construct a BA graph with 500 nodes and about 37000 edges. The number of edges to attach from a new node to existing nodes should be at least 91 to make enough number of edges. I ...