/*
* Copyright (c) 2003, The JUNG Authors
*
* All rights reserved.
*
* This software is open-source under the BSD license; see either
* "license.txt" or
* https://github.com/jrtom/jung/blob/master/LICENSE for a description.
*/
package edu.uci.ics.jung.algorithms.generators.random;
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Random;
import java.util.Set;
import com.google.common.base.Preconditions;
import com.google.common.base.Supplier;
import edu.uci.ics.jung.algorithms.generators.EvolvingGraphGenerator;
import edu.uci.ics.jung.algorithms.util.WeightedChoice;
import edu.uci.ics.jung.graph.Graph;
import edu.uci.ics.jung.graph.MultiGraph;
import edu.uci.ics.jung.graph.util.EdgeType;
import edu.uci.ics.jung.graph.util.Pair;
/**
*
* 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 "A.-L. Barabasi and R. Albert, Emergence of scaling in random networks, Science 286, 1999."
* @author Scott White
* @author Joshua O'Madadhain
* @author Tom Nelson - adapted to jung2
* @author James Marchant
*/
public class BarabasiAlbertGenerator implements EvolvingGraphGenerator {
private Graph mGraph = null;
private int mNumEdgesToAttachPerStep;
private int mElapsedTimeSteps;
private Random mRandom;
protected List vertex_index;
protected int init_vertices;
protected Map index_vertex;
protected Supplier> graphFactory;
protected Supplier vertexFactory;
protected Supplier edgeFactory;
/**
* Constructs a new instance of the generator.
*
* @param graphFactory
* factory for graphs of the appropriate type
* @param vertexFactory
* factory for vertices of the appropriate type
* @param edgeFactory
* factory for edges of the appropriate type
* @param init_vertices
* number of unconnected 'seed' vertices that the graph should
* start with
* @param numEdgesToAttach
* the number of edges that should be attached from the new
* vertex to pre-existing vertices at each time step
* @param seed
* random number seed
* @param seedVertices
* storage for the seed vertices that this graph creates
*/
// TODO: seedVertices is a bizarre way of exposing that information,
// refactor
public BarabasiAlbertGenerator(Supplier> graphFactory, Supplier vertexFactory,
Supplier edgeFactory, int init_vertices, int numEdgesToAttach, int seed, Set seedVertices) {
Preconditions.checkArgument(init_vertices > 0,
"Number of initial unconnected 'seed' vertices must be positive");
Preconditions.checkArgument(numEdgesToAttach > 0,
"Number of edges to attach at each time step must be positive");
Preconditions.checkArgument(numEdgesToAttach <= init_vertices,
"Number of edges to attach at each time step must less than or equal to the number of initial vertices");
mNumEdgesToAttachPerStep = numEdgesToAttach;
mRandom = new Random(seed);
this.graphFactory = graphFactory;
this.vertexFactory = vertexFactory;
this.edgeFactory = edgeFactory;
this.init_vertices = init_vertices;
initialize(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.
*
* @param graphFactory
* factory for graphs of the appropriate type
* @param vertexFactory
* factory for vertices of the appropriate type
* @param edgeFactory
* factory for edges of the appropriate type
* @param init_vertices
* number of vertices that the graph should start with
* @param numEdgesToAttach
* the number of edges that should be attached from the new
* vertex to pre-existing vertices at each time step
* @param seedVertices
* storage for the seed vertices that this graph creates
*/
public BarabasiAlbertGenerator(Supplier> graphFactory, Supplier vertexFactory,
Supplier edgeFactory, int init_vertices, int numEdgesToAttach, Set seedVertices) {
this(graphFactory, vertexFactory, edgeFactory, init_vertices, numEdgesToAttach,
(int) System.currentTimeMillis(), seedVertices);
}
private void initialize(Set seedVertices) {
mGraph = graphFactory.get();
vertex_index = new ArrayList(2 * init_vertices);
index_vertex = new HashMap(2 * init_vertices);
for (int i = 0; i < init_vertices; i++) {
V v = vertexFactory.get();
mGraph.addVertex(v);
vertex_index.add(v);
index_vertex.put(v, i);
seedVertices.add(v);
}
mElapsedTimeSteps = 0;
}
public void evolveGraph(int numTimeSteps) {
for (int i = 0; i < numTimeSteps; i++) {
evolveGraph();
mElapsedTimeSteps++;
}
}
private void evolveGraph() {
Collection preexistingNodes = mGraph.getVertices();
V newVertex = vertexFactory.get();
mGraph.addVertex(newVertex);
// generate and store the new edges; don't add them to the graph
// yet because we don't want to bias the degree calculations
// (all new edges in a timestep should be added in parallel)
Set> added_pairs = createRandomEdges(preexistingNodes, newVertex, mNumEdgesToAttachPerStep);
for (Pair pair : added_pairs) {
V v1 = pair.getFirst();
V v2 = pair.getSecond();
if (mGraph.getDefaultEdgeType() != EdgeType.UNDIRECTED || !mGraph.isNeighbor(v1, v2))
mGraph.addEdge(edgeFactory.get(), pair);
}
// now that we're done attaching edges to this new vertex,
// add it to the index
vertex_index.add(newVertex);
index_vertex.put(newVertex, new Integer(vertex_index.size() - 1));
}
private Set> createRandomEdges(Collection preexistingNodes, V newVertex, int numEdges) {
Set> added_pairs = new HashSet>(numEdges * 3);
/* Generate the probability distribution */
Map item_weights = new HashMap();
for (V v : preexistingNodes) {
/*
* as preexistingNodes is a view onto the vertex set, it will
* contain the new node. In the construction of Barabasi-Albert,
* there should be no self-loops.
*/
if (v == newVertex)
continue;
double degree;
double denominator;
/*
* Attachment probability is dependent on whether the graph is
* directed or undirected.
*
* Subtract 1 from numVertices because we don't want to count
* newVertex (which has already been added to the graph, but not to
* vertex_index).
*/
if (mGraph.getDefaultEdgeType() == EdgeType.UNDIRECTED) {
degree = mGraph.degree(v);
denominator = (2 * mGraph.getEdgeCount()) + mGraph.getVertexCount() - 1;
} else {
degree = mGraph.inDegree(v);
denominator = mGraph.getEdgeCount() + mGraph.getVertexCount() - 1;
}
double prob = (degree + 1) / denominator;
item_weights.put(v, prob);
}
WeightedChoice nodeProbabilities = new WeightedChoice(item_weights, mRandom);
for (int i = 0; i < numEdges; i++) {
createRandomEdge(preexistingNodes, newVertex, added_pairs, nodeProbabilities);
}
return added_pairs;
}
private void createRandomEdge(Collection preexistingNodes, V newVertex, Set> added_pairs,
WeightedChoice weightedProbabilities) {
V attach_point;
boolean created_edge = false;
Pair endpoints;
do {
attach_point = weightedProbabilities.nextItem();
endpoints = new Pair(newVertex, attach_point);
/*
* If parallel edges are not allowed, skip attach_point if
* already exists; note that because of
* the way the new node's edges are added, we only need to check the
* list of candidate edges for duplicates.
*/
if (!(mGraph instanceof MultiGraph)) {
if (added_pairs.contains(endpoints))
continue;
if (mGraph.getDefaultEdgeType() == EdgeType.UNDIRECTED
&& added_pairs.contains(new Pair(attach_point, newVertex)))
continue;
}
created_edge = true;
} while (!created_edge);
added_pairs.add(endpoints);
if (mGraph.getDefaultEdgeType() == EdgeType.UNDIRECTED) {
added_pairs.add(new Pair(attach_point, newVertex));
}
}
public int numIterations() {
return mElapsedTimeSteps;
}
public Graph get() {
return mGraph;
}
}
Ads help maintain this website.