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.

12
votes
0answers
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 ...
12
votes
0answers
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 ...
10
votes
0answers
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....
7
votes
0answers
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. ...
6
votes
0answers
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 ...
5
votes
0answers
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 ...
5
votes
0answers
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 ...
5
votes
0answers
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 ...
4
votes
0answers
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 ...
4
votes
0answers
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-...
4
votes
0answers
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, ...
4
votes
0answers
32 views

terminology for a “forward flow” type of random digraph

I am trying to find a characterization of the probability that vertex $1$ is connected to an arbitrary large vertex $N$ in a random digraph. The difference from typical random digraphs is that if $(...
4
votes
0answers
529 views

Stochastic dominance of Binomial and Poission

In order to investigate the size of the cluster of a given vetex in a random graph I need to use a fact about stochastic dominance that I don't know how to prove. Namely, I am looking for a proof of ...
4
votes
0answers
113 views

2-dimensional percolation and a random graph

Imagine turning the square grid defined by $\mathbb{N}^2$ in the plane into a directed graph. The vertices are $\mathbb{N}^2$ and for each vertex $(x,y)$, there is an edge pointing from it to $(x+1, y)...
3
votes
0answers
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 ...
3
votes
0answers
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 ...
3
votes
0answers
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 ...
3
votes
0answers
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$. ...
3
votes
0answers
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 ...
3
votes
0answers
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 ...
3
votes
0answers
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$?
3
votes
0answers
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$ ...
2
votes
0answers
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 ...
2
votes
0answers
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? ...
2
votes
0answers
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 ...
2
votes
0answers
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 ...
2
votes
0answers
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 ...
2
votes
0answers
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 ...
2
votes
0answers
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 ...
2
votes
0answers
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 ...
2
votes
0answers
37 views

Asymptotics of $\sum_{k=m}^N u_k$ knowing the first term and $\frac {u_{k+1}}{u_k}$

Lemma 1.3 in "Random graphs" by Frieze and Karoński contains the following treatment of asymptotics unclear to me. Claim. Let $n,m \in \mathbb N, N = \binom n2, p= \frac mN$. Define $$u_k = \binom ...
2
votes
0answers
127 views

Expected value for edge existence and independence, given a class of random graphs

Set up Let $G$ be a graph with $n$ vertex: $\{ e_i \}_{i=1}^n = E$. Define, for all $i$ and $j$ from $1$ to $n$, $e_{i,j}: E \times E \rightarrow \{0,1\}$, the random variable which takes $1$ if ...
2
votes
0answers
98 views

Lower bound on average shortest path in graphs

I am looking for information on the lower bound of the average shortest path in a connected undirected graph, given the number $n$ of vertices and number $k$ of edges in the graph. I would like to ...
2
votes
0answers
87 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')$ ...
2
votes
0answers
98 views

Probability that a random bipartite graphs is the intersection of simple cycles

I have the following problem and honestly i don't know how to start working on it. Any clue will be appreciated. I need to calculate the probability that following the Erdos-Renyi model, a random ...
2
votes
0answers
41 views

Limit of a certain sum

I need to show that $$\sum_{i=0}^{m} \binom{m}{m-i}\binom{m^2-m}{i} (1-p)^{\binom{i}{2} + i m} \bigg/ \binom{m^2}{m} (1-p)^{\binom{m}{2}} \to 0$$ as $m \to \infty$, where $p = \frac{1}{m}$, and the ...
2
votes
0answers
197 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 ...
2
votes
0answers
279 views

Cut distance between two random graphs

I am studying the cut metric from Large Networks and Graph Limits by Lovasz and need help proving one of the statements. On page 128, it says that the cut distance between two independent random ...
2
votes
0answers
236 views

Large Random Graph is Surely Connected

I'm trying to prove that for a random graph on $n$ vertices with edge-probability $p \in (0, 1)$ is almost surely connected as $n$ grows large. I've tried making an argument using the probability of ...
2
votes
0answers
133 views

Expected size of largest connected component in a random k-out digraph?

Given a digraph with n vertices and kn edges, where each vertex has k out-neighbors randomly chosen at uniform without loops, how would I go about figuring out the expected value of the size of the ...
2
votes
0answers
102 views

maximum degree of $G(n,n^{-\varepsilon})$

I am given a graph $G(n,n^{-\varepsilon})$, so a random graph with each edge drawn independenly with the probability $n^{-\varepsilon}$ and I want to somehow bound the maximum degree $d_\max$, such ...
2
votes
0answers
403 views

Expected path length in a Random Geometric Graph

Random Geometric graphs (graphs where n points are placed at random in the unit square, and two nodes are connected with probability 1 if $r \leq r^*$) are known to percolate iff: $$\pi r^2 = \frac{\...
2
votes
0answers
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$ ...
2
votes
0answers
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”. ...
2
votes
0answers
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 ...
1
vote
0answers
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 ...
1
vote
0answers
44 views

Is it true that a random graph's degree gives Poission distribution?

In many documents, it is said that a random graph's degree follows Poisson distribution. However, my numerical calculation contradicts with the fact. Assume a random graph whose number of nodes $N = ...
1
vote
0answers
24 views

Probability of having a path connecting clusters of random graphs

Construct a graph $H$ with $3n$ nodes in this way: Create three $G(n, p)$ graphs on a line, each with $p{n \choose 2}$ many edges within each cluster. For any node-pair in the neighboring ...
1
vote
0answers
39 views

Size of min-cut in a Rényi–Erdős graph

For a Rényi–Erdős graph $G(n, p)$, what can we say about the size of the min-cut (in the whole graph)? I'm looking for something like this: $$ \Pr(\text{min-cut-size} > x) \geq \cdots $$ or $$ \...
1
vote
0answers
27 views

Materials to read for Graph Theory.

I am interested in graph theory and currently finished learning the basic knowledge in graph theory. Before I continue on to study the following three branch of graph theory, namely Topological Graph ...