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

-1
votes
1answer
21 views

What is the probability of a chain of a given length in a random graph?

Let $G$ be an undirected graph with $n$ nodes. An edge is randomly and independently drawn from each node to any of the other nodes. If some arbitrary node $a$ is chosen, what is the probability that ...
1
vote
0answers
13 views

Nearest node in a generation of a random graph

Assume I have a set of $n$ nodes that I want to define their pairwise distances. I also assume that a node $i$ is characterised by an exponential distribution with parameter $\lambda _i$ in the ...
1
vote
0answers
19 views

Deviation of number of cycles of length 4 in Erdős–Rényi random graphs.

I'm working on my homework and can't find any relevant information for this problem. Problem: Let $G(n, p)$ be Erdős–Rényi random graph. I need to find deviation of number of cycles of length 4 in ...
1
vote
0answers
60 views

Phase trasition of $f(x)$ on random graph $G(n,p(n))$

Random graph $G(n,p(n))$ and graph $H$, which shown below, are given. I'm in need to find $f(x) : f(x) > 0$, such as: if $lim_{n \to \infty}p(n)f(n) = 0$, then asymptotically almost surely G ...
0
votes
0answers
34 views

Nullifying columns of a matrix by nullifying rows

Let $A$ be a real rectangular matrix. Each column of $A$ is a nonzero vector. Now each row of $A$ is nullified with probability $p$, all independently of each other. What is the probability that ...
1
vote
1answer
75 views

Hypergraph rainbow colouring of $\{1 \dots n\}$ for $A = \{A_1, \dots A_k\} : A_i \subset \{1, \dots n\}$

We are given collection of sets $A = \{A_1, \dots A_k\}$, where each set $A_i \subset \{1,\dots n\}$. Colouring $\{1, \dots n\}$ into $s$ colours would be called 'rainbow' for given $A$, if $\forall ...
0
votes
1answer
23 views

Proof for k-connectedness of random graphs

I am really new to the theory of random graphs. It seems a lot of articles take for granted that: For $k\in\mathbb{N}\setminus\{0\}$ and $p\in(0,1)$ fixed, almost every graph in $G(n,p)$ is ...
0
votes
1answer
22 views

Bounds on the Neighborhood Size of a Random Vertex in $G(n,p)$

Let $G(n,p)$ be the Erdős-Rényi random graph model. I am interested in the regime $p = c/n$, where $c > 0$. Further, let $B_G(d)$ denote the neighborhood of depth $d$ of a randomly chosen vertex ...
1
vote
1answer
33 views

What kind of studies are this?

at this link there are quite a number of images reporting different patterns inside a circle: what kind of studies are this and does this belongs to a specific branch of the mathematics ?
0
votes
1answer
18 views

