***** To join INSNA, visit http://www.sfu.ca/~insna/ *****
Carl Nordlund wrote:
> ***** To join INSNA, visit http://www.sfu.ca/~insna/ *****
> 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,
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.