'''
Algorithmic Thinking - Week 1 Application
Citations in physics papers dataset
# Data originally from https://snap.stanford.edu/data/cit-HepTh.html
2016-Jan-31
Python 2.7
Chris
'''

import degree_graphs
import algo_load_graph
import dpa_trial

import numpy as np
import csv
from matplotlib import pyplot as plt

'''
Overview

In the Module 1 Application, we will combine the mathematical analysis that we began in the Homework
with the code that you have written in the Project to analyze a real-world problem: How do scientific papers get cited?

This part of the module will probably be much more unstructured than you are accustomed to in an on-line class.
Our goal is to provide a more realistic simulation of how the concepts that you are learning are actually used in practice.
Your key task in this part of the module is to think about the problem at hand as you answer each question.

As part of this portion of the module, you'll need to write code that processes medium-sized datasets.

Citation graphs

Our task for this application is to analyze the structure of graphs generated by citation patterns from scientific papers.
Each scientific paper cites many other papers, say 20-40, and sometimes (e.g., review papers) hundreds of other papers.
But, let's face it: It is often the case that the authors of a paper are superficially familiar with some (many?) of the papers they cite.
So, the question is: Are the cited papers chosen randomly (from within the domain of the paper) or is there some "hidden pattern"?

Given that we will be looking at "paper i cites paper j" relationships, it makes sense to represent the citation data as a directed graph (a citation graph)
in which the nodes correspond to papers, and there is an edge from node i to node j if the paper corresponding to node i cites the paper corresponding to node j.
Since we're interested in understanding how papers get cited, we will analyze the in-degree distribution of a specific graph,
and contrast it to those of graphs generated by two different random processes.
'''

def question_one():
    '''
    Question 1 (4 pts)

    For this question, your task is to load a provided citation graph for 27,770 high energy physics theory papers.
    This graph has 352,768 edges. You should use the following code to load the citation graph as a dictionary.
    (For an extra challenge, you are welcome to write your own function to create the citation graph by parsing this text representation of the citation graph.)

    Your task for this question is to compute the in-degree distribution for this citation graph.
    Once you have computed this distribution, you should normalize the distribution (make the values in the dictionary sum to one)
    and then compute a log/log plot of the points in this normalized distribution.
    '''
    CITATION_URL = "http://storage.googleapis.com/codeskulptor-alg/alg_phys-cite.txt"

    # load data from web using algo_load_graph
    # then get in degree distribution via degree_graphs
    citation_graph = algo_load_graph.load_graph(CITATION_URL)
    in_degree_dict = degree_graphs.in_degree_distribution(citation_graph)

    # normalise so dictionary equals 1
    # individual total / sum of all totals

    factor = 1.0 / sum(in_degree_dict.itervalues())

    for k in in_degree_dict:
      in_degree_dict[k] *= factor

    # store dict in a csv file
    with open('loglog.csv', 'wb') as f:  # Just use 'w' mode in 3.x
        w = csv.DictWriter(f, in_degree_dict.keys())
        w.writeheader()
        w.writerow(in_degree_dict)

    x = np.array(list(in_degree_dict.keys()))
    y = np.array(list(in_degree_dict.values()))

    plt.loglog(x, y, 'ro')

    plt.xlim(1, 2**14)

    plt.xlabel('In-degree')
    plt.ylabel('Frequency')
    plt.title('Normalized in-degree distribution graph (log-log) \n for citations from scientific papers')
    plt.show()
    # see question1.png for graph

