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$.
4
votes
0answers
49 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 ...
4
votes
0answers
58 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
44 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 ...
3
votes
0answers
12 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, ...
2
votes
0answers
21 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 ...
2
votes
0answers
13 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$?
2
votes
0answers
62 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 ...
2
votes
0answers
44 views
Expected diameter for non-regular random graph
I'm wondering whether I could determine the expected value for the diameter of a random graph given the distribution of the degree of the vertices.
Specifically I have a network of computers that ...
1
vote
0answers
30 views
Extracting hitting times from the pseudoinverse of a Laplacian matrix for an undirected graph
Provided a pseudoinverted Laplacian matrix for an undirected graph $G$, how can I extract first passage and commute times between vertex pairs in $G$?
1
vote
0answers
20 views
Independence and the size-biased degree distribution in the configuration model
I'm teaching a course on complex networks using M.E.J. Newman's Networks: An Introduction. There is a claim in the book that is not really justified, and I don't know how to prove it.
Background and ...
1
vote
0answers
26 views
Connectivity of a random graph
I am wondering whether a $k$-regular graph of size $n$ is connected. $k$ in my case is 8 and $n$ is ~3500. Any way of calculating the probability of such a graph not being connected?
1
vote
0answers
59 views
What discrete distribution is completely determined by its mode and variance, is easy to sample, and has nice border properties?
I need to generate random ordered unranked trees that will be used to test some computer program. I'd like to incorporate some kind of control into the generation process, so that the generated trees ...
1
vote
0answers
53 views
Compute the probability $p$ of creating an edge in $G(n,p)$. (Erdős–Rényi random graph)
Consider $G(n,p)$, an Erdős–Rényi random graph with $n$ nodes, $m$ edges, and mean degree $c$:
Compute the probability $p$ of creating an edge in $G(n,p)$.
What exactly it means?
1
vote
0answers
26 views
Models for multiple graphs
I am trying to understand how to model multiple graphs. To make that concrete, I have two distinct graphs $\{V_1, E_1\}$ and $\{V_2, E_2\}$ where $V_i$ and $E_i$ are the node sets and the edge lists ...
1
vote
0answers
83 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$ ...
