| Line | Hits | Source |
|---|---|---|
| 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.random.generators; | |
| 11 | ||
| 12 | import java.util.Random; | |
| 13 | ||
| 14 | import edu.uci.ics.jung.graph.ArchetypeGraph; | |
| 15 | import edu.uci.ics.jung.graph.Edge; | |
| 16 | import edu.uci.ics.jung.graph.Graph; | |
| 17 | import edu.uci.ics.jung.graph.Vertex; | |
| 18 | import edu.uci.ics.jung.graph.decorators.Indexer; | |
| 19 | import edu.uci.ics.jung.graph.impl.UndirectedSparseGraph; | |
| 20 | import edu.uci.ics.jung.utils.GraphUtils; | |
| 21 | ||
| 22 | /** | |
| 23 | * WattsBetaSmallWorldGenerator is a graph generator that produces a small | |
| 24 | * world network using the beta-model as proposed by Duncan Watts. The basic ideas is | |
| 25 | * to start with a one-dimensional ring lattice in which each vertex has k-neighbors and then randomly | |
| 26 | * rewire the edges, with probability beta, in such a way that a small world networks can be created for | |
| 27 | * certain values of beta and k that exhibit low charachteristic path lengths and high clustering coefficient. | |
| 28 | * @see "Small Worlds:The Dynamics of Networks between Order and Randomness by D.J. Watts" | |
| 29 | * @author Christopher Brooks, Scott White | |
| 30 | * | |
| 31 | */ | |
| 32 | public class WattsBetaSmallWorldGenerator extends Lattice1DGenerator { | |
| 33 | 61 | private int numNodes = 0; |
| 34 | 61 | private double beta = 0; |
| 35 | 61 | private int degree = 0; |
| 36 | 61 | private Random random = new Random(); |
| 37 | ||
| 38 | /** | |
| 39 | * Constructs the small world graph generator. | |
| 40 | * @param numNodes the number of nodes in the ring lattice | |
| 41 | * @param beta the probability of an edge being rewired randomly; the proportion of randomly rewired edges in a graph. | |
| 42 | * @param degree the number of edges connected to each vertex; the local neighborhood size. | |
| 43 | */ | |
| 44 | public WattsBetaSmallWorldGenerator(int numNodes, double beta, int degree) { | |
| 45 | 61 | super(numNodes,true); |
| 46 | ||
| 47 | 61 | if (numNodes < 10) { |
| 48 | 0 | throw new IllegalArgumentException("Lattice must contain at least 10 vertices."); |
| 49 | } | |
| 50 | 61 | if (degree % 2 != 0) { |
| 51 | 0 | throw new IllegalArgumentException("All nodes must have an even degree."); |
| 52 | } | |
| 53 | 61 | if (beta > 1.0 || beta < 0.0) { |
| 54 | 0 | throw new IllegalArgumentException("Beta must be between 0 and 1."); |
| 55 | } | |
| 56 | 61 | this.numNodes = numNodes; |
| 57 | 61 | this.beta = beta; |
| 58 | 61 | this.degree = degree; |
| 59 | ||
| 60 | //System.out.println("Creating a lattice with n="+nodes+", k="+degree+", and beta="+beta+"."); | |
| 61 | 61 | } |
| 62 | ||
| 63 | /** | |
| 64 | * Generates a beta-network from a 1-lattice according to the parameters given. | |
| 65 | * @return a beta-network model that is potentially a small-world | |
| 66 | */ | |
| 67 | public ArchetypeGraph generateGraph() { | |
| 68 | 61 | Graph g = new UndirectedSparseGraph(); |
| 69 | 61 | GraphUtils.addVertices(g, numNodes); |
| 70 | 61 | int upI = 0;//, downI = 0; |
| 71 | 61 | Indexer id = Indexer.getIndexer(g); |
| 72 | ||
| 73 | 61 | int numKNeighbors = (degree / 2); |
| 74 | ||
| 75 | //create lattice structure | |
| 76 | 4986 | for (int i = 0; i < numNodes; i++) { |
| 77 | 14775 | for (int s = 1; s <= numKNeighbors; s++) { |
| 78 | 9850 | Vertex ithVertex = (Vertex) id.getVertex(i); |
| 79 | 9850 | upI = upIndex(i, s); |
| 80 | // downI = downIndex(i, s); | |
| 81 | 9850 | GraphUtils.addEdge(g, ithVertex, (Vertex) id.getVertex(upI)); |
| 82 | //GraphUtils.addEdge((Graph) g, ithVertex, id.getVertex(downI)); | |
| 83 | } | |
| 84 | } | |
| 85 | ||
| 86 | //rewire edges | |
| 87 | 4986 | for (int i = 0; i < numNodes; i++) { |
| 88 | 14775 | for (int s = 1; s <= numKNeighbors; s++) { |
| 89 | ||
| 90 | while (true) { | |
| 91 | // randomly rewire a proportion, beta, of the edges in the graph. | |
| 92 | 9909 | double r = random.nextDouble(); |
| 93 | 9909 | if (r < beta) { |
| 94 | 1340 | int v = (int) random.nextInt(numNodes); |
| 95 | ||
| 96 | 1340 | Vertex vthVertex = (Vertex) id.getVertex(v); |
| 97 | 1340 | Vertex ithVertex = (Vertex) id.getVertex(i); |
| 98 | 1340 | Vertex kthVertex = (Vertex) id.getVertex(upIndex(i, s)); |
| 99 | 1340 | Edge e = ithVertex.findEdge(kthVertex); |
| 100 | ||
| 101 | 1340 | if (!kthVertex.isNeighborOf(vthVertex) && kthVertex != vthVertex) { |
| 102 | 1281 | g.removeEdge(e); |
| 103 | 1281 | GraphUtils.addEdge(g, kthVertex, vthVertex); |
| 104 | 1281 | break; |
| 105 | } | |
| 106 | } else { | |
| 107 | 59 | break; |
| 108 | } | |
| 109 | } | |
| 110 | } | |
| 111 | } | |
| 112 | ||
| 113 | 61 | return g; |
| 114 | } | |
| 115 | } |
|
this report was generated by version 1.0.5 of jcoverage. |
copyright © 2003, jcoverage ltd. all rights reserved. |