<jupyter_start><jupyter_text>SD212: Graph mining Lab 5: PageRankYou will learn how to compute, use and interpret various PageRank metrics of a node in a graph. You **must** be connected to Telecom ParisTech network!  Getting started<jupyter_code>from connector import Connector
import operator
import heapq
import warnings
warnings.filterwarnings('ignore')
base_url = 'http://172.16.58.3:8234'
lab_id = 'lab5'<jupyter_output><empty_output><jupyter_text>To do* Enter your login and test it using question 0<jupyter_code># Enter your login (last name followed by first letter of first name)
login = 'zhuf'
connector = Connector(base_url, lab_id, login)
get_question = connector.get_question
post_answer = connector.post_answer
post_text = connector.post_text
get_question(0)<jupyter_output>Welcome!<jupyter_text>Import<jupyter_code>import networkx as nx<jupyter_output><empty_output><jupyter_text>The documentation is available [here](https://networkx.readthedocs.io/en/stable/).<jupyter_code>%pylab notebook
import numpy as np
from scipy import sparse as sp<jupyter_output><empty_output><jupyter_text>1. PageRankThe PageRank corresponds to the stationary distribution of a random walk with restart probability $1-\alpha$. Unless otherwise specified, we take the default value $\alpha = 0.85$ and the restart probability distribution uniform over the set of nodes.  Toy graphConsider the following graph:<jupyter_code>edgelist = [(7,5),(5,3),(3,7),(4,5),(4,6),(7,4),(1,6),(9,8),(7,8),(6,1),(2,9),(8,2)]
G = nx.DiGraph()
G.add_edges_from(edgelist)
figure()
nx.draw(G,with_labels = True)<jupyter_output><empty_output><jupyter_text>To do* Answer question 1 **(0.5 point)*** Check the PageRank of each node using the `networkx` function (see below)* Add edges 2->5 and 6->3 and observe the impact on the top-3 nodes* Do the same experiment with betweenness centrality* Answer question 2 **(open answer)**<jupyter_code>get_question(1)
answer = 6
post_answer(1,answer)
pg_score = nx.pagerank(G, 0.85)
sorted(pg_score.items(), key=operator.itemgetter(1), reverse= True)
PR = nx.pagerank(G)
get_question(2)
post_text(2)<jupyter_output><empty_output><jupyter_text>Path graph Now consider a path graph:<jupyter_code>n = 10
G = nx.path_graph(n)
pos = [(i,0) for i in range(n)]
figure()
nx.draw(G,pos,with_labels = True)<jupyter_output><empty_output><jupyter_text>To do* What are the two best ranked nodes? Try with different values of $\alpha$* Compare with the two most central nodes (in terms of betweenness centrality)* Answer question 3 **(0.5 point)**<jupyter_code>get_question(3)
x = nx.pagerank(G,1, max_iter=100000)
answer = list(x.values())
post_answer(3,answer)<jupyter_output>This is correct!<jupyter_text>Real datasetsWe now consider the following real datasets, to be downloaded [here](http://perso.telecom-paristech.fr/~bonald/graphs/lab5.zip):* the graph of [Les Misérables](https://fr.wikipedia.org/wiki/Les_Misérables) (co-occurence of characters in chapters of the novel of <NAME>),* the graph of [Wikipedia for Schools](https://en.wikipedia.org/wiki/Wikipedia:Wikipedia_for_Schools) (links between a selection of articles from Wikipedia)* the bipartite graph of movies-actors links extracted from [YaGo](https://www.mpi-inf.mpg.de/departments/databases-and-information-systems/research/yago-naga/yago/)  To do* List the 10 best ranked nodes of Les Misérables* Compare with the 10 nodes of highest degrees and the 10 nodes of highest weights* Answer question 4 **(open answer)**<jupyter_code>G = nx.read_graphml("miserables.graphml", node_type = int)
names = nx.get_node_attributes(G, 'name')
figure()
nx.draw(G, labels = names,font_size = 8,node_size = 50,edge_color = 'gray')
get_question(4)
dictx = dict()
for x in G.edges(data=True):
    if(x[0] not in dictx):
        dictx[x[0]] = x[2]['weight']
    else:
        dictx[x[0]] += x[2]['weight']
    if(x[1] not in dictx):
        dictx[x[1]] = x[2]['weight']
    else:
        dictx[x[1]] += x[2]['weight']
x = sorted(dictx.items(), key=operator.itemgetter(1), reverse=True)[:10]

sorted(dict(G.degree()).items(), key=operator.itemgetter(1), reverse=True)[:10]
print()
for x in range(0,11):
    A = nx.pagerank(G, alpha = x * 0.1) 
    top10 = heapq.nlargest(10, A, key=A.get) 
    print(x,'\t', top10)
# 
# a = 
# b = 
# c = heapq.nlargest(10, nx.pagerank(G, alpha = 0.5).items(), key=A.get)
# d = heapq.nlargest(10, nx.pagerank(G, alpha = 0.8).items(), key=A.get)
# print(a)
# print(b)
# print(c)
# print(d)

post_text(4)<jupyter_output><empty_output><jupyter_text>To do* List the 10 best ranked nodes of Wikipedia for Schools* Compare with the 10 nodes of highest out-degrees and the 10 nodes of highest in-degrees* Answer question 5 **(0.5 point)**<jupyter_code>G = nx.read_graphml("wikipedia-schools.graphml", node_type = int)
names = nx.get_node_attributes(G, 'name')
get_question(5)
in_degree = dict(G.in_degree())
top_degree = heapq.nlargest(10, in_degree, in_degree.get)
set_degree = set([names[i] for i in top_degree])
pg = dict(nx.pagerank(G, alpha = 0.85))
pg = heapq.nlargest(10, pg, pg.get)
set_pg = set([names[i] for i in pg])
set_pg - set_degree
answer = "Latin"
post_answer(5,answer)<jupyter_output>This is correct!<jupyter_text>2. Sparse matrices You will now implement your own PageRank algorithm. Graphs can be efficiently represented by their (weighted) adjacency matrix in sparse format:<jupyter_code>A = nx.adjacency_matrix(G)
type(A)<jupyter_output><empty_output><jupyter_text>If the nodes are not indexed from 0 to $n-1$, you need to keep a list of nodes:<jupyter_code>nodes = list(G.nodes())
n = len(nodes)
nodes == list(range(n))<jupyter_output><empty_output><jupyter_text>The `scipy` Python package provides very efficient methods for matrix-vector multiplications:<jupyter_code>n = shape(A)[0]
x = np.ones(n)
# Out-weights
print(A.dot(x))
# In-weights
print(A.T.dot(x))<jupyter_output>[11. 12. 10. ...  2.  4.  6.]
[ 0. 27. 13. ...  0.  0.  0.]<jupyter_text>The following function returns the list of non-sink nodes and the (rectangular) transition matrix of the regular random walk from non-sink nodes:<jupyter_code>def transition_matrix(G):
    # index: list of non-sink nodes (as numpy array)
    # P: sparse transition matrix of the random walk (from non-sink nodes)
    A = nx.adjacency_matrix(G)
    n = np.shape(A)[0]
    w = A.dot(np.ones(n, float))
    index = np.where(w > 0)[0]
    D = sp.diags(1. / w[index])
    P = D.dot(A[index,:])
    return index, P 
index, P = transition_matrix(G)
shape(P)
n = shape(P)[1]
P.dot(np.ones(n))
# Move from node s
s = 0
x = np.zeros(n)
x[s] = 1
P.T.dot(x[index])<jupyter_output><empty_output><jupyter_text>To do* Complete the function `transition` below so that it returns the vector $\pi$ after $k$ iterations of the update:$$\pi \gets \alpha  P^T \pi + (1-\alpha)\mu,$$where $\mu$ is the initial / restart distribution and $P$ is the transition matrix with forced restart in $\mu$ from sink nodes.* Compare the results (ranking and computation time) of your `pagerank` function to those given by `networkx` functions: `pagerank` and `pagerank_scipy`* Answer question 6 **(0.5 point)**<jupyter_code>def transition(index, P, mu, alpha, k):
    # index: list of non-sink nodes (as numpy array)
    # P: sparse transition matrix of the random walk (from non-sink nodes)
    # mu: initial / restart distribution 
    # alpha: damping factor
    # k: number of iterations
    pi = mu
    for i in range(k): 
        pi = alpha * P.T.dot(pi[index]) + (1-alpha) * mu
    # to be completed
    return pi
def pagerank(G, personalization = None, alpha = 0.85, k = 3):
    # personalization: dictionary for initial / restart distribution (default = uniform)
    # alpha: damping factor
    # k: number of iterations
    n = G.number_of_nodes()
    node_index = {u:i for i,u in enumerate(G.nodes())}
    if personalization == None:
        mu = np.ones(n,float) / n
    else:
        mu = np.zeros(n,float)
        for u in personalization:
            mu[node_index[u]] = personalization[u]
    index, P = transition_matrix(G)
    pi = transition(index, P, mu, alpha, k)
    PR = {u: pi[node_index[u]] for u in G.nodes()}
    return PR
get_question(6)
pg_list= pagerank(G, k=3, alpha=1)[285]
pg_list
for x in G.nodes(data = True):
    if(x[1]['name'] == 'Japan'):
        print(x)
post_answer(6,0.004473267676873789)<jupyter_output>This is correct!<jupyter_text>3. Personalized PageRank Unless otherwise specified, we take the default values $\alpha = 0.85$ and $k = 3$.  To do* Answer questions 7 and 8 **(0.5 point each)**<jupyter_code>get_question(7)
nx.pagerank(G,alpha=0.85)
dict(G.neighbors(1185)
answer = "Henri_Matisse"
G.nodes(data=True)
post_answer(7,answer)
get_question(8)
for x in G.nodes(data = True):
    if(x[1]['name'] == 'Nairobi'):
      print(x)
    if(x[1]['name'] == 'Oslo'):
      print(x)
    if(x[1]['name'] == 'Tokyo'):
      print(x)

ne1 = set(G.neighbors(699))
ne2 = set(G.neighbors(1485))
ne3 = set(G.neighbors(2534))

post_answer(8,'Football_(soccer)')<jupyter_output>This is correct!<jupyter_text>4. Forward-Backward PageRank  To do* Complete the functions below to get the (Personalized) Forward-Backward PageRank vector* Answer question 9 and 10 **(1 point each)**<jupyter_code>def forward_backward_transition(index, P, index_, P_, mu, alpha, k):
    # index: list of non-sink nodes (as numpy array)
    # P: sparse transition matrix of the forward random walk (from non-sink nodes)
    # index_: list of non-source nodes (as numpy array)
    # P_: sparse transition matrix of the backward random walk (from non-source nodes)
    # mu: initial / restart distribution (default = uniform)
    # alpha: damping factor
    # k: number of iterations
    pi = mu
    # to be completed
    return pi
def forward_backward_pagerank(G, personalization = None, alpha = 0.85, k = 3):
    # personalization: dictionary for initial / restart distribution (default = uniform)
    # alpha: damping factor
    # k: number of iterations
    PR = {u: 0. for u in G.nodes()}
    # to be completed
    return PR
get_question(9)
list(G.neighbors(1185))
nodes = nodes
answer = "History_of_painting"
post_answer(9,answer)
G = nx.read_graphml("movies-actors.graphml", node_type = int)
names = nx.get_node_attributes(G, 'name')
get_question(10)
answer = "<NAME>"
post_answer(10,answer)<jupyter_output>This is correct!
{'fraction_non_alphanumeric': 0.13446676970633695, 'fraction_numerical': 0.0258887171561051, 'mean_word_length': 4.793508673754896, 'pattern_counts': {'":': 0, '<': 64, '<?xml version=': 0, '>': 67, 'https://': 4, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 1, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '17', 'dir': 'jupyter-structured-clean-dedup', 'id': '290800', 'license': 'Apache-2.0', 'n_tokens_mistral': 3830, 'n_tokens_neox': 3625, 'n_words': 1046, 'path': 'SD212/lab_session/lab5.ipynb', 'repo_name': 'zhufangda/Telecom-Paristech', 'size': '10363'}