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

0
votes
1answer
17 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
28 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
28 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, ...
0
votes
1answer
34 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
55 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
17 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
46 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
0answers
29 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
60 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
80 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
54 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
80 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
23 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
37 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
21 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
72 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
36 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
28 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
68 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
81 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
50 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
72 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
76 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
48 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
62 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
79 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
29 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
277 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
14 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
71 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
34 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: ...
0
votes
1answer
30 views

Expected number of directed links in a network

Suppose we have a network with n nodes, in which every directed link exists with probability p (independent from each other). What would be the expected number of directed links if we express them in ...
1
vote
1answer
48 views

Random Graphs: Examples of their Uses

Just writing a paper at the moment on random / random geometric graphs. If any of you could perhaps give examples, as broad and interesting as possible, of where these have been used across science? ...
1
vote
1answer
59 views

Probability that exists at least an edge in the configuration model

In this period, I am studying some topics on random networks to understand the modularity optimization used in community detection. In particular, I am trying to understand a model called ...
2
votes
1answer
528 views

Expected number of triangles in a random graph of size $n$

Consider the set $V = \{1,2,\ldots,n\}$ and let $p$ be a real number with $0<p<1$. We construct a graph $G=(V,E)$ with vertex set $V$, whose edge set $E$ is determined by the following random ...
1
vote
1answer
50 views

Probability that there is an edge between two nodes in a random geometric graph

I am new to Random geometric graphs. I have a graph with vertices being generated uniformly over $[0,1]^2$. There is an edge between two vertices if the Euclidean distance between the two vertices is ...
1
vote
0answers
17 views

Shortest path length when edge length is limited

$N$ nodes are uniformly distributed in a square whose side length is $1$. There exists an undirected edge between two nodes, if and only if the distance between them is less than or equal to $r$. Here ...
10
votes
1answer
168 views

Probability that a random graph is planar

I've been attempting to solve the following challenge problem from a combinatorics class but am getting absolutely nowhere. Prove: For sufficiently large $n$, the probability a random graph ...
1
vote
0answers
28 views

Conditional covariance in gaussian graphical models

I have a hypothesis, but I'm not sure if its true. The Wikipedia page states that if the covariance matrix is given by $$\Sigma=\left[\begin{matrix} A & B \\ B^T & C \end{matrix}\right]$$ ...
37
votes
1answer
913 views

How likely is it not to be anyone's best friend?

A teenage acquaintance of mine lamented: Every one of my friends is better friends with somebody else. Thanks to my knowledge of mathematics I could inform her that she's not alone and ...
0
votes
0answers
34 views

Threshold function for non-balanced graphs counter example

Let $G(n,p)$ be a random graph and let $H$ be a balanced graph with $e$ edges and $v$ vertices.. We know that $p^{*}(n)=n^{-v/e}$ is the threshold function for containing a copy of $H$. That is, if ...
0
votes
0answers
31 views

number of k-plex in a random graph

I saw Moon & Moser (1965) result on the bound on number of maximal cliques in a graph that any n-vertex graph has at most $n^{n/3}$ maximal cliques. Is there any similar results regarding the ...
1
vote
0answers
27 views

random graph on the reals

Is there a unique graph $G$ such that a random graph with vertex set $\mathbb{R}$ and a half chance of any two vertices being connected is isomorphic to $G$ with probability $1$? I am curious about ...
0
votes
0answers
61 views

Erdös-Rényi random graphs: Binomial approximation

I am working on extending the Erdös-Rényi paper "On the evolution of random graphs" (http://www.renyi.hu/~p_erdos/1960-10.pdf). In theorem 2a they calculate the number of isolated trees of order k. I ...
0
votes
0answers
48 views

Expected assortativity coefficient of random graphs

I am wondering whether there exist a closed-form expression for the expected assortativity coefficient (http://arxiv.org/pdf/cond-mat/0205405.pdf) of an Erdos Ranyi random graph model $G(n,m)$, where ...
3
votes
0answers
218 views

Maximum size of a bipartite subgraph on a random graph

Show that almost every $G \in \mathscr{G}(n,\frac{1}{2})$ contains no bipartite subgraph with more than $\frac{n^2}{8} + n^{\frac{3}{2}}$ edges. Tried using Markov's inequality by setting a = ...