Class BarabasiAlbertGenerator<V,E>
- All Implemented Interfaces:
com.google.common.base.Supplier<Graph<V,
,E>> EvolvingGraphGenerator<V,
,E> GraphGenerator<V,
,E> Supplier<Graph<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.
- See Also:
-
Field Summary
Fields -
Constructor Summary
ConstructorsConstructorDescriptionBarabasiAlbertGenerator
(com.google.common.base.Supplier<Graph<V, E>> graphFactory, com.google.common.base.Supplier<V> vertexFactory, com.google.common.base.Supplier<E> edgeFactory, int init_vertices, int numEdgesToAttach, int seed, Set<V> seedVertices) Constructs a new instance of the generator.BarabasiAlbertGenerator
(com.google.common.base.Supplier<Graph<V, E>> graphFactory, com.google.common.base.Supplier<V> vertexFactory, com.google.common.base.Supplier<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
Modifier and TypeMethodDescriptionprivate void
createRandomEdge
(Collection<V> preexistingNodes, V newVertex, Set<Pair<V>> added_pairs, WeightedChoice<V> weightedProbabilities) createRandomEdges
(Collection<V> preexistingNodes, V newVertex, int numEdges) private void
void
evolveGraph
(int numTimeSteps) Instructs the algorithm to evolve the graph N steps.get()
private void
initialize
(Set<V> seedVertices) int
Retrieves the total number of steps elapsed.
-
Field Details
-
mGraph
-
mNumEdgesToAttachPerStep
private int mNumEdgesToAttachPerStep -
mElapsedTimeSteps
private int mElapsedTimeSteps -
mRandom
-
vertex_index
-
init_vertices
protected int init_vertices -
index_vertex
-
graphFactory
-
vertexFactory
-
edgeFactory
-
-
Constructor Details
-
BarabasiAlbertGenerator
public BarabasiAlbertGenerator(com.google.common.base.Supplier<Graph<V, E>> graphFactory, com.google.common.base.Supplier<V> vertexFactory, com.google.common.base.Supplier<E> edgeFactory, int init_vertices, int numEdgesToAttach, int seed, Set<V> seedVertices) Constructs a new instance of the generator.- Parameters:
graphFactory
- factory for graphs of the appropriate typevertexFactory
- factory for vertices of the appropriate typeedgeFactory
- factory for edges of the appropriate typeinit_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 seedseedVertices
- storage for the seed vertices that this graph creates
-
BarabasiAlbertGenerator
public BarabasiAlbertGenerator(com.google.common.base.Supplier<Graph<V, E>> graphFactory, com.google.common.base.Supplier<V> vertexFactory, com.google.common.base.Supplier<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:
graphFactory
- factory for graphs of the appropriate typevertexFactory
- factory for vertices of the appropriate typeedgeFactory
- factory for edges of the appropriate typeinit_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 stepseedVertices
- storage for the seed vertices that this graph creates
-
-
Method Details
-
initialize
-
evolveGraph
public void evolveGraph(int numTimeSteps) Description copied from interface:EvolvingGraphGenerator
Instructs the algorithm to evolve the graph N steps.- Specified by:
evolveGraph
in interfaceEvolvingGraphGenerator<V,
E> - Parameters:
numTimeSteps
- number of steps to iterate from the current state
-
evolveGraph
private void evolveGraph() -
createRandomEdges
-
createRandomEdge
private void createRandomEdge(Collection<V> preexistingNodes, V newVertex, Set<Pair<V>> added_pairs, WeightedChoice<V> weightedProbabilities) -
numIterations
public int numIterations()Description copied from interface:EvolvingGraphGenerator
Retrieves the total number of steps elapsed.- Specified by:
numIterations
in interfaceEvolvingGraphGenerator<V,
E> - Returns:
- number of elapsed steps
-
get
-