Print

Print


On Sun, Feb 24, 2002 at 10:04:58AM -0500, Steve Borgatti wrote:
> Lin Freeman tells me that Anthonisse's 1971 paper doesn't actually mention edge betweenness. Apparently, the gradap people did the extension themselves. As the gradap manual puts it "Both [freeman's and anthonisse's betweenness models] differ however in their normalization...Moreover, Anthonisse's model provides the possibility of computing the rush for lines. The rush then gives the proportion of flow that passes [through] a line."

Actually, Anthonisse does define edge betweenness.  Quoting from his '71 paper [1]
(note that A. considers the more general problem on directed graphs):

    To define rush [read: betweenness], one unit of flow is sent from each
  vertex x_i to each vertex x_j, provided 0 < d_ij < infinity.  The flow is sent
  along minpaths [read: geodesics] only, if e_ij minpaths from x_i to x_j exist
  then 1/e_ij units are sent along each path.
    The rush in an element (vertex or arc [sic!]) is defined as the total flow
  through that element, resulting from the flows defined above.

Anthonisse also mentions generalizations involving weights for paths between
pairs (e.g., to reduce the influence of distant pairs as in Valdis Krebs'
variant of stress, which corresponds to sending 1 unit of flow along each
geodesic), and different lengths of directed edges.  He also gives an
algorithm to compute both vertex and edge betweenness, though it is not
quite as efficient as the one implemented in UCINET, which is a straightforward
extension of [2].

Regarding other "link centralities", note that _any_ node index can be used to define
an edge index by computing it in the line graph:  The line graph L(G) of a graph G
contains a vertex for each edge in G, and two vertices in L(G) are adjacent,
if the corresponding edges share a vertex in G.  In general it is not even
necessary to construct the line graph explicitly.  Observe, however, that
betweenness in the line graph and edge betweenness yield different measures.

B.


[1] Jac. M. Anthonisse (1971).  The rush in a directed graph.
    Technical Report BN 9/71, Stichting Mathematisch Centrum, Amsterdam.
    [I am grateful to Frans Stokman for sending me a copy of this paper in '99]

[2] U. Brandes (2001).  A faster algorithm for betweenness centrality.
    Journal of Mathematical Sociology 25(2): 163--177.

--
Dr. Ulrik Brandes
University of Konstanz         | +49 7531 88 4263 (phone)
Department of Computer &       | +49 7531 88 3577 (fax)
Information Science, Box D 188 | [log in to unmask]
78457 Konstanz, Germany        | http://www.inf.uni-konstanz.de/~brandes/