## SOCNET@LISTS.UFL.EDU

#### View:

 Message: [ First | Previous | Next | Last ] By Topic: [ First | Previous | Next | Last ] By Author: [ First | Previous | Next | Last ] Font: Proportional Font

Subject:

Re: correction

From:

Date:

Mon, 25 Feb 2002 04:46:28 -0800

Content-Type:

TEXT/PLAIN

Parts/Attachments:

 TEXT/PLAIN (65 lines)
 ```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 ---------------------------------------------------------------------------```