001/* 002 * Copyright 2006 - 2013 003 * Stefan Balev <stefan.balev@graphstream-project.org> 004 * Julien Baudry <julien.baudry@graphstream-project.org> 005 * Antoine Dutot <antoine.dutot@graphstream-project.org> 006 * Yoann Pigné <yoann.pigne@graphstream-project.org> 007 * Guilhelm Savin <guilhelm.savin@graphstream-project.org> 008 * 009 * This file is part of GraphStream <http://graphstream-project.org>. 010 * 011 * GraphStream is a library whose purpose is to handle static or dynamic 012 * graph, create them from scratch, file or any source and display them. 013 * 014 * This program is free software distributed under the terms of two licenses, the 015 * CeCILL-C license that fits European law, and the GNU Lesser General Public 016 * License. You can use, modify and/ or redistribute the software under the terms 017 * of the CeCILL-C license as circulated by CEA, CNRS and INRIA at the following 018 * URL <http://www.cecill.info> or under the terms of the GNU LGPL as published by 019 * the Free Software Foundation, either version 3 of the License, or (at your 020 * option) any later version. 021 * 022 * This program is distributed in the hope that it will be useful, but WITHOUT ANY 023 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A 024 * PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details. 025 * 026 * You should have received a copy of the GNU Lesser General Public License 027 * along with this program. If not, see <http://www.gnu.org/licenses/>. 028 * 029 * The fact that you are presently reading this means that you have had 030 * knowledge of the CeCILL-C and LGPL licenses and that you accept their terms. 031 */ 032package org.graphstream.algorithm.generator; 033 034import static java.lang.Math.*; 035 036/** 037 * A generator following the small-world model of Watts and Strogatz. 038 * 039 * <p> 040 * This generator creates small-world graphs of arbitrary size. 041 * </p> 042 * 043 * <p> 044 * This model 045 * generates a ring of n nodes where each node is connected to its k nearest 046 * neighbours in the ring (k/2 on each side, which means k must be even). 047 * Then it process each node of the ring in order following the ring, and "rewiring" 048 * each of their edges toward the not yet processed nodes with randomly chosen nodes 049 * with a probability beta. 050 * </p> 051 * 052 * <h2>Usage</h2> 053 * 054 * <p> 055 * You must provide values for n, k and beta at construction time. You must ensure 056 * that k is event, that n >> k >> log(n) >> 1. Furthermore, beta being a probability 057 * it must be between 0 and 1. 058 * </p> 059 * 060 * <p> 061 * By default, the generator will produce a placement for nodes using the ``xyz`` 062 * attribute. 063 * </p> 064 * 065 * <p> 066 * This generator will produce the ring of nodes once {@link #begin()} has been 067 * called. Then calling {@link #nextEvents()} will rewire one node at a time 068 * return true until each node is processed, in which case it returns false. 069 * You must then call {@link #end()}. 070 * </p> 071 * 072 * <h2>Example</h2> 073 * 074 * <pre> 075 * Graph graph = new SingleGraph("This is a small world!"); 076 * Generator gen = new WattsStrogatzGenerator(20, 2, 0.5); 077 * 078 * gen.addSink(graph); 079 * gen.begin(); 080 * while(gen.nextEvents()) {} 081 * gen.end(); 082 * 083 * graph.display(false); // Node position is provided. 084 * </pre> 085 * 086 * <h2>Reference</h2> 087 * 088 * <p> 089 * This generator is based on the Watts-Strogatz model. 090 * </p> 091 * 092 * @reference Watts, D.J. and Strogatz, S.H. 093 * "Collective dynamics of 'small-world' networks". Nature 393 094 * (6684): 409–10. doi:10.1038/30918. PMID 9623998. 1998. 095 */ 096public class WattsStrogatzGenerator extends BaseGenerator { 097 /** The number of nodes to generate. */ 098 protected int n; 099 100 /** Base degree of each node. */ 101 protected int k; 102 103 /** Probability to "rewire" an edge. */ 104 protected double beta; 105 106 /** Current rewired node, used to allo nextEvents() iteration. */ 107 protected int current; 108 109 /** 110 * New Watts-Strogatz generator. 111 * 112 * @param n 113 * The number of nodes to generate. 114 * @param k 115 * The base degree of each node. 116 * @param beta 117 * Probability to "rewire" an edge. 118 */ 119 public WattsStrogatzGenerator(int n, int k, double beta) { 120 setUseInternalGraph(true); 121 122 if (n <= k) 123 throw new RuntimeException("parameter n must be >> k"); 124 if (beta < 0 || beta > 1) 125 throw new RuntimeException("parameter beta must be between 0 and 1"); 126 if (k % 2 != 0) 127 throw new RuntimeException("parameter k must be even"); 128 if (k < 2) 129 throw new RuntimeException("parameter k must be >= 2"); 130 131 this.n = n; 132 this.k = k; 133 this.beta = beta; 134 } 135 136 public void begin() { 137 double step = (2 * PI) / n; 138 double x = 0; 139 140 for (int i = 0; i < n; i++) { 141 addNode(nodeId(i), cos(x), sin(x)); 142 x += step; 143 } 144 145 // Add the circle links. 146 147 int kk = k / 2; 148 149 for (int i = 0; i < n; i++) { 150 for (int j = 1; j <= kk; j++) { 151 int jj = (i + j) % n; 152 addEdge(edgeId(i, jj), nodeId(i), nodeId(jj)); 153 } 154 } 155 156 current = 0; 157 } 158 159 public boolean nextEvents() { 160 int kk = k / 2; 161 162 if (current < n) { 163 for (int j = 1; j <= kk; j++) { 164 int jj = (current + j) % n; 165 166 if (random.nextDouble() < beta) { 167 delEdge(edgeId(current, jj)); 168 int newTarget = chooseNewNode(current, jj); 169 String edgeId = edgeId(current, newTarget); 170 171 if (internalGraph.getEdge(edgeId) == null) 172 addEdge(edgeId, nodeId(current), nodeId(newTarget)); 173 } 174 } 175 176 current += 1; 177 178 return true; 179 } else { 180 return false; 181 } 182 } 183 184 @Override 185 public void end() { 186 super.end(); 187 } 188 189 protected String nodeId(int id) { 190 return String.format("%d", id); 191 } 192 193 protected String edgeId(int from, int to) { 194 if (from > to) { 195 to += from; 196 from = to - from; 197 to -= from; 198 } 199 200 return String.format("%d_%d", from, to); 201 } 202 203 protected int chooseNewNode(int avoid, int old) { 204 int newId = 0; 205 boolean exists = true; 206 207 do { 208 newId = random.nextInt(n); 209 exists = internalGraph.getEdge(edgeId(avoid, newId)) != null; 210 } while (newId == avoid || exists); 211 212 return newId; 213 } 214}