Search Results
| Search type | Search syntax |
|---|---|
| Tags | [tag] |
| Exact | "words here" |
| Author |
user:1234 user:me (yours) |
| Score |
score:3 (3+) score:0 (none) |
| Answers |
answers:3 (3+) answers:0 (none) isaccepted:yes hasaccepted:no inquestion:1234 |
| Views | views:250 |
| Code | code:"if (foo != bar)" |
| Sections |
title:apples body:"apples oranges" |
| URL | url:"*.example.com" |
| Saves | in:saves |
| Status |
closed:yes duplicate:no migrated:no wiki:no |
| Types |
is:question is:answer |
| Exclude |
-[tag] -apples |
| For more details on advanced search visit our help page | |
Results tagged with random-graphs
Search options answers only
not deleted
user 11142
The study of probability distributions over graphs. For example, the Erdős–Rényi model where each edge occurs independently with equal probability.
2
votes
Number of nodes in a given distance in (random) regular graph
The magic words are "expander graph". A random regular graph is an expander, which means that the size of the layers is expanding until half the vertices are consumed. This (more or less) answers you …
- 96.4k
1
vote
Finding loops and double edges ASAP in configuration model random graph
Check out this work of Kim and Vu and references therein. WARNING: their algorithm is of very questionable use in practice, since the distribution is only asymptotically uniform, and since in the limi …
- 96.4k
2
votes
Expected number of leaf nodes in some theoretical graph models
For Erdos Renyi, the degree distribution is binomial, see for example these Cornell lecture notes by John Hopcroft.
- 96.4k
3
votes
Accepted
Max cut value in a random graph
This is addressed in:
An upper bound for the maximum cut mean value
Alberto Bertoni, Paola Campadelli and Roberto Posenato
Their bound is the same as yours; more precisely, for a random graph with $ …
- 96.4k
4
votes
Probability of Generating a Connected Graph
See
Clique sizes in a unit disk graph
and references mentioned there... Your graphs are the unit disk graphs of the title.
EDIT
See http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.7.4866 …
- 96.4k
3
votes
A more efficient way to generate random graphs with a given degree sequence?
There is the algorithm of Blitzstein and Diaconis -- they claim very good practical performance.
- 96.4k
7
votes
Accepted
Generate random graphs that satisfy the triangle inequality
I am not sure I understand the issues: First you generate an ER (or your favorite model) random graph. The constraints that the edge lengths are in $[0, 1]$ and satisfy all possible triangle inequalit …
- 96.4k
1
vote
Relation between expected values of eigenvalues of Laplacian matrix of a graph and eigenvalu...
See the papers by Erdos (no relation) and collaborators, e.g.:
Erdős, László; Knowles, Antti; Yau, Horng-Tzer; Yin, Jun, Spectral statistics of Erdős-Rényi graphs. I: Local semicircle law, Ann. Proba …
- 96.4k
2
votes
Proving a random bipartite graph contains a perfect matching
For a lot on the subject, see Frieze and Pittel and references therein (in particular, I think the result you want is due to Erdos-Renyi(!)(1960, 1964); average degree $O(\log n)$ is enough.
- 96.4k
1
vote
1
vote
Largest eigenvalue of the adjacency matrix of weighted random graph
When $p$ is reasonably large, you are basically looking at a random symmetric matrix, so any insight would come from the Tracy-Widom theory.
- 96.4k
2
votes
Accepted
Distribution of eigenvectors and eigenvalues for random, symmetric matrix
It sounds like the OP has a random perturbation of a fixed graph, which is not considered very frequently, but when they have, it seems to be by A. Flaxman (see, e.g.:
Expansion and lack thereof in r …
- 96.4k
7
votes
Do these polynomials have alternating coefficients?
To add to the preceding answer: The absolute values of the coefficients appear normal (in particular, unimodal): Which means that the technology developed, in, eg,
Lebowitz, J.L.; Pittel, B.; Ruell …
- 96.4k