Another kind of random graphs?

58 Views Asked by At

Maybe this is just another method to generate random graphs of a known kind, but it's not obvious for me, and I'd like to ask if someone sees this at a glance.

Start with an empty set of nodes. For $i = 1,\dots,n$ add a node $i$ and connect it to $k<n$ nodes picked uniformly at random from the set of previously added nodes (with replacement). By chance, nodes $1$ and $n$ may have degree 1 (and all the other nodes have degree 2), and node $1$ may have degree $n-1$, but thats unprobable.

Alternatives:

  • Pick the $k$ nodes (to connect the new node $i$ with) without replacement. In this case, node $n$ will have degree $k$.

  • Pick the $k$ nodes (to connect the new node $i$ with) only from the set $\{i-1,\dots,i-K\}$ with $K > k$.

Especially I'd like to know what the degree distribution will be. (And other distributions: clustering coefficient, betweenness, and so on.)

1

There are 1 best solutions below

2
On BEST ANSWER

I can't comment, but I believe this is also known as the Uniform Attachment Model, or Uniform Attachment Graphs. A study of Perfect Matchings and Hamilton cycles in such graphs, along with some more references and history can be found in this paper by Huseyin Acan: https://arxiv.org/pdf/1908.03659.pdf

For the "sliding window model" you described, I also found the following reference: https://arxiv.org/pdf/1704.08597.pdf https://en.wikipedia.org/wiki/UPA_model

Chapter 8 of this book https://www.win.tue.nl/~rhofstad/NotesRGCN.pdf discusses a generalized preferential attachment model, of which the uniform attachment model is a limiting case for one of the parameters ($\delta \to \infty$).