|
|
Boost-Commit : |
From: asutton_at_[hidden]
Date: 2007-08-01 10:44:27
Author: asutton
Date: 2007-08-01 10:44:25 EDT (Wed, 01 Aug 2007)
New Revision: 38336
URL: http://svn.boost.org/trac/boost/changeset/38336
Log:
Rewrote degree distribution docs as degree centrality
Added:
sandbox/SOC/2007/graphs/libs/graph/doc/concepts/degree_measure.qbk (contents, props changed)
sandbox/SOC/2007/graphs/libs/graph/doc/reference/degree_centrality.qbk
- copied, changed from r38332, /sandbox/SOC/2007/graphs/libs/graph/doc/reference/distributions.qbk
Removed:
sandbox/SOC/2007/graphs/libs/graph/doc/reference/distributions.qbk
Text files modified:
sandbox/SOC/2007/graphs/libs/graph/doc/boost_concepts.qbk | 3
sandbox/SOC/2007/graphs/libs/graph/doc/concepts/distance_measure.qbk | 8 +
sandbox/SOC/2007/graphs/libs/graph/doc/concepts/utility.qbk | 1
sandbox/SOC/2007/graphs/libs/graph/doc/reference/degree_centrality.qbk | 213 +++++++++++++++------------------------
sandbox/SOC/2007/graphs/libs/graph/doc/reference/mean_geodesic.qbk | 2
sandbox/SOC/2007/graphs/libs/graph/doc/reference/reference.qbk | 2
6 files changed, 91 insertions(+), 138 deletions(-)
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/boost_concepts.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/boost_concepts.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/boost_concepts.qbk 2007-08-01 10:44:25 EDT (Wed, 01 Aug 2007)
@@ -12,12 +12,10 @@
[template BoostMultiPassInputIterator[] [@http://www.boost.org/libs/utility/MultiPassInputIterator.html MultipPassInputIterator]]
-
[template BoostReadablePropertyMap[] [@http://www.boost.org/libs/property_map/ReadablePropertyMap.html ReadablePropertyMap]]
[template BoostWritablePropertyMap[] [@http://www.boost.org/libs/property_map/WritablePropertyMap.html WritablePropertyMap]]
[template BoostReadWritePropertyMap[] [@http://www.boost.org/libs/property_map/ReadWritePropertyMap.html ReadWritePropertyMap]]
-
[template BoostGraph[] [link boost_graph.concepts.graph_concepts.graph Graph]]
[template BoostIncidenceGraph[] [link boost_graph.concepts.graph_concepts.incidence_graph IncidenceGraph]]
[template BoostBidirectionalGraph[] [link boost_graph.concepts.graph_concepts.bidirectional_graph BidirectionalGraph]]
@@ -46,4 +44,5 @@
[template BoostNumericValue[] [link boost_graph.concepts.general_concepts.numeric_value [^NumericValue]]]
[template BoostPropertyMap[] [link boost_graph.concepts.general_concepts.property_map [^PropertyMap]]]
[template BoostPropertyMatrix[] [link boost_graph.concepts.general_concepts.property_matrix [^PropertyMatrix]]]
+[template BoostDegreeMeasure[] [link boost_graph.concepts.general_concepts.degree_measure [^DegreeMeasure]]]
[template BoostDistanceMeasure[] [link boost_graph.concepts.general_concepts.distance_measure [^DistanceMeasure]]]
Added: sandbox/SOC/2007/graphs/libs/graph/doc/concepts/degree_measure.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/concepts/degree_measure.qbk 2007-08-01 10:44:25 EDT (Wed, 01 Aug 2007)
@@ -0,0 +1,51 @@
+[/
+ / Copyright (c) 2007 Andrew Sutton
+ /
+ / Distributed under 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)
+ /]
+
+[section Degree Measure]
+The [BoostDegreeMeasure] concept defines requirements for function objects
+that are used in computations on the degree of a vertex.
+
+[heading Notation]
+The following expressions are used within this document:
+[table
+ [[Expression] [Description]]
+ [[M] [A type modeling the [BoostDegreeMeasure] concept.]]
+ [[m] [An object of type `M`.]]
+ [[G] [A type modeling the [BoostGraph] concept.]]
+ [[g] [An object of type `G`.]]
+ [[v] [An object of type `graph_traits<G>::vertex_descriptor`.]]
+]
+
+[heading Associated Types]
+[table
+ [[Name] [Type] [Description]]
+ [
+ [Degree Type]
+ [`M::degree_type`]
+ [
+ The result type of the computation. Note that unlike
+ `graph_traits<G>::degree_size_type`, the `degree_type` is not
+ required to be numerice.
+ ]
+ ]
+]
+
+[heading Expressions]
+[table
+ [[Name] [Expression] [Result Type] [Description]]
+ [
+ [Function Call]
+ [`m(v, g)`]
+ [`M::degree_type`]
+ [
+ Invoke the measure on the vertex `v`, with respect
+ to the graph `g`. This returns the result as type `degree_type`.
+ ]
+ ]
+]
+
+[endsect]
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/concepts/distance_measure.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/concepts/distance_measure.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/concepts/distance_measure.qbk 2007-08-01 10:44:25 EDT (Wed, 01 Aug 2007)
@@ -16,7 +16,8 @@
[[M] [A type modeling the [BoostDistanceMeasure] concept.]]
[[m] [An object of type `M`.]]
[[d] [An object of type `M::distance_type`.]]
- [[g] [An object whose type models the [BoostGraph] concept.]]
+ [[G] [A type modeling the [BoostGraph] concept.]]
+ [[g] [An object of type `G`.]]
]
[heading Associated Types]
@@ -26,7 +27,10 @@
[Distance Type]
[`M::distance_type`]
[
- The type used to measure distances in graphs.
+ The type used to measure distances in graphs. The `distance_type`
+ is typically derived from the value type of a distance map or
+ the edge-weight type of a graph type `G`. However, this is not
+ required.
*Requirements:* The `distance_type` must be a model of the
[BoostNumericValue] concept.
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/concepts/utility.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/concepts/utility.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/concepts/utility.qbk 2007-08-01 10:44:25 EDT (Wed, 01 Aug 2007)
@@ -13,6 +13,7 @@
[include numeric_value.qbk]
[include property_map.qbk]
[include property_matrix.qbk]
+[include degree_measure.qbk]
[include distance_measure.qbk]
[endsect]
Copied: sandbox/SOC/2007/graphs/libs/graph/doc/reference/degree_centrality.qbk (from r38332, /sandbox/SOC/2007/graphs/libs/graph/doc/reference/distributions.qbk)
==============================================================================
--- /sandbox/SOC/2007/graphs/libs/graph/doc/reference/distributions.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/reference/degree_centrality.qbk 2007-08-01 10:44:25 EDT (Wed, 01 Aug 2007)
@@ -5,166 +5,115 @@
/ file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
/]
-[section Degree Distributions]
+[section Degree Centrality]
- template <typename Graph, typename Histogram>
- void degree_histogram(
- const Graph& _graph,
- Histogram& _histogram = ``['nothing]``,
- Histogram& _out_histogram = ``['nothing]``,
- Histogram& _in_histogram = ``['nothing]``)
-
-The degree histogram function computes /histograms/ of the degrees
-of vertices in a graph. A histogram is table that records the frequency
-of occurence of some event. With regards to this function, the computed
-histograms record the occurence of each degree of vertices in the graph.
-
-Specifically, each `_histogram` parameter describes a sequence of possible
-vertex-degrees in the graph and his size \[0, /max{degree(v,g)} + 1}\] where
-/max{degree(v,g)}/ is the maximum degree of any vertex in `_graph`. In this
-sequence, the ['i[super th]] element corresponds to the number of vertices
-in `_graph` with degree /i/.
-
-[figure
- images/reference/distributions_undirected.png
- [*Figure 1.] A simple undirected graph.
-]
-
-Consider the example in Figure 1. The assignment of frequencies (number of
-vertices with degree /i/) in the histogram will be:
-
- _histogram[0] == 0;
- _histogram[1] == 1; // vertex 0
- _histogram[2] == 0;
- _histogram[3] == 5; // vertices 1, 2, 3, 4, 5
-
-For directed graphs, it is also possible to compute histograms for both the in-
-and out-degrees of the vertices of a graph.
-
-[figure
- images/reference/distributions_directed.png
- [*Figure 2.] A simple directed graph.
-]
-
-For Figure 2, the in- and out-degree distributions will be:
-
- _in_histogram[0] == 1; _out_histogram[0] == 0;
- _in_histogram[1] == 2; _out_histogram[1] == 4;
- _in_histogram[2] == 3; _out_histogram[2] == 2;
-
-Note that the cumulative degree histogram for an directed graph is the
-same as it would be if we treated edges as undirected. The cumulative
-histogram for the graph in Figure 2 is:
-
- _histogram[0] == 1;
- _histogram[0] == 0;
- _histogram[0] == 5;
-
-Note that computing the in- or -out degree for an undirected graph will yield
-the same histogram as the cumulative.
-
-[note
-The /histogram/ is different than a /distribution/, which is commonly used as a
-synonym for /probability distribution/. The probability of a histogram
-can be computed by dividing each element of the `_histogram` by the number
-of vertices in the graph.
-]
+ template <typename Graph, typename CentralityMap>
+ void degree_centrality(const Graph& g, CentralityMap cent)
-In both of these functions, the computation of histograms depends on the
-parameters passed to the function. For example, if called as:
+ template <typename Graph, typename CentralityMap, typename Measure>
+ void degree_centrality(const Graph& g, CentralityMap cent, Measure measure)
- degree_distribution(g, _histogram = hist, _in_histogram = in_hist);
-
-The algorithm will compute both the degree histogram and in-degree histogram,
-but not the out-degree histogram. If not arguments are supplied, the algorithm
-performs no computations (but does so in linear time).
+ template <typename Graph>
+ typename graph_traits<Graph>::degree_size_type
+ vertex_degree_centrality(const Graph& g,
+ typename graph_traits<Graph>::vertex_descriptor v)
+
+ template <typename Graph, typename Measure>
+ typename Measure::degree_type
+ vertex_degree_centrality(const Graph& g,
+ typename graph_traits<Graph>::vertex_descriptor v,
+ Measure measure)
+
+The /degree centrality/ measure is used in social network analysis to help
+determine which vertices (or more specifically actors) are the most central
+or important to the network. Degree centrality is computed over the number of
+connections that a vertex has. For undirected graphs, the degree centrality of
+a vertex is typically equivalent to its degree. For directed graphs the out-degree
+is measured for its degree centrality.
+
+There are related two interpretations of degree centrality for directed graphs.
+When this measure is computed over the out-degree of a vertex, the measure is
+sometimes called /influence/. When the in-degree is considered, the measure is
+called /prestige/.
+
+This module provides two generic functions for measuring degree centrality.
+The first function, `degree_centrality()` computes this measure for each vertex
+in the graph, assigning the values to an output property map.
+
+The second funtion, `vertex_degree_centrality()` computes this measure for
+a single vertex, returning the value to the caller.
+
+These functions can be specialized throught the use of alternate /measure/
+functors. These funtors are called to actually compute the degree centraltiy
+of a vertex. For exmaple, it is possible to redefine the detault notion of
+degree centrality for a directed graph to return /prestige/ instead of /influence/.
[heading Where Defined]
-`boost/graph/degree_distribution.hpp`
+`boost/graph/degree_centrality.hpp`
[heading Parameters]
[table
[[Type] [Parameter] [Description]]
[
- [required, in] [`const Graph& _graph`]
+ [required, in] [`const Graph& graph`]
[
- The graph object for which the distribution will be computed. If
- the `_distribution` or `_in_distribution` arguments are supplied
- when calling this function then `_graph` must be a model of
- [BoostBidirectionalGraph]. If only `_out_distribution` is supplied,
- then `_graph` must be a model of [BoostIncidenceGraph].
+ The graph object for which the degree centralities will be computed.
+
+ *Requirements:* The `Graph` type must be a model of the
+ [BoostIncidenceGraph] concept.
]
]
[
- [optional, out]
+ [required, in] [`vertex_descriptor v`]
[
- Histogram& `_histogram`
-
- Histogram& `_out_histogram`
-
- Histogram& `_in_histogram`
+ The vertex descriptor for which the degree centrality is computed.
]
+ ]
+ [
+ [required, out] [`CentralityMap cent`]
[
- The distribution parameters maps instances of vertex degree to the
- number of observed vertices in the graph with that degree.
+ The property map that contains the degree centralities of all vertices
+ in a graph after calling the `degree_centrality()` function.
- These parameters must model both the [SgiSequence] and
- [SgiRandomAccessContainer] concepts (e.g., `std::vector`). The index type of the
- distribution must be the same as `degree_size_type`. The `value_type` must
- be integral (preferably unsigned).
+ *Requirements:* The `CentralityMap` type must be a model of the
+ [BoostWritablePropertyMap] concept. The `key_type` of the map must
+ be the same as the `vertex_descriptor` of the `Graph` type. If the
+ `measure` parameter is given in the call, then the `value_type`
+ of `CentralityMap` must be the same as `Measure::degree_type`.
+ Otherwise, the `value_type` must be the same as the `degree_size_type`
+ of the graph.
+ ]
+ ]
+ [
+ [optional, in] [`Measure measure`]
+ [
+ The `measure` parameter allows the caller to override the default
+ computation of degree centrality for a vertex.
- If not supplied, these parameters assume the default value of `not_given`,
- implying that no computation is performed.
+ *Requirements:* The `Measure` type must be a model of the
+ [BoostDegreeMeasure] concept. The `degree_type` of `Measure` must
+ be the same as the `value_type` of the `CentralityMap` type.
]
]
]
[h5 Return Value]
-This function does not return a value.
+The `vertex_degree_centrality()` function returns the centrality of a vertex.
+If no `measure` parameter is given, the return type is the same as the
+`degree_size_type` of the `Graph`. Otherwise, it is the `degree_type` of
+the `Measure`.
[h5 Complexity]
-The time complexity of all these functions is /O(V)/.
-
-[h5 Notes]
-Because a graph may be a multigraph, there is no determinable upper bound on the
-size of the histogram parameters. As such they are required to be dynamically resized
-during the execution of the algorithm.
-
-The recommended type for the distribution parameters is:
-
- std::vector<graph_traits<Graph>::degree_size_type>
-
-Note that if `dist` is the name of the output distribution after a call to
-`degree_distribution()` then the maximum degree is `dist.size() - 1`. The
-minimum degree corresponds to the index in `dist` with the first non-zero value.
-
-[h5 Examples]
-[note
- Expand these a bit... Perhaps show computations based on the previous.
-]
-
-The first example show how to compute and print the degree distribution.
-
- undirected_graph<> g;
- // add vertices and edges to g
-
- std::vector<size_t> dist;
- degree_distribution(g, dist);
- copy(dist.begin(), dist.end(), ostream_iterator<size_t>(cout, " "));
-
-The following example shows how to access the vertex (or vertices) with the maximum
-degree by using the `degree_histogram()` algorithm. This prints the index of that
-vertex.
-
- undirected_graph<> g;
- // add vertice and edges to g
+The default measure is a constant-time function. Replacing the default measure
+with a non-constant-time function will affect the complexity of the computations.
- typedef graph_traits<undirected_graph<> >::vertex_descriptor vertex_type;
- typedef std::vector<vertex_type> vertex_vector;
+The `degree_centrality()` function is ['O(n * O(measure))]. This is linear by
+default.
- std::vector<vertex_vector> hist;
- degree_histogram(g, hist);
- cout << get_vertex_index(hist.back().back()) << "\n";
+The `vertex_degree_centrality()` is ['O(O(measure))]. This is constant by
+default.
+[heading Example]
+Write an example.
[endsect]
\ No newline at end of file
Deleted: sandbox/SOC/2007/graphs/libs/graph/doc/reference/distributions.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/reference/distributions.qbk 2007-08-01 10:44:25 EDT (Wed, 01 Aug 2007)
+++ (empty file)
@@ -1,170 +0,0 @@
-[/
- / Copyright (c) 2007 Andrew Sutton
- /
- / Distributed under 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)
- /]
-
-[section Degree Distributions]
-
- template <typename Graph, typename Histogram>
- void degree_histogram(
- const Graph& _graph,
- Histogram& _histogram = ``['nothing]``,
- Histogram& _out_histogram = ``['nothing]``,
- Histogram& _in_histogram = ``['nothing]``)
-
-The degree histogram function computes /histograms/ of the degrees
-of vertices in a graph. A histogram is table that records the frequency
-of occurence of some event. With regards to this function, the computed
-histograms record the occurence of each degree of vertices in the graph.
-
-Specifically, each `_histogram` parameter describes a sequence of possible
-vertex-degrees in the graph and his size \[0, /max{degree(v,g)} + 1}\] where
-/max{degree(v,g)}/ is the maximum degree of any vertex in `_graph`. In this
-sequence, the ['i[super th]] element corresponds to the number of vertices
-in `_graph` with degree /i/.
-
-[figure
- images/reference/distributions_undirected.png
- [*Figure 1.] A simple undirected graph.
-]
-
-Consider the example in Figure 1. The assignment of frequencies (number of
-vertices with degree /i/) in the histogram will be:
-
- _histogram[0] == 0;
- _histogram[1] == 1; // vertex 0
- _histogram[2] == 0;
- _histogram[3] == 5; // vertices 1, 2, 3, 4, 5
-
-For directed graphs, it is also possible to compute histograms for both the in-
-and out-degrees of the vertices of a graph.
-
-[figure
- images/reference/distributions_directed.png
- [*Figure 2.] A simple directed graph.
-]
-
-For Figure 2, the in- and out-degree distributions will be:
-
- _in_histogram[0] == 1; _out_histogram[0] == 0;
- _in_histogram[1] == 2; _out_histogram[1] == 4;
- _in_histogram[2] == 3; _out_histogram[2] == 2;
-
-Note that the cumulative degree histogram for an directed graph is the
-same as it would be if we treated edges as undirected. The cumulative
-histogram for the graph in Figure 2 is:
-
- _histogram[0] == 1;
- _histogram[0] == 0;
- _histogram[0] == 5;
-
-Note that computing the in- or -out degree for an undirected graph will yield
-the same histogram as the cumulative.
-
-[note
-The /histogram/ is different than a /distribution/, which is commonly used as a
-synonym for /probability distribution/. The probability of a histogram
-can be computed by dividing each element of the `_histogram` by the number
-of vertices in the graph.
-]
-
-In both of these functions, the computation of histograms depends on the
-parameters passed to the function. For example, if called as:
-
- degree_distribution(g, _histogram = hist, _in_histogram = in_hist);
-
-The algorithm will compute both the degree histogram and in-degree histogram,
-but not the out-degree histogram. If not arguments are supplied, the algorithm
-performs no computations (but does so in linear time).
-
-[heading Where Defined]
-`boost/graph/degree_distribution.hpp`
-
-[heading Parameters]
-[table
- [[Type] [Parameter] [Description]]
- [
- [required, in] [`const Graph& _graph`]
- [
- The graph object for which the distribution will be computed. If
- the `_distribution` or `_in_distribution` arguments are supplied
- when calling this function then `_graph` must be a model of
- [BoostBidirectionalGraph]. If only `_out_distribution` is supplied,
- then `_graph` must be a model of [BoostIncidenceGraph].
- ]
- ]
- [
- [optional, out]
- [
- Histogram& `_histogram`
-
- Histogram& `_out_histogram`
-
- Histogram& `_in_histogram`
- ]
- [
- The distribution parameters maps instances of vertex degree to the
- number of observed vertices in the graph with that degree.
-
- These parameters must model both the [SgiSequence] and
- [SgiRandomAccessContainer] concepts (e.g., `std::vector`). The index type of the
- distribution must be the same as `degree_size_type`. The `value_type` must
- be integral (preferably unsigned).
-
- If not supplied, these parameters assume the default value of `not_given`,
- implying that no computation is performed.
- ]
- ]
-]
-
-[h5 Return Value]
-This function does not return a value.
-
-[h5 Complexity]
-The time complexity of all these functions is /O(V)/.
-
-[h5 Notes]
-Because a graph may be a multigraph, there is no determinable upper bound on the
-size of the histogram parameters. As such they are required to be dynamically resized
-during the execution of the algorithm.
-
-The recommended type for the distribution parameters is:
-
- std::vector<graph_traits<Graph>::degree_size_type>
-
-Note that if `dist` is the name of the output distribution after a call to
-`degree_distribution()` then the maximum degree is `dist.size() - 1`. The
-minimum degree corresponds to the index in `dist` with the first non-zero value.
-
-[h5 Examples]
-[note
- Expand these a bit... Perhaps show computations based on the previous.
-]
-
-The first example show how to compute and print the degree distribution.
-
- undirected_graph<> g;
- // add vertices and edges to g
-
- std::vector<size_t> dist;
- degree_distribution(g, dist);
- copy(dist.begin(), dist.end(), ostream_iterator<size_t>(cout, " "));
-
-The following example shows how to access the vertex (or vertices) with the maximum
-degree by using the `degree_histogram()` algorithm. This prints the index of that
-vertex.
-
- undirected_graph<> g;
- // add vertice and edges to g
-
- typedef graph_traits<undirected_graph<> >::vertex_descriptor vertex_type;
- typedef std::vector<vertex_type> vertex_vector;
-
- std::vector<vertex_vector> hist;
- degree_histogram(g, hist);
- cout << get_vertex_index(hist.back().back()) << "\n";
-
-
-[endsect]
\ No newline at end of file
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/reference/mean_geodesic.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/reference/mean_geodesic.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/reference/mean_geodesic.qbk 2007-08-01 10:44:25 EDT (Wed, 01 Aug 2007)
@@ -107,7 +107,7 @@
for large graphs, this difference is negligible.
[heading Where Defined]
-`boost/graph/closeness_centrality.hpp`
+`boost/graph/mean_geodesic.hpp`
[heading Parameters]
[table
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/reference/reference.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/reference/reference.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/reference/reference.qbk 2007-08-01 10:44:25 EDT (Wed, 01 Aug 2007)
@@ -66,7 +66,7 @@
[endsect]
[section Graph Measures]
-[include distributions.qbk]
+[include degree_centrality.qbk]
[include closeness_centrality.qbk]
[include mean_geodesic.qbk]
[include eccentricity.qbk]
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk