|
|
Boost-Commit : |
From: asutton_at_[hidden]
Date: 2007-08-15 10:32:39
Author: asutton
Date: 2007-08-15 10:32:37 EDT (Wed, 15 Aug 2007)
New Revision: 38677
URL: http://svn.boost.org/trac/boost/changeset/38677
Log:
Finished docs for eccentricity
Added docs for betweenness centrality
Added:
sandbox/SOC/2007/graphs/libs/graph/doc/reference/betweenness_centrality.qbk (contents, props changed)
Removed:
sandbox/SOC/2007/graphs/libs/graph/doc/reference/diameter.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/reference/radius.qbk
Text files modified:
sandbox/SOC/2007/graphs/libs/graph/doc/reference/closeness_centrality.qbk | 28 ++--
sandbox/SOC/2007/graphs/libs/graph/doc/reference/degree_centrality.qbk | 8
sandbox/SOC/2007/graphs/libs/graph/doc/reference/eccentricity.qbk | 208 +++++++++++++++++++++++++------
sandbox/SOC/2007/graphs/libs/graph/doc/reference/mean_geodesic.qbk | 259 +++++++++++++++++++++++++--------------
sandbox/SOC/2007/graphs/libs/graph/doc/reference/reference.qbk | 3
5 files changed, 345 insertions(+), 161 deletions(-)
Added: sandbox/SOC/2007/graphs/libs/graph/doc/reference/betweenness_centrality.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/reference/betweenness_centrality.qbk 2007-08-15 10:32:37 EDT (Wed, 15 Aug 2007)
@@ -0,0 +1,185 @@
+[/
+ / 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 Betweenness Centrality]
+
+ template<typename Graph, typename CentralityMap>
+ void
+ brandes_betweenness_centrality(const Graph& g, CentralityMap cm)
+
+ template<typename Graph, typename CentralityMap, typename EdgeCentralityMap>
+ void
+ brandes_betweenness_centrality(const Graph& g,
+ CentralityMap cm,
+ EdgeCentralityMap ecm)
+
+ // Named Parameter Interface
+ template<typename Graph, ...>
+ void brandes_betweenness_centrality(const Graph& g, ...);
+
+
+The /betweenness centrality/ measure is commonly used in network analysis to identify
+vertices (also called actors) that are lie many shortest paths between other vertices
+in a graph. Intuitively, vertices with high betweenness centrality act as "hubs" through
+which more information flows. The betweenness centrality of a vertex is given as
+
+[$images/eq/betweenness.png]
+
+Where ['[delta][sub st]] is the number of shortest paths between the vertices /s/ and
+/t/ and ['[delta][sub st](v)] is the number of shortest paths that pass through the
+vertex /v/. Note that the ratio inside the sum an be interpreted as the probability
+that /v/ lies on a shortest path between the vertices /s/ and /t/.
+
+This function can also consider the /edge betweenness centrality/, which is defined
+as, fro each edge, the betweenness centrality that was contribuetd to the targets
+of the edge. This is plural for undirected graphs. Like vertex betweenness, this
+measure can be used to determine the edges through which most shortest paths must
+pass.
+
+These functions measure the /absolute/ betweenness centrality for vertices. These
+values can be converted to /relative/ betweenness centrality by scaling each of
+the absolute values by:
+
+[$images/eq/relative_betweenness.png]
+
+Where /n/ is the number of vertices in the graph. Also, given the relative betwenness
+centrality, one can compute the /central point dominance/, which is a mueasure of the
+maximum betweenness of any point in the graph. For example, this value will be 0 for
+complete graphs and 1 for star graphs (where all paths cross a central vertex).
+The central point dominance of a graph is defined as:
+
+[$images/eq/central_point_dominance.png]
+
+This module provides a number of functions for computing both vertex and edge
+centrality and related measures.
+
+[heading Where Defined]
+`boost/graph/betweenness_centrality.hpp`
+
+[heading Parameters]
+[table
+ [[Type] [Parameter] [Description]]
+ [
+ [required, in] [`const Graph& g`]
+ [
+ The graph for which the betweenness centrality of vertices or edges
+ is being computed.
+
+ *Requirements:* The `Graph` type must be a model of the [BoostVertexListGraph]
+ and [BoostIncidenceGraph] concepts. If the `EdgeCentralityMap` parameter
+ is present, this parameter type must also model the [BoostEdgeListGraph].
+ ]
+ ]
+ [
+ [required, out] [`CentralityMap cm`]
+ [
+ The graph for which the betweenness centrality of vertices or edges
+ is being computed.
+
+ *Requirements:*
+ ]
+ ]
+ [
+ [required, in] [`DistanceMap dm`]
+ [
+ Given a vertex `v`, the `dm` parameter provides the length of the
+ shortest path between a vertex `u` and `v`. The vertex `u` is the
+ vertex for which the distance map was initially computed.
+
+ *Requirements:* `DistanceMap` must be a model of [BoostReadablePropertyMap].
+ The `key_type` of the distance map must be the same as the `vertex_descriptor`
+ of the `Graph` parameter. The `value_type` is required to be a model of
+ [BoostNumericValue].
+ ]
+ ]
+ [
+ [required, in] [`DistanceMatrixMap dm`]
+ [
+ Given vertices /u/ and /v/, the `dm` parameter provides the length
+ of the shortest path between the two vertices. Note that the
+ distance between a vertex and itself should be 0 (i.e., `dm[u][u] == 0`).
+
+ *Requirements:* `DistanceMatrixMap` must be a model of [BoostReadablePropertyMap].
+ The `key_type` of the distance matrixc must be the same as the `vertex_descriptor`
+ of the `Graph` parameter. The `value_type` must be a [BoostReadWritePropertyMap]
+ whose `key_type` is also the `vertex_descriptor` of the `Graph` and
+ whose `value_type` is a model of [BoostNumericValue].
+ ]
+ ]
+ [
+ [required, out] [`ClosenessMap cm`]
+ [
+ The cm parameter stores the output of the computed closeness (or
+ distance) for each vertex in `g`.
+
+ *Requirements:* The type of `close` must be model the [BoostWritablePropertyMap]
+ concepts. The `key_type` of the property map must be the same as the
+ `vertex_descriptor` of the `Graph`, and the `value_type` must be a model
+ of [BoostNumericValue].
+ ]
+ ]
+ [
+ [optional, in] [`Measure measure`]
+ [
+ The 'measure' parameter is an instance of a closeness measure that
+ performs the final operation (the reciprocal) for this computation.
+
+ *Requirements:* The `Measure` type must be a model of the [BoostDistanceMeasure]
+ concept. The `distance_type` must be the same type as the `value_type`
+ of the `DistanceMap` or `DistanceMatrixMap`. The `result_type` of the
+ `Measure` must model the [BoostNumericValue] concept.
+ ]
+ ]
+]
+
+[heading Return]
+The `vertex_closeness_centrality()` function returns the closeness of a vertex.
+If the source vertex is disconnected from any vertices in the graph, this value is 0.
+
+[heading Complexity]
+The `closenesss_centrality()` function returns in ['O(n[super 2]*O(M))] where /n/
+is the number of vertices in the graph and /M/ is the complexity of the given distance
+measure. This is ['O(n[super 2])] by default
+
+The `vertex_closeness_centrality()` function returns in ['O(n*O(M))]. This is
+linear by default.
+
+[heading Example (Closeness Centrality)]
+
+[heading Undocumented Functions]
+These functions are also part of the betweenness centrality module, but are not
+documented since they are more appropriately called using the named parameter
+interface.
+
+ template<typename Graph, typename CentralityMap, typename EdgeCentralityMap,
+ typename IncomingMap, typename DistanceMap, typename DependencyMap,
+ typename PathCountMap, typename VertexIndexMap>
+ void
+ brandes_betweenness_centrality(const Graph& g,
+ CentralityMap centrality,
+ EdgeCentralityMap edge_centrality,
+ IncomingMap incoming,
+ DistanceMap distance,
+ DependencyMap dependency,
+ PathCountMap path_count,
+ VertexIndexMap vertex_index)
+
+ template<typename Graph, typename CentralityMap, typename EdgeCentralityMap,
+ typename IncomingMap, typename DistanceMap, typename DependencyMap,
+ typename PathCountMap, typename VertexIndexMap, typename WeightMap>
+ void
+ brandes_betweenness_centrality(const Graph& g,
+ CentralityMap centrality,
+ EdgeCentralityMap edge_centrality,
+ IncomingMap incoming,
+ DistanceMap distance,
+ DependencyMap dependency,
+ PathCountMap path_count,
+ VertexIndexMap vertex_index,
+ WeightMap weight_map)
+
+[endsect]
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/reference/closeness_centrality.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/reference/closeness_centrality.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/reference/closeness_centrality.qbk 2007-08-15 10:32:37 EDT (Wed, 15 Aug 2007)
@@ -34,11 +34,12 @@
actors that are "closer" to all others have a greater reach, making them more
influential in the network. The closeness measure is defined as the inverse of the
sum of all geodesic distances (lengths of shortest path) from one vertex to all
-others. Closeness is formally given as:
+others (excluding itself). Closeness is computed as:
[$images/eq/closeness.png]
-Where /d(u,v)/ is the shortest path (geodesic distance) from /u/ to /v/.
+Where /d(u,v)/ is the shortest path (geodesic distance) from /u/ to /v/. Note that
+the distance of /(u,u)/ is neither
Note that if any vertex in the graph is unreachable from any other, then distance
between those two unonnected vertices is infinite. This imlplies that the closeness
of that vertex is zero. If an undirected graph has unconnected components, then
@@ -202,18 +203,17 @@
First, we define the graph and its associated types.
[social_network_types]
-Here, we use the `Actor` to store an actor name with each vertex. We also define a
-number of related property types.
+Here, we use the `Actor` to store an actor name with each vertex. We also need to
+define a number of related property types to support property maps for the algorithms
+called in the program.
-Since this program will call
-[boost_floyd_warshall_all_pairs_shortest_paths] to compute distances between
-vertices, we need a matrix to store the distances.
+Since this program will call [boost_floyd_warshall_all_pairs_shortest_paths] to
+compute distances between vertices, we need a matrix to store the distances.
[distance_matrix_types]
-We also need a property map
-that assigns weights to each edge. Since our graph is unweighted, we can use
-the [boost_constant_property_map] to return a constant value for each edge.
-[constant_weight_map_types]
+We also need a property map that assigns weights to each edge. Since our graph is
+unweighted, we can use the [boost_constant_property_map] to return a constant value
+for each edge. [constant_weight_map_types]
We also need an output property map to store the closeness centrality for each
vertex.
@@ -221,13 +221,11 @@
In the main program, we instantiate the graph and an extra `std::map` that we
use during graph construction.
-
[setup_social_network]
The graph is read from standard input. This process uses the `add_named_vertex()`
function, which is not part of the Boost.Graph library but defined in the file
`examples/helper.hpp`.
-
[build_social_network]
The next step is to compute the distance. This is done using the
@@ -243,7 +241,7 @@
the property maps for each vertex. This is done by constructing a container for
the closeness values and a property map accessor for it. The previously computed
distance map and closeness map are passed as inputs to the computation.
-[compute_closeness]
+[compute_closeness_centrality]
In the next step, we sort the vertices of the graph into the given vector. For
this sort, we use the values in the property map as the sort keys. The resulting
@@ -285,7 +283,7 @@
obtained by multiplying the default result by the number of vertices in the graph.
This example uses the following files:
-* [^examples/norm_closeness.hpp]
+* [^examples/norm_closeness_centrality.hpp]
* [^examples/social_network.hpp]
* [^examples/helper.hpp]
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/reference/degree_centrality.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/reference/degree_centrality.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/reference/degree_centrality.qbk 2007-08-15 10:32:37 EDT (Wed, 15 Aug 2007)
@@ -8,18 +8,18 @@
[section Degree Centrality]
template <typename Graph, typename CentralityMap>
- void degree_centrality(const Graph& g, CentralityMap cent);
+ void degree_centrality(const Graph& g, CentralityMap cent)
template <typename Graph, typename CentralityMap, typename Measure>
- void degree_centrality(const Graph& g, CentralityMap cent, Measure measure);
+ void degree_centrality(const Graph& g, CentralityMap cent, Measure measure)
template <typename Graph, typename Vertex>
typename graph_traits<Graph>::degree_size_type
- vertex_degree_centrality(const Graph& g, Vertex v);
+ vertex_degree_centrality(const Graph& g, Vertex v)
template <typename Graph, typename Vertex, typename Measure>
typename Measure::degree_type
- vertex_degree_centrality(const Graph& g, Vertex v, Measure measure);
+ vertex_degree_centrality(const Graph& g, Vertex 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
Deleted: sandbox/SOC/2007/graphs/libs/graph/doc/reference/diameter.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/reference/diameter.qbk 2007-08-15 10:32:37 EDT (Wed, 15 Aug 2007)
+++ (empty file)
@@ -1,62 +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 Diameter]
-
- template <typename Graph, typename EccentricityMap>
- typename property_traits<EccentricityMap>::value_type
- graph_diameter(const Graph& g, EccentricityMap ecc)
-
-The /diameter/ of a graph is the maximum /eccentricty/ of any vertex in the
-graph. This computes and returns that value using previously computed
-eccentricity values. Eccentricity values are typically computed using the
-[boost_eccentricity] functions.
-
-The diameter of a graph is also used to establish the graph's /periphery/ - the
-set of vertices having the same eccentricity as the graph diameter. This subset
-can be computed using the [boost_graph_periphery] functions.
-
-[heading Where Defined]
-`boost/graph/diameter.hpp`
-
-[heading Parameters]
-[table
- [[Type] [Parameter] [Description]]
- [
- [required, in] [`const Graph& g`]
- [
- The graph for which the eccentricity measures are being comptued.
-
- *Requirements:* The `Graph` type must be a model of the
- [BoostVertexListGraph] concepts.
- ]
- ]
- [
- [required, in] [`EccentricityMap ecc`]
- [
- The `ecc` property map associates an eccentricity value with every
- vertex in the graph.
-
- *Requirements:* `EccentricityMap` must be a model of [BoostReadablePropertyMap].
- The `key_type` of the distance map must be the same as the `vertex_descriptor`
- of the `Graph` parameter. The `value_type` must model the [SgiLessThanComparable]
- concept.
- ]
- ]
-]
-
-[heading Return Value]
-The `graph_diameter()` function returns the radius of the given graph with respect
-to the given eccentricity values.
-
-[heading Complexity]
-The `graph_diameter()` function is linear.
-
-[heading Examples]
-Write an example.
-
-[endsect]
\ No newline at end of file
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/reference/eccentricity.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/reference/eccentricity.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/reference/eccentricity.qbk 2007-08-15 10:32:37 EDT (Wed, 15 Aug 2007)
@@ -9,33 +9,69 @@
template <typename Graph, typename DistanceMap>
typename property_traits<DistanceMap>::value_type
- vertex_eccentricity(const Graph& g, GeodesicMap dist)
+ vertex_eccentricity(const Graph& g, DistanceMap dm)
- template <typename Graph, typename DistanceMatrix, typename EccentricityMap>
- void eccentricity(const Graph& g, const DistanceMatrix& dist, EccentricityMap ecc)
+ template <typename Graph, typename DistanceMatrixMap, typename EccentricityMap>
+ void eccentricity(const Graph& g, DistanceMatrixMap dm, EccentricityMap em)
-The /eccentricity/ of a vertex is the maximum geodesic distance to any other
-vertex in the graph. Intuitively, Vertices with low eccentricity can reach all
-other vertices in the graph more quickly than vertices with high eccentricity.
-Eccentricity values are used to help compute the [boost_graph_radius] and
-[boost_graph_diameter]. These values can be used in turn, to identify the
-[boost_gaph_center] and [boost_graph_periperhy] subgraphs.
-
-Note that for any vertex in a graph that is not connected to another, its
-eccentricity is defined to be infinite.
-
-This module provide two generic functions. The first function, `eccentricity()`
-computes this values for all vertices in the graph given a matrix that provides
-the shortest paths between all pairs of vertices. This matrix can be computed
-as the output of an all-pairs shortest paths algorithm (e.g.,
-[boost_floyd_warshall_all_pairs_shortest_paths]) or repeated application of a
-breadth-first search. The output of this function is stored in a property map.
+
+ template <typename Graph, typename EccentricityMap>
+ inline typename property_traits<EccentricityMap>::value_type
+ graph_radius(const Graph& g, EccentricityMap ecc)
+
+
+ template <typename Graph, typename EccentricityMap>
+ inline typename property_traits<EccentricityMap>::value_type
+ graph_diameter(const Graph& g, EccentricityMap ecc)
+
+ template <typename Graph, typename EccentricityMap>
+ inline std::pair<typename property_traits<EccentricityMap>::value_type,
+ typename property_traits<EccentricityMap>::value_type>
+ graph_radius_diameter(const Graph& g, EccentricityMap ecc)
+
+The /eccentricity/ of a vertex is the maximum geodesic distance (shortest path) from
+that vertex to any other vertex in the graph. Intuitively, vertices with low
+eccentricity can reach all other vertices in the graph more "quickly" than vertices
+with high eccentricity. Eccentricity values are used to help compute the /radius/ and
+/diameter/.
+
+Note that if vertex /u/ is disconnected from any other vertex /v/ the distance from
+/u/ to /v/ is infinite. This implies the eccentricity of /v/ is infinite as well.
+If any vertex in a graph has infinite eccentricity, the graph also has an infinite
+diameter.
+
+Consider the following social network represented by an undirected, unweighted
+graph.
+
+[figure
+ images/reference/social_network.png
+ *Figure 1.* A network of friends
+]
+
+Because the graph is small and relatively well, connected the eccentricies are
+exaclty 2 or 3 for all vertices. The radius (the smaller of these numbers)
+is 2, and the diameter is 3.
+
+This module provide a set of generic functions for computing eccentricities and
+related measures. The first function, `eccentricity()` computes this values for all
+vertices in the graph, given a matrix that provides the shortest paths between all
+pairs of vertices. This matrix can be computed as the output of an "all-pairs shortest
+paths "algorithm (e.g., [boost_floyd_warshall_all_pairs_shortest_paths]) or repeated
+application of a [boost_breadth_first_search] (if the graph is unweighted). The
+output of this function is stored in the eccentricity property map.
The second function, `vertex_eccentricity()` computes the eccentricty of a
single vertex given the shortest paths to every other vertex in the graph. The
-distance map can be computed using a shortest paths algorithms (e.g.,
-[boost_dijkstra_shortest_paths] or a breadth-first search. The output of this
-function is returned to the caller.
+distance map can be computed using a shortest paths algorithms (e.g., [boost_dijkstra_shortest_paths]
+or a [boost_breadth_first_search]. The output of this function is returned to the
+caller.
+
+This module also provides a set of functions for computing the related measures
+of a graph's radius and diameter. These functions take as input, the previously
+computed eccentricity values output by the `eccentricity()` function, and return
+the computed value to the caller. The `graph_radius_and_diameter()` function
+combines both computations to a single iteratation and returns the values as a
+pair. The `first` value in the pair is the radius and the `second` is the diameter.
[heading Where Defined]
`boost/graph/eccentricity.hpp`
@@ -53,12 +89,11 @@
]
]
[
- [required, in] [`DistanceMap dist`]
+ [required, in] [`DistanceMap dm`]
[
- Given a vertex `v`, the `dist` parameter provides the length of the
+ Given a vertex `v`, the `dm` parameter provides the length of the
shortest path between a vertex `u` and `v`. The vertex `u` is the
- vertex for which the distance map was initially computed. The
- distance from /u/ to itself should be zero (i.e., `dist[u] == 0`).
+ vertex for which the distance map was initially computed.
*Requirements:* `DistanceMap` must be a model of [BoostReadablePropertyMap].
The `key_type` of the distance map must be the same as the `vertex_descriptor`
@@ -67,28 +102,36 @@
]
]
[
- [required, in] [`const DistanceMatrix& dist`]
+ [required, in] [`DistanceMatrixMap dm`]
[
- Given vertices /u/ and /v/, the `dist` parameter provides the length
+ Given vertices /u/ and /v/, the `dm` parameter provides the length
of the shortest path between the two vertices. Note that the
- distance between a vertex and itself should be 0 (i.e., `dist[u][u] == 0`).
+ distance between a vertex and itself should be 0 (i.e., `dm[u][u] == 0`).
- *Requirements:* `DistanceMatrix` must be a model of [BoostPropertyMatrix].
- The `key_type` of the distance matrixc must be the same as the
- `vertex_descriptor` of the `Graph` parameter. The `value_type` is
- required to be a model of [BoostNumericValue].
+ *Requirements:* `DistanceMatrixMap` must be a model of [BoostReadablePropertyMap].
+ The `key_type` of the distance matrixc must be the same as the `vertex_descriptor`
+ of the `Graph` parameter. The `value_type` must be a [BoostReadWritePropertyMap]
+ whose `key_type` is also the `vertex_descriptor` of the `Graph` and
+ whose `value_type` is a model of [BoostNumericValue].
]
]
[
- [required, out] [`EccentricityMap ecc`]
+ [required, out] [`EccentricityMap em`]
[
- The `ecc` parameter stores the computed results of the `eccentricity()`
- function for each vertex in the graph.
-
- *Requirements:* The `EccentricityMap` type must be a model of the
- [BoostReadablePropertyMap] type. The `key_type` of the property map
- must be the `vertex_descriptor` of the `Graph`. The `value_type`
- must be the same as the `value_type` of the distance matrix.
+ When used with the `eccentricity()` function, the `em` parameter stores
+ the eccentricity of each vertex in the graph. When used with the
+ `radius()` or `diameter()` functions, `em` provides the input to compute
+ the given graph property.
+
+ [*Requirements - [^eccentricity()]:] The `EccentricityMap` must be a model
+ of the [BoostWritablePropertyMap] concept.
+
+ [*Requirements - [^graph_radius()]/[^graph_diameter()]:] The `EccentricityMap` must
+ be a model of the [BoostReadablePropertyMap] concept.
+
+ *Requirements:* The `key_type` of the property map must be the `vertex_descriptor`
+ of the `Graph` parameter. The `value_type` must be the same type as the
+ `value_type` of the `DistanceMatrixMap` parameter.
]
]
]
@@ -98,12 +141,89 @@
If the graph is unconnected, this returns the infinite value of the distance
map's `value_type`.
+The `graph_radius()` and `graph_diameter()` functions return their respective measures.
+The return type of these functions is the same as the `value_type` of the `EccentricityMap`
+parameter.
+
+The `graph_radius_diameter()` funtion returns a pair containing both the radius (`first`)
+and diameter (`second`) of the graph. The types of these values are the same as the
+`value_type` of the `EccentricityMap`.
+
[heading Complexity]
-The `eccentricity()` function has /O(n^2)/ time complexity.
+The `eccentricity()` function returns in ['O(n[super 2])] where /n/ is the number
+of vertices in the graph.
-The `vertex_eccentricity()` is linear.
+The `vertex_eccentricity()` is linear with respect to the number of vertices in
+the graph.
+
+The `graph_diameter()`, `graph_radius()`, and `graph_radius_diameter()` function are
+all linear with respect to the number of vertices in the graph.
[heading Examples]
-Write an example.
+This example computes the eccentricities for all vertices in a graph, and the radius
+and diameter of the graph itself. This example includes the following files:
+
+* [^examples/closeness_centrality.hpp]
+* [^examples/social_network.hpp]
+* [^examples/helper.hpp]
+
+First, we define the graph and its associated types.
+[social_network_types]
+Here, we use the `Actor` to store an actor name with each vertex. We also need to
+define a number of related property types to support property maps for the algorithms
+called in the program.
+
+Since this program will call [boost_floyd_warshall_all_pairs_shortest_paths] to
+compute distances between vertices, we need a matrix to store the distances.
+[distance_matrix_types]
+
+We also need a property map that assigns weights to each edge. Since our graph is
+unweighted, we can use the [boost_constant_property_map] to return a constant value
+for each edge. [constant_weight_map_types]
+
+We also need an output property map to store the eccentricities of each vertex.
+[eccentricity_map_types]
+
+In the main program, we instantiate the graph and an extra `std::map` that we
+use during graph construction.
+[setup_social_network]
+
+The graph is read from standard input. This process uses the `add_named_vertex()`
+function, which is not part of the Boost.Graph library but defined in the file
+`examples/helper.hpp`.
+[build_social_network]
+
+The next step is to compute the distance. This is done using the
+[boost_floyd_warshall_all_pairs_shortest_paths] function. This could also be done
+using [boost_johnson_all_pairs_shortest_paths]. This is done by first constructing
+a matrix to hold the distance values, and a property map over the matrix. Additionally,
+we use a [boost_constant_property_map] to return the value `1` for all edge weights.
+Both the distance matrix and edge-weight maps are used as inputs to the distance
+algorithm.
+[compute_constant_distances]
+
+After computing the distance, we can use the resulting distance matrix to compute
+the eccentricity of each vertex. This is done by constructing a container for
+the eccentricity values and a property map accessor for it. The previously computed
+distance map and eccentricity map are passed as inputs to the computation. The
+eccentricity map is also used as an input to the `graph_radius()` and `graph_diameter()`
+functions.
+[compute_eccentricity]
+
+If the input graph is large, it would be better to compute the radius and diameter
+in a single call. The last two lines above could be repaced with:
+
+ int radius, diameter;
+ tie(radius, diameter) = graph_radius_diameter(g, em);
+
+Finally, we can print the radius and diameter of the graph.
+[print_radius_diameter]
+
+If given the `social_network.graph` file as input, the output will be:
+
+[pre
+radius 2
+diameter 3
+]
[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-15 10:32:37 EDT (Wed, 15 Aug 2007)
@@ -7,106 +7,101 @@
[section Mean Geodesic]
- template <typename Graph, typename DistanceMatrix, typename GeodesicMap>
- void mean_geodesic(const Graph& g, const DistanceMatrix& dist, GeodesicMap geo)
+ template <typename Graph, typename DistanceMatrixMap, typename GeodesicMap>
+ void mean_geodesic(const Graph& g, DistanceMatrixMap dm, GeodesicMap gm)
- template <typename Graph,
- typename DistanceMatrix,
- typename GeodesicMap,
- typename Measure>
+ template <typename Graph, typename DistanceMatrixMap, typename GeodesicMap, typename Measure>
void mean_geodesic(const Graph& g,
- const DistanceMatrix& dist,
- ClosenessMap close,
- Measure measure)
+ DistanceMatrixMap dm,
+ GeodesicMap gm,
+ Measure m)
template <typename Graph, typename DistanceMap>
- float vertex_mean_geodesic(const Graph& g, DistanceMap dist)
+ float vertex_mean_geodesic(const Graph& g, DistanceMap dm)
template <typename ResultType, typename Graph, typename DistanceMap>
- ResultType vertex_mean_geodesic(const Graph& g, DistanceMap dist)
+ ResultType vertex_mean_geodesic(const Graph& g, DistanceMap dm)
template <typename Graph, typename DistanceMap, typename Measure>
typename Measure::result_type
- vertex_mean_geodesic(const Graph& g, DistanceMap dist, Measure measure)
+ vertex_mean_geodesic(const Graph& g, DistanceMap dm, Measure m)
template <typename Graph, typename GeodesicMap, typename Measure>
typename Measure::result_type
- graph_mean_geodesic(const Graph& g, GeodesicMap geo, Measure measure)
+ graph_mean_geodesic(const Graph& g, GeodesicMap gm, Measure m)
template <typename Graph, typename GeodesicMap>
typename property_traits<GeodesicMap>::value_type
- graph_mean_geodesic(const Graph& g, GeodesicMap geo)
+ graph_mean_geodesic(const Graph& g, GeodesicMap gm)
-The /mean geodesic distance/ measure is commonly used in large network analysis
-to quantify the /small world/ phenomonon. If the mean geodesic distance is small
-in relation to the graph (e.g., 6), then all vertices are (on average) only 6
-steps or hops away from any other. The mean geodesic distance of a vertex is
-computed over the shortest paths between vertices. Formally, it is given as:
+The /mean geodesic distance/ measure is used in large network analysis to identify
+central vertices and as a measure of the /small world phenomenon/. The mean geodesic
+distance of a vertex is defined as the average of geodesic distances from that
+vertex every /other/ vertex in the graph. It is computed as:
[$images/eq/mean_geodesic.png]
-Where /d(u,v)/ is the shortest path (geodesic distance) from /u/ to /v/.
-Note that if any vertex in the graph is unreachable from any other, then the
-graph is unconnected, and the distance between those two unonnected vertices
-is infinite. This imlplies that the closeness of every vertex in an unconnected
-(and undirected) graph is also infinite. This is not necessarily the case for
-directed graphs.
-
-The mean geodesic distance for the entire graph is essentially the average of
-mean geodesic distances of every vertex in the graph. There are alternative
-means of computing this average (e.g,. in the case of simple graphs), but
-differences in the results are negligible for large graphs. If any vertex has
-infinite mean geodesic distance, then the graph also has infinite mean geodesic
-distance.
-
-It is also important to note the relationship between /mean geodesic distance/,
-/farness/, and /closeness/. The /farness/ of a vertex is the sum of its goedesic
-distances to all other vertices (mean geodesic distances * number of vertices),
-and /closeness/ is the inverse of
+Where /d(u,v)/ is the shortest path (geodesic distance) from /u/ to /v/. Note
+that this excludes /d(u,u)/ from the average, even if /d(u,u)/ is non-zero, which
+is rare for social networks. Note that if any vertex in the graph is unreachable
+from any other, then the graph is unconnected, and the distance between those two
+unonnected vertices is infinite. This imlplies that the closeness of every vertex
+in an unconnected (and undirected) graph is also infinite. This is not necessarily
+the case for directed graphs.
+
+The mean geodesic distance is often used to quantify whether or not a graph exhibits
+the so-called small-world phenomenon. If the mean geodesic distance of a graph is
+small with respect to its density (the ratio of vertices to edges), then the graph
+is said to exhibit the small-world phenomenon. This implies that vertices are
+The mean geodesic distance of a graph is the average of the mean geodesics for
+each vertex. It is computed as:
+
+[$images/eq/graph_mean_geodesic.png]
+
+Note that computing the measure in this fashion means that the mean geodesic distance
+of the graph may lie outside the minimum and maximum mean geodesic distances of
+its vertices.
+
+Consider a social network of friends, which is represented by an undirected graph.
+
+[figure
+ images/reference/social_network.png
+ *Figure 1.* A network of friends.
+]
+
+In this network, Frank has the lowest mean geodesic distance with an average of
+1.375. Scott and Laurie have the second lowest distances with values of 1.5 and
+1.875 respectively.
This module defines a flexible framework for computing the mean geodesic distance
of vertices in a graph for previously computed geodesics by providing thrtee generic
functions. The first function, `mean_geodesic()` computes the average distance of
each vertex in a graph from a matrix containing the distances between vertices.
-This matrix can be computed as the output of an "all pairs shortest path" algorithm,
-or as the result of many breadth first searches (if the graph is unweighted).
+This matrix can be computed as the output of an "all pairs shortest path" algorithm
+(e.g., [boost_floyd_warshall_all_pairs_shortest_paths] or [boost_johnson_all_pairs_shortest_paths])
+or as the result repeated [boost_breadth_first_search]s (if the graph is unweighted).
The second function, `vertex_mean_geodesic()` can be used to compute the
closeness of a single vertex. This function requires a distance map that contains
the distance from one vertex (the source) to all others in the graph. This
-distance map can be computed as the result of a "shortest paths" algorithm or
-recording distances from a breadth-first search.
-
-The third function, `graph_mean_geodesic()` computes a single mean geodesic
-distance for the graph by averaging the mean geodesic distances of each vertex
-in the geodesic distance map. This average is computed differently for both
-directed and undirected graphs. For undirected graphs, the mean geodesic distance
-is computed as:
-
-[$images/eq/mean_geodesic_undirected.png]
-
-Intuitively, this is the average distance over all possible edges in the graph.
-For directed graphs the mean geodesic distance is computed as:
-
-[$images/eq/mean_geodesic_directed.png]
+distance map can be computed as the result of a "shortest paths" algorithm such
+as [boost_dijkstra_shortest_paths] or [boost_bellman_ford_shortest_paths]. If the
+graph is unweighted, distances can be recorded from a [boost_breadth_first_search].
+
+The third function, `graph_mean_geodesic()` computes the mean geodesic distance
+for the graph by averaging the mean geodesic distances of each vertex in the geodesic
+distance map. Note that this function does not compute the mean geodesic distances
+of each vertex. Those values must be computed by using one of the functions above.
This framework also allows for a specialization of measures used to compute
-these values. This framework employs two distinct measures. The first is used
-to compute the mean geodesic distance of a single vertex. By default this simply
-divides the sum of distances by the number of vertices. The second measure is
-used to compute the mean geodesic distance for the entire graph. This provides
-the factors in the algorithms given above.
-
-Note that for small graphs, the default choice of divisors in computations may
-seem inappropriate. For example, most simple networks preclude the possibility
-of self-loops and so the average can be computed over /n/ - 1 vertices. However,
-for large graphs, this difference is negligible.
+these values. The default measures used in this framework implement the formulas
+given above.
[heading Where Defined]
-`boost/graph/mean_geodesic.hpp`
+`boost/graph/geodesic_distance.hpp`
[heading Parameters]
[table
@@ -132,12 +127,11 @@
]
]
[
- [required, in] [`DistanceMap dist`]
+ [required, in] [`DistanceMap dm`]
[
- Given a vertex `v`, the `dist` parameter provides the length of the
+ Given a vertex `v`, the `dm` parameter provides the length of the
shortest path between a vertex `u` and `v`. The vertex `u` is the
- vertex for which the distance map was initially computed. The
- distance from /u/ to itself should be zero (i.e., `dist[u] == 0`).
+ vertex for which the distance map was initially computed.
*Requirements:* `DistanceMap` must be a model of [BoostReadablePropertyMap].
The `key_type` of the distance map must be the same as the `vertex_descriptor`
@@ -146,45 +140,47 @@
]
]
[
- [required, in] [`const DistanceMatrix dist`]
+ [required, in] [`DistanceMatrixMap dm`]
[
- Given vertices /u/ and /v/, the `dist` parameter provides the length
- of the shortest path between the two vertices. Note that the
- distance between a vertex and itself should be 0 (i.e., `dist[u][u] == 0`).
+ Given vertices /u/ and /v/, the `dm` parameter provides the length
+ of the shortest path between the two vertices.
- *Requirements:* `DistanceMatrix` must be a model of [BoostPropertyMatrix].
- The `key_type` of the distance matrixc must be the same as the
- `vertex_descriptor` of the `Graph` parameter. The `value_type` is
- required to be a model of [BoostNumericValue].
+ *Requirements:* `DistanceMatrixMap` must be a model of [BoostReadablePropertyMap].
+ The `key_type` of the distance matrixc must be the same as the `vertex_descriptor`
+ of the `Graph` parameter. The `value_type` must be a [BoostReadWritePropertyMap]
+ whose `key_type` is also the `vertex_descriptor` of the `Graph` and
+ whose `value_type` is a model of [BoostNumericValue].
]
]
[
- [required, both] [`GeodesicMap geo`]
+ [required, both] [`GeodesicMap gm`]
[
- When used with the `mean_geodesic()` function, the `geo` parameter stores
+ When used with the `mean_geodesic()` function, the `gm` parameter stores
the computed mean geodesic distances for each vertex pair in the matrix.
When used with the `graph_mean_geodesic()` function, the parameter provides
the input required to compute the mean distance for the graph.
- *Requirements:* As an input parameter, the `GeodesicMap` type is required
- to model the [BoostReadablePropertyMap] concept. As an output parameter,
- it is required to model the [BoostWritablePropertyMap] concept. The
- `key_type` of this parameter must be the `vertex_descriptor` of the
- `Graph`, and the `value_type` must be a model of the [BoostNumericValue]
- concept.
+ [*Requirements - [^mean_geodesic()]:] The `GeodesicMap` type is required
+ to model the [BoostReadablePropertyMap] concept.
+
+ [*Requirements - [^graph_mean_geodesic()]:] The `GeodesicMap` type is
+ required to model the [BoostWritablePropertyMap] concept.
+
+ *Requirements:* The `key_type` of this parameter must be the
+ same as the `vertex_descriptor` of the `Graph` parameter, and the
+ `value_type` must be a model of the [BoostNumericValue] concept.
]
]
[
[optional, in] [`Measure measure`]
[
- The 'measure' parameter is an instance of a measure type that performs
- the "averaging" operation in this computation. For the `mean_geodesic()`
- functions, this measure is responsible for computing the average distance
- over the graph. For the `graph_mean_geodesic()` function, this measure
- is responsible for averaging the averages.
+ The 'measure' parameter is an instance of a closeness measure that
+ performs the final division for this computation.
*Requirements:* The `Measure` type must be a model of the [BoostDistanceMeasure]
- concept.
+ concept. The `distance_type` must be the same type as the `value_type`
+ of the `DistanceMap` or `DistanceMatrixMap`. The `result_type` of the
+ `Measure` must model the [BoostNumericValue] concept.
]
]
]
@@ -199,13 +195,84 @@
unconnected, the mean geodesic distance is infinite.
[heading Complexity]
-The `mean_geodesic()` and `graph_mean_geodesic()` functions are ['O(n[super 2])]
-where /n/ is the number of vertices in the graph.
+The `mean_geodesic()` function returns in ['O(n[super 2]*O(M))] where /n/ is the
+number of vertices in the graph, and /M/ is the complexity of the measure. By
+defualt, /M/ is constant.
-The `vertex_mean_geodesic()` function is linear with respect to the number
-of vertices in the graph.
+The `vertex_mean_geodesic()` function returns in /O(n*O(M))/. By default /M/ is
+constant.
+
+The `graph_mean_geodesic()` function returns in /O(n*O(M))/. By default /M/ is
+constant.
[heading Example]
-Write an example.
+This example shows how to compute the mean geodesic distance for each vertex
+in a social network, and the mean geodesic distance for the graph as a whole.
+This example includes the files
+
+* [^examples/mean_geodesic.hpp]
+* [^examples/social_network.hpp]
+* [^examples/helper.hpp]
+
+First, we define the graph and its associated types.
+[social_network_types]
+Here, we use the `Actor` to store an actor name with each vertex. We also need to
+define a number of related property types to support property maps for the algorithms
+called in the program.
+
+Since this program will call [boost_floyd_warshall_all_pairs_shortest_paths] to
+compute distances between vertices, we need a matrix to store the distances.
+[distance_matrix_types]
+
+We also need a property map that assigns weights to each edge. Since our graph is
+unweighted, we can use the [boost_constant_property_map] to return a constant value
+for each edge. [constant_weight_map_types]
+
+We also need an output property map to store the mean geodesic distance of each
+vertex.
+[geodesic_map_types]
+
+In the main program, we instantiate the graph and an extra `std::map` that we
+use during graph construction.
+
+[setup_social_network]
+
+The graph is read from standard input. This process uses the `add_named_vertex()`
+function, which is not part of the Boost.Graph library but defined in the file
+`examples/helper.hpp`.
+
+[build_social_network]
+
+The next step is to compute the distance. This is done using the
+[boost_floyd_warshall_all_pairs_shortest_paths] function. This could also be done
+using [boost_johnson_all_pairs_shortest_paths]. This is done by first constructing
+a matrix to hold the distance values, and a property map over the matrix. Additionally,
+we use a [boost_constant_property_map] to return the value `1` for all edge weights.
+Both the distance matrix and edge-weight maps are used as inputs to the distance
+algorithm.
+[compute_constant_distances]
+
+After computing the distance, we can use the resulting distance matrix to compute
+the mean geodesic distance of each vertex. This is done by constructing a container
+for the distance values and a property map accessor for it. The previously computed
+distance map and geodesic map are passed as inputs to `mean_geodesic()` function.
+The geodesic map, once computed, is then used as an input to the `graph_mean_geodesic()`
+function, which returns the mean geodesic distance of the graph.
+[compute_mean_geodesics]
+
+As a final step, we print the mean geodesic distance of the graph.
+[print_graph_mean_geodesic]
+
+If this program is given the `social_network.graph` file as input, the output
+will be:
+
+[pre
+mean geodesic distance: 1.91667
+]
+
+Note that this program can be easily modified to work on directed graphs. In the
+file `social_network.hpp`, simply replace `typedef undirected_graph<Actor> ...` to
+`typedef directed_graph<Actor> ...`.
+
[endsect]
\ No newline at end of file
Deleted: sandbox/SOC/2007/graphs/libs/graph/doc/reference/radius.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/reference/radius.qbk 2007-08-15 10:32:37 EDT (Wed, 15 Aug 2007)
+++ (empty file)
@@ -1,62 +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 Radius]
-
- template <typename Graph, typename EccentricityMap>
- typename property_traits<EccentricityMap>::value_type
- graph_radius(const Graph& g, EccentricityMap ecc)
-
-The /radius/ of a graph is the minimum /eccentricty/ of any vertex in the
-graph. This computes and returns that value using previously computed
-eccentricity values. Eccentricity values are typically computed using the
-[boost_eccentricity] functions.
-
-The radius of a graph is also used to establish the graph's /center/ - the
-set of vertices having the same eccentricity as the graph radius. This subset
-can be computed using the [boost_graph_center] functions.
-
-[heading Where Defined]
-`boost/graph/radius.hpp`
-
-[heading Parameters]
-[table
- [[Type] [Parameter] [Description]]
- [
- [required, in] [`const Graph& g`]
- [
- The graph for which the eccentricity measures are being comptued.
-
- *Requirements:* The `Graph` type must be a model of the
- [BoostVertexListGraph] concepts.
- ]
- ]
- [
- [required, in] [`EccentricityMap ecc`]
- [
- The `ecc` property map associates an eccentricity value with every
- vertex in the graph.
-
- *Requirements:* `EccentricityMap` must be a model of [BoostReadablePropertyMap].
- The `key_type` of the distance map must be the same as the `vertex_descriptor`
- of the `Graph` parameter. The `value_type` must model the [SgiLessThanComparable]
- concept.
- ]
- ]
-]
-
-[heading Return Value]
-The `graph_radius()` function returns the radius of the given graph with respect
-to the given eccentricity values.
-
-[heading Complexity]
-The `graph_radius()` function is linear.
-
-[heading Examples]
-Write an example.
-
-[endsect]
\ No newline at end of file
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-15 10:32:37 EDT (Wed, 15 Aug 2007)
@@ -71,10 +71,9 @@
[section Measures]
[include degree_centrality.qbk]
[include closeness_centrality.qbk]
+[include betweenness_centrality.qbk]
[include mean_geodesic.qbk]
[include eccentricity.qbk]
-[include radius.qbk]
-[include diameter.qbk]
[endsect]
[endsect]
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