In the last section we laid down the basics of our language for talking about networks
by looking at graph theory, in this module we are going to continue to expand on our
vocabulary but this time focusing on how we model the connectivity of a node or between
nodes within a graph.
As we mentioned connectivity is a key concept within the network paradigm, we often try
to measure the significance of things in terms of the quantity to one of their properties
but within networks how connected an individual node is becomes a key metric of its significant
within the network.
So an important question we will often be asking is how connected is any given node
in the network?
And this is termed its degree of connectivity.
The degree of a node in a network is a measure of the number of connections it has to other
nodes.
This degree of connectivity can be interpreted in terms of the immediate likelihood of a
node catching whatever is flowing through the network, so for example the higher your
degree within a given social network the more likely you are to hear about some juicy piece
of gossip, because you have many more channels through which to intercept it, of cause this
works both ways as it might not be juicy gossip that is spreading on this network, but instead
a virus, connectivity is often interpreted as a positive thing but not always.
If we are analyzing an undirected and unweight network, a node’s degree of connectivity
will then simply be a summation of all the links that the node has.
If the graph is directed then we can refine our analysis by dividing this into a measure
for the amount of in and out links, so returning to our example of nations trading the in degree
of any node would be the total number of import relations it has with other nations and the
out degree would be the total number of exporting relations it has.
If this is a weighted graph we can then of cause refine our model farther by placing
quantitative values on each edge.
If an edge exists between node A and B then we say they are adjacent, so if we take a
map of a subway we could say that each station or node is adjacent to any other station that
is just one stop away from it.
We can then capture all the relations within a network by creating an adjacency matrix.
This is a non-mathematical introductory course so we will not be going into matrixes but
to just give you a quick insight into how this is represent.
We can create a simple 2 by 2 matrix to capture the connections within a network by placing
a 1 at the cross section between two nodes if they are adjacent and a 0 if not, with
the end result being a table of all the connections within the system and this will give you an
idea of what a graph looks like to a computer.
Another thing we might be interested in is looking at how two nodes in a network are
connected, that is to say the channel or paths through a network from one node to another
and this is called a walk.
A walk on a graph is a sequence of adjacent vertices where repetition is allowed, with
a walk we are simply going from one node to the next along a sequences of edges.
A path is a walk without revisiting any nodes that is a sequence of links from the first
node to last without repetition.
So as a quick example of why this might be of interest to us we could cite the so called
travelling salesman problem, which involves a salesman that has to visit a number of different
cities within a particular region, he of cause wants to avoid walks where he will be retracing
the same ground and try and find a path that will not involve any repetition of the cities
he has to visit, their are a number of different algorithms for achieving this but we won't
go into them here.
Our travelling salesman will also be interested in finding the shortest path between each
place he has to visit, this shortest path between two nodes on a graph is called the
geodesic and it represents the fewest number of links we need to traverse in order to get
from any given node to another.