| 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.Arrays; | |
| 13 | ||
| 14 | import edu.uci.ics.jung.graph.ArchetypeGraph; | |
| 15 | import edu.uci.ics.jung.graph.Graph; | |
| 16 | import edu.uci.ics.jung.graph.Vertex; | |
| 17 | import edu.uci.ics.jung.graph.decorators.Indexer; | |
| 18 | import edu.uci.ics.jung.utils.GraphUtils; | |
| 19 | ||
| 20 | /** | |
| 21 | * Graph generator that produces a random graph with small world properties. The underlying model is | |
| 22 | * an nxn toroidal lattice. Each node u has four local connections, one to each of its neighbors, and | |
| 23 | * in addition one long range connection to some node v where v is chosen randomly according to | |
| 24 | * probability proportional to d^-alpha where d is the lattice distance between u and v and alpha | |
| 25 | * is the clustering expononent. | |
| 26 | * @see "Navigation in a small world J. Kleinberg, Nature 406(2000), 845." | |
| 27 | * @author Scott White | |
| 28 | */ | |
| 29 | public class KleinbergSmallWorldGenerator extends Lattice2DGenerator { | |
| 30 | //private int mNumNodes; | |
| 31 | private double mClusteringExponent; | |
| 32 | private int mLongRangeDistanceDistributionsSize; | |
| 33 | private int[] mLongRangeDistanceDistributions; | |
| 34 | ||
| 35 | /** | |
| 36 | * Constructs the small world graph generator. | |
| 37 | * @param latticeSize the lattice size (length of row or column dimension) | |
| 38 | * @param clusteringExponent the clustering exponent parameter (somewhere around 2 is a good choice) | |
| 39 | */ | |
| 40 | public KleinbergSmallWorldGenerator(int latticeSize, double clusteringExponent) { | |
| 41 | 10 | super(latticeSize,true); |
| 42 | ||
| 43 | 10 | mLongRangeDistanceDistributionsSize = getLatticeSize() * 1000; |
| 44 | 10 | mClusteringExponent = clusteringExponent; |
| 45 | 10 | } |
| 46 | ||
| 47 | /** | |
| 48 | * Generates a random small world network according to the parameters given | |
| 49 | * @return a random small world graph | |
| 50 | */ | |
| 51 | public ArchetypeGraph generateGraph() { | |
| 52 | ||
| 53 | 10 | Lattice2DGenerator generator = new Lattice2DGenerator(getLatticeSize(),true); |
| 54 | 10 | Graph graph = (Graph) generator.generateGraph(); |
| 55 | ||
| 56 | 10 | Indexer id = Indexer.getIndexer( graph ) ; |
| 57 | ||
| 58 | 10 | computeLongDistanceEdgeDistributionSample(); |
| 59 | ||
| 60 | 10 | int numNodes = (int) Math.pow(getLatticeSize(), 2); |
| 61 | ||
| 62 | //Add long range connections | |
| 63 | 260 | for (int i = 0; i < numNodes; i++) { |
| 64 | ||
| 65 | //choose random distance | |
| 66 | 250 | int sampleNodeIndex = (int) (Math.random() * mLongRangeDistanceDistributionsSize); |
| 67 | 250 | int randomDistance = mLongRangeDistanceDistributions[sampleNodeIndex]; |
| 68 | while (true) { | |
| 69 | 251 | int randomNodeIndex = simulatePath(i, randomDistance); |
| 70 | ||
| 71 | 251 | Vertex source = (Vertex) id.getVertex(i); |
| 72 | 251 | Vertex target = (Vertex) id.getVertex(randomNodeIndex); |
| 73 | ||
| 74 | 251 | if (!target.isSuccessorOf(source)) { |
| 75 | 250 | GraphUtils.addEdge( graph, source, target); |
| 76 | 250 | break; |
| 77 | } | |
| 78 | ||
| 79 | } | |
| 80 | } | |
| 81 | ||
| 82 | 10 | return graph; |
| 83 | } | |
| 84 | ||
| 85 | private static int pickValue(boolean[] choices) { | |
| 86 | ||
| 87 | 659 | int totalNumChoicesLeft= 0; |
| 88 | 3295 | for (int x =0;x<choices.length;x++) { |
| 89 | 2636 | if (choices[x]) { |
| 90 | 2109 | totalNumChoicesLeft++; |
| 91 | } | |
| 92 | } | |
| 93 | ||
| 94 | 659 | double randValue = Math.random(); |
| 95 | 659 | int i = 1; |
| 96 | ||
| 97 | 2211 | for (;i<=totalNumChoicesLeft; i++) { |
| 98 | 1435 | if (randValue < (double) i/ (double) totalNumChoicesLeft) { |
| 99 | 659 | break; |
| 100 | } | |
| 101 | } | |
| 102 | ||
| 103 | 659 | int currentChoice = 1; |
| 104 | 1492 | for (int j=0;i<choices.length;j++) { |
| 105 | 1419 | if (choices[j]) { |
| 106 | 1143 | if (currentChoice == i) { |
| 107 | 586 | return j+1; |
| 108 | } | |
| 109 | 557 | currentChoice++; |
| 110 | } | |
| 111 | } | |
| 112 | ||
| 113 | 73 | return currentChoice; |
| 114 | } | |
| 115 | ||
| 116 | private int simulatePath(int index, int distance) { | |
| 117 | ||
| 118 | //1 = up,2 = down,3 = left, 4 = right | |
| 119 | 251 | boolean[] currentChoices = new boolean[4]; |
| 120 | 251 | Arrays.fill(currentChoices, true); |
| 121 | ||
| 122 | 251 | int numSteps = 0; |
| 123 | 251 | int currentChoice = 0; |
| 124 | 251 | int newIndex = 0; |
| 125 | 251 | int xCoordinate = index / getLatticeSize(); |
| 126 | 251 | int yCoordinate = index % getLatticeSize(); |
| 127 | ||
| 128 | ||
| 129 | 910 | while (numSteps < distance) { |
| 130 | ||
| 131 | 659 | currentChoice = pickValue(currentChoices); |
| 132 | ||
| 133 | 659 | switch (currentChoice) { |
| 134 | case 1: | |
| 135 | { | |
| 136 | 230 | currentChoices[1] = false; |
| 137 | 230 | newIndex = upIndex(xCoordinate, yCoordinate); |
| 138 | 230 | break; |
| 139 | } | |
| 140 | case 2: | |
| 141 | { | |
| 142 | 126 | currentChoices[0] = false; |
| 143 | 126 | newIndex = downIndex(xCoordinate, yCoordinate); |
| 144 | 126 | break; |
| 145 | } | |
| 146 | case 3: | |
| 147 | { | |
| 148 | 202 | currentChoices[3] = false; |
| 149 | 202 | newIndex = leftIndex(xCoordinate, yCoordinate); |
| 150 | 202 | break; |
| 151 | } | |
| 152 | case 4: | |
| 153 | { | |
| 154 | 101 | currentChoices[2] = false; |
| 155 | 101 | newIndex = rightIndex(xCoordinate, yCoordinate); |
| 156 | break; | |
| 157 | } | |
| 158 | } | |
| 159 | 659 | xCoordinate = newIndex / getLatticeSize(); |
| 160 | 659 | yCoordinate = newIndex % getLatticeSize(); |
| 161 | ||
| 162 | 659 | numSteps++; |
| 163 | } | |
| 164 | ||
| 165 | 251 | return newIndex; |
| 166 | } | |
| 167 | ||
| 168 | ||
| 169 | public double getClusteringExponent() { | |
| 170 | 0 | return mClusteringExponent; |
| 171 | } | |
| 172 | ||
| 173 | public void setClusteringExponent(double clusteringExponent) { | |
| 174 | 0 | this.mClusteringExponent = clusteringExponent; |
| 175 | 0 | } |
| 176 | ||
| 177 | private void computeLongDistanceEdgeDistributionSample() { | |
| 178 | 10 | int numLongRangeLevels = getLatticeSize() - 2; |
| 179 | 10 | if ((getLatticeSize() % 2) == 0) { |
| 180 | 0 | numLongRangeLevels = getLatticeSize() - 1; |
| 181 | } | |
| 182 | ||
| 183 | 10 | double[] probDists = new double[numLongRangeLevels]; |
| 184 | 10 | double normalizingFactor = 0; |
| 185 | 10 | int currentDistance = 2; |
| 186 | 40 | for (int i = 0; i < numLongRangeLevels; i++) { |
| 187 | 30 | probDists[i] = Math.pow(currentDistance, -1 * mClusteringExponent); |
| 188 | 30 | normalizingFactor += probDists[i]; |
| 189 | 30 | currentDistance++; |
| 190 | } | |
| 191 | ||
| 192 | 40 | for (int i = 0; i < numLongRangeLevels; i++) { |
| 193 | 30 | probDists[i] /= normalizingFactor; |
| 194 | } | |
| 195 | ||
| 196 | 10 | mLongRangeDistanceDistributions = new int[mLongRangeDistanceDistributionsSize]; |
| 197 | ||
| 198 | ||
| 199 | 50010 | for (int i = 0; i < mLongRangeDistanceDistributionsSize; i++) { |
| 200 | 50000 | currentDistance = 2; |
| 201 | 50000 | double currentCumProb = 0; |
| 202 | 50000 | double randomVal = Math.random(); |
| 203 | ||
| 204 | 78306 | for (int j = 0; j < numLongRangeLevels; j++) { |
| 205 | 78306 | currentCumProb += probDists[j]; |
| 206 | 78306 | if (randomVal < currentCumProb) { |
| 207 | 50000 | mLongRangeDistanceDistributions[i] = currentDistance; |
| 208 | 50000 | break; |
| 209 | } | |
| 210 | 28306 | currentDistance += 1; |
| 211 | } | |
| 212 | } | |
| 213 | 10 | } |
| 214 | } |
|
this report was generated by version 1.0.5 of jcoverage. |
copyright © 2003, jcoverage ltd. all rights reserved. |