Network Science Week 5:
Measures of Centrality

Overview, Activity, and Discussion

Overview

Suppose you are investigating a social network (draw an edge between two people if they are considered "friends") and you'd like to rank the people in terms of how influential they are to the rest of the network. You'll find there are several ways to define and measure "influence" in the network. For instance, you might consider the person with the most connections (degree) to be most important - this gives rise to degree centrality. Then again, what if a person doesn't have a high number of connections (relative to the rest of the vertices) but they are friends with people who themselves are influential (i.e. take into account not just how many people you know but who you know).

In an extreme example, consider a social network of 5 thousand people that contains 100 people (Group A) that are each friends with 100 people and which cover the network (each person is a friend to one of these special 100 people). Suppose further that there are 5 people (Group B) that are only friends to 20 people each, but each of those 20 people are from Group A. Even further, perhaps there is one person (Star) who is friends with and only with the people in Group B. In this case, Star might have influence over Group B who in turn have influence over Group A, who in turn influence the rest of the network. While star only has five friends, each of those friends is highly influential to the rest of the network. In this case, degree is no longer a realistic proxy for influence. To measure this type of influence we introduce eigenvector centrality.

Of course, there are several ways to define centrality by way of eigenvectors - especially if our network is directed. So, there are several similar centrality measures related to eigenvector centrality: Katz centrality, PageRank, and HITS (Hubs and Authorities).

In a different setting, say the Western States Power Grid network, we might consider a vertex important if its removal drastically changes the route power takes as it flows through the network. The measure we care most about here is called betweenness centrality, which measures how many shortest paths on which each vertex lies.

In yet another setting, a vertex might be important if it is (graph theoretically) close to ever other vertex in the network. An important vertex may then correspond to a vertex with high eccentricity, i.e., the vertex is central in a purely graph theoretic sense. Similar to this is the concept of closeness centrality.

Depending on the context of the network, the type of graph model, and the research question being investigated, we are led to a particular measure of importance referred to as centrality. This week, we encounter many popular measures of centrality, see how each is computed, and understand the contexts in which each should be use. Ultimately, we seek to understand what each of these centrality measures says about our network.

To make progress on the learning objectives, you should complete the following tasks this week:

Read Newman section 7.1
Watch the related content videos.
Read the instructions for Activity for Week 5 and watch the associated demonstration video.
Complete and submit Activity for Week 5
Make a post and reply to the discussion prompt

Learning Objectives

By the end of the week, you should be able to:

Describe, define, and contextualize each of the centrality measures encountered this week (degree, eigenvector, Katz, PageRank, Hubs/Authorities, closeness, betweenness).
Given a network together with a research question under investigation, choose an appropriate centrality measure and interpret the results in the context of the network.
Compute each of the centrality measures either by hand, using software, or by working with a matrix representation of the network.

Activity

Activity for Week 5.pdf

Discussion Prompt

We've seen many different types of centrality this week. It is important that we understand not only (1) the extent to which each centrality applies to a given network and (2) what each centrality score reveals about the network, but also (3) to observe differences between the types of centrality. In this way, we seek to gain a holistic perspective on our network and reveal the various forces at work.

Make a post in response to each of the prompts below and reply to at least one other's post this week.

Choose a centrality score that is important for your network, and report on the information it reveals about your network.
Tell us about an observation you find interesting that is revealed by comparing types of centrality in your network.