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