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
18 views

Number of edges in randomly induced graph

If I have a simple graph $G$ with $n$ vertices and $m$ edges, then I want to create a randomly induced graph $G_x$ by selecting vertices with a probability of $n/2m$. The edges of $G_x$ are defined to ...
1
vote
0answers
14 views

Select a random edge [on hold]

Given a source of random bits and a multigraph G(V, E), provide an algorithm for selecting an edge e ∈ E uniformly at random in O(n) time.
5
votes
0answers
34 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. ...
-1
votes
0answers
9 views

Good broad review of agent-based modeling? [closed]

Trying to find some good review of agent-based models and networks, covering what is called "opinion dynamics", correlated behavior of agents, phase transition analogies, etc. Are there any articles ...
2
votes
1answer
51 views

How to estimate the conditional probability of node reachability on a random graph?

Let $G=(V,E)$ be an undirected random graph such that $V$ is the node set, $E$ is the edge set. Each edge $uv \in E$ is associated with a probability $p_{uv}$, i.e., $uv$ is kept with probability ...
0
votes
1answer
49 views

Dijkstra's algorithm, am I or the teacher mistaken?

Imagine that Dijkstra’s algorithm has been used to show the length of the shortest path from $a$ to $g$ in the graph in figure 1. Which of the following vertices is added first to the set $S$? It's ...
4
votes
0answers
21 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 ...
0
votes
1answer
48 views

Diameter of random graph.

Basically I was given a random graph with fixed probability and I need to prove that the diameter of the random graph is asymptotically 2. See the following picture for the detail of the question. ...
2
votes
0answers
41 views

Expected maximum degree Erdős–Rényi graph

Consider an Erdős–Rényi random graph $\mathrm{ER}(N,p)$, where $N$ is the number of nodes and $p$ the probability of placing an edge between each distinct pair of nodes. I'm interested in finding ...
1
vote
0answers
15 views

Size of intersection of balls on non-ameanable graphs

Let $G$ be a vertex-transitive non-ameanable graph and let $B(x,n)$ be the ball of radius $n$ centered on the vertex $x$. I am interested in estimates on the cardinality of the following set, ...
1
vote
0answers
29 views

Number of same degree vertex pairs between two random graphs

I am considering the random graphs generated by the Erdős-Rényi model for this question. Random Graphs as Models of Networks by Newman is a reference on this topic. A random graph $\Gamma_{n,p}$ has ...
0
votes
0answers
20 views

Function/algorithm to generate a random walk on a graph

I'm looking for a graph function or an algorithm that can generate a random fluctuating random walk that will eventually converge between the value of y = 0 and y = 1, more or less after a number of ...
0
votes
1answer
37 views

Prerequisites for Random Graph Theory

I would dearly love to know the prerequisites for self-studying Random Graph Theory and Percolation Theory in Probability. My knowledge currently involves: Basic probability concepts: the axioms, ...
0
votes
1answer
30 views

How to proove Hammer Split-graph Theorem?

Let $G=(V,E)$ be a Split Graph with $|V| \geq 4$. Then how to prove that: No induced sub-graph of G with 4 Vertices is a cycle with length 4 OR a pair of not incident edges? Well it must be from ...
0
votes
1answer
39 views

Degree distribution of the line graph of an Erdös-Rényi random graph

An Erdös-Rényi random graph is a graph, which consists of N nodes and where each link between them is present with probability p. It comes natural then that the pdf giving the probability of a node in ...
3
votes
0answers
26 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 ...
0
votes
0answers
47 views

Size of the connected components

Assume that we have a disconnected graph with a random number of connected components. Is there any bounds/distribution on the size of these connected components (the number of vertices). The degree ...
0
votes
0answers
23 views

Cardinality of maximum independent set for a given degree distribution

Consider undirected graph $G(V,E)$. Assume that $f_n(k)$ be the probability mass function of degree of a vertex in $G$. Further, assume that $f_n(k)$ is an strictly decreasing function of $k$ with ...
1
vote
1answer
32 views

Probability of dominating set in random balanced tournament

I'm trying to estimate some probability in a random tournament, and I know that what I have is false, as it leads to contradicting results published some 40 years ago. But I don't know where the ...
1
vote
1answer
35 views

Graph Theory: Conditional Expected Value of Product of two Random Variables

Consider a graph with $n$ vertices, where each edge between any two vertices is independently drawn with probability $p$. Let $D_i$ be the degree of vertex $i$. What is $E[D_i \cdot D_j]$? Here is ...
0
votes
1answer
79 views

Watts-Strogatz graphs

I'm stuck with this particular question. Can someone explain/help me? Suppose we construct a graph in $WS(n,k,p)$, starting from the n vertices in a ring, where each vertex is connected to its first ...
2
votes
0answers
67 views

ER graphs, expected number of triangles incident to one vertex

I'm really sorry for this question. I'm new to a graph theory, and I hope you will help me to understand one statement. Consider $ER(n,p)$ graph with $n \geq 3$ and $p \in [0,1]$. The statement ...
0
votes
1answer
29 views

Subgraph isomorphism in random graphs. What am I forgetting?

We are asked to calculate the expected number of embeddings of graph $H$ in graph $G$. $G$ is a graph on $n$ vertices. Between each pair of vertices, with probability $p$ there is a blue edge, and ...
1
vote
1answer
24 views

Scale-free property of random graphs

From this Wikipedia page, I gather that when the degree distribution of a graph obeys the power law, the graph is termed 'scale-free'. I would like to know the reason for this term. What has scaling ...
0
votes
0answers
17 views

How to find embeddings of 3-cycle in random graphs?

I'm not sure whether this is the correct place to ask, but we have an assignment for uni as posted below. Before I start searching the large space of papers that exist on embeddings in a random graph. ...
0
votes
0answers
52 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
32 views

The probability of having a perfect matching in a bipartite graph

Say we have a bipartite graph $G$ with two sets, $\{x_1,\dotsc,x_n\}$ and $\{y_1,\dotsc,y_n\}$. For each pair $xy$, there is an edge with probability $p$. Then, what is the probability of having a ...
3
votes
2answers
30 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
25 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
23 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 ...
1
vote
0answers
130 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 ...
0
votes
0answers
31 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
19 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
42 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
28 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
41 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
43 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
17 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
38 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
43 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
36 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
56 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
38 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
55 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
89 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
59 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
36 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
70 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
69 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
22 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 ...