Networks? Graphs?¶
A mathematical structure used to model pairwise relations between objects, where the objects are usually called nodes and the relationship between them edges.
G = (V, E)
V = set of nodes/vetices
E = set of (x, y) edges
import networkx as nx
import matplotlib.pyplot as plt
import numpy as np
%matplotlib inline
nx.draw_circular(nx.erdos_renyi_graph(10, 0.4), with_labels=True)
# Creating a graph/network object
G = nx.Graph()
# accessing nodes
G.nodes()
# accessing edges
G.edges()
# Let's create a recipe network
# G.add_node('Tomato')
# G.add_node('Eggs')
# G.add_node('Lamb')
# G.add_node('Chicken')
G.add_nodes_from(['Tomato', 'Eggs', 'Lamb', 'Chicken'])
# G.add_edge('Tomato', 'Eggs')
# G.add_edge('Lamb', 'Tomato')
# G.add_edge('Chicken', 'Tomato')
G.add_edges_from([('Tomato', 'Eggs'), ('Tomato', 'Lamb'), ('Tomato', 'Chicken')])
G.nodes()
G.edges()
nx.draw(G, with_labels=True)
# any hashable object can be a node in the network
G.add_node([1, 2])
Let's work on a read world network.¶
Arxiv GR-QC (General Relativity and Quantum Cosmology) collaboration network is from the e-print arXiv and covers scientific collaborations between authors papers submitted to General Relativity and Quantum Cosmology category. If an author i co-authored a paper with author j, the graph contains a undirected edge from i to j. If the paper is co-authored by k authors this generates a completely connected (sub)graph on k nodes.
# If six authors wrote a paper together, they will have a complete graph
nx.draw(nx.complete_graph(6))
# create a author graph from the dataset
import csv
authors_graph = nx.Graph()
with open('CA-GrQc.txt', 'r') as f:
reader = csv.reader(f, delimiter='\t')
for row in reader:
authors_graph.add_edge(row[0], row[1])
print(authors_graph.number_of_edges())
print(authors_graph.number_of_nodes())
Can we find the most influential researcher in this network?¶
Something which is not so much dependent on citations.
How do we evaluate the importance of some individuals in a network?¶
Within a social network, there will be certain individuals which perform certain important functions. For example, there may be hyper-connected individuals who are connected to many, many more people. They would be of use in the spreading of information. Alternatively, if this were a disease contact network, identifying them would be useful in stopping the spread of diseases. How would one identify these people?
Exercise¶
Create a list of (node, degree of node) tuples and find the node with maximum degree.
degree of node = number of neighbors
result = [(node, len(list(authors_graph.neighbors(node)))) for node in authors_graph.nodes()]
max(result, key=lambda node:node[1])
The degree of a node translates to degree centrality (which is a normalised version of degree)
nx.degree_centrality(authors_graph)
Exercise¶
Plot a histogram of degree centrality of authors_graph.
Hint: plt.hist(list_of_values) will plot a histogram
(count vs degree centrality)
plt.hist(list(nx.degree_centrality(authors_graph).values()))
plt.show()
G = nx.erdos_renyi_graph(1000, 0.3, seed=1)
plt.hist(list(nx.degree_centrality(G).values()))
plt.show()
H = nx.barabasi_albert_graph(1000, 30, 0.3)
# K = nx.powerlaw_cluster_graph(1000, 30, 0.3)
plt.hist(list(nx.degree_centrality(H).values()))
plt.show()
# plt.hist(list(nx.degree_centrality(K).values()))
# plt.show()
Let's have a look at Connected Components of a graph.¶
In graph theory, a connected component (or just component) of an undirected graph is a subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices in the supergraph.
G = nx.erdos_renyi_graph(10, 0.15, seed=1)
nx.draw(G, with_labels=True)
print([len(c) for c in sorted(nx.connected_components(authors_graph), key=len, reverse=True)])
graphs = [c for c in sorted(nx.connected_component_subgraphs(authors_graph), key=len, reverse=True)]
len(graphs[0])
nx.draw(graphs[10])
Shortest Path in the network¶
nx.draw(nx.erdos_renyi_graph(10, 0.15, seed=1), with_labels=True)
print(nx.shortest_path(graphs[0], '22504', '23991'))
print(len(nx.shortest_path(graphs[0], '22504', '23991')))
print(nx.shortest_path_length(graphs[0], '22504', '23991'))
Exercise¶
Six degrees of separation, Erdos Number, Bacon Number!!¶
Find the '22504' number of the graph authors_graph, if there is no connection between nodes then give it the number -1.
Also plot a histogram of the '22504' number.
Find the average shortest path length in the first component i.e. graphs[0]
HINT: nx.shortest_path_length
d = {}
for node in authors_graph.nodes():
try:
d[node] = nx.shortest_path_length(authors_graph, '22504', node)
except:
d[node] = -1
plt.hist(list(d.values()))
plt.show()
Let's change gears and talk about Game of thrones or shall I say Network of Thrones.¶
It is suprising right? What is the relationship between a fatansy TV show/novel and network science or python(it's not related to a dragon).
If you haven't heard of Game of Thrones, then you must be really good at hiding. Game of Thrones is the hugely popular television series by HBO based on the (also) hugely popular book series A Song of Ice and Fire by George R.R. Martin. In this notebook, we will analyze the co-occurrence network of the characters in the Game of Thrones books. Here, two characters are considered to co-occur if their names appear in the vicinity of 15 words from one another in the books.
Andrew J. Beveridge, an associate professor of mathematics at Macalester College, and Jie Shan, an undergraduate created a network from the book A Storm of Swords by extracting relationships between characters to find out the most important characters in the book(or GoT).
The dataset is publicly avaiable for the 5 books at https://github.com/mathbeveridge/asoiaf. This is an interaction network and were created by connecting two characters whenever their names (or nicknames) appeared within 15 words of one another in one of the books. The edge weight corresponds to the number of interactions.
Credits:
Blog: https://networkofthrones.wordpress.com
Math Horizons Article: https://www.maa.org/sites/default/files/pdf/Mathhorizons/NetworkofThrones%20%281%29.pdf
import pandas as pd
import networkx as nx
import matplotlib.pyplot as plt
from matplotlib import cm
import community
import numpy as np
import warnings
warnings.filterwarnings('ignore')
%matplotlib inline
Let's load in the datasets¶
book1 = pd.read_csv('data/asoiaf-book1-edges.csv')
book2 = pd.read_csv('data/asoiaf-book2-edges.csv')
book3 = pd.read_csv('data/asoiaf-book3-edges.csv')
book4 = pd.read_csv('data/asoiaf-book4-edges.csv')
book5 = pd.read_csv('data/asoiaf-book5-edges.csv')
The resulting DataFrame book1 has 5 columns: Source, Target, Type, weight, and book. Source and target are the two nodes that are linked by an edge. A network can have directed or undirected edges and in this network all the edges are undirected. The weight attribute of every edge tells us the number of interactions that the characters have had over the book, and the book column tells us the book number.
book1.head()
Once we have the data loaded as a pandas DataFrame, it's time to create a network. We create a graph for each book. It's possible to create one MultiGraph instead of 5 graphs, but it is easier to play with different graphs.
G_book1 = nx.Graph()
G_book2 = nx.Graph()
G_book3 = nx.Graph()
G_book4 = nx.Graph()
G_book5 = nx.Graph()
Let's populate the graph with edges from the pandas DataFrame.
for row in book1.iterrows():
G_book1.add_edge(row[1]['Source'], row[1]['Target'], weight=row[1]['weight'], book=row[1]['book'])
for row in book2.iterrows():
G_book2.add_edge(row[1]['Source'], row[1]['Target'], weight=row[1]['weight'], book=row[1]['book'])
for row in book3.iterrows():
G_book3.add_edge(row[1]['Source'], row[1]['Target'], weight=row[1]['weight'], book=row[1]['book'])
for row in book4.iterrows():
G_book4.add_edge(row[1]['Source'], row[1]['Target'], weight=row[1]['weight'], book=row[1]['book'])
for row in book5.iterrows():
G_book5.add_edge(row[1]['Source'], row[1]['Target'], weight=row[1]['weight'], book=row[1]['book'])
books = [G_book1, G_book2, G_book3, G_book4, G_book5]
Let's have a look at these edges.
list(G_book1.edges(data=True))[16]
list(G_book1.edges(data=True))[400]
Finding the most important node i.e character in these networks.¶
Is it Jon Snow, Tyrion, Daenerys, or someone else? Let's see! Network Science offers us many different metrics to measure the importance of a node in a network as we saw in the first part of the tutorial. Note that there is no "correct" way of calculating the most important node in a network, every metric has a different meaning.
First, let's measure the importance of a node in a network by looking at the number of neighbors it has, that is, the number of nodes it is connected to. For example, an influential account on Twitter, where the follower-followee relationship forms the network, is an account which has a high number of followers. This measure of importance is called degree centrality.
Using this measure, let's extract the top ten important characters from the first book (book[0]) and the fifth book (book[4]).
deg_cen_book1 = nx.degree_centrality(books[0])
deg_cen_book5 = nx.degree_centrality(books[4])
sorted(deg_cen_book1.items(), key=lambda x:x[1], reverse=True)[0:10]
sorted(deg_cen_book5.items(), key=lambda x:x[1], reverse=True)[0:10]
# Plot a histogram of degree centrality
plt.hist(list(nx.degree_centrality(G_book4).values()))
plt.show()
d = {}
for i, j in dict(nx.degree(G_book4)).items():
if j in d:
d[j] += 1
else:
d[j] = 1
x = np.log2(list((d.keys())))
y = np.log2(list(d.values()))
plt.scatter(x, y, alpha=0.9)
plt.show()
Exercise¶
Create a new centrality measure, weighted_degree(Graph, weight) which takes in Graph and the weight attribute and returns a weighted degree dictionary. Weighted degree is calculated by summing the weight of the all edges of a node and find the top five characters according to this measure.
def weighted_degree(G, weight):
result = dict()
for node in G.nodes():
weight_degree = 0
for n in G.edges([node], data=True):
weight_degree += n[2]['weight']
result[node] = weight_degree
return result
plt.hist(list(weighted_degree(G_book1, 'weight').values()))
plt.show()
sorted(weighted_degree(G_book1, 'weight').items(), key=lambda x:x[1], reverse=True)[0:10]
Let's do this for Betweeness centrality and check if this makes any difference¶
Haha, evil laugh
# First check unweighted, just the structure
sorted(nx.betweenness_centrality(G_book1).items(), key=lambda x:x[1], reverse=True)[0:10]
# Let's care about interactions now
sorted(nx.betweenness_centrality(G_book1, weight='weight').items(), key=lambda x:x[1], reverse=True)[0:10]
PageRank¶
The billion dollar algorithm, PageRank works by counting the number and quality of links to a page to determine a rough estimate of how important the website is. The underlying assumption is that more important websites are likely to receive more links from other websites.
# by default weight attribute in pagerank is weight, so we use weight=None to find the unweighted results
sorted(nx.pagerank_numpy(G_book1, weight=None).items(), key=lambda x:x[1], reverse=True)[0:10]
sorted(nx.pagerank_numpy(G_book1, weight='weight').items(), key=lambda x:x[1], reverse=True)[0:10]
cor = pd.DataFrame.from_records([nx.pagerank_numpy(G_book1, weight='weight'), nx.betweenness_centrality(G_book1, weight='weight'), weighted_degree(G_book1, 'weight'), nx.degree_centrality(G_book1)])
# cor.T
cor.T.corr()
Evolution of importance of characters over the books¶
According to degree centrality the most important character in the first book is Eddard Stark but he is not even in the top 10 of the fifth book. The importance changes over the course of five books, because you know stuff happens ;)
Let's look at the evolution of degree centrality of a couple of characters like Eddard Stark, Jon Snow, Tyrion which showed up in the top 10 of degree centrality in first book.
We create a dataframe with character columns and index as books where every entry is the degree centrality of the character in that particular book and plot the evolution of degree centrality Eddard Stark, Jon Snow and Tyrion. We can see that the importance of Eddard Stark in the network dies off and with Jon Snow there is a drop in the fourth book but a sudden rise in the fifth book
evol = [nx.degree_centrality(book) for book in books]
evol_df = pd.DataFrame.from_records(evol).fillna(0)
evol_df[['Eddard-Stark', 'Tyrion-Lannister', 'Jon-Snow']].plot()
set_of_char = set()
for i in range(5):
set_of_char |= set(list(evol_df.T[i].sort_values(ascending=False)[0:5].index))
set_of_char
Exercise¶
Plot the evolution of weighted degree centrality of the above mentioned characters over the 5 books, and repeat the same exercise for betweenness centrality.
evol_df[list(set_of_char)].plot(figsize=(29,15))
evol = [nx.betweenness_centrality(graph, weight='weight') for graph in [G_book1, G_book2, G_book3, G_book4, G_book5]]
evol_df = pd.DataFrame.from_records(evol).fillna(0)
set_of_char = set()
for i in range(5):
set_of_char |= set(list(evol_df.T[i].sort_values(ascending=False)[0:5].index))
evol_df[list(set_of_char)].plot(figsize=(19,10))
So what's up with Stannis Baratheon?¶
nx.draw(nx.barbell_graph(5, 1), with_labels=True)
sorted(nx.degree_centrality(G_book5).items(), key=lambda x:x[1], reverse=True)[:5]
sorted(nx.betweenness_centrality(G_book5).items(), key=lambda x:x[1], reverse=True)[:5]
Community detection in Networks¶
A network is said to have community structure if the nodes of the network can be easily grouped into (potentially overlapping) sets of nodes such that each set of nodes is densely connected internally.
We will use louvain community detection algorithm to find the modules in our graph.
plt.figure(figsize=(15, 15))
partition = community.best_partition(G_book1)
size = (len(set(partition.values())))
pos = nx.kamada_kawai_layout(G_book1)
count = 0
colors = [cm.jet(x) for x in np.linspace(0, 1, size)]
for com in set(partition.values()):
list_nodes = [nodes for nodes in partition.keys()
if partition[nodes] == com]
nx.draw_networkx_nodes(G_book1, pos, list_nodes, node_size = 100, node_color=colors[count])
count = count + 1
nx.draw_networkx_edges(G_book1, pos, alpha=0.2)
plt.show()
d = {}
for character, par in partition.items():
if par in d:
d[par].append(character)
else:
d[par] = [character]
d
nx.draw(nx.subgraph(G_book1, d[3]))
nx.draw(nx.subgraph(G_book1, d[1]))
nx.density(G_book1)
nx.density(nx.subgraph(G_book1, d[4]))
nx.density(nx.subgraph(G_book1, d[4]))/nx.density(G_book1)
Exercise¶
Find the most important node in the partitions according to degree centrality of the nodes.
max_d = {}
deg_book1 = nx.degree_centrality(G_book1)
for group in d:
temp = 0
for character in d[group]:
if deg_book1[character] > temp:
max_d[group] = character
temp = deg_book1[character]
max_d
A bit about power law in networks¶
G_random = nx.erdos_renyi_graph(100, 0.1)
nx.draw(G_random)
G_ba = nx.barabasi_albert_graph(100, 2)
nx.draw(G_ba)
# Plot a histogram of degree centrality
plt.hist(list(nx.degree_centrality(G_random).values()))
plt.show()
plt.hist(list(nx.degree_centrality(G_ba).values()))
plt.show()
G_random = nx.erdos_renyi_graph(2000, 0.2)
G_ba = nx.barabasi_albert_graph(2000, 20)
d = {}
for i, j in dict(nx.degree(G_random)).items():
if j in d:
d[j] += 1
else:
d[j] = 1
x = np.log2(list((d.keys())))
y = np.log2(list(d.values()))
plt.scatter(x, y, alpha=0.9)
plt.show()
d = {}
for i, j in dict(nx.degree(G_ba)).items():
if j in d:
d[j] += 1
else:
d[j] = 1
x = np.log2(list((d.keys())))
y = np.log2(list(d.values()))
plt.scatter(x, y, alpha=0.9)
plt.show()
