Data.Graph.Generators.Random.BarabasiAlbert

Random graph generators using the generator algorithm introduced by A. L. Barabási and R. Albert.

See. A. L. Barabási and R. Albert "Emergence of scaling in random networks", Science 286, pp 509-512, 1999.

Graph generators

barabasiAlbertGraph

Arguments

:: GenIO

The random number generator to use

-> Int

The overall number of nodes (n)

-> Int

The number of edges to create between a new and existing nodes (m)

-> IO GraphInfo

The resulting graph (IO required for randomness)

Generate a random quasi-undirected Barabasi graph.

Only one edge (with nondeterministic direction) is created between a node pair, because adding the other edge direction is easier than removing duplicates.

Precondition (not checked): m <= n

Modeled after NetworkX 1.8.1 barabasi_albert_graph()

barabasiAlbertGraph'

Arguments

:: Int

The number of nodes

-> Int

The number of edges to create between a new and existing nodes (m)

-> IO GraphInfo

The resulting graph (IO required for randomness)

Like barabasiAlbertGraph, but uses a newly initialized random number generator.

See withSystemRandom for details on how the generator is initialized.

By using this function, you don't have to initialize the generator by yourself, however generator initialization is slow, so reusing the generator is recommended.

Usage example:

barabasiAlbertGraph' 10 5

Utility functions

selectNth :: Int -> [(Int, Int)] -> Int

Select the nth element from a multiset occur list, treating it as virtual large list This is significantly faster than building up the entire list and selecting the nth element

selectRandomElement :: GenIO -> (IntMultiSet, Int) -> IO Int

Select a single random element from the multiset, with precalculated size Note that the given size must be the total multiset size, not the number of distinct elements in said se

selectNDistinctRandomElements :: GenIO -> Int -> (IntMultiSet, Int) -> IO [Int]

Select n distinct random elements from a multiset, with This function will fail to terminate if there are less than n distinct elements in the multiset. This function accepts a multiset with precomputed size for performance reasons