public class BarabasiAlbertGenerator extends java.lang.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.
Modifier and Type | Field and Description |
---|---|
protected boolean |
directed |
protected java.util.Map |
index_vertex |
protected int |
init_vertices |
protected boolean |
parallel |
static java.lang.Object |
SEED
Tags the initial "seed" vertices that the graph starts with
|
protected java.util.Vector |
vertex_index |
Constructor and Description |
---|
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.
|
Modifier and Type | Method and Description |
---|---|
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.
|
protected java.util.Vector vertex_index
protected int init_vertices
protected java.util.Map index_vertex
protected boolean directed
protected boolean parallel
public static final java.lang.Object SEED
public BarabasiAlbertGenerator(int init_vertices, int numEdgesToAttach, boolean directed, boolean parallel, int seed)
init_vertices
- number of unconnected 'seed' vertices that the graph should start withnumEdgesToAttach
- the number of edges that should be attached from the
new vertex to pre-existing vertices at each time stepdirected
- specifies whether the graph and edges to be created should be directed or notparallel
- specifies whether the algorithm permits parallel edgesseed
- random number seedpublic BarabasiAlbertGenerator(int init_vertices, int numEdgesToAttach, int seed)
init_vertices
- number of unconnected 'seed' vertices that the graph should start withnumEdgesToAttach
- the number of edges that should be attached from the
new vertex to pre-existing vertices at each time stepseed
- random number seedpublic BarabasiAlbertGenerator(int init_vertices, int numEdgesToAttach)
init_vertices
- number of vertices that the graph should start withnumEdgesToAttach
- the number of edges that should be attached from the
new vertex to pre-existing vertices at each time steppublic void evolveGraph(int numTimeSteps)
EvolvingGraphGenerator
evolveGraph
in interface EvolvingGraphGenerator
numTimeSteps
- number of time steps to simulate from its
current statepublic int getIndex(Vertex v)
public int getNumElapsedTimeSteps()
EvolvingGraphGenerator
getNumElapsedTimeSteps
in interface EvolvingGraphGenerator
public ArchetypeGraph generateGraph()
EvolvingGraphGenerator
generateGraph
in interface EvolvingGraphGenerator
generateGraph
in interface GraphGenerator
public void reset()
EvolvingGraphGenerator
reset
in interface EvolvingGraphGenerator