search

sbromberger / LightGraphs.jl

An optimized graphs package for the Julia programming language
Other
672 stars 185 forks source link

Strange initial graph in Barabasi-Albert model #831

Closed adamglos92 closed 6 years ago

adamglos92 commented 6 years ago

I just realized the Barabasi Albert model starts with empty graph of order k. As I remember (confirmed by fast pre-research), in this model initial graph is a complete graph, or at least connected or with vertices with nonzero degrees.

sbromberger commented 6 years ago

We start with an empty graph, then add edges to the existing vertices per the docstring:

Create a [Barabási–Albert model](https://en.wikipedia.org/wiki/Barab%C3%A1si%E2%80%93Albert_model)
random graph with `n` vertices. It is grown by adding new vertices to an initial
graph with `n0` vertices. Each new vertex is attached with `k` edges to `k`
different vertices already present in the system by preferential attachment.
Initial graphs are undirected and consist of isolated vertices by default.

The initial graph is not completely disconnected; we add one vertex and k edges before adding (n - n0 - 1) new vertices.

This comports with the NetworkX implementation, which references the 1999 paper.

adamglos92 commented 6 years ago

Agreed. Especially that I just realized that barabasi_albert! exists

sbromberger commented 6 years ago

Well, barabasi_albert() merely calls barabasi_albert!() with some preallocated data structures that get mutated. That's all...