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

3
votes
1answer
19 views

Looking for information about a random graph model

I have the following random graph model, and I am looking for its name and/or any work done concerning it. Given $n$ nodes, $\{v_1,...,v_n\}$, and $n$ timesteps, proceed as follows: On the $k$th ...
0
votes
0answers
11 views

How to show a random matrix has large spectral gap?

If I know $Y$ is a random d-regular bipartite graph (tanner code in coding theory), can I show $Y^TY$ has large spectral gap with high probability? More specifically: If I know $Y=AX \in ...
1
vote
0answers
17 views

Expected number of leaf nodes in some theoretical graph models

If a leaf node of a graph refers to a node having the degree of 1, how can one compute the expected number of leaf nodes of: (A) a random graph (e.g., Erdos-Renyi graph), (B) a small-world graph ...
0
votes
0answers
67 views
+50

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 ...
0
votes
0answers
17 views

Graph Theory: small-worldness

I have two groups, each including several networks. I calculate following three network measures for each network clustering coefficient characteristic path length small-worldness (by comparing 1 ...
0
votes
0answers
13 views

The minimum degree of G(n,p) with p=(1+o(1))ln(n)/n

It is not difficult to show, using standard concentration bounds, that for $G\sim G(n,p)$ with $p=f(n)\cdot\ln{n}/n$, $f(n)\ge 1+\varepsilon$, $\varepsilon>0$ constant, that $G$ is nearly regular. ...
0
votes
1answer
28 views

Question on the proof of the upper bound of girth in dense graph.

I have trouble understanding the proof of the following theorem from Upfal's Probability textbook pg 134 Theorem: For any integer $k \geq 3$ there is a graph with n nodes, at least ...
1
vote
2answers
19 views

Why is the maximum cut of an undirected graph at lest 1/2 the number of edges in the graph?

In Upfal's Probability textbook he claims in Theorem 6.3 Given an undirected graph G with n vertices and m edges there is a partition of V into two disjoint sets A and B such that at least m/2 edges ...
1
vote
1answer
37 views

Components in random graphs $G(n,p)$

My question involves two constants which I don't know how to compute, but it probably doesn't matter. The constant $C>0$ is rather small, say $C=e^{-1000}$. The constant $K$ is larger than $1$. I ...
2
votes
0answers
32 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 ...
0
votes
0answers
11 views

Statistics, distributions and graphing

Lets say that you have data containing one variable - the waiting time between each car passing from 1200 hours... so you have something like 23, 54, 26, 8, 2, 59 etc what is the best way to analyse ...
0
votes
1answer
28 views

Threshold for matchings in random bipartite graphs

In the calculation on pages 82-83 of the book on Random Graphs by Janson et al they calculate the threshold for matchings in the random bipartite graph $\mathbb{G}(n,n,p)$. They say that if ...
2
votes
3answers
36 views

Probability for 2 vertices to lie in the same component of a random graph

Consider $G(4,p)$ - the random graph on 4 vertices. What is the probability that vertex 1 and 2 lie in the same connected component? So far, I have considered the event where 1 and 2 do not lie in ...
0
votes
1answer
21 views

Generate random graph under centrality constraints

Is it possible to generate a random graph under centrality constraints? I am currently working on a project involving characterization of biological properties stemming from different centrality ...
2
votes
1answer
47 views

Probability of a cubic graph containing a perfect matching

Let $G_n$ be a uniformly random cubic graph on $n$ vertices (cubic=all vertices have degree 3). What's the probability $p_n$ that $G_n$ contains a perfect matching? Does it have a limit? Note that ...
0
votes
1answer
17 views

Attractors of a Random Boolean Network?

I need some direction on the topic of Random boolean networks (NK-boolean networks or Kauffman automata). I now some of the results like if K=1 the systems settles down to fixed points, if K=2 it ...
3
votes
2answers
43 views

Random walk on a tree

Consider a Cayley tree with coordination number 3 (http://en.wikipedia.org/wiki/Bethe_lattice). Consider two sites, $x$ and $y$, having a distance $k$ one from another. What is the probability that ...
5
votes
1answer
83 views

Almost every graph is asymmetric?

Here is a question: If i choose at random an isomorphism class of graph(no loops, undirected) on n vertices(with uniform probability on the set of such isomorphism classes), is the probability that ...
1
vote
0answers
43 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 ...
1
vote
0answers
34 views

If I colour $n$ vertices independently, randomly with $n^{(1-x)}$ colours, why is the size of the colour classes $(1+o(1))n^x$?

By $o(1)$, I mean 'little-o' of $1$. A paper I'm reading uses this result, but I can't see where it comes from. Thanks.
0
votes
0answers
42 views

A question on Chung-Lu model of random graph modeling

when I read this book chapter, I got confused on this statement on the first page: $$w_i=K\text{ when }i/n=BK^{-\beta+1}$$ Is $K$ a constant or a random variable? I guess it's a constant. What is ...
0
votes
2answers
64 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
20 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
28 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
1answer
68 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
41 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
78 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
33 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
25 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
37 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
25 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
19 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
27 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
37 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
19 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
118 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
66 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
34 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
40 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
60 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
65 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
37 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
91 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
57 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
72 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
142 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
62 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
106 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
36 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
51 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 ...