Assignment 3

In this assignment you will explore measures of centrality on two networks, a friendship network in Part 1, and a blog network in Part 2.

Part 1

Answer questions 1-4 using the network G1, a network of friendships at a university department. Each node corresponds to a person, and an edge indicates friendship.

The network has been loaded as networkx graph object G1.

import networkx as nx

G1 = nx.read_gml('assets/friendships.gml')

Question 1

Find the degree centrality, closeness centrality, and betweeness centrality of node 100.

This function should return a tuple of floats (degree_centrality, closeness_centrality, betweenness_centrality).

def answer_one():
    # YOUR CODE HERE
    return (nx.degree_centrality(G1)[100], nx.closeness_centrality(G1)[100], nx.betweenness_centrality(G1)[100])

ans_one = answer_one()
assert type(ans_one) == tuple, "You must return a tuple"

Use centrality measures to answer questions 2-4

Question 2

Suppose you are employed by an online shopping website and are tasked with selecting one user in network G1 to send an online shopping voucher to. We expect that the user who receives the voucher will send it to their friends in the network. You want the voucher to reach as many nodes as possible. The voucher can be forwarded to multiple users at the same time, but the travel distance of the voucher is limited to one step, which means if the voucher travels more than one step in this network, it is no longer valid. Apply your knowledge in network centrality to select the best candidate for the voucher.

This function should return an integer, the chosen node.

def answer_two():
    # YOUR CODE HERE
    dc = nx.degree_centrality(G1)
    max_dc = max(dc.items(), key=lambda x: x[1])
    return max_dc[0]

ans_two = answer_two()

Question 3

Now the limit of the voucher’s travel distance has been removed. Because the network is connected, regardless of who you pick, every node in the network will eventually receive the voucher. However, we now want to ensure that the voucher reaches nodes as quickly as possible (i.e. in the fewest number of hops). How will you change your selection strategy? Write a function to tell us who is the best candidate in the network under this condition.

This function should return an integer, the chosen node.

def answer_three():
    # YOUR CODE HERE
    cc = nx.closeness_centrality(G1)
    max_cc = max(cc.items(), key = lambda x: x[1])
    return max_cc[0]

ans_three = answer_three()

Question 4

Assume the restriction on the voucher’s travel distance is still removed, but now a competitor has developed a strategy to remove a person from the network in order to disrupt the distribution of your company’s voucher. You competitor plans to remove people who act as bridges in the network. Identify the best possible person to be removed by your competitor?

This function should return an integer, the chosen node.

def answer_four():
    # YOUR CODE HERE
    bc = nx.betweenness_centrality(G1)
    max_bc = max(bc.items(), key = lambda x: x[1])
    return max_bc[0]

ans_four = answer_four()

Part 2

G2 is a directed network of political blogs, where nodes correspond to a blog and edges correspond to links between blogs. Use your knowledge of PageRank and HITS to answer Questions 5-9.

G2 = nx.read_gml('assets/blogs.gml')

Question 5

Apply the Scaled Page Rank Algorithm to this network. Find the Page Rank of node 'realclearpolitics.com' with damping value 0.85.

This function should return a float.

def answer_five():
    # YOUR CODE HERE
    pr = nx.pagerank(G2, alpha= 0.85)
    return pr['realclearpolitics.com']

ans_five = answer_five()

Question 6

Apply the Scaled Page Rank Algorithm to this network with damping value 0.85. Find the 5 nodes with highest Page Rank.

This function should return a list of the top 5 blogs in desending order of Page Rank.

def answer_six():
    # YOUR CODE HERE
    pg_rank = nx.pagerank(G2, alpha=0.85)
    sorted_pg_rank = sorted(pg_rank.items(), reverse=True, key=lambda x: x[1])
    top_5 = sorted_pg_rank[:5]
    top_5_blogs = [blog for blog, pg_rank in top_5]
    return top_5_blogs

ans_six = answer_six()
assert type(ans_six) == list, "You must return a list"

Question 7

Apply the HITS Algorithm to the network to find the hub and authority scores of node 'realclearpolitics.com'.

Your result should return a tuple of floats (hub_score, authority_score).

def answer_seven():
    # YOUR CODE HERE
    hits = nx.hits(G2)
    hub_score = hits[0]['realclearpolitics.com']
    auth_score = hits[1]['realclearpolitics.com']
    return (hub_score, auth_score)

ans_seven = answer_seven()
assert type(ans_seven) == tuple, "You must return a tuple"

c:\Users\Don\AppData\Local\Programs\Python\Python311\Lib\site-packages\networkx\algorithms\link_analysis\hits_alg.py:78: FutureWarning: adjacency_matrix will return a scipy.sparse array instead of a matrix in Networkx 3.0.
  A = nx.adjacency_matrix(G, nodelist=list(G), dtype=float)

Question 8

Apply the HITS Algorithm to this network to find the 5 nodes with highest hub scores.

This function should return a list of the top 5 blogs in desending order of hub scores.

def answer_eight():
    # YOUR CODE HERE
    hits = nx.hits(G2)
    sorted_hubs = sorted(hits[0].items(), reverse = True, key= lambda x: x[1])
    top_5 = sorted_hubs[:5]
    return [blog for blog, hub_score in top_5]

ans_eight = answer_eight()
assert type(ans_eight) == list, "You must return a list"

Question 9

Apply the HITS Algorithm to this network to find the 5 nodes with highest authority scores.

This function should return a list of the top 5 blogs in desending order of authority scores.

def answer_nine():
    # YOUR CODE HERE
    hits = nx.hits(G2)
    sorted_auth = sorted(hits[1].items(), reverse = True, key = lambda x: x[1])
    top_5 = sorted_auth[:5]
    return [blog for blog, auth_score in top_5]

ans_nine = answer_nine()
assert type(ans_nine) == list, "You must return a list"