The Stack Overflow podcast is back! Listen to an interview with our new CEO.

# Tag Info

## Hot answers tagged random-graphs

12

Binary trees are counted by Catalan numbers: the number of "full" binary trees (each node has either 0 or 2 children) with $n$ leaves is $C_{n-1}$. The Catalan numbers are given by an explicit formula, and also satisfy the recurrence $$C_{n+1} = \sum_{i+j = n} C_i C_j,$$ which follows directly from the interpretation as counting binary trees. You can use ...

9

So basically there are three questions involved. I know that $E(X_k)=\tbinom{n}{k}\cdot p^{\tbinom{k}{2}}$, but how do I prove it? You use the linearity of expectation and some smart re-writing. First of all, note that $$X_k = \sum_{T \subseteq V, \, |T|=k} \mathbb{1}[T \text{ is clique}].$$ Now, when taking the expectation of $X_k$, one can simply draw ...

8

It is very easy to say something about the expected length before you get stuck in a loop: if there are $n$ videos, it will (starting from a random video) take in expectation $\Theta(\sqrt{n})$ videos before you loop around (the actual value is around $1.25\sqrt{n}$). This is effectively the birthday problem, since each time you draw a video at random. ...

6

Check out [1] and the discussion in Section 4, Random Automata Generation. The paper benchmarks different DFA minimization algorithms. A uniform random generator is used that produces canonical string representations of complete DFAs with $n$ states and $k$ symbols. They also discuss other methods. [1] Almeida, M., Moreira, N., & Reis, R. (2007). On the ...

4

You should look at Cyril Nicaud's homepage. In particular, the following references are relevant to your question: F. Bassino, J. David and C. Nicaud, Enumeration and random generation of possibly incomplete deterministic automata, Pure Mathematics and Applications 19 (2-3) (2009) 1-16. F. Bassino and C. Nicaud. Enumeration and Random Generation of ...

4

Your thinking is correct. To verify your claim you can check this lecture notes on the probabilistic method by Matousek and Vondrak. More specifically check the proof of Theorem 3.3.1 stating that any graph with $m$ edges contains a bipartite subgraph with $\frac{m}{2}$ edges.

4

this may be a bit unexpected but yes, this has been studied in at least one particular context: PRNGs. a PRNG can be visualized as a directed graph, specifically a functional graph (all vertices, single outdegree) of "current value, next value". however most PRNGs are designed to have a single very long cycle. there is some analysis of PRNGs with multiple ...

3

I recommend Wilson's Algorithm. It is proven to select spanning trees uniformly at random. In worst case scenarios it can have complexity $n^3$, but in practical usage it often runs much faster, I believe typically $n log(n)$. I am part of a large research project at Duke and this is the algorithm we use. The current algorithm you have while faster, does not ...

3

The value is $2\log_2 n - 2\log_2\log_2 n + O(1)$. Let $k_0$ be the maximal value such that the expected number of cliques of size $k_0$ is at least 1. A boring calculation shows that $k_0 = 2\log_2 n - 2\log_2\log_2 n + O(1)$. It is a classical result that with high probability, $G(n,1/2)$ contains a $(k_0-1)$-clique. This implies that $k > k_0-1$. On ...

3

A classical result of Erdős and Rényi states that if $k = \frac{n}{2} (\log n + c)$, then as $n\to\infty$, the probability that the graph is connected tends to $e^{-e^{-c}}$. You can find the proof in any textbook on random graphs.

3

Okay, this is my approach to this problem. I think the key concept here is the clustering coefficient $c$. The value of $c$ is denotes how likely it is that two nodes are connected by an edge, if the have a common neighbor. In SN-friendship graphs the clustering coefficient is usually high compared to classical random graph models, such as Erdös-Rényi. What ...

3

Since $\mu$ is the sum of $n$ terms, we can estimate it up to a factor of $n$ by the maximal term: $$\max_{d=1}^n \binom{n}{d} p^{\binom{d}{2}} (1-p^d)^{n-d} \leq \sum_{d=1}^n \binom{n}{d} p^{\binom{d}{2}} (1-p^d)^{n-d} \leq n\max_{d=1}^n \binom{n}{d} p^{\binom{d}{2}} (1-p^d)^{n-d}.$$ In order to find out which term is the largest, we can use the estimate $... 3 There are algorithms to randomly generate DFAs up to a permutation http://paranthoen.thomas.free.fr/PAPERS/RandDFAToAppearInTCS.ps.gz. But, it is also mentionned in the above paper that almost all DFAs are already minimal. Non minimal DFAs are like prime numbers ... there are just few of them. And if you use this algorithm to test minimization algorithm it ... 2 one natural strategy is to regard the DFA as a graph and then there are many "natural" and highly studied random distributions of graphs, the simplest is probably Erdos-Renyi. in that case you treat all states of the DFA as nodes of the graph and some fixed percent of all possible edges (DFA transitions) are chosen. more sophisticated distributions that are ... 2 The following is based on J. Michael Steele's paper proving the rigorous bound. The pigeonhole principle shows that out of any$n$points in$[0,1]^d$, there are two at distance at most$O(n^{1/d})$, say at most$c_d n^{1/d}$; the idea is to divide$[0,1]^d$into small enough boxes, and find a box containing two points. Construct a spanning tree by ... 2 What you need is to take advantage of disjoint set, a very efficient data structure. Here is the simple algorithm to generate a random graph of$n$vertices and$m$component. MakeSet of size$n$. Choose two random vertices that has not been connected by an edge. Union these two vertices. That means adding the edge between them. Use an implementation of ... 1 I don't know if my solution is correct, but after some searching, I eventually came up to this conclusion: The algorithm that is used to build the graph is not compatible with a different choice other than$\theta_i = i^{-\alpha}\$. This is because the algo is derived from the Barabási–Albert with some modifies. We start with N nodes, and we add a link ...

1

I have found an algorithm on p.16 of the book: L. Alonso, R. Schott, Random Generation of Trees, Kluwer, 1995. Note however that the C code for it on p.191-192 of the book is erroneous (from communication of the first author). (I have coded the algorithm in Python and included it in a program of my own: http://s13.zetaboards.com/Crypto/topic/7164646/1/)

Only top voted, non community-wiki answers of a minimum length are eligible