 |
 |
***** To join INSNA, visit http://www.sfu.ca/~insna/ ***** X-Recipient-Split-By Carter, Thanks for your assistance! That's a mighty expensive book but I'll get it through the library! >As for the diameter, you can find it as a byproduct of the all-pairs shortest path problem (just look for >the maximum geodesic). Then I must have misunderstood diameters and geodesics - please allow me presenting a simple example network (undirected valued network): A B C D E A 0 - - 3 - B - 0 1 - - C - 1 0 1 - D 3 - 1 0 4 E - - - 4 0 The geodesic is here 3 - the path B-C-D-E - correct? Which would make the diameter the path length of this geodesic, i.e. 1+1+4 = 6. But what about A-D-E, which has a path length of 3+4 = 7? If A-D-E of 7 isn't the diameter of the network, then what is it? Yours, Carl -----Ursprungligt meddelande----- Från: Social Networks Discussion Forum [mailto:[log in to unmask]] För Carter T. Butts Skickat: den 12 november 2003 20:46 Till: [log in to unmask] Ämne: Re: Searching for diameter calculation algoritm ***** To join INSNA, visit http://www.sfu.ca/~insna/ ***** Carl Nordlund wrote: > ***** To join INSNA, visit http://www.sfu.ca/~insna/ ***** > > SocNetters, > > I am working on a small java program for drawing valued undirectional > graphs/networks while it calculates some network indices. However, I > cannot find a suitable algorithm for calculating geodesics and > diameters. I could, I guess, calculate the geodesic by dichotomizing > the matrix and calculating the power matrices until all the blanks are > filled in (Shimbel-style) - but is that the best algorithm for > calculating the geodesic? And what algorithms are available for > calculating diameters? All I can think of is a recursive n2-iterative > djikstra solution! > > I currently store the network as a graph (nodes as objects and edges > as objects referring to two node-objects) but I would prefer to > calculate geodesics and diameters from sociomatrices (which poses > problems with using the djikstra, right?) > > Thanks for any advice! > Try Ahuja et al.'s (1993) _Network Flows: Theory, Algorithms, and Applications_ for a variety of algorithms. As for the diameter, you can find it as a byproduct of the all-pairs shortest path problem (just look for the maximum geodesic). The manner in which your data is stored (sociomatrices, linked lists, etc.) should not pose problems here, although some storage schemes are more efficient than others. Hope that helps, -Carter _____________________________________________________________________ SOCNET is a service of INSNA, the professional association for social network researchers (http://www.sfu.ca/~insna/). To unsubscribe, send an email message to [log in to unmask] containing the line UNSUBSCRIBE SOCNET in the body of the message. _____________________________________________________________________ SOCNET is a service of INSNA, the professional association for social network researchers (http://www.sfu.ca/~insna/). To unsubscribe, send an email message to [log in to unmask] containing the line UNSUBSCRIBE SOCNET in the body of the message.