Question about consistency in the junction tree algorithm (graphical models

I have a question about consistency in graphical models. It is often stated that when running the junction tree algorithm on a clique (cluster) tree, the marginals of all nodes are locally and ...
1
vote
0answers
18 views

Random graphs: A random graph induces a distribution on each link. Do they uniquely determine the graph?

Let $G$ be a random graph with $n$ nodes, with the nodes numbered. $G$ induces a distribution in the set of all graphs of $n$ nodes and we can identify this distribution with $G$. Given the nodes ...
0
votes
1answer
22 views

How to calculate a line vector from a bunch of points.

I get a bunch of not really random points, which should be abled to formed a single line, the example looks like the following: In this sample, we could easily imagine there is a line formed by the ...
2
votes
0answers
32 views

How to compute the following sum?

How to compute the following sum? $$\sum_{k=1}^{\infty} \frac{k^{k-1} \cdot e^{-k}}{k!}$$ It is likely to be equal $1$ (there is an argumentation that goes back to random graphs). Moreover, i think ...
1
vote
0answers
17 views

Navigation in a graph

The problem Let $G=(V,E)$ be a graph. $k = O\left(\log(|V|)\right)$ distinct vertices are picked randomly from $V$. We call the set of chosen $k$ vertices $T$. We define the graph metric $d$ for ...
3
votes
0answers
62 views

Extinction probability of binomial branching process tends to poisson one.

The folowing is stated and proved in the random graphs book by Luczak, Janson, Rucinski and this is on page 108 in the Giant component section. I can't understand why the conclusion follows from the ...
0
votes
1answer
39 views

Random Binary Search Tree, expected value of nodes with two children

In class, the professor showed that using a uniform random permutation $$ X_1,..., X_n$$ (each being i.i.d.) we can construct a Binary Search Tree by inserting the values in to the tree by their ...
0
votes
0answers
31 views

Recognize a shape with a set of Data points

So I have a number of points on graph. For Ex: (1,1) (2,5) ......... and so on. And I want to recognize which shape is it closest to from circle, triangle and rectangle. -By closest I mean ...
1
vote
1answer
30 views

raBinomial distribution with dependent trials?

I need your help with following problem: String with n characters is given. For each character in string there is probability p that it is wrong. Now you take a sliding window of length k, k<= n, ...
1
vote
1answer
46 views

How to compute the average number of wedges and triangles present in the Erdős-Rényi random graph?

Let $ER_{n} (p)$ be the Erdős-Rényi random graph (see the second model in the link), where $p=\frac{\lambda}{n}$. Furthermore, let $W_{ER_{n}}$ be the number of wedges in the graph, and ...
0
votes
0answers
59 views

What does it mean for a stochastic sequence to be “stochastically smaller” than some other stochastic sequence?

A relatively simple type of random graph is the Erdős-Rényi random graph. The graph created by means of the following process: Let $V$ consists of $n \in \mathbb{N}$ vertices, and let each edge of the ...
0
votes
1answer
25 views

Generating a weighted random graph with a correlation between degrees per edge and edge weight

I would like to generate using a single, coherent mathematical formalism a weighted random graph, either a small-wolrd or a scale free graph, with a probabilistic distribution of weights and vertex ...
2
votes
1answer
61 views

Graphs: probability of two vertices, chosen at random, of being connected by a link

If I choose the vertices h and k in a simple graph uniformly, I know the probability of them being joined by an edge is $ \frac{2e}{n(n-1)} $ , where: e is the number of edges in the graph, n is the ...
2
votes
1answer
46 views

What does scale free mean in terms of a scale free graph

My understanding of a scale free graph is as follows: Say if we have a large graph $G$ if we were to take random partitions of $G$: $g1, g2,\dots$ Any centrality metric (such as page rank, degree ...
1
vote
1answer
66 views

Probability that the distance from some source vertex to any other vertex is at most exactly $l$ in a random graph?

Given a random (undirected and unweighted) graph $G$ on $n$ vertices where each of the edges has equal and independent probability $p$ of existing (see Erdős–Rényi model). Fix some vertex $u\in G$ and ...
7
votes
0answers
106 views

Why “One cannot construct more than countably many independent random variables”?

I'm reading the book "Large Networks and Graph Limits" by László Lovász. On the page 18 he said the following: One cannot construct more than countably many independent random variables (in a ...
2
votes
1answer
55 views

A basic question on random graph

Consider undirected graphs with $n$ vertices. now consider the set of all possible edges (excluding self-loops). now, select edges from the set with probability $p$ independent of the other edges. so, ...
3
votes
0answers
101 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 ...
0
votes
0answers
26 views

Threshold function for component of size $k$

Show that, for each fixed $k$, there is a function $p(n)$ such that the probability that $G(n,p(n))$ has a component of size exactly $k$ tends to $1$ as $n \rightarrow \infty$. My initial thoughts are ...
0
votes
0answers
46 views

Proving properties of Random Graphs

I am asking the question on a slightly abstract level and it may depend on the specifics but it would be great to have related references or ideas. Consider the random graph model $G_{n,p}$ where its ...
0
votes
1answer
22 views

Types of graphs for this

How many ways could this be graphed, in a way such that it shows that the degree or slope of a surface affects the average speed. I think T1, t2 etc means at second 1, second 2. This was done using a ...
0
votes
1answer
75 views

Counting nodes in a random tree

Suppose we have a random tree where the probability that a node has $n$ successors is given by $\delta(n)$. What is the distribution of the number of nodes at the $s$-th level deep in the tree, ...
0
votes
0answers
50 views

Percolation Theory Basics: Open cluster size decay (Square Lattice)

I am trying to learn some stuff about percolation. On wiki (http://en.wikipedia.org/wiki/Percolation_theory) it says: "when $p<p_{c}$, the probability that a specific point (for example, the ...
1
vote
1answer
28 views

Random graphs question regarding exponents

On page 19 http://www.iecn.u-nancy.fr/~chassain/GDT/documents/SpencerStFlour.pdf All in the first Paragraph. it gives an estimate of (they use equal instead of approximation) ...
1
vote
0answers
34 views

Expected number of neighbor nodes of a subset of nodes of a randomly constructed bipartite graph

Suppose a right-regular bipartite graph with $m$ left nodes and $n$ right nodes ($m>n$ and $B=m/n$ is an integer) is constructed as follows: First, each successive $B=m/n$ left nodes are connected ...
2
votes
0answers
33 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 ...
1
vote
1answer
71 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 ...
5
votes
0answers
95 views

Probability of transmission between two nodes in a neural network at exactly d timesteps

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 the ...
0
votes
2answers
74 views

Asymmetry of random graphs

By a well known result of Pólya we know that the number $g_n$ of isomorphism classes of simple graphs on $n$ vertices is asymptotically equivalent to $\frac{2^{\binom{n}{2}}}{n!}$. In this paper the ...
1
vote
2answers
55 views

Highest degree vertices in random graph with hidden clique

We create a random graph $G(n,1/2)$. Next, we choose randomly $k$ vertices, and form a clique out of these $k$ vertices. My question is: how do you prove (with high probability) that when $$k > ...
0
votes
1answer
78 views

Derivative of average number (density) of clusters in Erdős–Rényi random graph

Let $G(n, p)$ be the Erdős–Rényi random graph model with $n$ vertices and $p\in[0,1]$. Furthermore let $\mathbb{E}_{n,p}[k]$ be the average number of clusters (counting isolated vertices as $1$). I ...
1
vote
0answers
78 views

Density of bridges for critical random regular graph

Let $G_{n,d}$ be the space of all $d$-regular graphs with $n$ vertices. Now choose a graph from $G_{n,d}$ uniform at random. Once obtained do independent bond-percolation on it, i.e. keep an edge with ...
0
votes
1answer
63 views

Expected number of $k$-cliques in $G(n, 1/2) \ge 1$

Let the expected number of $k$-cliques be denoted by $$f(k) = \binom{n}{k} (\frac{1}{2})^{- \binom{k}{2}}$$ let $k_0$ denote the largest $k$ such that $f(k) \ge 1$. I want to prove that $k_0 = ...
1
vote
1answer
63 views

Probability there is no vertex at distance larger than $d$ away from source in random graph?

Given a random (undirected and unweighted) graph $G$ on $n$ vertices where each of the edges has equal and independent probability $p$ of existing (see Erdős–Rényi model). Fix some vertex $u\in G$ and ...
1
vote
1answer
81 views

Number of connections for a graph

Suppose we have a graph $G(12,0.7)$ where 12 is the number of nodes and 0.7 is the probability of an edge being present. So total number of edges = $\binom{12}{2} = 66$ Q1 (SOLVED): What is the ...
1
vote
1answer
43 views

Threshold for apperance of quite short paths/cycles in random graphs

We say that a graph $G$ is distributed with $\mathcal{G}_{n,p}$ if it is a graph on $n$ vertices, and for which each of the ${n\choose 2}$ possible edges is chosen independently of the other edges and ...
3
votes
0answers
327 views

Expected Value of the maximum of a set of random variables (not indep)

As a preface, this is related to a graph of $n+1$ nodes, which is generated through (equally likely) random attachments to existing nodes - this occurs in $n$ "stages" of attachment. Suppose that we ...
0
votes
1answer
15 views

Mean number of FFL subgraphs with one output node

So, this is a Feed Forward Loop. It is a regularly occurring subgraph of a huge random graph. In the case of X,Y,Z being any nodes, we have that the mean number of times that a subgraph G appears is ...
1
vote
1answer
57 views

Predicting the number of simple circuits in a graph

If I have a directed graph with $n$ vertices, and the mean number of out-edges per vertex is $x$, what is the expected number of simple circuits that will be found in the graph? What happens to the ...
5
votes
1answer
87 views

Probability of finding a Hamilton circuit in a graph

In short, I would like to know either/both the probability that there exists a Hamiltonian circuit within a graph, or the number of circuits expected to exist. (Without actually finding all the ...
0
votes
1answer
39 views

Expected number of feed-forward/backward triangles in a random graph with internal nodes.

Suppose we have a graph with N* nodes (these are internal nodes. they all have at least one child). Every directed link in the network exists with probability p. What would be the expected number of: ...