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