## 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: Searching for diameter calculation algoritm

From:

Date:

Thu, 13 Nov 2003 14:10:38 +0100

Content-Type:

text/plain

Parts/Attachments:

 text/plain (72 lines)
 ```***** To join INSNA, visit http://www.sfu.ca/~insna/ ***** Carl, It seems you are confusing weighted and unweighted shortest paths. A geodesic is always a minimal-weight path between a pair of nodes, and it can be calculated either with or without edge weights, and by extension, so can the diameter. Dichotomizing the (adjacency) matrix effectively makes it unvalued, and unweighted shortest paths can be found efficiently through repeated breadth-first-search. It is of course possible to sum edge weights along such (unweighted) shortest paths, but only you know what this means (What does your weights measure?). If you keep the edge values to get weighted geodesics and diameter, you need something like (repeated) Dijkstra, matrix multiplication or Floyd-Warshall. What is the size of your datasets? Finding the diameter of valued graphs with thousands of nodes is a breeze with any good implementation available as open source. No need to code basic stuff like this from scratch, look into the implementation in e.g Jung (http://jung.sourceforge.net, ver 1.1, announced just a few days ago on this list). If you want exact results, there is no known way to improve in principle upon the basic algorithms described in any good book (e.g Corman, Leiserson, Rivest, Stein "Introduction to Algorithms, 2nd ed.", Chap. 24-25). Algorithms that estimates the diameter (up to some constant term) can achieve a lower computational complexity. If you want to see whats on the "bleeding edge", see for example: D. Aingworth, C. Chekuri, P. Indyk, R. Motwani, "Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)" http://epubs.siam.org/sam-bin/dbq/article/30342 Christian 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! > > Yours, > Carl > > _____________________________________________________________________ > 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. -- ==================================================================== Christian Carling E-mail: [log in to unmask] Swedish Defence Research Agency, FOI Tel: +46 8 55 50 39 17 Dept of Command and Control Studies Fax: +46 8 55 50 38 68 SE-172 90 Stockholm Mobile: +46 708 52 01 42 _____________________________________________________________________ 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.```