Network Connections

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.

Add a Comment

Your email address will not be published. Required fields are marked *