def question_two():
    '''
    Question 2 (3 pts)
    In Homework 1, you saw Algorithm ER for generating random graphs and reasoned analytically about the properties of the ER graphs it generates.
    Consider the simple modification of the algorithm to generate random directed graphs: For every ordered pair of distinct nodes (i,j),
    the modified algorithm adds the directed edge from i to j with probability p.

    For this question, your task is to consider the shape of the in-degree distribution for an ER graph and compare its shape to that of the physics citation graph.
    In the homework, we considered the probability of a specific in-degree, k, for a single node.
    Now, we are interested in the in-degree distribution for the entire ER graph.
    To determine the shape of this distribution, you are welcome to compute several examples of in-degree distributions or determine the shape mathematically.

    Once you have determined the shape of the in-degree distributions for ER graphs, compare the shape of this distribution to the
    shape of the in-degree distribution for the citation graph. When answering this question, make sure to address the following points:

    Is the expected in-degree the same for every node in an ER graph? Please answer yes or no and include a short explanation for your answer.
    What does the in-degree distribution for an ER graph look like? You may either provide a plot (linear or log/log)
    of the degree distribution for a small value of n or a short written description of the shape of the distribution.
    Does the shape of the in-degree distribution plot for ER look similar to the shape of the in-degree distribution for the citation graph?
    Provide a short explanation of the similarities or differences.
    Focus on comparing the shape of the two plots as discussed in the class page on "Creating, formatting, and comparing plots".
    '''

    '''
    Answer:
    1 - Yes, the expected in-degree is the same for every node.
    This is because in this model each individual node has an equal chance of being connected to any other individual node.
    In the example of n = 1000, p = 0.5, the expected in-degree is 500 (n * p).

    2 - See graph - it is a binomial distribution. # question2.png

    3 - No, the shape of the two graphs look completely different.
    The ER graph is binomial, frequency peaks at the expected in-degree and falls at higher and lower values of in-degree.
    However the range of these values is still quite narrow and close together.
    In contrast the citation graph is a decaying curve - low in-degrees have a high frequency and as in-degree increases, frequency falls.
    It also has a much wider range of in-degree values than the ER graph.
    '''
    er_graph = degree_graphs.in_degree_distribution(degree_graphs.make_graph_prob(1000, 0.5))

    factor = 1.0 / sum(er_graph.itervalues())
    for k in er_graph:
        er_graph[k] *= factor

    x = list(er_graph.keys())
    y = list(er_graph.values())
    plt.plot(x, y, 'go')
    plt.yscale('log')
    plt.xlim(300, 700)
    plt.xlabel('In-degree')
    plt.ylabel('Frequency (log)')
    plt.title('ER normalized in-degree distribution graph')
    plt.tight_layout()
    plt.show()
    # see question2.png

def question_three():
    '''
    Question 3 (2 pts)
    We next consider a different process for generating synthetic directed graphs.
    In this process, a random directed graph is generated iteratively, where in each iteration a new node is created,
    added to the graph, and connected to a subset of the existing nodes.
    This subset is chosen based on the in-degrees of the existing nodes.
    More formally, to generate a random directed graph in this process, the user must specify two parameters:
    n, which is the final number of nodes,
    and m (where m<=n), which is the number of existing nodes to which a new node is connected during each iteration.
    Notice that m is fixed throughout the procedure.

    The algorithm starts by creating a complete directed graph on m nodes.
    (Note, you've already written the code for this part in the Project.)
    Then, the algorithm grows the graph by adding n-m nodes, where each new node is connected to m nodes randomly chosen from the set of existing nodes.
    As an existing node may be chosen more than once in an iteration, we eliminate duplicates (to avoid parallel edges);
    hence, the new node may be connected to fewer than m existing nodes upon its addition.

    The full description of the algorithm for generating random directed graphs with this process is given below,
    and is called Algorithm DPA (note that the m in the input is a parameter that is specified to this algorithm,
    and it does not denote the total number of edges in the resulting graph).

    # see DPA.png for psuedo-code

    Notice that this algorithm is more complex than the ER algorithm.
    As a result, reasoning about the properties of the graphs that it generates analytically is not as simple.
    When such a scenario arises, we can implement the algorithm, run it, produce graphs, and visually inspect their in-degree distributions.
    In general, this is a powerful technique: When analytical solutions to systems are very hard to derive,
    we can simulate the systems and generate data that can be analyzed to understand the properties of the systems.

    For this question, we will choose values for n and m that yield a DPA graph whose number of nodes and edges is roughly the same to those of the citation graph.
    For the nodes, choosing n to be the number of nodes as the citation graph is easy.
    Since each step in the DPA algorithm adds m edges to the graph,
    a good choice for m is an integer that is close to the average out-degree of the physics citation graph.

    For this question, provide numerical values for n and m that you will use in your construction of the DPA graph.
    '''

    '''
    Answer:
    n = 27,770 # same as example physics papers
    m = 13 # for physics papers, 352,768 total edges / 27,770 total nodes = ~12.70 average edge per node.
    '''
    pass

