The minimal path in an information network has 3 points ( and therefore the path has the order k=3 )
- one starting point
- one mid point
- one target point
and we can specify each path by a sequence of figures like 123 or 231 etc.
An important question when analyzing networks is, how many different paths exist in a complete network ( without feedback loops ) and all its sub-networks.
- in a network of order 3 exist 6 different paths.
We consider only open paths; the number of closed paths is just twice the number of the open paths.
Two equations from mathematical combinatorics are used:
The faculty of a natural number n is noted as n! = 1*2*3* …n
3! = 1*2*3 = 6
4! = 1*2*3*4 = 24
Important to note is the definition: 0! = 1
If we want to calculate, in how many different ways we can form different groups of k numbers, if n different numbers are given, then we can calculate that with following equation:
This equation is valid, if it the order of the k chosen numbers does not matter.
If the order matters, we have to multiply this equation with k! , because there exist so many different arrangenents of k numbers.
And then we get the number of different paths in a complete network of order n, each path with k different points
The complete network has the order 7.
- In the first row are the orders of the sub-networks
- In the first column are the orders of the paths, 3 being the minimal possible order.
From this table we can deduce probabilities, that a certain path will be used.
For instance, if we know, that the complete network has the order n = 5 and that there will be taken a path of order k= 3, then the probability for it is 1/60
For a network of order n=3 and a path of order k=3, the probability is 1/6. That is 10 times higher, than for a network of order n=5
From that observation we can deduce a criteria, to find out, if we really use a complete network of order n.
We have only to note, how many times a path of order k exists. If for instance, we find out, that paths of order 3 exist 50 times, then the order of the complete network must be at least n= 5
If we have found only 4 points, then at least 1 point is still missing, to get the complete network. And in this way we can go on with the other orders of paths.