Skip to content

Remove quadratic Barabasi Albert Generator #787

@manpen

Description

@manpen

We currently support two generation algorithms in BarabasiAlbertGenerator which are selected using the 'turbo flag' batagelj in the constructors:

  • the default generateBatagelj generator with a linear runtime
  • the original implementation with a (presumably) quadratic runtime

When I reworked the Batagelj implementation, we agreed to keep the original implementation. In a recent discussion Hans-Peter Stricker pointed out that both implementations diverged; while bataglj uses a circle as seed graph, the original uses a path. I introduced this difference in #4fe073d, probably by accident (I dont recall), but the circle is the more natural choice. The fix is a single line of code, but I would rather remove the original code:

  • The quadratic implementation has nothing speaking for it other than it was the first implementation and it uses slightly less memory (something less than 25%) --- this is only relevant in regimes where the quadratic runtime makes the algorithm infeasible anyhow.
  • The super-seeding implementation is the default since before the switch to GIT in 2016.
  • Leaving it in may has the risk of more divergence
  • Less code to maintain

If we remove the code, I suggest to leave the batagelj in the constructors for a grace period and issue a warning via stderr(?) if it is set to select the slow algorithm.

Metadata

Metadata

Assignees

No one assigned

    Labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions