Difference between revisions of "Closeness"

From visone manual
Jump to navigation Jump to search
Line 7: Line 7:
 
where <math>d_G(v,t)</math> denotes the length of a shortest directed path from <math>v</math> to <math>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.
 
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) ==
 +
 +
On directed, unweighted graphs <math>G=(V,E)</math> that are [[Connectivity|strongly connected]], the closeness centrality <math>c_C(v)</math> of a node <math>v\in V</math> is defined as
 +
 +
<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>.
 +
 +
== Example ==
 +
 +
== Special cases ==
 +
 +
=== Unconnected graphs ===
 +
 +
=== Edge weights and distances ===
 +
 +
== Implementation in visone ==
 +
 +
=== Normalization and treatment of special cases ===
 +
 +
=== Algorithmic runtime ===
 +
 +
== Related measures ==
 +
 +
== References ==

Revision as of 12:25, 30 March 2011

Closeness is a radial measure of centrality that favors actors who are connected with many others via short paths.

The raw closeness score of a node is defined as the reciprocal of its total distance to those it can reach via directed paths,

where denotes the length of a shortest directed path from to . 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.


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 .

Example

Special cases

Unconnected graphs

Edge weights and distances

Implementation in visone

Normalization and treatment of special cases

Algorithmic runtime

Related measures

References