My apologies to all.  Anthonisse visited me in 1978 and brought along a
copy of the 1971 paper on rush.  I read it several times over the next few
months but I don't have a copy here with me currently.  My, obviously
faulty, memory did not include the passage quoted by Ulrik.





On Mon, 25 Feb 2002, Ulrik Brandes wrote:

> 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/
>

--------------------------------------------------------------------------
Linton C. Freeman                         Phone: Office: 949 824-6698
Department of Sociology                   Sec.:          949 824-6336
School of Social Sciences  SSPA 2143      Home:          949 494-6139
University of California                  FAX:           949 824-3733
Irvine, CA 92697-5100                     E-mail: [log in to unmask]
http://moreno.ss.uci.edu/lin.html
---------------------------------------------------------------------------