Overview | Package | Class | Use | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

## 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 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`
  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`

Overview | Package | Class | Use | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD