third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/generators/random/BarabasiAlbertGenerator.java

   1 /*
   2  * Copyright (c) 2003, the JUNG Project and the Regents of the University
   3  * of California
   4  * All rights reserved.
   5  *
   6  * This software is open-source under the BSD license; see either
   7  * "license.txt" or
   8  * http://jung.sourceforge.net/license.txt for a description.
   9  */
  10 package edu.uci.ics.jung.algorithms.generators.random;
  11
  12 import java.util.ArrayList;
  13 import java.util.Collection;
  14 import java.util.HashMap;
  15 import java.util.HashSet;
  16 import java.util.List;
  17 import java.util.Map;
  18 import java.util.Random;
  19 import java.util.Set;
  20
  21 import org.apache.commons.collections15.Factory;
  22
  23 import edu.uci.ics.jung.algorithms.generators.EvolvingGraphGenerator;
  24 import edu.uci.ics.jung.graph.Graph;
  25 import edu.uci.ics.jung.graph.MultiGraph;
  26 import edu.uci.ics.jung.graph.util.EdgeType;
  27 import edu.uci.ics.jung.graph.util.Pair;
  28
  29
  30 /**
  31  * <p>Simple evolving scale-free random graph generator. At each time
  32  * step, a new vertex is created and is connected to existing vertices
  33  * according to the principle of "preferential attachment", whereby
  34  * vertices with higher degree have a higher probability of being
  35  * selected for attachment.</p>
  36  *
  37  * <p>At a given timestep, the probability <code>p</code> of creating an edge
  38  * between an existing vertex <code>v</code> and the newly added vertex is
  39  * <pre>
  40  * p = (degree(v) + 1) / (|E| + |V|);
  41  * </pre>
  42  *
  43  * <p>where <code>|E|</code> and <code>|V|</code> are, respectively, the number
  44  * of edges and vertices currently in the network (counting neither the new
  45  * vertex nor the other edges that are being attached to it).</p>
  46  *
  47  * <p>Note that the formula specified in the original paper
  48  * (cited below) was
  49  * <pre>
  50  * p = degree(v) / |E|
  51  * </pre>
  52  * </p>
  53  *
  54  * <p>However, this would have meant that the probability of attachment for any existing
  55  * isolated vertex would be 0.  This version uses Lagrangian smoothing to give
  56  * each existing vertex a positive attachment probability.</p>
  57  *
  58  * <p>The graph created may be either directed or undirected (controlled by a constructor
  59  * parameter); the default is undirected.
  60  * If the graph is specified to be directed, then the edges added will be directed
  61  * from the newly added vertex u to the existing vertex v, with probability proportional to the
  62  * indegree of v (number of edges directed towards v).  If the graph is specified to be undirected,
  63  * then the (undirected) edges added will connect u to v, with probability proportional to the
  64  * degree of v.</p>
  65  *
  66  * <p>The <code>parallel</code> constructor parameter specifies whether parallel edges
  67  * may be created.</p>
  68  *
  69  * @see "A.-L. Barabasi and R. Albert, Emergence of scaling in random networks, Science 286, 1999."
  70  * @author Scott White
  71  * @author Joshua O'Madadhain
  72  * @author Tom Nelson - adapted to jung2
  73  */
  74 public class BarabasiAlbertGenerator<V,E> implements EvolvingGraphGenerator<V,E> {
  75     private Graph<V, E> mGraph = null;
  76     private int mNumEdgesToAttachPerStep;
  77     private int mElapsedTimeSteps;
  78     private Random mRandom;
  79     protected List<V> vertex_index;
  80     protected int init_vertices;
  81     protected Map<V,Integer> index_vertex;
  82     protected Factory<Graph<V,E>> graphFactory;
  83     protected Factory<V> vertexFactory;
  84     protected Factory<E> edgeFactory;
  85
  86     /**
  87      * Constructs a new instance of the generator.
  88      * @param init_vertices     number of unconnected 'seed' vertices that the graph should start with
  89      * @param numEdgesToAttach the number of edges that should be attached from the
  90      * new vertex to pre-existing vertices at each time step
  91      * @param directed  specifies whether the graph and edges to be created should be directed or not
  92      * @param parallel  specifies whether the algorithm permits parallel edges
  93      * @param seed  random number seed
  94      */
  95     public BarabasiAlbertGenerator(Factory<Graph<V,E>> graphFactory,
  96                 Factory<V> vertexFactory, Factory<E> edgeFactory,
  97                 int init_vertices, int numEdgesToAttach,
  98             int seed, Set<V> seedVertices)
  99     {
 100         assert init_vertices > 0 : "Number of initial unconnected 'seed' vertices " +
 101                     "must be positive";
 102         assert numEdgesToAttach > 0 : "Number of edges to attach " +
 103                     "at each time step must be positive";
 104
 105         mNumEdgesToAttachPerStep = numEdgesToAttach;
 106         mRandom = new Random(seed);
 107         this.graphFactory = graphFactory;
 108         this.vertexFactory = vertexFactory;
 109         this.edgeFactory = edgeFactory;
 110         this.init_vertices = init_vertices;
 111         initialize(seedVertices);
 112     }
 113
 114
 115     /**
 116      * Constructs a new instance of the generator, whose output will be an undirected graph,
 117      * and which will use the current time as a seed for the random number generation.
 118      * @param init_vertices     number of vertices that the graph should start with
 119      * @param numEdgesToAttach the number of edges that should be attached from the
 120      * new vertex to pre-existing vertices at each time step
 121      */
 122     public BarabasiAlbertGenerator(Factory<Graph<V,E>> graphFactory,
 123                 Factory<V> vertexFactory, Factory<E> edgeFactory,
 124                 int init_vertices, int numEdgesToAttach, Set<V> seedVertices) {
 125         this(graphFactory, vertexFactory, edgeFactory, init_vertices, numEdgesToAttach, (int) System.currentTimeMillis(), seedVertices);
 126     }
 127
 128     private void initialize(Set<V> seedVertices) {
 129
 130         mGraph = graphFactory.create();
 131
 132         vertex_index = new ArrayList<V>(2*init_vertices);
 133         index_vertex = new HashMap<V, Integer>(2*init_vertices);
 134         for (int i = 0; i < init_vertices; i++) {
 135             V v = vertexFactory.create();
 136             mGraph.addVertex(v);
 137             vertex_index.add(v);
 138             index_vertex.put(v, i);
 139             seedVertices.add(v);
 140         }
 141
 142         mElapsedTimeSteps = 0;
 143     }
 144
 145     private void createRandomEdge(Collection<V> preexistingNodes,
 146                 V newVertex, Set<Pair<V>> added_pairs) {
 147         V attach_point;
 148         boolean created_edge = false;
 149         Pair<V> endpoints;
 150         do {
 151             attach_point = vertex_index.get(mRandom.nextInt(vertex_index.size()));
 152
 153             endpoints = new Pair<V>(newVertex, attach_point);
 154
 155             // if parallel edges are not allowed, skip attach_point if <newVertex, attach_point>
 156             // already exists; note that because of the way edges are added, we only need to check
 157             // the list of candidate edges for duplicates.
 158             if (!(mGraph instanceof MultiGraph))
 159             {
 160                 if (added_pairs.contains(endpoints))
 161                         continue;
 162                 if (mGraph.getDefaultEdgeType() == EdgeType.UNDIRECTED &&
 163                         added_pairs.contains(new Pair<V>(attach_point, newVertex)))
 164                         continue;
 165             }
 166
 167             double degree = mGraph.inDegree(attach_point);
 168
 169             // subtract 1 from numVertices because we don't want to count newVertex
 170             // (which has already been added to the graph, but not to vertex_index)
 171             double attach_prob = (degree + 1) / (mGraph.getEdgeCount() + mGraph.getVertexCount() - 1);
 172             if (attach_prob >= mRandom.nextDouble())
 173                 created_edge = true;
 174         }
 175         while (!created_edge);
 176
 177         added_pairs.add(endpoints);
 178
 179         if (mGraph.getDefaultEdgeType() == EdgeType.UNDIRECTED) {
 180                 added_pairs.add(new Pair<V>(attach_point, newVertex));
 181         }
 182     }
 183
 184     public void evolveGraph(int numTimeSteps) {
 185
 186         for (int i = 0; i < numTimeSteps; i++) {
 187             evolveGraph();
 188             mElapsedTimeSteps++;
 189         }
 190     }
 191
 192     private void evolveGraph() {
 193         Collection<V> preexistingNodes = mGraph.getVertices();
 194         V newVertex = vertexFactory.create();
 195
 196         mGraph.addVertex(newVertex);
 197
 198         // generate and store the new edges; don't add them to the graph
 199         // yet because we don't want to bias the degree calculations
 200         // (all new edges in a timestep should be added in parallel)
 201         Set<Pair<V>> added_pairs = new HashSet<Pair<V>>(mNumEdgesToAttachPerStep*3);
 202
 203         for (int i = 0; i < mNumEdgesToAttachPerStep; i++)
 204                 createRandomEdge(preexistingNodes, newVertex, added_pairs);
 205
 206         for (Pair<V> pair : added_pairs)
 207         {
 208                 V v1 = pair.getFirst();
 209                 V v2 = pair.getSecond();
 210                 if (mGraph.getDefaultEdgeType() != EdgeType.UNDIRECTED ||
 211                                 !mGraph.isNeighbor(v1, v2))
 212                         mGraph.addEdge(edgeFactory.create(), pair);
 213         }
 214         // now that we're done attaching edges to this new vertex,
 215         // add it to the index
 216         vertex_index.add(newVertex);
 217         index_vertex.put(newVertex, new Integer(vertex_index.size() - 1));
 218     }
 219
 220     public int numIterations() {
 221         return mElapsedTimeSteps;
 222     }
 223
 224     public Graph<V, E> create() {
 225         return mGraph;
 226     }
 227 }