<jupyter_start><jupyter_text>First we import all the necessary libraries<jupyter_code>from collections import defaultdict, deque
from operator import itemgetter
import networkx as nx
import statistics
import numpy as np
import time
import pickle<jupyter_output><empty_output><jupyter_text>Importing the given data into data structures that we want Dictionary of categories:<jupyter_code>categories = {}
with open('wiki-topcats-categories.txt', 'r') as f:    
    for i in f:
        i = i.strip('').lstrip('Category:').replace(';','').split()
        if len(i)-1 >= 3500:
            key = i[0]
            value = list(map(int, i[1:]))
            categories.update({key:value})
        else:
            pass<jupyter_output><empty_output><jupyter_text>Making the list of page names:<jupyter_code>with open('wiki-topcats-page-names.txt', 'r') as f:
    pagenames = [' '.join(i.split()) for i in f]
pagenames[0:10]<jupyter_output><empty_output><jupyter_text>Nested list of connections<jupyter_code>with open('wiki-topcats-reduced.txt', 'r') as f:
    connections = [tuple(map(int, i.strip().split())) for i in f]
connections[0:10]<jupyter_output><empty_output><jupyter_text>Research questions RQ1 Constructing directed graph dictionary<jupyter_code>graph = defaultdict(set)
for i in connections:
    graph[i[0]].add(i[1])
    if i[1] not in graph:
        graph[i[1]] = set()<jupyter_output><empty_output><jupyter_text>Constructing the graph  We are aware that there is a faster way to build the graph by only one function given by networkX, but we want  to add attributes for the nodes, thus we build the graph by normal way.<jupyter_code>G = nx.DiGraph()
for key, value in graph.items():
    G.add_node(key)
    for attr in value:
        G.node[key][attr] = pagenames[attr] # insert page name as attribute for each node
for connection in connections:
    G.add_edge(connection[0], connection[1])<jupyter_output><empty_output><jupyter_text>Checking the graph (Answers for RQ1)<jupyter_code>nx.info(G)
nx.density(G)<jupyter_output><empty_output><jupyter_text>As we can see, the graph is not dense as the density is very low.We can also check a node is connected to others and by their names<jupyter_code>G.node[62]
adj_dict = dict(G.adjacency()) # adjacency dictionary of the graph<jupyter_output><empty_output><jupyter_text>RQ2<jupyter_code># set of articles in the reduced list
set_reduce = set([i for j in connections for i in j])
len(set_reduce)<jupyter_output><empty_output><jupyter_text>Here we only consider those categories with number of connected nodes >= 3500<jupyter_code>reduce_categories = {}
for category, articles in categories.items():
    set_articles = set(articles)
    intersect = set_reduce.intersection(set_articles) # only taking the nodes inside the reduce graph
    intersect = list(intersect)
    for article in intersect:
        if len(list(G.neighbors(article))) == 0: # remove the nodes that are not connected
            intersect.remove(article)
    if len(intersect) >= 3500:
        reduce_categories[category] = intersect
        print(category,len(intersect))
len(reduce_categories.keys())
giant_set = [] # set of all non-duplicated articles
for category, articles in reduce_categories.items():
    giant_set.extend(articles)
giant_set = list(set(giant_set))
print(len(giant_set))
giant_set[:10]<jupyter_output>422144<jupyter_text>Next, we choose "Year_of_death_missing" as the input due to the time factor:<jupyter_code>C0 = input() 
C0_list = reduce_categories.get(C0)
C0_list[0:10]<jupyter_output><empty_output><jupyter_text>Self-created bfs for a list<jupyter_code>def bfs(adjacency_dict,start,goal_list):
    # dict which holds parents, later helpful to retrieve path.
    # Also useful to keep track of visited node
    parent = defaultdict(lambda:(False, np.inf))

    parent[start] = (True,0)   
    queue = deque([start])
    while queue:
        currNode = queue.popleft()
        for child in adjacency_dict[currNode]:
            if child not in parent: # if not visited
                parent[child] = (True,parent[currNode][1]+1)
                queue.append(child)
    distance_list = []
    for article in goal_list:
        distance_list.append(parent[article][1])
    return distance_list<jupyter_output><empty_output><jupyter_text>Check our function's performance with the default nx.shortest_path_length nx.shortest_path_length:<jupyter_code>Ci_list = reduce_categories.get('Living_people')
category = 'Living_people'
for article in C0_list[:10]:
    bfs_path = []
    for article1 in Ci_list[:10]:
        try:
            distance = nx.shortest_path_length(G,article,article1) # bfs distance
            bfs_path.append(distance)  # a list of shortest paths
        except: # when there is not a path
            bfs_path.append(np.inf)
    print(bfs_path)<jupyter_output>[9, 8, inf, inf, 10, 11, 9, 9, inf, 10]
