Closeness: Difference between revisions
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
'''Closeness''' is a radial measure of centrality that favors actors who are connected with many others via short paths. | '''Closeness''' is a radial measure of centrality that favors actors who are connected with many others via short paths. Intuitively, if the graph represents a transportation network, then a node with high closeness would make a good location for a warehouse since the average distance to all other locations (i.e., all other nodes in the graph) is relatively short. In information-spreading networks, a node with high closeness centrality would be a good choice to start a rumor since many others can be reached with relatively few intermediates. | ||
== Definition (simple case) == | == Definition (simple case) == | ||
| Line 15: | Line 7: | ||
<math>c_C(v)=\frac{|V|-1}{\sum\limits_{t\in V\setminus v} d_G(v,t)}</math>, | <math>c_C(v)=\frac{|V|-1}{\sum\limits_{t\in V\setminus v} d_G(v,t)}</math>, | ||
where <math>d_G(v,t)</math> denotes the length of a [[Shortest path|shortest directed path]] from <math>v</math> to <math>t</math>. | where <math>d_G(v,t)</math> denotes the length of a [[Shortest path|shortest directed path]] from <math>v</math> to <math>t</math>. The definition for [[Connectivity|connected]] undirected graphs is identical with <math>d_G(v,t)</math> being defined as the length of a [[Shortest path|shortest path]]. | ||
== Example == | == Example == | ||
| Line 24: | Line 16: | ||
=== Edge weights and distances === | === Edge weights and distances === | ||
If a [[link strength]] has been selected, the length of an <math>(v,t)</math>-path is the sum of the corresponding attribute values of all links in the path. | |||
== Implementation in visone == | == Implementation in visone == | ||
Revision as of 13:29, 30 March 2011
Closeness is a radial measure of centrality that favors actors who are connected with many others via short paths. Intuitively, if the graph represents a transportation network, then a node with high closeness would make a good location for a warehouse since the average distance to all other locations (i.e., all other nodes in the graph) is relatively short. In information-spreading networks, a node with high closeness centrality would be a good choice to start a rumor since many others can be reached with relatively few intermediates.
Definition (simple case)
On directed, unweighted graphs that are strongly connected, the closeness centrality of a node is defined as
,
where denotes the length of a shortest directed path from to . The definition for connected undirected graphs is identical with being defined as the length of a shortest path.
Example
Special cases
Unconnected graphs
Edge weights and distances
If a link strength has been selected, the length of an -path is the sum of the corresponding attribute values of all links in the path.
