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