Print

Print


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