Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [random-graphs]

The tag has no usage guidance.

11
votes
1answer
2k views

Number of clique in random graphs

There is a family of random graphs $G(n, p)$ with $n$ nodes (due to Gilbert). Each possible edge is independently inserted into $G(n, p)$ with probability $p$. Let $X_k$ be the number of cliques of ...
9
votes
4answers
822 views

What is a good algorithm for generating random DFAs?

I am generating random DFAs to test a DFA reduction algorithm on them. The algorithm that I'm using right now is as follows: for each state $q$, for each symbol in the alphabet $c$, add $\delta (q, c)...
6
votes
2answers
187 views

Has this model of random directed graphs been studied?

Youtube recently added a feature called autoplay, where each clip is assigned a (presumably related) clip that follows it. This, in effect, defines a directed graph on the set of youtube clips, where ...
6
votes
1answer
378 views

Expected number of maximal cliques in $G(n,p)$

The $G(n,p)$ random graph model creates graphs with $n$ vertices and each possible edge exists independently with probability $p\in (0,1)$. Much is known about the (expected) size of a largest ...
5
votes
2answers
976 views

Generation of random binary trees

Given n, I want to randomly generate a binary tree (unlabelled) that has n end nodes. Could someone kindly provide a reference containing an algorithm for doing that? I attempted to do as follows: ...
3
votes
1answer
832 views

What is the probability of friendship conditioned on the number of mutual friends

Let Alice and Bob be two users chosen uniformly at random from a social network (e.g. Facebook). What is the probability that they are friends assuming that they share $k$ mutual friends? I am ...
2
votes
1answer
69 views

Mean number of edges between two equal partitions

For a random undirected graph with $n$ nodes, where each node has $k$ incident edges ($nk/2$ edges in total), the vertex set is partitioned into two sets each having $n/2$ nodes. What is the ...
2
votes
1answer
110 views

How many edges before a random graph is connected?

Let $G$ be a undirected graph with $n$ vertices and no edges, and let $f(k)$ be the probability that if we add $k$ edges randomly to $G$ that $G$ will be connected. How would one determine $f(k)$ for ...
2
votes
1answer
156 views

How to generate random adjacency matrix with given number of components in graph

I am building a graph package in C and a part of the work involves generating a random graph with a given number of components in the graph. For example, if I wanted to generate a graph of 50 ...
2
votes
1answer
176 views

Expected weight of euclidean minimum spanning tree on a unit square

Suppose I randomly generate $n$ points from the unit square $[0,1]^2$, form a complete graph in which the weight of each edge is just the Euclidean distance between its endpoints, and compute the ...
2
votes
0answers
65 views

Eigenvalues of an induced subgraph of a random graph

Suppose $G$ is a random graph on $n$ vertices where each edge appears with probability half. Suppose someone looks at the resulting graph and chooses an arbitrary subset $W$ of vertices of size $k>\...
2
votes
1answer
98 views

Fitness model for scale free networks

In order to generate scale-free networks, we can use this algorithm, derived from Barabási–Albert model: 1) we assign every node a "weight" $\theta_i$ (or two in the direct case). 2) we place $m$ ...
2
votes
0answers
237 views

Complexity class of maximum flow problem with random arc capacity

Given a graph $G=(N,E)$ with a special source node $s$ and sink node $t$. There is a subset of arcs $E^* \subset E$ that has the capacity drawn from a probability distribution $F$ independently. Then ...
1
vote
1answer
48 views

Given a simple graph G, what's the quickest known way to sample one of its spanning trees at random?

Let's say I have a simple graph G with an edge set E, vertex set V, and at least 1 cycle. We can determine the number of spanning trees in this graph by finding its graph Laplacian matrix, striking ...
1
vote
1answer
298 views

Probability of k-clique in a random graph

I need to find the order of the minimum k = k(n) such that the probability of having at least 1 k-clique in a random graph $G(n, \frac{1}{2}$) is $\mathcal{O}(\frac{1}{n})$. $X_k$ is the random ...
1
vote
1answer
32 views

Singleton in a simple SBM

I can't work out the solution to the following exercise: We have $2n$ vertices grouped in $2$ clusters of equal size. The probability of having an edge between $i$ and $j$ is $p$ if $i$ and $j$ are ...
1
vote
0answers
49 views

probability that the vertex set {1,…,k} is component of random graph

Consider a graph with vertices 1,...,n and suppose that each of the $\binom{n}{2}$pairs of vertices is, independently, an edge of this graph with probability p.Let $P_n$ denote the probability that ...