Degree of Connectivity
The degree of connectivity to a node in a network is a measure of the number of in and out links the node 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.1 For example, the higher one’s degree of connectivity within a given social network the more likely you are to hear about some piece of news that is being shared, because you have many more channels through which to intercept it. Of course, this works both ways as it might not be news that is spreading on the network, but instead a virus.
If we are analyzing an undirected and unweighted 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 of the amount of in and out links. With an 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 course, refine our model further 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. 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; this is how a graph is represented in computer code.
Path & Geodesic
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 sequence of edges. A path is a walk without revisiting any nodes, that is a sequence of links from the first node to the last without repetition. As an example of why this might be of interest to us, we could cite the so-called traveling salesman problem, which involves a salesman that has to visit a number of different cities within a particular region. He, of course, 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. The traveling 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.