# 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.