Difference between revisions of "Closeness"

From visone manual
Jump to navigation Jump to search
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.
 
 
The raw closeness score of a node <math>v</math> is defined as the reciprocal of its total distance to those it can reach via directed paths,
 
 
 
<math>c_C(v)=\frac{\text{number of reachable nodes}}{\sum\limits_{\text{reachable nodes } t} d_G(v,t)}</math>
 
 
 
where <math>d_G(v,t)</math> denotes the length of a shortest directed path from <math>v</math> to <math>t</math>.
 
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.
 
 
 
  
 
== 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.

Implementation in visone

Normalization and treatment of special cases

Algorithmic runtime

Related measures

References