Description

Last week we learned how to use iterative techniques to find the dominant eigenvector for a system, and used this to analyze a Markov process. This week we are going to further explore these techniques and see how they can be used to analyze networks. Simply put, a network consists of a collection of nodes and edges, where each edge can be thought of as a connection which joins two nodes. We often represent networks graphically, by drawing a dot for each node, and a line for each edge as shown below in Figure 1. Networks are sometimes referred to as graphs in mathematics, and the nodes are sometimes referred to as vertices.

Networks are incredibly useful in real world applications, as they allow us to represent relationships between objects in a wide variety of different systems. For example, a data scientist might use networks to represent connections on social media, by displaying each Facebook user as a node of the network, with an edge joining two nodes when the corresponding users are Facebook friends (see Figure 2). Urban planners may use networks to design important infrastructure, by representing water pump station as nodes, and water mains as edges. Law enforcement officials may use networks to understand criminal organizations, with gang members represented by nodes, and known affiliations between members represented by edges. Finally, we could use networks to represent Hollywood actors and actresses, connecting two actors/actresses if they’ve starred in a movie together. This would allow us to answer definitively whether all of Hollywood really is 6 degrees from Kevin Bacon. By introducing a slight variation on the idea of a network as defined above, we can capture other types of relationships. For example, we could add a direction to each of our edges, and think of them as providing a connection from one node, to another node. We indicate the direction of each edge by adding an arrow, and call the resulting network a directed network (see Figure 5). Directed networks allow us to model relationships that are not symmetric. For example, the food chain could be represented as a directed network, with each node representing a different species, and a directed edge added which travels from each predator to the prey it is known to eat. In this network there would be an edge from the node representing lions to the node representing gazelles, because lions are known to eat gazelles, but not one going the other way