def question_four():
    '''
    Question 4 (3 pts)
    Your task for this question is to implement the DPA algorithm,
    compute a DPA graph using the values from Question 3,
    and then plot the in-degree distribution for this DPA graph.
    Creating an efficient implementation of the DPA algorithm from scratch is surprisingly tricky.
    The key issue in implementing the algorithm is to avoid iterating through every node in the graph when executing Line 6.
    Using a loop to implement Line 6 leads to implementations that require on the order of 30 minutes in desktop Python to create a DPA graph with 28000 nodes.

    To avoid this bottleneck, you are welcome to use this provided code that implements a DPATrial class. The class has two methods:

        __init__(num_nodes): Create a DPATrial object corresponding to a complete graph with num_nodes nodes.
        run_trial(num_nodes): Runs num_nodes number of DPA trials (lines 4- 6).
                              Returns a set of the nodes, computed with the correct probabilities, that are neighbors of the new node.

    In the provided code, the DPATrial class maintains a list of node numbers that contains multiple instances of the same node number.
    If the number of instances of each node number is maintained in the same ratio as the desired probabilities,
    a call to random.choice() produces a random node number with the desired probability.

    Using this provided code, implementing the DPA algorithm is fairly simple and leads to an efficient implementation of the algorithm. For a challenge, you are also welcome to develop your own implementation of the DPA algorithm that does not use this provided code.

    Once you have created a DPA graph of the appropriate size, compute a (normalized) log/log plot of the points in the graph's in-degree distribution.
    '''

    dpa_graph = dpa_trial.make_dpa_graph(27770, 13)
    in_degree_dict = degree_graphs.in_degree_distribution(dpa_graph)

    factor = 1.0 / sum(in_degree_dict.itervalues())

    for k in in_degree_dict:
      in_degree_dict[k] *= factor

    x = np.array(list(in_degree_dict.keys()))
    y = np.array(list(in_degree_dict.values()))

    plt.loglog(x, y, 'bo')
    plt.xlim(1, 2**14)

    plt.xlabel('In-degree')
    plt.ylabel('Frequency')
    plt.title('DPA normalized in-degree distribution graph (log-log) \n \
            n = 27,770, m = 13')
    plt.show()

    # see question4.png

def question_five():
    '''
    Question 5 (3 pts)
    In this last problem, we will compare the in-degree distribution for the citation graph to the in-degree distribution for the DPA graph as constructed in Question 4.
    In particular, we will consider whether the shape of these two distributions are similar and, if they are similar, what might be the cause of the similarity.

    To help you in your analysis, you should consider the following three phenomena:

    The "six degrees of separation" phenomenon,
    The "rich gets richer" phenomenon, and
    The "Hierarchical structure of networks" phenomenon.

    If you're not familiar with these phenomena, you can read about them by conducting a simple Google or Wikipedia search.
    Your task for this problem is to consider how one of these phenomena might explain the structure of the citation graph or, alternatively,
    how the citations patterns follow one of these phenomena.

    When answering this question, please include answers to the following:

    Is the plot of the in-degree distribution for the DPA graph similar to that of the citation graph?
    Provide a short explanation of the similarities or differences.
    Focus on the various properties of the two plots as discussed in the class page on "Creating, formatting, and comparing plots".
    Which one of the three social phenomena listed above mimics the behavior of the DPA process? Provide a short explanation for your answer.
    Could one of these phenomena explain the structure of the physics citation graph? Provide a short explanation for your answer.
    '''

    '''
    Answer:
    1 - As you can see, there is a lot of similarity between the two.
    Both are a decaying curve, with low in-degrees at high frequency and then as in-degree rises frequency falls.
    The citation line is slightly above the DPA line through the low to middling in-degrees, but overall the model is a good fit to the real-world data.

    2 - The social phenomena that mimics this behaviour is the "rich get richer" phenomena.
    The first m nodes (in this case 13) are all linked to each other, giving them a headstart.
    Then consider the next few n nodes added (in this example say numbers 14-30).
    They can have a maximum of m connections, so they are again going to connect to a large percentage of the original m nodes (because those are the only ones available).
    And each time a node is linked to, it increases the chances it will be linked to again in the future.
    Lastly the earlier nodes have more opportunities to gain connections -
    in this example the first node will get ~27,000 opportunities, while node 25,000 will only get ~2,000 chances.

    3 - Yes, again the "rich get richer" phenomena could explain this.
    Consider web searches - these are most likely to return the most-used and most-linked sites at the top, such as Wikipedia or BBC.
    And because they return those websites and the user clicks through and/or links to them, that boosts their search ranking even further,
    and future users will be even more likely to use these websites.
    The same could be true of citations for science papers.
    If a few early papers are regularly cited and well-known, then new writers are going to be more aware of these papers and more likely to cite them.
    This further boosts those papers connections, and leads to even more citations in the future. It is a positive feedback loop.
    '''
    # see question5.png
    pass


#question_one()
#question_two()
#question_four()
