1<HTML> 2<!-- 3 Copyright (c) The Trustees of Indiana University 4 5 Use, modification and distribution is subject to the Boost Software 6 License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at 7 http://www.boost.org/LICENSE_1_0.txt) 8 9 Authors: Douglas Gregor 10 Andrew Lumsdaine 11 --> 12<Head> 13 <Title>Boost Graph Library: Power Law Out Degree (PLOD) Generator</Title> 14<script language="JavaScript" type="text/JavaScript"> 15<!-- 16function address(host, user) { 17 var atchar = '@'; 18 var thingy = user+atchar+host; 19 thingy = '<a hre' + 'f=' + "mai" + "lto:" + thingy + '>' + user+atchar+host + '</a>'; 20 document.write(thingy); 21} 22//--> 23</script> 24</head> 25 26<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b" 27 ALINK="#ff0000"> 28<IMG SRC="../../../boost.png" 29 ALT="C++ Boost" width="277" height="86"> 30 31<tt>plod_iterator</tt> 32 33<br> 34 35<PRE> 36template<typename RandomGenerator, typename Graph> 37class plod_iterator 38{ 39public: 40 typedef std::input_iterator_tag iterator_category; 41 typedef std::pair<vertices_size_type, vertices_size_type> value_type; 42 typedef const value_type& reference; 43 typedef const value_type* pointer; 44 typedef void difference_type; 45 46 plod_iterator(); 47 plod_iterator(RandomGenerator& gen, vertices_size_type n, 48 double alpha, double beta, bool allow_self_loops = false); 49 // Iterator operations 50 reference operator*() const; 51 pointer operator->() const; 52 plod_iterator& operator++(); 53 plod_iterator operator++(int); 54 bool operator==(const plod_iterator& other) const; 55 bool operator!=(const plod_iterator& other) const; 56}; 57</PRE> 58 59<p> This class template implements a generator for scale-free graphs 60using the Power Law Out Degree (PLOD) algorithm 61 [<a href="bibliography.html#palmer2000">63</a>], suitable for 62initializing an <a 63href="adjacency_list.html"><tt>adjacency_list</tt></a> or other graph 64structure with iterator-based initialization. A scale-free graph 65typically has a very skewed degree distribution, where few vertices 66have a very high degree and a large number of vertices have a very 67small degree. Many naturally evolving networks, such as the World 68Wide Web, are scale-free graphs, making these graphs a good model for 69certain networking problems.</p> 70 71<p>The Power Law Out Degree (PLOD) algorithm generates a scale-free 72graph from three parameters, <em>n</em>, <em>alpha</em>, and 73<em>beta</em>, by allocating a certain number of degree "credits" to 74each vertex, drawn from a power-law distribution. It then creates 75edges between vertices, deducting a credit from each involved vertex 76(in the undirected case) or the source vertex (in the directed 77case). The number of credits assigned to a vertex is: 78<em>beta*x<sup>-alpha</sup></em>, where <em>x</em> is a random value 79between 0 and <em>n-1</em>. The value of <em>beta</em> controls the 80y-intercept of the curve, so that increasing <em>beta</em> increases 81the average degree of vertices. The value of <em>alpha</em> controls 82how steeply the curve drops off, with larger values indicating a 83steeper curve. The web graph, for instance, has <em>alpha ~ 842.72</em>.</p> 85 86<h3>Where Defined</h3> 87 88<a href="../../../boost/graph/plod_generator.hpp"><tt>boost/graph/plod_generator.hpp</tt></a> 89 90<h3>Constructors</h3> 91 92<a name="default-constructor"/> 93<pre>plod_iterator();</pre> 94<blockquote> 95Constructs a past-the-end iterator. 96</blockquote> 97 98<pre> 99plod_iterator(RandomGenerator& gen, vertices_size_type n, 100 double alpha, double beta, bool allow_self_loops = false); 101</pre> 102<blockquote> 103Constructs a PLOD generator iterator that creates a 104graph with <tt>n</tt> vertices. Probabilities are drawn from the 105random number generator <tt>gen</tt>. Self-loops are permitted only 106when <tt>allow_self_loops</tt> is <tt>true</tt>. 107</blockquote> 108 109<H3>Example</H3> 110 111<pre> 112#include <boost/graph/adjacency_list.hpp> 113#include <boost/graph/plod_generator.hpp> 114#include <boost/random/linear_congruential.hpp> 115 116typedef boost::adjacency_list<> Graph; 117typedef boost::plod_iterator<boost::minstd_rand, Graph> SFGen; 118 119int main() 120{ 121 boost::minstd_rand gen; 122 // Create graph with 100 nodes 123 Graph g(SFGen(gen, 100, 2.5, 1000), SFGen(), 100); 124 return 0; 125} 126</pre> 127 128<br> 129<HR> 130<TABLE> 131<TR valign=top> 132<TD nowrap>Copyright © 2005</TD><TD> 133<A HREF="http://www.boost.org/people/doug_gregor.html">Doug Gregor</A>, Indiana University (<script language="Javascript">address("cs.indiana.edu", "dgregor")</script>)<br> 134 <A HREF="https://homes.cs.washington.edu/~al75">Andrew Lumsdaine</A>, 135Indiana University (<script language="Javascript">address("osl.iu.edu", "lums")</script>) 136</TD></TR></TABLE> 137 138</BODY> 139</HTML> 140
