|
|
Boost-Commit : |
From: asutton_at_[hidden]
Date: 2007-08-13 13:02:23
Author: asutton
Date: 2007-08-13 13:02:19 EDT (Mon, 13 Aug 2007)
New Revision: 38624
URL: http://svn.boost.org/trac/boost/changeset/38624
Log:
Finsined docs for degreee and closeness centrality.
Moved code imports to boost_reference file
Text files modified:
sandbox/SOC/2007/graphs/libs/graph/doc/boost_reference.qbk | 18 ++
sandbox/SOC/2007/graphs/libs/graph/doc/reference/closeness_centrality.qbk | 268 +++++++++++++++++++++++++++++++--------
sandbox/SOC/2007/graphs/libs/graph/doc/reference/degree_centrality.qbk | 76 ++++------
3 files changed, 261 insertions(+), 101 deletions(-)
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/boost_reference.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/boost_reference.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/boost_reference.qbk 2007-08-13 13:02:19 EDT (Mon, 13 Aug 2007)
@@ -9,6 +9,11 @@
/ This file contains references to Boost.Graph reference docs
/]
+
+[template boost_constant_property_map[] [link
+ boost_graph
+ [^constant_property_map]]]
+
[/ Graph traits and types /]
[template boost_graph_traits[] [link boost_graph.reference_guide.traits_classes.graph_traits [^graph_traits]]]
[template boost_undirected_graph[] [link boost_graph.reference_guide.graph_types.undirected_graph [^undirected_graph]]]
@@ -43,6 +48,9 @@
[template boost_floyd_warshall_all_pairs_shortest_paths[] [link
boost_graph.reference_guide.algorithms.shortest_paths.floyd_warshall_all_pairs_shortest_paths
[^floyd_warshall_all_pairs_shortest_paths()]]]
+[template boost_johnson_all_pairs_shortest_paths[] [link
+ boost_graph.reference_guide.algorithms.shortest_paths.johnson_all_pairs_shortest_paths
+ [^johnson_all_pairs_shortest_paths()]]]
[/ Connectivity /]
[template boost_connected_components[] [link
@@ -86,4 +94,12 @@
[^exterior_vertex_property]]]
[template boost_exterior_edge_property[] [link
boost_graph
- [^exterior_edge_property]]]
\ No newline at end of file
+ [^exterior_edge_property]]]
+
+[/ Import lots of examples to build code templates]
+[import ../examples/social_network.hpp]
+[import ../examples/flow_network.hpp]
+[import ../examples/degree_centrality.cpp]
+[import ../examples/influence_prestige.cpp]
+[import ../examples/closeness_centrality.cpp]
+[import ../examples/norm_closeness_centrality.cpp]
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-13 13:02:19 EDT (Mon, 13 Aug 2007)
@@ -7,52 +7,77 @@
[section Closeness Centrality]
- template <typename Graph, typename DistanceMatrix, typename ClosenessMap>
+ template <typename Graph, typename DistanceMatrixMap, typename ClosenessMap>
void closeness_centrality(const Graph& g,
- const DistanceMatrix& dist,
- ClosenessMap close)
+ DistanceMatrixMap dm,
+ ClosenessMap cm)
- template <typename Graph,
- typename DistanceMatrix,
- typename ClosenessMap,
- typename Measure>
+ template <typename Graph, typename DistanceMatrixMap, typename ClosenessMap, typename Measure>
void closeness_centrality(const Graph& g,
- const DistanceMatrix& dist,
- ClosenessMap close,
- Measure measure)
+ DistanceMatrixMap dm,
+ ClosenessMap cm,
+ Measure m)
template <typename Graph, typename DistanceMap>
- float vertex_closeness_centrality(const Graph& g, DistanceMap dist)
+ float vertex_closeness_centrality(const Graph& g, DistanceMap dm)
template <typename ResultType, typename Graph, typename DistanceMap>
- ResultType vertex_closeness_centrality(const Graph& g, DistanceMap dist)
+ ResultType vertex_closeness_centrality(const Graph& g, DistanceMap dm)
template <typename Graph, typename DistanceMap, typename Measure>
typename Measure::result_type
- vertex_closeness_centrality(const Graph& g, DistanceMap dist, Measure measure)
+ vertex_closeness_centrality(const Graph& g, DistanceMap dm, Measure m)
-The /closeness centrality/ measure is commonly used in social network analysis to
-identify vertices (also called actors) that are "close" to all others. To phrase
-differently, 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
-as the sum of all geodesic distances (lengths of shortest path) from one vertex
-to all others. Formally it is given as:
+The /closeness centrality/ measure is commonly used in network analysis to identify
+vertices (also called actors) that are "close" to all others. To phrase differently,
+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:
[$images/eq/closeness.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 zero. This is not necessarily the case for directed
-graphs.
-
-It is also important to note the relationship between /closeness/, /farness/
-and /mean geodesic distance/. Specifcially, /farness/ is the inverse of
-/closeness/ (or the other way around) and indicates how far an actor is from
-all others in the graph. The /mean geodesic distance/ is the average /farness/
-of a vertex.
+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
+all vertices will have a closeness of zero. This is not necessarily true for
+directed graphs.
+
+Consider the following social network represented by an undirected graph in
+Figure 1.
+
+[figure
+ images/reference/social_network.png
+ *Figure 1.* A network of friends.
+]
+
+Computing the closeness for each person in the graph, we find that Frank is the
+most central person in the network, with a closeness centrality of approximiately
+0.091 (1/11). We also find that Jill, Mary, and Laurie are the least central
+people in the network (with closeness centralities of .056 or 1/18).
+
+The same measure can also be applied to directed graphs, but has dubious meaning
+if the graph is not /strongly connected/. Consider the communication networks
+between the friends listed above. For this graph, we connect two people /a/ and
+/b/ if /a/ sends a text message to /b/ (for example).
+
+[figure
+ images/reference/comm_network.png
+ *Figure 2.* Communications between friends.
+]
+
+In this network, Frank is once again the most central (with a closeness centrality
+of 0.067) because he is "closer" to each of the various communication cycles in the
+network. Laurie is the furthest removed, with a closeness centrality of .028.
+
+In these examples, distance is defined as the number of "hops" in the shortest path
+from one vertex to another. It should be noted, however, that distance can also be
+represented as the sum of edge-weights on the shortest path between the two vertices.
+The definition of distance for this measure is outside the scope of this computation.
+This is to say that distance is defined and computed before closeness centrality
+can be computed.
This module defines a flexible framework for computing the closeness centrality
of vertices in a graph for previously computed geodesics by providing two generic
@@ -65,8 +90,9 @@
The second function, `vertex_closeness_centrality()` 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.
+distance map can be computed as the result of a "shortest paths" algorithm (e.g.,
+[boost_dijkstra_shortest_paths], [boost_bellman_ford_shortest_paths], or
+[boost_dag_shortest_paths]), or recording distances from a [boost_breadth_first_search].
This framework also allows for a specialization of the measure through the use
of a function object. This measure defaults to the reciprocal in the equation
@@ -100,12 +126,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`
@@ -114,28 +139,29 @@
]
]
[
- [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] [`ClosenessMap close`]
+ [required, out] [`ClosenessMap cm`]
[
- The `close` parameter stores the output of the computed closeness (or
+ 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
- [BoostPropertyMap] and [BoostWritablePropertyMap] concepts. The `key_type`
- of the property map must be the same as the `vertex_descriptor` of
- the `Graph` type, and the `value_type` must be a model of [BoostNumericValue].
+ *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].
]
]
[
@@ -145,23 +171,151 @@
performs the final operation (the reciprocal) 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.
]
]
]
[heading Return]
The `vertex_closeness_centrality()` function returns the closeness of a vertex.
-If the source vertex is not connected to one other in the graph, this value is 0.
+If the source vertex is disconnected from any vertices in the graph, this value is 0.
[heading Complexity]
-The `closenesss_centrality()` function is ['O(n[super 2])] where /n/ is the
-number of vertices in the graph.
+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)]
+This example computes the closeness centrality for all vertices (people) a social
+network such as the one pictured in Figure 1. The program also sorts the vertices by
+their corresponding closeness in descending order. 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 define a
+number of related property types.
+
+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 closeness centrality for each
+vertex.
+[closeness_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 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]
+
+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
+vector will contain the vertices of the graph in descending order of closeness.
+The `sort_vertices()` function is given in the `helper.hpp` file.
+[closeness_sort_vertices]
+
+Finally, we iterate over the sorted vector of vertices and print them to standard
+output.
+[print_sorted_closeness]
+
+If this program is given the `social_network.graph` file as input, the output
+will be:
+
+[pre
+Frank 0.0909091
+Scott 0.0833333
+Josh 0.0625
+Bill 0.0588235
+Anne 0.0588235
+Howard 0.0588235
+Jill 0.0555556
+Mary 0.0555556
+Laurie 0.0555556
+]
-The `vertex_closeness_centrality()` function is linear with respect to the number
-of vertices in the graph.
+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> ...`.
+
+[heading Example (Normalized Closeness)]
+In some literature, closeness is defined as the number of vertices divided by the
+sum of distances, or more formally.
+
+[$images/eq/norm_closeness.png]
+
+Where /n/ is the number of vertices in the graph. While this example demonstrates
+the implementation of a [BoostDistanceMeasure], the resulting value can be also
+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/social_network.hpp]
+* [^examples/helper.hpp]
+
+Defining the a distance measure that models the [BoostDistanceMeasure] type is
+fairly simple, and is similar to providing custom function objects for algorithms
+in the Standard Library. Our custom measure is defined as:
+[normalized_closeness_measure]
+
+Using this measure requires that we instantiate it. Since we did not provide
+any convenience functions for instantiating the type, it must be explicitly
+declared before its use. The distance and result types are given as `int` and
+`float` respectively. Once constructed, it is simply passed to the computation
+as an argument.
+[compute_normalized_closeness]
+
+If given the same social network as input, the output of this program will be:
+
+[pre
+Frank 0.818182
+Scott 0.75
+Josh 0.5625
+Bill 0.529412
+Anne 0.529412
+Howard 0.529412
+Jill 0.5
+Mary 0.5
+Laurie 0.5
+]
-[heading Example]
-Write an example.
+It is relatively easy to verify that each of these values is nine times the values
+given in the previous example.
[endsect]
\ No newline at end of file
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-13 13:02:19 EDT (Mon, 13 Aug 2007)
@@ -38,8 +38,8 @@
This graph depicts a set of friends and their relationships (friendship, dating, etc.)
The degree centrality of each person in this graph is their number of friends.
-Here, Frank has the highest degree centrality (five friends each), whereas Laurie
-has the lowest degree centrality since she has only one friend.
+Here, Frank has the highest degree centrality with five friends, whereas Laurie,
+Jill, Bill, Anne, and Howard are the least central with two friends apiece.
For directed graphs, there are related two interpretations of degree centrality.
When degree centrality is measured over the out-degree of a vertex, it is called
@@ -47,7 +47,7 @@
Consider the information network represented by the directed graph in Figure 2.
[figure
- images/reference/information_network.png
+ images/reference/info_network.png
*Figure 2.* A network of informational websites.
]
@@ -147,54 +147,46 @@
number of vertices in the graph and /M/ is a measure of a vertex. This is
linear for both the `influence_measure` and `prestige_measure`.
-The `vertex_degree_centrality()` returns in /O(M)/ where /M/ is a measure of
-a vertex. This is constant for both the `influence_measure` and `prestige_measure`.
+The `vertex_degree_centrality()` returns in /O(M)/. This is constant for both
+the `influence_measure` and `prestige_measure`.
The complexity of the `influence_measure` and `prestige_measure` functions are
both constant time.
[heading Example (Degree Centrality)]
-[import ../../examples/degree_centrality.cpp]
-
This example reads a graph from standard input (in a simple edge-list format),
computes the degree-centrality of each vertex, and prints them to standard
-output. The edge-list format is simply a comma-delimited listing of vertex pairs.
-For example:
+output. This example includes of the following files:
-[pre
-Scott,Bill
-Frank,Anne
-]
+* [^examples/closeness_centrality.hpp]
+* [^examples/social_network.hpp]
+* [^examples/helper.hpp]
To make typing easier, we define some aliases for the types used in this program
-in the global scope. Specifically, we define names for the graph and vertex types,
-types used to record the centralities of a social network, and a mapping of name
-to vertex (which is used to help build the graph).
-[declare_social_network]
-Note that the value type of the centrality property is `size_t` (an unsigned
-integer). This type must be the same as the `degree_size_type` of `Graph`, which
-is required to be an unsigned integer.
+in the global scope. This defines a social network as an undirected graph whose
+vertices are `Actor` properties. The `Actor` type simply stores an associated name
+for each vertex.
+[social_network_types]
+
+We also need a property map that will store the degree centrality as an output
+of the measure. The value type is given as `unsigned` because vertices do
+have negative degree.
+[centrality_map_types]
-The graph and a `VertexMap` object are declared in the main program as:
+In the main program, we construct an empty graph, and an associated mapping of
+names to vertices. This mapping is used in the construction of the graph.
[setup_social_network]
-The graph object `g` is the data structure which this program will construct
-and measure. The vertex map `verts` is used to ensure that vertices are uniquely
-associated with a name in the social network.
-The program starts by reading the input and buiding the graph.
+Building the network requires reading graph data from standard input. Here, the
+`add_named_vertex()` function is used to ensure that each name corresponds to
+a single vertex. This function is defined in `helper.hpp`.
[build_social_network]
-This snippet uses the `add_named_vertex()` to ensure that each vertex added
-to the graph corresponds to exactly one name in the input data. The `add_named_vertex()`
-function is not part of the Boost.Graph library, but provided as a helper function
-for many of these examples. See ... for its implementation.
-
-The program can now measure the degree centrality of the graph or social network.
-[measure_social_network]
-The `CentralityContainer` is the underlying container for the abstract `CentralityMap`
-accessor. It is constructed to be the same size as the number of vertices in the
-graph, and the centrality map is constructed over the container with respect to the
-graph `g`. The `degree_centrality()` function is called to populate the centrality
-map with measured values.
+
+Having built the graph, we can now compute the degree centrality of each vertex.
+This is done by constructing a container for the centrality values and a property
+map over it. This map is passed to the `degree_centrality()` function to store
+the computed values.
+[compute_degree_centrality]
Finally, we iterate over the vertices, printing the degree centrality of each
person in the network.
@@ -216,8 +208,6 @@
]
[heading Example (Influence and Prestige)]
-[import ../../examples/influence_prestige.cpp]
-
This example is nearly identical to the previous in that it computes the degree
centrality over vertices in a graph. However, this example constructs a directed
graph and computes both influence and prestige.
@@ -226,7 +216,7 @@
of the graph itself. Specifically, we declare this as a direted graph to help
capture the semantics of information flow.
- typedef directed_graph<Person> Graph;
+ typedef directed_graph<Actor> Graph;
Even the code that builds the graph is identical. Since the graph is directed, however,
the order in which vertices are listed determine directionality of the edge. For
@@ -237,15 +227,15 @@
and two calls to the `degree_centrality()` function. The calls to `measure_influence()`
and `measure_prestige()` create temporary measure functions that are responsible
for those values respectively.
-[measure_information_network]
+[compute_influence_prestige]
Note that the `measure_influence()` call can be ommitted to compute the influence
of vertices. If not given, `degree_centrality()` and `vertex_degree_centrality()`
will compute influence by default.
Finally, print the results for each vertex in the graph.
-[print_information_network]
+[print_influence_prestige]
-If given the `information_network.graph` file as input, the program will produce
+If given the `info_network.graph` file as input, the program will produce
the following output where the second column is influence and the third is prestige:
[pre
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