[8, 7, inf, inf, 9, 10, 8, 8, inf, 9]
[7, 6, inf, inf, 8, 9, 7, 7, inf, 8]
[inf, inf, inf, inf, inf, inf, inf, inf, inf, inf]
[6, 5, inf, inf, 6, 7, 6, 6, inf, 6]
[5, 4, inf, inf, 6, 7, 6, 5, inf, 6]
[inf, inf, inf, inf, inf, inf, inf, inf, inf, inf]
[inf, inf, inf, inf, inf, inf, inf, inf, inf, inf]
[inf, inf, inf, inf, inf, inf, inf, inf, inf, inf]
[6, 5, inf, inf, 7, 8, 6, 6, inf, 7]<jupyter_text>Our own bfs function:<jupyter_code>category = 'Living_people'
Ci_list = reduce_categories.get('Living_people')
for article in C0_list[:10]:
    bfs_path = bfs(adj_dict,article,Ci_list) # bfs distance
    print(bfs_path[0:10])<jupyter_output>[9, 8, inf, inf, 10, 11, 9, 9, inf, 10]
[8, 7, inf, inf, 9, 10, 8, 8, inf, 9]
[7, 6, inf, inf, 8, 9, 7, 7, inf, 8]
[inf, inf, inf, inf, inf, inf, inf, inf, inf, inf]
[6, 5, inf, inf, 6, 7, 6, 6, inf, 6]
[5, 4, inf, inf, 6, 7, 6, 5, inf, 6]
[inf, inf, inf, inf, inf, inf, inf, inf, inf, inf]
[inf, inf, inf, inf, inf, inf, inf, inf, inf, inf]
[inf, inf, inf, inf, inf, inf, inf, inf, inf, inf]
[6, 5, inf, inf, 7, 8, 6, 6, inf, 7]<jupyter_text>Deleting unnecessary variables to save the memory, as we know that the next steps will be very memory-consuming:<jupyter_code>del bfs_path, distance, categories, graph, connections<jupyter_output><empty_output><jupyter_text>As can be seen from above our function is working fine. Now we work on a very very big dictionary. In order to do so we save it chunk by chunk we define the size the save the files for later computation of median.<jupyter_code>node_distance = {}
s = time.time()
size = 0
for article in C0_list:
    size += 1
    bfs_path = bfs(adj_dict,article,giant_set) # bfs distance on whole list 
    node_distance[article] = bfs_path # a dict of shortest paths
    if (size%300) == 0:
        print(size)        
        f = open("node_distance"+str(size)+".pkl","wb")
        pickle.dump(node_distance,f)
        f.close()
        node_distance = {} # reset our dict
print(time.time()-s)<jupyter_output><empty_output><jupyter_text>Get the last items for our dictionary:<jupyter_code>s = time.time()
node_distance = {}
for article in C0_list[3600:]:
    bfs_path = bfs(adj_dict,article,giant_set) # bfs distance on whole list 
    node_distance[article] = bfs_path # a dict of shortest paths
    f = open("node_distance"+str(len(C0_list))+".pkl","wb")
    pickle.dump(node_distance,f)
    f.close()
node_distance = {} # reset our dict
print(time.time()-s)<jupyter_output><empty_output><jupyter_text>As we merged all the list of articles in the previous steps for faster computation of Breadth first search, now we have to create a dictionary to record down the positions of articles for each category<jupyter_code>s = time.time()
index = {} # a dictionary records down positions of the articles
for k, v in reduce_categories.items():
    num_list = []
    for i in v:
        num_list.append(giant_set.index(i))
    index[k] = num_list
print(time.time()-s)<jupyter_output>2380.6984961032867<jupyter_text>Save the file for future usage<jupyter_code>f = open("index.pkl","wb")
pickle.dump(index,f)
f.close()<jupyter_output><empty_output><jupyter_text>Now we can find the median and arrange the block<jupyter_code>median_list = []
s = time.time()
files = ['300','600','900','1200','1500','1800',
         '2100','2400','2700','3000','3300','3600','3629'] #get all the files 

for key, value in index.items(): # key gives the list name, value is the indeces
    if key == C0:                # if key is the input
        median_list.append((C0,0.0))
    else:    
        sub_list = []
        for file in files:
            with open("node_distance"+file+".pkl", 'rb') as f:
                node_distance = pickle.load(f)    
                for k, v in node_distance.items(): # v gives distances, k gives articles in input        
                    for i in value:
                        sub_list.append(v[i])
        # calculate median for each category
        median = statistics.median(sub_list)
        component = (key,median)
        median_list.append(component)
