Coverage details for edu.uci.ics.jung.random.generators.WattsBetaSmallWorldGenerator

LineHitsSource
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 {
3361    private int numNodes = 0;
3461    private double beta = 0;
3561    private int degree = 0;
3661    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) {
4561        super(numNodes,true);
46         
4761        if (numNodes < 10) {
480            throw new IllegalArgumentException("Lattice must contain at least 10 vertices.");
49         }
5061        if (degree % 2 != 0) {
510            throw new IllegalArgumentException("All nodes must have an even degree.");
52         }
5361        if (beta > 1.0 || beta < 0.0) {
540            throw new IllegalArgumentException("Beta must be between 0 and 1.");
55         }
5661        this.numNodes = numNodes;
5761        this.beta = beta;
5861        this.degree = degree;
59  
60         //System.out.println("Creating a lattice with n="+nodes+", k="+degree+", and beta="+beta+".");
6161    }
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() {
6861        Graph g = new UndirectedSparseGraph();
6961        GraphUtils.addVertices(g, numNodes);
7061        int upI = 0;//, downI = 0;
7161        Indexer id = Indexer.getIndexer(g);
72  
7361        int numKNeighbors = (degree / 2);
74  
75         //create lattice structure
764986        for (int i = 0; i < numNodes; i++) {
7714775            for (int s = 1; s <= numKNeighbors; s++) {
789850                Vertex ithVertex = (Vertex) id.getVertex(i);
799850                upI = upIndex(i, s);
80 // downI = downIndex(i, s);
819850                GraphUtils.addEdge(g, ithVertex, (Vertex) id.getVertex(upI));
82                 //GraphUtils.addEdge((Graph) g, ithVertex, id.getVertex(downI));
83             }
84         }
85  
86         //rewire edges
874986        for (int i = 0; i < numNodes; i++) {
8814775            for (int s = 1; s <= numKNeighbors; s++) {
89  
90                 while (true) {
91                     // randomly rewire a proportion, beta, of the edges in the graph.
929931                    double r = random.nextDouble();
939931                    if (r < beta) {
941385                        int v = (int) random.nextInt(numNodes);
95  
961385                        Vertex vthVertex = (Vertex) id.getVertex(v);
971385                        Vertex ithVertex = (Vertex) id.getVertex(i);
981385                        Vertex kthVertex = (Vertex) id.getVertex(upIndex(i, s));
991385                        Edge e = ithVertex.findEdge(kthVertex);
100  
1011385                        if (!kthVertex.isNeighborOf(vthVertex) && kthVertex != vthVertex) {
1021304                            g.removeEdge(e);
1031304                            GraphUtils.addEdge(g, kthVertex, vthVertex);
1041304                            break;
105                         }
106                     } else {
10781                        break;
108                     }
109                 }
110             }
111         }
112  
11361        return g;
114     }
115 }

this report was generated by version 1.0.5 of jcoverage.
visit www.jcoverage.com for updates.

copyright © 2003, jcoverage ltd. all rights reserved.
Java is a trademark of Sun Microsystems, Inc. in the United States and other countries.