*****  To join INSNA, visit  *****

Hello all,

I'm looking for an algorithm to help me lower
the average distance in a network.

I have a NxN network matrice and run it
through an All Pairs Shortest Path (APSP) algorithm
to determine the distance between
all nodes.

Following that I can calculate the average distance
between the notes.

I now have two (connected) tasks.

First, I want to calculate the top 10 ties (only 1
implemented), that will lower the average distance
the most. Of course I can do this by trying each tie at
a time and then performing the
APSP afterwards. But this is slow and I'd
like to find a quicker algorithm.

Second, I want to calculate those X (for example 10)
ties that will lower the average distance
the most, if they are all implemented at once.
I'm also looking for an algorithm for this one.

I will be thankful for any suggestions, ideas
or hints.

Flemming Madsen
(Always on the lookout for interesting social network
analysis cases - to read about or to perform)

SOCNET is a service of INSNA, the professional association for social
network researchers ( To unsubscribe, send
an email message to [log in to unmask] containing the line
UNSUBSCRIBE SOCNET in the body of the message.