print(time.time()-s)
f = open("median_list.pkl","wb")
pickle.dump(median_list,f)
f.close()
with open('median_list.pkl', 'rb') as f:
    median_list = pickle.load(f)
median_list    # take a look<jupyter_output><empty_output><jupyter_text>Block Ranking<jupyter_code>median_list.sort(key=itemgetter(1))
median_list<jupyter_output><empty_output><jupyter_text>Visualize in a dataframe<jupyter_code>import pandas as pd
df = pd.DataFrame(median_list,columns= ['Category','Median_Score'])
df<jupyter_output><empty_output><jupyter_text>Sorting the nodes in each category  Step1: Computing the sub_graph induced by C0<jupyter_code>C0_graph = {}
C0_set = set(C0_list)
for article in C0_list:
    temp = set(G.predecessors(article)) # return predecessors of a node in the graph
    score = len(temp.intersection(C0_set))
    C0_graph[article] = score<jupyter_output><empty_output><jupyter_text>Now we have C0 sub-graph of format: {article1:score,article2:score....} We are now moving to step 2  Step2:  Extending the graph to the nodes that belong to C1 As we notice, this step is consisted of two sub-steps. First one is to compute the in-edge scores of the nodes in C1, the second one is to compute the total scores by adding the scores in sub-step 1 to the inter-edge scores from nodes in C0.<jupyter_code>C1 = median_list[1][0]
C1
C1_list = reduce_categories.get(C1)
C1_list[0:10]
# first sub-step
C1_graph = {}
C1_set = set(C1_list)
for article in C1_list:
    temp = set(G.predecessors(article))
    score = len(temp.intersection(C1_set))
    C1_graph[article] = score
# second sub_step
for article, score in C1_graph.items():
    new_score = score
    temp = set(G.predecessors(article))
    predecessors = temp.intersection(C0_set)
    for i in predecessors:
        new_score += C0_graph.get(i)
    C1_graph[article] = new_score<jupyter_output><empty_output><jupyter_text>Now we check the ranking of C1 by the highest score first and going down:<jupyter_code>sorted_ = sorted(C1_graph.items(), key=itemgetter(1), reverse = True)
sorted_[:10]<jupyter_output><empty_output><jupyter_text>This seems a little bit odd when the article 1041937 has such a high score. However when we check the predecessors of 1041937 the case is well-explained:<jupyter_code>len(set(G.predecessors(1041937)))<jupyter_output><empty_output><jupyter_text>And a lot of that predecessors should come from the same category, such they give many ones to the score of 1041937!  Step3:  Repeating Step2 up to the last category of the ranking<jupyter_code>score_dict = {**C0_graph,**C1_graph} # joining the first two graphs
len(score_dict.keys())
for i in range(2,len(median_list)):
    Ci = median_list[i][0]
    print(Ci)                          # checking the progress
    Ci_list = reduce_categories.get(Ci)
    
    set_dict = set(score_dict.keys())
    # sub-steps
    Ci_graph = {}
    Ci_set = set(Ci_list)
    for article in Ci_list:
        temp = set(G.predecessors(article))
        score = len(temp.intersection(Ci_set))
        predecessors = temp.intersection(set_dict)
        for i in predecessors:
            score += score_dict.get(i)
        Ci_graph[article] = score
    score_dict = {**score_dict,**Ci_graph}
len(score_dict.keys()) # checking the keys whether it's matched total number of articles or not<jupyter_output><empty_output><jupyter_text>Now we check the top articles with the highest scores:<jupyter_code>sorted_ = sorted(score_dict.items(), key=itemgetter(1), reverse = True)
sorted_[:10]<jupyter_output><empty_output><jupyter_text>Now we return the node ranking inside the sub-graph by the name of the articles:<jupyter_code>ranking = []
for i in sorted_:
    attribute = (pagenames[i[0]], i[1])
    ranking.extend(attribute)
ranking[:10]<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.11672172408368728, 'fraction_numerical': 0.025483718735252476, 'mean_word_length': 4.28031561461794, 'pattern_counts': {'":': 0, '<': 113, '<?xml version=': 0, '>': 116, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 8, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '29', 'dir': 'jupyter-structured-clean-dedup', 'id': '644051', 'license': 'MIT', 'n_tokens_mistral': 4572, 'n_tokens_neox': 4310, 'n_words': 1260, 'path': 'Homework_5.ipynb', 'repo_name': 'nguyenphuhien13/ADM-HW5', 'size': '12714'}