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 timestep, choose a node, $v_j$ uniformly at random from $\{v_1,...,v_{k-1}, v_{k+1},...,v_n\}$ and add the undirected edge $(v_k, v_j)$ to the graph. Note that this edge may have been added at an earlier timestep, in which case skip adding an edge and proceed to the next timestep.

As an example, for $n=3$:

1) Add edge $(v_1, v_2)$ to the graph.

2) Add edge $(v_2, v_1)$ to the graph. This edge already exists, so do nothing instead.

3) Add edge $(v_3, v_1)$ to the graph.

4) The final graph has two edges, one between $v_1$ and $v_2$ and one between $v_1$ and $v_3$

  • $\begingroup$ Indeed, this is not clear to me. Do we have timesteps? Do we add an edge for each node, or just one edge for the whole graph? Why would 2 edges be a complete graph when $n=3$? $\endgroup$ – Archaick Apr 22 '15 at 0:07
  • $\begingroup$ Timesteps is probably a more clear way to describe it. I will change the post. $\endgroup$ – Davis Yoshida Apr 22 '15 at 0:16
  • $\begingroup$ This is much clearer now, thank you. $\endgroup$ – Archaick Apr 22 '15 at 0:21

That random graph is denoted by $\mathbb{G}_{1-out}$. A common generalization is $\mathbb{G}_{k-out}$, where in step $j$, we choose $k$ vertices out of $V\setminus\{v_j\}$ and add the $k$ edges $\{v_j, \cdot\}$. Then at the end, delete multiple edges.

One place that you can read about this models is Alan Frieze and Michal Karoński's new book on Random Graphs. An early copy of this book is at http://www.math.cmu.edu/~af1p/Book.html

| cite | improve this answer | |

This generative model has some interesting properties. It has a fixed average degree with each node having degree at least one. It is also my intuition that it minimizes or comes very close to minimizing clustering for a fixed number of edges. I'm not familiar with any models which behave as the one you are describing. Good for you, it's hard to come up with new models nowadays =).

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.