<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
Step1:  Link analysis
(Inspired by and borrowed heavily from
Step2:  Co-authorship network
Summaries maps paper ids to paper summaries. Let us now create here mappings by different criteria.
We'll start by building a mapping from authors to the set of ids of papers they authored. 
We'll be using Python's sets again for that purpose.
Step3:  We now build a co-authorship network, a graph linking authors, to the set of co-authors they have published with.
Step4:  Now we can have a look at some basic statistics about our graph
Step5:  With this data in hand, we can plot the degree distribution by showing the number of collaborators a scientist has published with
Step6:  Citations network
We'll start by expanding the Citations dataset into two mappings
Step7:  Let us now look at an arbitrary paper, let's say PubMed ID 16820458 ("Changes in the spoilage-related microbiota of beef during refrigerated storage under different packaging conditions"). We can now use the cited_by mapping to retrieve what we know of its list of references.
As mentioned above, because the process generating the dataset asked for papers citing a given paper (and not papers a paper cites), the papers we get through cited_by are then necessarily all members of our datasets, and we can therefore find them in Summaries.
Step8:  If we lookup the same paper in papers_citing, we now see that some of the cited papers are themselves in our dataset, but others are not (denote here by '??')
Step9:  Paper 17696886, for example, is not in our dataset and we do not have any direct information about it, but its repeated occurrence in other papers' citation lists does allow us to reconstruct a good portion of its references. Below is the list of papers in our dataset cited by that paper
Step10:  Now that we have a better understanding about the data we're dealing with, let us obtain again some basic statistics about our graph.
Step11:  Most cited papers
Let us now find which 10 papers are the most cited in our dataset.
Step12:  Link Analysis for Search Engines
In order to use the citation network, we need to be able to perform some complex graph algorithms on it. To make our lives easier, we will load the data into the python package NetworkX, a package for the creation, manipulation, and study of the structure, dynamics, and function of complex networks, which provides a number of these graph algorithms (such as HITS and PageRank) out of the box.
You probably have to install the NetworkX package first.
Step13:  We now have a NetworkX Directed Graph stored in G, where a node represents a paper, and an edge represents a citation. This means we can now apply the algorithms and functions of NetworkX to our graph
Step14:  As this graph was generated from citations only, we need to add all isolated nodes (nodes that are not cited and do not cite other papers) as well
Step15:  Assignments
Your name
Step16:  [Write your answer text here]
Using the Link Analysis algorithms provided by NetworkX, calculate the PageRank score for each node in the citation network, and store them in a variable. Print out the PageRank values for the two example papers given below.
Hint
Step17:  Copy your search engine from mini-assignment 3, and create a version that incorporates a paper's PageRank score in it's final score, in addition to tf-idf. Show the result of an example query, and explain your decision on how to combine the two scores (PageRank and tf-idf).
<ASSISTANT_TASK:>
Python Code:
import pickle, bz2
from collections import *
import numpy as np
import matplotlib.pyplot as plt
# show plots inline within the notebook
%matplotlib inline
# set plots' resolution
plt.rcParams['savefig.dpi'] = 100
from IPython.display import display, HTML
Ids_file = 'data/air__Ids.pkl.bz2'
Summaries_file = 'data/air__Summaries.pkl.bz2'
Citations_file = 'data/air__Citations.pkl.bz2'
Abstracts_file = 'data/air__Abstracts.pkl.bz2'
Ids = pickle.load( bz2.BZ2File( Ids_file, 'rb' ) )
Summaries = pickle.load( bz2.BZ2File( Summaries_file, 'rb' ) )
paper = namedtuple( 'paper', ['title', 'authors', 'year', 'doi'] )
for (id, paper_info) in Summaries.items():
    Summaries[id] = paper( *paper_info )
Citations = pickle.load( bz2.BZ2File( Citations_file, 'rb' ) )
def display_summary( id, extra_text='' ):
    
    Function for printing a paper's summary through IPython's Rich Display System.
    Trims long titles or author lists, and links to the paper's  DOI (when available).
    
    s = Summaries[ id ]
    
    title = ( s.title if s.title[-1]!='.' else s.title[:-1] )
    title = title[:150].rstrip() + ('' if len(title)<=150 else '...')
    if s.doi!='':
        title = '<a href=http://dx.doi.org/%s>%s</a>' % (s.doi, title)
    
    authors = ', '.join( s.authors[:5] ) + ('' if len(s.authors)<=5 else ', ...')
    
    lines = [
        title,
        authors,
        str(s.year),
        '<small>id: %d%s</small>' % (id, extra_text)
        ]
    
    display( HTML( '<blockquote>%s</blockquote>' % '<br>'.join(lines) ) )
from math import log10
def tokenize(text):
    return text.split(' ')
def preprocess(tokens):
    result = []
    for token in tokens:
        result.append(token.lower())
    return result
Abstracts = pickle.load( bz2.BZ2File( Abstracts_file, 'rb' ) )
inverted_index = defaultdict(set)
for (id, abstract) in Abstracts.items():
    for term in preprocess(tokenize(abstract)):
        inverted_index[term].add(id)
tf_matrix = defaultdict(Counter)
for (id, abstract) in Abstracts.items():
    tf_matrix[id] = Counter(preprocess(tokenize(abstract)))
def tf(t,d):
    return float(tf_matrix[d][t])
def df(t):
    return float(len(inverted_index[t]))
numdocs = float(len(Abstracts))
def num_documents():
    return numdocs
# We don't need to keep this object in memory any longer:
Abstracts = {}
Explanation: Link analysis
(Inspired by and borrowed heavily from: Collective Intelligence - Luís F. Simões. IR version and assignments by J.E. Hoeksema, 2014-11-12. Converted to Python 3 and minor changes by Tobias Kuhn, 2015-11-17.)
This notebook's purpose is to give examples of how to use graph algorithms to improve search engine. We look at two graphs in particular: the co-authorship network and the citation network.
The citation network is similar to the link network of the web: Citations are like web links pointing to other documents. We can therefore apply the same network-based ranking methods.
Code from previous exercises
End of explanation
papers_of_author = defaultdict(set)
for id,p in Summaries.items():
    for a in p.authors:
        papers_of_author[a].add( id )
papers_of_author['Vine AK']
for id in papers_of_author['Vine AK']:
    display_summary(id)
Explanation: Co-authorship network
Summaries maps paper ids to paper summaries. Let us now create here mappings by different criteria.
We'll start by building a mapping from authors to the set of ids of papers they authored. 
We'll be using Python's sets again for that purpose.
End of explanation
coauthors = defaultdict(set)
for p in Summaries.values():
    for a in p.authors:
        coauthors[a].update( p.authors )
# The code above results in each author being listed as having co-autored with himself/herself.
# We remove these self-references here:
for a,ca in coauthors.items():
    ca.remove(a)
print(', '.join( coauthors['Vine AK'] ))
Explanation: We now build a co-authorship network, a graph linking authors, to the set of co-authors they have published with.
End of explanation
print('Number of nodes: %8d (node = author)' % len(coauthors))
print('Number of links: %8d (link = collaboration between the two linked authors on at least one paper)'  \
        % sum( len(cas) for cas in coauthors.values() ))
Explanation: Now we can have a look at some basic statistics about our graph:
End of explanation
plt.hist( x=[ len(ca) for ca in coauthors.values() ], bins=range(55), histtype='bar', align='left', normed=True )
plt.xlabel('number of collaborators')
plt.ylabel('fraction of scientists')
plt.xlim(0,50);
Explanation: With this data in hand, we can plot the degree distribution by showing the number of collaborators a scientist has published with:
End of explanation
papers_citing = Citations  # no changes needed, this is what we are storing already in the Citations dataset
cited_by = defaultdict(list)
for ref, papers_citing_ref in papers_citing.items():
    for id in papers_citing_ref:
        cited_by[ id ].append( ref )
Explanation: Citations network
We'll start by expanding the Citations dataset into two mappings: 
papers_citing[id]: papers citing a given paper;
cited_by[id]: papers cited by a given paper (in other words, its list of references).
If we see the Citations dataset as a directed graph where papers are nodes, and citations links between then, then papers_citing gives you the list of a node's incoming links, whereas cited_by gives you the list of its outgoing links.
The dataset was assembled by querying for papers citing a given paper. As a result, the data mapped to in cited_by (its values) is necessarily limited to ids of papers that are part of the dataset.
End of explanation
paper_id = 16820458
refs = { id : Summaries[id].title for id in cited_by[paper_id] }
print(len(refs), 'references identified for the paper with id', paper_id)
refs
Explanation: Let us now look at an arbitrary paper, let's say PubMed ID 16820458 ("Changes in the spoilage-related microbiota of beef during refrigerated storage under different packaging conditions"). We can now use the cited_by mapping to retrieve what we know of its list of references.
As mentioned above, because the process generating the dataset asked for papers citing a given paper (and not papers a paper cites), the papers we get through cited_by are then necessarily all members of our datasets, and we can therefore find them in Summaries.
End of explanation
{ id : Summaries.get(id,['??'])[0]  for id in papers_citing[paper_id] }
Explanation: If we lookup the same paper in papers_citing, we now see that some of the cited papers are themselves in our dataset, but others are not (denote here by '??'):
End of explanation
paper_id2 = 17696886
refs2 = { id : Summaries[id].title for id in cited_by[paper_id2] }
print(len(refs2), 'references identified for the paper with id', paper_id2)
refs2
Explanation: Paper 17696886, for example, is not in our dataset and we do not have any direct information about it, but its repeated occurrence in other papers' citation lists does allow us to reconstruct a good portion of its references. Below is the list of papers in our dataset cited by that paper:
End of explanation
print('Number of core ids %d (100.00 %%)' % len(Ids))
with_cit = [ id for id in Ids if papers_citing[id]!=[] ]
print('Number of papers cited at least once: %d (%.2f %%)' % (len(with_cit), 100.*len(with_cit)/len(Ids)))
isolated = set( id for id in Ids if papers_citing[id]==[] and id not in cited_by )
print('Number of isolated nodes: %d (%.2f %%)\n\t'   \
      '(papers that are not cited by any others, nor do themselves cite any in the dataset)'% (
    len(isolated), 100.*len(isolated)/len(Ids) ))
noCit_withRefs = [ id for id in Ids if papers_citing[id]==[] and id in cited_by ]
print('Number of dataset ids with no citations, but known references: %d (%.2f %%)' % (
    len(noCit_withRefs), 100.*len(noCit_withRefs)/len(Ids)))
print('(percentages calculated with respect to just the core ids (members of `Ids`) -- exclude outsider ids)\n')
Ids_set    = set( Ids )
citing_Ids = set( cited_by.keys() ) # == set( c for citing in papers_citing.itervalues() for c in citing )
outsiders = citing_Ids - Ids_set    # set difference: removes from `citing_Ids` all the ids that occur in `Ids_set`
nodes     = citing_Ids | Ids_set - isolated     # set union, followed by set difference
print('Number of (non-isolated) nodes in the graph: %d\n\t(papers with at least 1 known citation, or 1 known reference)' % len(nodes))
print(len( citing_Ids ), 'distinct ids are citing papers in our dataset.')
print('Of those, %d (%.2f %%) are ids from outside the dataset.\n' % ( len(outsiders), 100.*len(outsiders)/len(citing_Ids) ))
all_cits      = [ c for citing in papers_citing.values() for c in citing ]
outsider_cits = [ c for citing in papers_citing.values() for c in citing if c in outsiders ]
print('Number of links (citations) in the graph:', len(all_cits))
print('A total of %d citations are logged in the dataset.' % len(all_cits))
print('Citations by ids from outside the dataset comprise %d (%.2f %%) of that total.\n' % (
    len(outsider_cits),
    100.*len(outsider_cits)/len(all_cits) ))
Explanation: Now that we have a better understanding about the data we're dealing with, let us obtain again some basic statistics about our graph.
End of explanation
nr_cits_per_paper = [ (id, len(cits)) for (id,cits) in papers_citing.items() ]
for (id, cits) in sorted( nr_cits_per_paper, key=lambda i:i[1], reverse=True )[:10]:
    display_summary( id, ', nr. citations: %d' % cits )
Explanation: Most cited papers
Let us now find which 10 papers are the most cited in our dataset.
End of explanation
import networkx as nx
G = nx.DiGraph(cited_by)
Explanation: Link Analysis for Search Engines
In order to use the citation network, we need to be able to perform some complex graph algorithms on it. To make our lives easier, we will load the data into the python package NetworkX, a package for the creation, manipulation, and study of the structure, dynamics, and function of complex networks, which provides a number of these graph algorithms (such as HITS and PageRank) out of the box.
You probably have to install the NetworkX package first.
End of explanation
print(nx.info(G))
print(nx.is_directed(G))
print(nx.density(G))
Explanation: We now have a NetworkX Directed Graph stored in G, where a node represents a paper, and an edge represents a citation. This means we can now apply the algorithms and functions of NetworkX to our graph:
End of explanation
G.add_nodes_from(isolated)
print(nx.info(G))
print(nx.is_directed(G))
print(nx.density(G))
Explanation: As this graph was generated from citations only, we need to add all isolated nodes (nodes that are not cited and do not cite other papers) as well:
End of explanation
# Add your code here
Explanation: Assignments
Your name: ...
Plot the in-degree distribution (the distribution of the number of incoming links) for the citation network. What can you tell about the shape of this distribution, and what does this tell us about the network?
End of explanation
# Add your code here
# print PageRank for paper 7168798
# print PageRank for paper 21056779
Explanation: [Write your answer text here]
Using the Link Analysis algorithms provided by NetworkX, calculate the PageRank score for each node in the citation network, and store them in a variable. Print out the PageRank values for the two example papers given below.
Hint: the pagerank_scipy implementation tend to be considerably faster than its regular pagerank counterpart (but you have to install the SciPy package for that).
End of explanation
# Add your code here
Explanation: Copy your search engine from mini-assignment 3, and create a version that incorporates a paper's PageRank score in it's final score, in addition to tf-idf. Show the result of an example query, and explain your decision on how to combine the two scores (PageRank and tf-idf).
End of explanation
<END_TASK>