## SOCNET@LISTS.UFL.EDU

#### View:

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

Subject:

Re: SV: Searching for diameter calculation algoritm

From:

Date:

Thu, 13 Nov 2003 05:08:12 -0800

Content-Type:

text/plain

Parts/Attachments:

 text/plain (51 lines)
 ***** To join INSNA, visit http://www.sfu.ca/~insna/ ***** Carl Nordlund wrote: > 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? I'm not sure that I follow you; a geodesic is a shortest path between two vertices. BCDE is, in the above, the unique BE geodesic, but it's just one of many geodesics in the graph. (For instance, ADE is the unique AE geodesic.) Thus, I'm not sure what you mean by "the" geodesic. I'm also not sure what you mean by saying that "the geodesic is here 3." Are you refering to the geodesic _distance_ between B and E? In this case, that distance is either 6 (if we consider the edge weights) or 3 (if we consider only distances in the underlying simple graph). > 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? > I think the problem here may be that you are mixing two different things: the diameter of the valued graph, and the diameter of the underlying simple graph. For your example (unless I have miscounted), the two diameters are 7 (ADE) and 3 (e.g., ADCB or BCDE), respectively.   Each represents the length of a longest shortest path within some graph, but the graphs in question (valued vs unvalued) are not the same. (And, of course, the geodesics which give rise to these diameters may not be the same, either -- e.g., the route from point A to point B which involves taking the smallest number of streets may not be the route which covers the minimum total distance (or travel time!).) 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.