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. |