Information networks: number of different paths. part 3

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

Examples:

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:

Kombinatorik

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.

Kombinatorik2

And then we get the number of different paths in a complete network of order n,  each path with k  different  points

 tabelle2

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.

Dieser Beitrag wurde unter information networks abgelegt und mit , , verschlagwortet. Setze ein Lesezeichen auf den Permalink.

Kommentar verfassen

Bitte logge dich mit einer dieser Methoden ein, um deinen Kommentar zu veröffentlichen:

WordPress.com-Logo

Du kommentierst mit Deinem WordPress.com-Konto. Abmelden / Ändern )

Twitter-Bild

Du kommentierst mit Deinem Twitter-Konto. Abmelden / Ändern )

Facebook-Foto

Du kommentierst mit Deinem Facebook-Konto. Abmelden / Ändern )

Google+ Foto

Du kommentierst mit Deinem Google+-Konto. Abmelden / Ändern )

Verbinde mit %s