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.
computer science
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
