Difference between revisions of "Betweenness"

From visone manual
Jump to navigation Jump to search
(Created page with ''''Betweenness''' is another means to quantify the structural importance of nodes in a network. It is defined as the percentage of all shortest paths that contain a certain node…')
 
 
(One intermediate revision by the same user not shown)
Line 1: Line 1:
'''Betweenness''' is another means to quantify the structural importance of nodes in a network.
+
'''Betweenness''' is a medial measure of the structural importance of nodes in a network.  It assigns higher values to those nodes that are in a position to control the indirect linkages of others.
  
It is defined as the percentage of all shortest paths that contain a certain node.
+
For each pair of nodes <math>s</math> and <math>t</math>, the ''dependency'' <math>\delta(s,t|v)</math> on a particular node <math>v</math> is defined as the fraction all shortest <math>st</math>-paths that contain <math>v</math> as an inner node. The betweenness score of <math>v</math> is the sum over all pair-dependencies,
  
That is, under the assumption that information, traffic etc. flows only along shortest paths, nodes are ranked according to the amount of information, traffic etc. that flows over them.
+
<math>c_B(v)=\sum_{s\neq v\neq t} \delta(s,t|v) = \sum_{s\neq v\neq t} \frac{\sigma(s,t|v)}{\sigma(s,t)}</math>
 +
 
 +
where <math>\sigma(s,t)</math> is the number of shortest path between <math>s</math> and <math>t</math>, and <math>\sigma(s,t|v)</math> the number of those containing <math>v</math> as an inner node.
 +
That is, under the assumption that information, traffic, resources, trust, etc. spread along shortest paths only, nodes are ranked according to the amount of information, traffic etc. that passes by them.  In link-valued graphs, the notion of a shortest path depends on the interpretation of those values.  For instance, the attribute might represent a length, and the length of a path is the sum over the lengths of its links.

Latest revision as of 20:50, 14 May 2011

Betweenness is a medial measure of the structural importance of nodes in a network. It assigns higher values to those nodes that are in a position to control the indirect linkages of others.

For each pair of nodes and , the dependency on a particular node is defined as the fraction all shortest -paths that contain as an inner node. The betweenness score of is the sum over all pair-dependencies,

where is the number of shortest path between and , and the number of those containing as an inner node. That is, under the assumption that information, traffic, resources, trust, etc. spread along shortest paths only, nodes are ranked according to the amount of information, traffic etc. that passes by them. In link-valued graphs, the notion of a shortest path depends on the interpretation of those values. For instance, the attribute might represent a length, and the length of a path is the sum over the lengths of its links.