In [1]:
import networkx as nx
import matplotlib.pyplot as plt
%matplotlib inline
In [2]:
GA = nx.read_gexf('../data/ga_graph.gexf')
The degree of a node is the number of other nodes to which it is connected.
NetworkX's degree centrality is calculated by taking the degree of the node and dividing by n-1 where where n is the number of nodes in G.
⚠️ NOTE: In a directed graph, both in-degree and out-degree centrality can be calculated.
Let's find the degree of our main character Grey.
In [3]:
GA.degree("grey")
Out[3]:
Likewise, we can find the degree of each cast member.
In [4]:
# See all of them (ok on this small graph)
GA.degree()
Out[4]:
In [5]:
# Here's the top 5.
sorted(GA.degree().items(), key=lambda x:x[1], reverse=True)[:5]
Out[5]:
While knowing the raw number is great, most centrality measures are normalized between zero and one so that they can be more easily compared to one another.
For the degree centrality measure, the normalized interpretion is really intuitive:
What percentage of nodes is this node connected to?
Or for our Grey's Anatomy example:
What percentage of the cast has this character been invovled with?
Let's calculate the degree centrality for Grey.
In [6]:
# Degree for the 'Grey' node
degree_grey = GA.degree("grey") # 4 romantic partners
# Total number of nodes (excluding Grey)
total_nodes_minus_grey = len(GA.nodes())-1 # 31 characters in the cast, excluding Grey
# Degree centrality for Grey
degree_centrality_grey = (degree_grey / total_nodes_minus_grey)
print("Calculated degree centrality for Grey:", degree_centrality_grey)
# Double check
print("Networkx degree centrality for Grey:", nx.degree_centrality(GA)["grey"])
def check_equal(val1, val2):
assert (val1 == val2),"Centrality measure calculated incorrectly!"
return "Values match, good job!"
check_equal(degree_centrality_grey, nx.degree_centrality(GA)["grey"])
Out[6]:
Likewise, let's find the degree centrality for all characters.
In [7]:
degree_centrality = nx.degree_centrality(GA)
degree_centrality
Out[7]:
In [8]:
# Top 5. Percent of cast this character has been with.
sorted(degree_centrality.items(), key=lambda x: x[1], reverse=True)[:5]
Out[8]:
In [9]:
# Top 5. Total # of partners this character has been with.
sorted(GA.degree().items(), key=lambda x: x[1], reverse=True)[:5]
Out[9]:
In [10]:
# apply measurements back to Graph
nx.set_node_attributes(GA, 'degree centrality', degree_centrality)
In [11]:
GA.node['karev']
Out[11]:
Closeness Centrality measures how many "hops" it would take to reach every other node in a network (taking the shortest path). It can be informally thought as 'average distance' to all other nodes.
In NetworkX, it the reciporical of of the average value, which normalizes the value in a 0 to 1 range.
$$ C_C (u) = \frac{n - 1}{\sum_{v=1}^{n-1} d(v, u)} $$If you again take the reciporical of this, you'll find the average distance to all other nodes.
⚠️ NOTE: If the graph is not completely connected, this algorithm computes the closeness centrality for each connected part separately. The closeness centrality is normalized to (n-1)/(|G|-1) where n is the number of nodes in the connected part of graph containing the node. [Source]
Why should we care about closeness centrality?
Degree centrality measures might be criticized because they only take into account the immediate ties that an actor has, or the ties of the actor's neighbors, rather than indirect ties to all others. One actor might be tied to a large number of others, but those others might be rather disconnected from the network as a whole. In a case like this, the actor could be quite central, but only in a local neighborhood. [Source]
In our example, closeness centrality could perhaps help us understand which characters have the greatest potential to spread an infectous disease or STD across the cast (an admittedly dark plot arc).
Let's calculate the closeness centrality for Grey. First we'll start by getting the shortest paths between Grey and all other characters.
In [12]:
# Shortest path between Grey and other characters
grey_shortest_path = nx.shortest_path_length(GA)['grey']
grey_shortest_path
Out[12]:
In [13]:
# Sum of the shortest paths to all other characters
grey_sum_shortest_path = sum(grey_shortest_path.values()) # 77
# Closeness centrality for Grey
closeness_centrality_grey = (total_nodes_minus_grey / grey_sum_shortest_path)
print("Calculated closeness centrality for Grey:", closeness_centrality_grey)
# Double check
print("Networkx closeness centrality for Grey:", nx.closeness_centrality(GA)["grey"])
check_equal(closeness_centrality_grey, nx.closeness_centrality(GA)["grey"])
Interesting...our calculated measure is not the same as the one in NetworkX.
What happened here?
This error occured because the character relationship graph is not fully connected. (i.e., there are groups of characters that do not have relationships with one another).
In [14]:
# View members of different subgraphs
sorted(nx.connected_components(GA), key = len, reverse=True)
Out[14]:
To correct for this, we will use the number of nodes in the Grey subgraph instead of the total number of nodes to calculated degree centrality. Additionally, we'll normalized to (n-1)/(|G|-1) where n is the number of nodes in the connected part of graph containing the node.
In [15]:
# Number of nodes in Grey subgraph, excluding Grey
total_nodes_minus_grey_sub = len(grey_shortest_path)-1 # 23
# Closeness centrality for Grey (unnormalized)
closeness_centrality_grey = (total_nodes_minus_grey_sub / grey_sum_shortest_path) # ~0.2987
# Closeness centrality for Grey (normalized)
closeness_centrality_grey_normalized = closeness_centrality_grey * (total_nodes_minus_grey_sub/total_nodes_minus_grey)
print("Calculated closeness centrality for Grey (normalized):", closeness_centrality_grey_normalized)
# Double check
print("Networkx closeness centrality for Grey:", nx.closeness_centrality(GA)["grey"])
check_equal(closeness_centrality_grey_normalized, nx.closeness_centrality(GA)["grey"])
Out[15]:
Let's find the closeness centrality for all characters.
In [16]:
closeness_centrality = nx.closeness_centrality(GA)
closeness_centrality
Out[16]:
In [17]:
# top 5
sorted(closeness_centrality.items(), key=lambda x: x[1], reverse=True)[:5]
Out[17]:
In [18]:
# apply measurements back to Graph
nx.set_node_attributes(GA, 'closeness centrality', closeness_centrality)
In [19]:
# average distance of torres:
1 / closeness_centrality['torres']
Out[19]:
In [20]:
7/(len(GA.nodes()) - 1)
Out[20]:
Betweenness centrality quantifies the number of times a node acts as a bridge (or "broker") along the shortest path between two other nodes.
In this conception, vertices that have a high probability to occur on a randomly chosen shortest path between two randomly chosen vertices have a high betweenness.
$$ C_B(v) =\sum_{s,t \in V} \frac{\sigma(s, t|v)}{\sigma(s, t)} $$where ${\sigma(s, t)}$ is total number of shortest paths from node ${s}$ to node ${t}$ and ${\sigma(s, t|v)}$ is the number of those paths that pass through ${v}$.
Why is betweeness centrality important?
Suppose that I want to influence you by sending you information, or make a deal to exchange some resources. But, in order to talk to you, I must go through an intermediary. For example, let's suppose that I wanted to try to convince the Chancellor of my university to buy me a new computer. According to the rules of our bureaucratic hierarchy, I must forward my request through my department chair, a dean, and an executive vice chancellor. Each one of these people could delay the request, or even prevent my request from getting through. This gives the people who lie "between" me and the Chancellor power with respect to me... Having more than one channel makes me less dependent, and, in a sense, more powerful. [Source]
While this metric seems less relevent to our particular network, let's create a hypothetical situation:
To engage with a new romantic partner, you needed permission from at least one of their former partners and you could only send your request through existing partners (awkward 😬). Betweeness centrality would tell you which actors had the most effective veto power to thwart random requests made by a member to another random member in the network.
In [21]:
betweeness_centrality = nx.betweenness_centrality(GA)
betweeness_centrality
Out[21]:
In [22]:
# top 5
sorted(betweeness_centrality.items(), key=lambda x: x[1], reverse=True)[:5]
Out[22]:
A node is high in eigenvector centrality if it is connected to many other nodes who are themselves well connected. Eigenvector centrality for each node is simply calculated as the proportional eigenvector values of the eigenvector with the largest eigenvalue.
Middle Left ("C"): Eigenvector Centrality. Middle Right ("D"): Degree Centrality
In [23]:
eigenvector_centrality = nx.eigenvector_centrality_numpy(GA)
eigenvector_centrality
Out[23]:
In [24]:
max_value = max(eigenvector_centrality.items(), key=lambda x: x[1])
ec_scaled = {}
for k in eigenvector_centrality.keys():
ec_scaled[k] = eigenvector_centrality[k] / max_value[1]
# Scaled by the most central character (karev)
sorted(ec_scaled.items(), key=lambda x:x[1], reverse=True)[0:5]
Out[24]: