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 java.util.ArrayList; 035import java.util.HashSet; 036import java.util.Set; 037 038/** 039 * Scale-free graph generator using the preferential attachment rule as defined 040 * in the Barabási-Albert model. 041 * 042 * <p> 043 * This is a very simple graph generator that generates a graph using the 044 * preferential attachment rule defined in the Barabási-Albert model: nodes are 045 * generated one by one, and each time attached by one or more edges other 046 * nodes. The other nodes are chosen using a biased random selection giving more 047 * chance to a node if it has a high degree. 048 * </p> 049 * 050 * <h2>Usage</h2> 051 * 052 * <p> 053 * The more this generator is iterated, the more nodes are generated. It can 054 * therefore generate graphs of any size. One node is generated at each call to 055 * {@link #nextEvents()}. At each node added at least one new edge is added. The 056 * number of edges added at each step is given by the 057 * {@link #getMaxLinksPerStep()}. However by default the generator creates a 058 * number of edges per new node chosen randomly between 1 and 059 * {@link #getMaxLinksPerStep()}. To have exactly this number of edges at each 060 * new node, use {@link #setExactlyMaxLinksPerStep(boolean)}. 061 * </p> 062 * 063 * <h2>Complexity</h2> 064 * 065 * For each new step, the algorithm act in O(n) with n the number of 066 * nodes if 1 max edge per new node is created, else the complexity 067 * is O(nm) if m max edge per new node is created. 068 * 069 * <h2>Example</h2> 070 * 071 * <pre> 072 * Graph graph = new SingleGraph("Barabàsi-Albert"); 073 * // Between 1 and 3 new links per node added. 074 * Generator gen = new BarabasiAlbertGenerator(3); 075 * // Generate 100 nodes: 076 * gen.addSink(graph); 077 * gen.begin(); 078 * for(int i=0; i<100; i++) { 079 * gen.nextEvents(); 080 * } 081 * gen.end(); 082 * graph.display(); 083 * </pre> 084 * 085 * @reference Albert-László Barabási & Réka Albert 086 * "Emergence of scaling in random networks", Science 286: 509–512. 087 * October 1999. doi:10.1126/science.286.5439.509. 088 */ 089public class BarabasiAlbertGenerator extends BaseGenerator { 090 /** 091 * Degree of each node. 092 */ 093 protected ArrayList<Integer> degrees; 094 095 /** 096 * The maximum number of links created when a new node is added. 097 */ 098 protected int maxLinksPerStep; 099 100 /** 101 * Does the generator generates exactly {@link #maxLinksPerStep}. 102 */ 103 protected boolean exactlyMaxLinksPerStep = false; 104 105 /** 106 * The sum of degrees of all nodes 107 */ 108 protected int sumDeg; 109 110 /** 111 * The sum of degrees of nodes not connected to the new node 112 */ 113 protected int sumDegRemaining; 114 115 /** 116 * Set of indices of nodes connected to the new node 117 */ 118 protected Set<Integer> connected; 119 120 /** 121 * New generator. 122 */ 123 public BarabasiAlbertGenerator() { 124 this(1, false); 125 } 126 127 public BarabasiAlbertGenerator(int maxLinksPerStep) { 128 this(maxLinksPerStep, false); 129 } 130 131 public BarabasiAlbertGenerator(int maxLinksPerStep, 132 boolean exactlyMaxLinksPerStep) { 133 this.directed = false; 134 this.maxLinksPerStep = maxLinksPerStep; 135 this.exactlyMaxLinksPerStep = exactlyMaxLinksPerStep; 136 } 137 138 /** 139 * Maximum number of edges created when a new node is added. 140 * 141 * @return The maximum number of links per step. 142 */ 143 public int getMaxLinksPerStep() { 144 return maxLinksPerStep; 145 } 146 147 /** 148 * True if the generator produce exactly {@link #getMaxLinksPerStep()}, else 149 * it produce a random number of links ranging between 1 and 150 * {@link #getMaxLinksPerStep()}. 151 * 152 * @return Does the generator generates exactly 153 * {@link #getMaxLinksPerStep()}. 154 */ 155 public boolean produceExactlyMaxLinkPerStep() { 156 return exactlyMaxLinksPerStep; 157 } 158 159 /** 160 * Set how many edge (maximum) to create for each new node added. 161 * 162 * @param max 163 * The new maximum, it must be strictly greater than zero. 164 */ 165 public void setMaxLinksPerStep(int max) { 166 maxLinksPerStep = max > 0 ? max : 1; 167 } 168 169 /** 170 * Set if the generator produce exactly {@link #getMaxLinksPerStep()} 171 * (true), else it produce a random number of links ranging between 1 and 172 * {@link #getMaxLinksPerStep()} (false). 173 * 174 * @param on 175 * Does the generator generates exactly 176 * {@link #getMaxLinksPerStep()}. 177 */ 178 public void setExactlyMaxLinksPerStep(boolean on) { 179 exactlyMaxLinksPerStep = on; 180 } 181 182 /** 183 * Start the generator. Two nodes connected by edge are added. 184 * 185 * @see org.graphstream.algorithm.generator.Generator#begin() 186 */ 187 public void begin() { 188 addNode("0"); 189 addNode("1"); 190 addEdge("0_1", "0", "1"); 191 degrees = new ArrayList<Integer>(); 192 degrees.add(1); 193 degrees.add(1); 194 sumDeg = 2; 195 connected = new HashSet<Integer>(); 196 } 197 198 /** 199 * Step of the generator. Add a node and try to connect it with some others. 200 * 201 * The number of links is randomly chosen between 1 and the maximum number 202 * of links per step specified in {@link #setMaxLinksPerStep(int)}. 203 * 204 * The complexity of this method is O(n) with n the number of nodes if the 205 * number of edges created per new node is 1, else it is O(nm) with m the 206 * number of edges generated per node. 207 * 208 * @see org.graphstream.algorithm.generator.Generator#nextEvents() 209 */ 210 public boolean nextEvents() { 211 // Generate a new node. 212 int nodeCount = degrees.size(); 213 String newId = nodeCount + ""; 214 addNode(newId); 215 216 // Attach to how many existing nodes? 217 int n = maxLinksPerStep; 218 if (!exactlyMaxLinksPerStep) 219 n = random.nextInt(n) + 1; 220 n = Math.min(n, nodeCount); 221 222 // Choose the nodes to attach to. 223 sumDegRemaining = sumDeg; 224 for (int i = 0; i < n; i++) 225 chooseAnotherNode(); 226 227 for (int i : connected) { 228 addEdge(newId + "_" + i, newId, i + ""); 229 degrees.set(i, degrees.get(i) + 1); 230 } 231 connected.clear(); 232 degrees.add(n); 233 sumDeg += 2 * n; 234 235 // It is always possible to add an element. 236 return true; 237 } 238 239 /** 240 * Choose randomly one of the remaining nodes 241 */ 242 protected void chooseAnotherNode() { 243 int r = random.nextInt(sumDegRemaining); 244 int runningSum = 0; 245 int i = 0; 246 while (runningSum <= r) { 247 if (!connected.contains(i)) 248 runningSum += degrees.get(i); 249 i++; 250 } 251 i--; 252 connected.add(i); 253 sumDegRemaining -= degrees.get(i); 254 } 255 256 257 /** 258 * Clean degrees. 259 * 260 * @see org.graphstream.algorithm.generator.Generator#end() 261 */ 262 @Override 263 public void end() { 264 degrees.clear(); 265 degrees = null; 266 connected = null; 267 super.end(); 268 } 269}