## Average distance for network topologies.

1. The problem statement, all variables and given/known data
I want to derive a general formula to calculate the average distance of the nodes in a network topology. The topologies can be line(linear), ring, mesh etc. The different nodes are numbered 0,1,2.. N-1. I understand the diameter of the network etc.

2. Relevant equations
None.

3. The attempt at a solution
I am doing self study and the book simply provides the formula without any proofs. I am not sure what are the techniques or where to start to solve it.
 PhysOrg.com science news on PhysOrg.com >> Leading 3-D printer firms to merge in $403M deal (Update)>> LA to give every student an iPad;$30M order>> CIA faulted for choosing Amazon over IBM on cloud contract
 Perhaps the formula is intuitively understandable?
 Well the book says the average distance is roughly (2/3)N for a linear bi directional linked network. Its does not seem intuitive for me. Can you please provide some hints?

## Average distance for network topologies.

Hmm. In case of unidirectional link the average distance of a ring I think I could derive as follows:

The sum of distance of a node to all other nodes : 0+1+2+3..+n-1 = n(n-1)/2
Total number of distances : (n-1).
Average distance : n(n-1)/2 /n-1) = n/2.

Now got to figure out bidirectional links and linear array.
 I'm thinking that in a unidirectional ring, the round-trip distance is the whole ring, so the average round-trip distance is the whole ring, or N. In a bidirectional ring, every node is like the center node in a bidirectional linear network. That case should be easier to understand than the linear case. I'll think some more about this. (You're right, it isn't intuitive.)
 Have you got enough to go on? The linear case becomes much easier to understand if you experiment with small numbers of nodes.

 Have you got enough to go on?
I am not sure. The only thing I am going with is the (sum of distances)/(number of distances).
In case of linear link is there any hint I can use? The smaller sums tend to be the following:

For a 3 node linear link:
Distances from
1 {1,2}
2 {1,1}
3 {2,1}

Generalizing
1 {1..n-1}
2 {1,1..n-2}
3 {2,1,.., n-3}
.
.
n {n-1,.. 1}

Turns out the distances form a symmetric matrix. Now is there any properties of matrices I can use to get the sum of the distances?
 I don't want to say too much because I think you can solve this, but I'll give a hint: 2 nodes: 11 3 nodes: 12, 11, 21 or 11, 2112 4 nodes: 123, 112, 211, 321 or 11, 2112, 321123
 Am I in the right path if I do this? (1+1) + (2+1+1+2) + (3+2+1+1+2+3) i.e. 2 * n * (n-1)/2 = n*(n-1). Hence the sequence n(n-1) + (n-1)(n-2)+.... n*n2 - n[1+3+5] + [2 + 6 + 12...]
 Do you recall that you were trying to find the average distance? If you know the sum of distances, then...

 Quote by vertigo Do you recall that you were trying to find the average distance? If you know the sum of distances, then...
Shouldn't I find a generic formula to find the sum of the distances?

In case of 4 nodes then the average distance is 20/12.
(The total number of distances will be n*(n-1))

 Quote by nascentmind Shouldn't I find a generic formula to find the sum of the distances? In case of 4 nodes then the average distance is 20/12. (The total number of distances will be n*(n-1))
It's not a matter of should or shouldn't. If you want to, then do that. I'm being obtuse just because that is what you wanted, given that you said you wanted to derive (yourself) a formula for average distance between nodes in a network.

So the rest is up to you. The last hurdle was the number of nodes but you have a formula for that, so you have all the ingredients. Now just find the answer, what is the average distance versus N nodes?
 I am sorry , I am confused. I am not able to find the sum of the distances for N nodes. I have distances for 2,3,4.. nodes. I am failing to see how I have enough ingredients here :(
 You don't need a generic formula for N nodes. Find the average distance for 2,3,4,... (You'll see, it works out pretty nicely.)
 I think I can see it now. 1,1.3,1.6.. difference is ~ 0.3 So the formula would be 0.7 + 0.3n ?
 Vertigo, Am I right? If not can you provide me some more hints?
 That formula is not correct. It works only for small numbers of nodes. Can you see why?

 Tags average, distance, network, topology

 Similar discussions for: Average distance for network topologies. Thread Forum Replies Introductory Physics Homework 1 Calculus & Beyond Homework 0 Introductory Physics Homework 3 Introductory Physics Homework 2 Introductory Physics Homework 5