# 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.

183 questions
469 views

### What is the Probability of Transmission Between Two Nodes in a Neural Network?

I have a network which is an Erdős–Rényi graph. It is a simple neural network with degree 0.7N where N is the number of nodes. Each weight between neurons is 1/N, meaning that if node n has fired ...
500 views

### Probability of the existence of a path of a specified length between any tw0 vertices in a random graph

Let $G$ be a graph with $n$ vertices, whose average degree is $k$. What is the probability that between any two vertices, there exists a path of length at most $l$? NOTE: For the above problem the ...
767 views

### How many edges does an Erdős-Rényi graph have to have, to almost surely have a component with multiple cycles?

An Erdős-Rényi graph is a random graph, selected according to the distribution obtained one where we have some number $n$ of nodes, and some probability $p$ of each potential edge being present....
724 views

### Generating a Random Connected Graph

Given a graph G(V, E), with |V | = n and |E| = 0 (that is, the graph is empty), and a static set F containing all the possible edges. Consider the following algorithm for generating a random graph. ...
105 views

### Central limit theorem for perfect matching counts

Set $N_G$ the number of copies of graph $G$ in the Erdős–Rényi random graph model $G(n,p)$. We have the law of large number for the number of copies of of graph $G$ i.e. $N_G$ is very close to the ...
111 views

### A probability problem on randomly generated graph

The graph we discuss here is a directed pseudo-graph (two vertices can have multiple edges) with self-loops. The problem is to prove a very intuitively probability formula at the end. The background ...
428 views

### Minimal number of edges removed to make a graph triangle free

I'm interested in finding an upper bound on the expected value of the minimal number of edges one needs to remove from a random graph $G_{n,p}$ (where each edge appears with probability $p$) in order ...
984 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 ...
184 views

### What is the expected length of the diameter of a special random graph?

Let $G=(n,p)$ be a random graph. For example, consider that $G$ is the following graph. Initially, the edges of $G$ is undirected. A random $id\in R$ is assigned to each vertex of $G$. The $id$ of ...
33 views

### Algebraic properties of random graphs

Is anything known about the algebraic properties of random graphs? For example, what is the expected size of the automorphism group of $G(n,p)$? What is the probability that $G(n,p)$ is vertex-...
541 views

### Expected number of cycles of length $k$ in a random graph. My simple (too simple?) solution

I attempted this on my own and got a fairly simple solution. However, after reading proofs here and here, I feel like I have massively over simplified the problem. I understand the other solutions, ...
32 views

118 views

### Prove the probability of the graph containing a triangle is 0 as n→∞

Let $G$ a random graph with $n$ vertices. Every vertex appears in the graph with a probability of $\frac{f(n)}{n}$ ($n$ is the number of vertices so the distribution is uniform), while $f(n)$ is a ...
72 views

### What are the measures, methods, and strategies for analyzing dynamical graphs?

I have a particular type of dynamical graph in mind which I'll describe below to provide motivation for my question, but I think the question applies to anyone working with graphs that change over ...
45 views

### Partition of regular graph

Let $G = (V, E)$ be a $d$-regular graph, drawn randomly using the configuration model. The number of vertices is $|V| = n$. Under this model, we know that the graph looks tree-like locally. In other ...
56 views

### Thresholds for Embedding of Large graphs into random graph

Let $G \sim G_{n,p}$ be a binomial random graph and consider a sequence of graphs $\{H_n\}_n$. When $|H_n|=\mathcal{O}(1)$, then one knows the exact threshold $p_0$ for embeddabiliy of $H_n$ in $G$. ...
89 views

### Joint distribution of degrees of Erdös Renyi random graph

The marginal degree distribution of any particular vertex is $$Bin(n-1,p)$$ in an Erdös Renyi random graph G(n,p). Denoting the degrees of the n vertices as d1,d2,...,dn, can you please let me know ...
340 views

### Bond percolation probability on a Bethe lattice

I derived the bond-percolation probability for a Bethe lattice and my result disagrees with a seemingly reputable reference by Albert & Barabasi (see below). I would be happy if somebody could ...
72 views

### Number of bridges in a random graph $G(n,p)$.

What can we say about the number of bridges in a $G(n,p)$ random graph? For example, can we estimate the expected number of bridges in terms of $n$ and $p$?
313 views

### Probability that a random graph is an expander

I have a random graph $G = (V, E)$ and each edge is in the graph with probability $p$. I need to show that the probability that $G$ is $\delta$-edge-expander* when $\delta= \frac{np}{4}$ goes to $1$ ...
59 views

### Probability of being in same connected component

I would like to answer the following basic question: Let $V$ be a collection of $n$ vertices and fix $x$ and $y$ in $V$. Let $G$ be a random graph on $n$ vertices and $M$ edges. What is the ...
38 views

### Are the eigenvectors of real Wigner matrices made of independent random variables with zero-mean?

I am trying to understand a portion of this paper [p. 3] and got stuck in the following statement, which sounded kind of trivial, but has been deceiving me for a while. Would you help me understand? ...
26 views

### How to randomly sample a social graph to find paths between at least 20% of profiles?

Given a Graph, where we know Total number of nodes (~100,000) Average no of connections per node (~200) Maximum distance between two nodes (~5) How many nodes (and its connections) do we have to ...
90 views

### Steady states to this generalized TASEP?

The standard setup of a Totally Asymmetric Simple Exclusion Process is pictured below: We have a one-dimensional lattice of length $n$ populated with particles($p_1,p_2,p_3$ in this case) that hop to ...
17 views

### Is $\|\lambda\|_3 << \|\lambda\|_2$ for all sub-matrices of a random matrix?

Let $A\in\{0,1\}^{n\times n}$ be a random, symmetric matrix, in which each upper triangular entry is sampled iid. from Bernoulli($p$). Let $\lambda=(\lambda_1, \dots, \lambda_n)$ be the vector of ...
35 views

### A Random Edge-colored Digraph Process

I'd like to understand a particular random graph process that I'll describe below. I don't know if it is difficult or elementary, any pointers would be helpful. For a given set $\{1,\dots,n\}$ of ...
50 views

### Probability of a path between two vertices, in a modified version of a random graph

Define $G$ to be random graph, with the following constructiion: The network begins with an initial node. New nodes are added to the network one at a time. Each new node is connected to the existing ...
56 views

### number of edges in a transitive closure of a random directed graph

First two definition: (A) Random Directed Graph: Suppose we have a random $DAG(n, p)$. Here is how it's generated: Put n distinct nodes on a line, and connect each node in the $i$th order to any ...
37 views

286 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$ ...
35 views

### how the number of steps needed depends on the number of nodes and depends on the transmission range?

I run the consensus algorithm, and for each round k, we record the norm of the disagreement vector(|(|δ(k)|)|>〖10〗^(-6)). We stop, at a predefined value|(|δ(k)|)|>〖10〗^(-6) and we call this “k_stop”. ...
554 views

### Erdős-Rényi graphs. A question about nodes degree

Let $G = (V, E)$ be an Erdős-Rényi graph, with $N = |V|$ nodes, $L = |E|$ edges. The distribution of the degree of any particular node is binomial (or Poisson under certain condition). Suppose that ...
28 views

### Probability of random graph being connected - block model

Let $n\in \mathbb{N}$ be given. Let us assume that the set of vertices is $V=[n]=\mathcal{C}^+ \cup \mathcal{C}^- \cup \mathcal{D}$, where the sets $\mathcal{C}^+$ and $\mathcal{C}^-$ stand for the ...