Print

Print


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