edu.uci.ics.jung.random.generators
Class BarabasiAlbertGenerator

java.lang.Object
  edu.uci.ics.jung.random.generators.BarabasiAlbertGenerator

All Implemented Interfaces:

EvolvingGraphGenerator, GraphGenerator

public class BarabasiAlbertGenerator

extends java.lang.Object

implements EvolvingGraphGenerator

Simple evolving scale-free random graph generator. At each time step t, a new vertex is created and m new edges are created and wired to pre-existing edges according the principle of "preferential attachment" whereby vertices with more existing edges have a higher probability of being selected for attachment at the current time step. The precise algorithm used here is a variant of the LCD model in that parallel edges are not allowed.

Author:

Scott White

See Also:

"A.-L. Barabasi and R. Albert, Emergence of scaling in random networks, Science 286, 1999."

Constructor Summary

BarabasiAlbertGenerator(int numEdgesToAttach)
Constructs a new instance of the generator

BarabasiAlbertGenerator(int numEdgesToAttach, int seed)
Constructs a new instance of the generator

Method Summary

void	evolveGraph(int numTimeSteps) Instructs the algorithm to evolve the graph N time steps and return the most current evolved state of the graph
ArchetypeGraph	generateGraph() Returns a copy of the evolved graph in its current state
int	getNumElapsedTimeSteps() Retrieves the total number of time steps elapsed
void	reset() Resets the random graph to have zero vertices and zero edges and resets the elapsed time to 0.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

BarabasiAlbertGenerator

public BarabasiAlbertGenerator(int numEdgesToAttach,
                               int seed)

Constructs a new instance of the generator

Parameters:

numEdgesToAttach - the number of edges that should be attached from the new vertex to pre-existing vertices at each time step

seed - random number seed

BarabasiAlbertGenerator

public BarabasiAlbertGenerator(int numEdgesToAttach)

Constructs a new instance of the generator

Parameters:

numEdgesToAttach - the number of edges that should be attached from the new vertex to pre-existing vertices at each time step

Method Detail

evolveGraph

public void evolveGraph(int numTimeSteps)

Description copied from interface: EvolvingGraphGenerator

Instructs the algorithm to evolve the graph N time steps and return the most current evolved state of the graph

Specified by:

evolveGraph in interface EvolvingGraphGenerator

Parameters:

numTimeSteps - number of time steps to simulate from its current state

getNumElapsedTimeSteps

public int getNumElapsedTimeSteps()

Description copied from interface: EvolvingGraphGenerator

Retrieves the total number of time steps elapsed

Specified by:

getNumElapsedTimeSteps in interface EvolvingGraphGenerator

Returns:

number of elapsed time steps

generateGraph

public ArchetypeGraph generateGraph()

Description copied from interface: EvolvingGraphGenerator

Returns a copy of the evolved graph in its current state

Specified by:

generateGraph in interface EvolvingGraphGenerator

Returns:

new instance of the evolved graph

reset

public void reset()

Description copied from interface: EvolvingGraphGenerator

Resets the random graph to have zero vertices and zero edges and resets the elapsed time to 0.

Specified by:

reset in interface EvolvingGraphGenerator