Information networks: some mathematical basics. part 1

Information networks can be represented by points and connections between them. In general the points and their connections do not have any geometrical meaning. But of course, if an information network represents a travelling route  on a map for instance, then the points and their connections have also a geometrical meaning.

But at first we consider only abstract information networks and if we represent them with a drawing, then the drawing should not get geometrically interpreted.

At first we consider complete information networks.

Definition 1:  A   network, which has  n points and all connections between them, is called a  complete information network.

The number of points are called the order of the network.

Conclusions:

There exist  n*n=n^2 connections between n points, which is easy do demonstrate.

As an exmple we use only a network with 3 points:

  • the points are numbered  1, 2, 3
  • the connections are numbered, using 2 figures: the first is the starting point and the second the target point

__1   2    3
1  11 12  13
2  21 22 23
3  31 32 33

In the table the numbers of the points are in row 1 and in column 1.

The connections are in the other cells of the table.

  • 11, 22 and 33  are connections of  the 3 points with themselves, which we call feedback loops.
  • 12, 13, 23  are the reverse connections  of  21, 31 and 32

If we can exclude all feedback loops  and if the directions are not of interest, then there are:

m =  (n^2-n )/2= n ( n-1)/2

connections between n points;  in the example with 3 points, there are  3 connections.

Definiton 2:  A path consists of at least 3 points, which are connected, so that each point has one or 2 neighbour points. There are 2 points in a path, with only 1 neighour: the starting and the target point.

Convention:

If an information network has maximal 9 points, then we can use an abbreviation, to write paths:

Example:

  • 123  is the path, which starts at point 1 over point 2 to point 3
  • 35789 is the path, which starts at 3, goes over 5,7,8 to point 9

If there are more than 9 points in an information network, then we would run into trouble:

  • 12411 could mean 1-2-4-11   or  1-2-4-1-1  and with more than 9 points, we will therefore use this notation for paths.

Definition 3: A complete network without feedback loops and reverse connections is called a  one-direction complete network.

Now it starts, to get interesting:

  • We ask ourselves, how many paths exist in a complete networks and in one direction complete network  with 3, 4 etc.  up to 9 points

There are two methods, to answer this question:

  • we make sketches of all paths
  • we make algebraic calculations

For networks with 3 or even 4 points, sketches could be used. But with 5 or more points,we will find, that this is almost impossible, because there exist too many paths.

That is a typical problem, when objects can be combined in many different ways. The number of combinations increases dramatically, if the number of points increases.

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