3 Copyright (c) The Trustees of Indiana University
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)
9 Authors: Douglas Gregor
13 <Title>Boost Graph Library: Power Law Out Degree (PLOD) Generator
</Title>
14 <script language=
"JavaScript" type=
"text/JavaScript">
16 function address(host, user) {
18 var thingy = user+atchar+host;
19 thingy = '<a hre' + 'f=' + "mai" + "lto:" + thingy + '>' + user+atchar+host + '</a>';
20 document.write(thingy);
26 <BODY BGCOLOR=
"#ffffff" LINK=
"#0000ee" TEXT=
"#000000" VLINK=
"#551a8b"
28 <IMG SRC=
"../../../boost.png"
29 ALT=
"C++ Boost" width=
"277" height=
"86">
31 <tt>plod_iterator
</tt>
36 template
<typename RandomGenerator, typename Graph
>
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;
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;
59 <p> This class template implements a generator for scale-free graphs
60 using the Power Law Out Degree (PLOD) algorithm
61 [
<a href=
"bibliography.html#palmer2000">63</a>], suitable for
63 href=
"adjacency_list.html"><tt>adjacency_list
</tt></a> or other graph
64 structure with iterator-based initialization. A scale-free graph
65 typically has a very skewed degree distribution, where few vertices
66 have a very high degree and a large number of vertices have a very
67 small degree. Many naturally evolving networks, such as the World
68 Wide Web, are scale-free graphs, making these graphs a good model for
69 certain networking problems.
</p>
71 <p>The Power Law Out Degree (PLOD) algorithm generates a scale-free
72 graph from three parameters,
<em>n
</em>,
<em>alpha
</em>, and
73 <em>beta
</em>, by allocating a certain number of degree
"credits" to
74 each vertex, drawn from a power-law distribution. It then creates
75 edges between vertices, deducting a credit from each involved vertex
76 (in the undirected case) or the source vertex (in the directed
77 case). 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
79 between
0 and
<em>n-
1</em>. The value of
<em>beta
</em> controls the
80 y-intercept of the curve, so that increasing
<em>beta
</em> increases
81 the average degree of vertices. The value of
<em>alpha
</em> controls
82 how steeply the curve drops off, with larger values indicating a
83 steeper curve. The web graph, for instance, has
<em>alpha ~
86 <h3>Where Defined
</h3>
88 <a href=
"../../../boost/graph/plod_generator.hpp"><tt>boost/graph/plod_generator.hpp
</tt></a>
92 <a name=
"default-constructor"/>
93 <pre>plod_iterator();
</pre>
95 Constructs a past-the-end iterator.
99 plod_iterator(RandomGenerator
& gen, vertices_size_type n,
100 double alpha, double beta, bool allow_self_loops = false);
103 Constructs a PLOD generator iterator that creates a
104 graph with
<tt>n
</tt> vertices. Probabilities are drawn from the
105 random number generator
<tt>gen
</tt>. Self-loops are permitted only
106 when
<tt>allow_self_loops
</tt> is
<tt>true
</tt>.
112 #include
<boost/graph/adjacency_list.hpp
>
113 #include
<boost/graph/plod_generator.hpp
>
114 #include
<boost/random/linear_congruential.hpp
>
116 typedef boost::adjacency_list
<> Graph;
117 typedef boost::plod_iterator
<boost::minstd_rand, Graph
> SFGen;
121 boost::minstd_rand gen;
122 // Create graph with
100 nodes
123 Graph g(SFGen(gen,
100,
2.5,
1000), SFGen(),
100);
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=
"http://www.osl.iu.edu/~lums">Andrew Lumsdaine
</A>,
135 Indiana University (
<script language=
"Javascript">address(
"osl.iu.edu",
"lums")
</script>)