edu.uci.ics.jung.algorithms.generators.random
Class BarabasiAlbertGenerator<V,E>

java.lang.Object
  extended by edu.uci.ics.jung.algorithms.generators.random.BarabasiAlbertGenerator<V,E>
All Implemented Interfaces:
EvolvingGraphGenerator<V,E>, GraphGenerator<V,E>, org.apache.commons.collections15.Factory<Graph<V,E>>

public class BarabasiAlbertGenerator<V,E>
extends Object
implements EvolvingGraphGenerator<V,E>

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, Tom Nelson - adapted to jung2
See Also:
"A.-L. Barabasi and R. Albert, Emergence of scaling in random networks, Science 286, 1999."

Field Summary
protected  org.apache.commons.collections15.Factory<E> edgeFactory
           
protected  org.apache.commons.collections15.Factory<Graph<V,E>> graphFactory
           
protected  Map<V,Integer> index_vertex
           
protected  int init_vertices
           
protected  List<V> vertex_index
           
protected  org.apache.commons.collections15.Factory<V> vertexFactory
           
 
Constructor Summary
BarabasiAlbertGenerator(org.apache.commons.collections15.Factory<Graph<V,E>> graphFactory, org.apache.commons.collections15.Factory<V> vertexFactory, org.apache.commons.collections15.Factory<E> edgeFactory, int init_vertices, int numEdgesToAttach, int seed, Set<V> seedVertices)
          Constructs a new instance of the generator.
BarabasiAlbertGenerator(org.apache.commons.collections15.Factory<Graph<V,E>> graphFactory, org.apache.commons.collections15.Factory<V> vertexFactory, org.apache.commons.collections15.Factory<E> edgeFactory, int init_vertices, int numEdgesToAttach, Set<V> seedVertices)
          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.
 
Method Summary
 Graph<V,E> create()
           
 void evolveGraph(int numTimeSteps)
          Instructs the algorithm to evolve the graph N steps.
 int numIterations()
          Retrieves the total number of steps elapsed.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

vertex_index

protected List<V> vertex_index

init_vertices

protected int init_vertices

index_vertex

protected Map<V,Integer> index_vertex

graphFactory

protected org.apache.commons.collections15.Factory<Graph<V,E>> graphFactory

vertexFactory

protected org.apache.commons.collections15.Factory<V> vertexFactory

edgeFactory

protected org.apache.commons.collections15.Factory<E> edgeFactory
Constructor Detail

BarabasiAlbertGenerator

public BarabasiAlbertGenerator(org.apache.commons.collections15.Factory<Graph<V,E>> graphFactory,
                               org.apache.commons.collections15.Factory<V> vertexFactory,
                               org.apache.commons.collections15.Factory<E> edgeFactory,
                               int init_vertices,
                               int numEdgesToAttach,
                               int seed,
                               Set<V> seedVertices)
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(org.apache.commons.collections15.Factory<Graph<V,E>> graphFactory,
                               org.apache.commons.collections15.Factory<V> vertexFactory,
                               org.apache.commons.collections15.Factory<E> edgeFactory,
                               int init_vertices,
                               int numEdgesToAttach,
                               Set<V> seedVertices)
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 steps.

Specified by:
evolveGraph in interface EvolvingGraphGenerator<V,E>
Parameters:
numTimeSteps - number of steps to iterate from the current state

numIterations

public int numIterations()
Description copied from interface: EvolvingGraphGenerator
Retrieves the total number of steps elapsed.

Specified by:
numIterations in interface EvolvingGraphGenerator<V,E>
Returns:
number of elapsed steps

create

public Graph<V,E> create()
Specified by:
create in interface org.apache.commons.collections15.Factory<Graph<V,E>>


Copyright © 2009. All Rights Reserved.