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

java.lang.Object
  extended by edu.uci.ics.jung.random.generators.BarabasiAlbertGenerator
All Implemented Interfaces:
EvolvingGraphGenerator, GraphGenerator

public class BarabasiAlbertGenerator
extends Object
implements EvolvingGraphGenerator

Simple evolving scale-free random graph generator. At each time step, a new vertex is created and is connected to existing vertices according to the principle of "preferential attachment", whereby vertices with higher degree have a higher probability of being selected for attachment.

At a given timestep, the probability p of creating an edge between an existing vertex v and the newly added vertex is

 p = (degree(v) + 1) / (|E| + |V|);
 

where |E| and |V| are, respectively, the number of edges and vertices currently in the network (counting neither the new vertex nor the other edges that are being attached to it).

Note that the formula specified in the original paper (cited below) was

 p = degree(v) / |E|
 

However, this would have meant that the probability of attachment for any existing isolated vertex would be 0. This version uses Lagrangian smoothing to give each existing vertex a positive attachment probability.

The graph created may be either directed or undirected (controlled by a constructor parameter); the default is undirected. If the graph is specified to be directed, then the edges added will be directed from the newly added vertex u to the existing vertex v, with probability proportional to the indegree of v (number of edges directed towards v). If the graph is specified to be undirected, then the (undirected) edges added will connect u to v, with probability proportional to the degree of v.

The parallel constructor parameter specifies whether parallel edges may be created.

Author:
Scott White, Joshua O'Madadhain
See Also:
"A.-L. Barabasi and R. Albert, Emergence of scaling in random networks, Science 286, 1999."

Field Summary
protected  boolean directed
           
protected  Map index_vertex
           
protected  int init_vertices
           
protected  boolean parallel
           
static Object SEED
          Tags the initial "seed" vertices that the graph starts with
protected  Vector vertex_index
           
 
Constructor Summary
BarabasiAlbertGenerator(int init_vertices, int numEdgesToAttach)
          Constructs a new instance of the generator, whose output will be an undirected graph, and which will use the current time as a seed for the random number generation.
BarabasiAlbertGenerator(int init_vertices, int numEdgesToAttach, boolean directed, boolean parallel, int seed)
          Constructs a new instance of the generator.
BarabasiAlbertGenerator(int init_vertices, int numEdgesToAttach, int seed)
          Constructs a new instance of the generator, whose output will be an undirected graph.
 
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 getIndex(Vertex v)
           
 int getNumElapsedTimeSteps()
          Retrieves the total number of time steps elapsed
 void reset()
          Resets the random graph to the state that it had after the constructor returned.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

vertex_index

protected Vector vertex_index

init_vertices

protected int init_vertices

index_vertex

protected Map index_vertex

directed

protected boolean directed

parallel

protected boolean parallel

SEED

public static final Object SEED
Tags the initial "seed" vertices that the graph starts with

Constructor Detail

BarabasiAlbertGenerator

public BarabasiAlbertGenerator(int init_vertices,
                               int numEdgesToAttach,
                               boolean directed,
                               boolean parallel,
                               int seed)
Constructs a new instance of the generator.

Parameters:
init_vertices - number of unconnected 'seed' vertices that the graph should start with
numEdgesToAttach - the number of edges that should be attached from the new vertex to pre-existing vertices at each time step
directed - specifies whether the graph and edges to be created should be directed or not
parallel - specifies whether the algorithm permits parallel edges
seed - random number seed

BarabasiAlbertGenerator

public BarabasiAlbertGenerator(int init_vertices,
                               int numEdgesToAttach,
                               int seed)
Constructs a new instance of the generator, whose output will be an undirected graph.

Parameters:
init_vertices - number of unconnected 'seed' vertices that the graph should start with
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 init_vertices,
                               int numEdgesToAttach)
Constructs a new instance of the generator, whose output will be an undirected graph, and which will use the current time as a seed for the random number generation.

Parameters:
init_vertices - number of vertices that the graph should start with
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

getIndex

public int getIndex(Vertex v)

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
Specified by:
generateGraph in interface GraphGenerator
Returns:
new instance of the evolved graph

reset

public void reset()
Description copied from interface: EvolvingGraphGenerator
Resets the random graph to the state that it had after the constructor returned.

Specified by:
reset in interface EvolvingGraphGenerator