02_Analysis_of_Twitter_Social_Network.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Analysis of a Twitter Social Network\n",
    "\n",
    "In this section we are going to parse the tweets we collected and build the social network of interactions between Twitter users. We will also see how to analyze the network using NetworkX. We will look at the different component of the network and at percolation processes on this network.\n",
    "\n",
    "## Parsing tweets\n",
    "\n",
    "Tweets are saved in JSON format ([JavaScript Object Notation](https://www.w3schools.com/js/js_json_intro.asp))\n",
    "JSON is text, written with JavaScript object notation.\n",
    "\n",
    "The `json` python module allows to easily import json file into python [Dictonairies](https://docs.python.org/3/tutorial/datastructures.html#dictionaries)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#load tweets \n",
    "\n",
    "import json\n",
    "\n",
    "#filename = 'tweets.txt'\n",
    "filename = 'tweets_cop24.txt'\n",
    "\n",
    "\n",
    "tweet_list = []\n",
    "\n",
    "with open(filename, 'r') as fopen:\n",
    "    # each line correspond to a tweet\n",
    "    for line in fopen:\n",
    "        if line != '\\n':\n",
    "            tweet_list.append(json.loads(line))\n",
    "        "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's look at the informations contained in a tweet"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# take the first tweet of the list\n",
    "tweet = tweet_list[2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# each tweet is a python dictionary\n",
    "type(tweet)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# all the 'entries' of the dictionary\n",
    "tweet.keys()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "you can find a description of the fields in the Twitter API documentation: https://dev.twitter.com/overview/api/tweets"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#creation time\n",
    "tweet['created_at']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# text of the tweet\n",
    "print(tweet['text'])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# user info\n",
    "tweet['user']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# user is itslef a dict\n",
    "print(type(tweet['user']))\n",
    "\n",
    "tweet['user']['name']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# unique id of the user\n",
    "tweet['user']['id']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#is the tweet a retweet?\n",
    "'retweeted_status' in tweet"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "if 'retweeted_status' in tweet:\n",
    "    print(tweet['retweeted_status'])\n",
    "# the `retweeted_status` is also a tweet dictionary    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "if 'retweeted_status' in tweet:\n",
    "    print(tweet['retweeted_status']['text'])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# user id and name of the retweeted user?\n",
    "if 'retweeted_status' in tweet:\n",
    "    print(tweet['retweeted_status']['user']['id'])\n",
    "    print(tweet['retweeted_status']['user']['name'])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# is the tweet a reply?\n",
    "'in_reply_to_user_id' in tweet and tweet['in_reply_to_user_id'] is not None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 'entities' contains the hashtags, urls and usernames used in the tweet\n",
    "tweet['entities']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# user id of the mentioned users\n",
    "for  mention in tweet['entities']['user_mentions']:\n",
    "    print(mention['id'])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# is the tweet a quote?\n",
    "'quoted_status' in tweet"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Building the network of interactions\n",
    "\n",
    "We will use the python module [`NetworkX`](https://networkx.readthedocs.io/en/stable/index.html) to construct and analyze the social network.\n",
    "\n",
    "A short introduction to networkx: https://github.com/networkx/notebooks\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There are four types of interactions between two users in Twitter:\n",
    "- Retweet\n",
    "- Quote\n",
    "- Reply\n",
    "- Mention"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# let's define some functions to extract the interactions from tweets\n",
    "\n",
    "def getTweetID(tweet):\n",
    "    \"\"\" If properly included, get the ID of the tweet \"\"\"\n",
    "    return tweet.get('id')\n",
    "    \n",
    "def getUserIDandScreenName(tweet):\n",
    "    \"\"\" If properly included, get the tweet \n",
    "        user ID and Screen Name \"\"\"\n",
    "    user = tweet.get('user')\n",
    "    if user is not None:\n",
    "        uid = user.get('id')\n",
    "        screen_name = user.get('screen_name')\n",
    "        return uid, screen_name\n",
    "    else:\n",
    "        return (None, None)\n",
    "\n",
    "def getRetweetedUserIDandSreenName(tweet):\n",
    "    \"\"\" If properly included, get the retweet \n",
    "        source user ID and Screen Name\"\"\"\n",
    "    \n",
    "    retweet = tweet.get('retweeted_status')\n",
    "    if retweet is not None:\n",
    "        return getUserIDandScreenName(retweet)\n",
    "    else:\n",
    "        return (None, None)\n",
    "    \n",
    "def getRepliedUserIDandScreenName(tweet):\n",
    "    \"\"\" If properly included, get the ID and Screen Name \n",
    "        of the user the tweet replies to \"\"\"\n",
    "    \n",
    "    reply_id = tweet.get('in_reply_to_user_id')\n",
    "    reply_screenname = tweet.get('in_reply_to_screen_name')\n",
    "    return reply_id, reply_screenname\n",
    "    \n",
    "def getUserMentionsIDandScreenName(tweet):\n",
    "    \"\"\" If properly included, return a list of IDs and Screen Names tuple\n",
    "        of all user mentions, including retweeted and replied users \"\"\"\n",
    "        \n",
    "    mentions = []\n",
    "    entities = tweet.get('entities')\n",
    "    if entities is not None:\n",
    "        user_mentions = entities.get('user_mentions')\n",
    "        for mention in user_mentions:\n",
    "            mention_id = mention.get('id')\n",
    "            screen_name = mention.get('screen_name')\n",
    "            mentions.append((mention_id, screen_name))\n",
    "    \n",
    "    return mentions\n",
    "\n",
    "    \n",
    "def getQuotedUserIDandScreenName(tweet):\n",
    "    \"\"\" If properly included, get the ID of the user the tweet is quoting\"\"\"\n",
    "    \n",
    "    quoted_status = tweet.get('quoted_status')\n",
    "    \n",
    "    if quoted_status is not None:\n",
    "        return getUserIDandScreenName(quoted_status)\n",
    "    else:\n",
    "        return (None, None)\n",
    "    \n",
    "def getAllInteractions(tweet):\n",
    "    \"\"\" Get all the interactions from this tweet\n",
    "    \n",
    "        returns : (tweeter_id, tweeter_screenname), list of (interacting_id, interacting_screenname)\n",
    "    \"\"\"\n",
    "    \n",
    "    # Get the tweeter\n",
    "    tweeter = getUserIDandScreenName(tweet)\n",
    "    \n",
    "    # Nothing to do if we couldn't get the tweeter\n",
    "    if tweeter[0] is None:\n",
    "        return (None, None), []\n",
    "    \n",
    "    # a python set is a collection of unique items\n",
    "    # we use a set to avoid duplicated ids\n",
    "    interacting_users = set()\n",
    "    \n",
    "    # Add person they're replying to\n",
    "    interacting_users.add(getRepliedUserIDandScreenName(tweet))\n",
    "    \n",
    "    # Add person they retweeted\n",
    "    interacting_users.add(getRetweetedUserIDandSreenName(tweet))\n",
    "    \n",
    "    # Add person they quoted\n",
    "    interacting_users.add(getQuotedUserIDandScreenName(tweet))\n",
    "    \n",
    "    # Add mentions\n",
    "    interacting_users.update(getUserMentionsIDandScreenName(tweet))\n",
    "  \n",
    "    # remove the tweeter if he is in the set\n",
    "    interacting_users.discard(tweeter)\n",
    "    # remove the None case\n",
    "    interacting_users.discard((None,None))\n",
    "    \n",
    "    # Return our tweeter and their influencers\n",
    "    return tweeter, list(interacting_users)\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(getUserIDandScreenName(tweet_list[3]))\n",
    "print(getAllInteractions(tweet_list[4]))\n",
    "\n",
    "tweet_list[100].get('text')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Let's build the network"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import networkx as nx\n",
    "\n",
    "# define an empty Directed Graph\n",
    "# A directed graph is a graph where edges have a direction\n",
    "# in our case the edges goes from user that sent the tweet to\n",
    "# the user with whom they interacted (retweeted, mentioned or quoted)\n",
    "G = nx.DiGraph()\n",
    "\n",
    "# loop over all the tweets and add edges if the tweet include some interactions\n",
    "for tweet in tweet_list:\n",
    "    # find all influencers in the tweet\n",
    "    tweeter, interactions = getAllInteractions(tweet)\n",
    "    tweeter_id, tweeter_name = tweeter\n",
    "    tweet_id = getTweetID(tweet)\n",
    "    \n",
    "    # add an edge to the Graph for each influencer\n",
    "    for interaction in interactions:\n",
    "        interact_id, interact_name = interaction\n",
    "        \n",
    "        # add edges between the two user ids\n",
    "        # this will create new nodes if the nodes are not already in the network\n",
    "        # we also add an attribute the to edge equal to the id of the tweet\n",
    "        G.add_edge(tweeter_id, interact_id, tweet_id=tweet_id)\n",
    "        \n",
    "        # add name as a property to each node\n",
    "        # with networkX each node is a dictionary\n",
    "        G.node[tweeter_id]['name'] = tweeter_name\n",
    "        G.node[interact_id]['name'] = interact_name\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# The graph's node are contained in a dictionary \n",
    "print(type(G.node))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "interactions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# the keys are the user_id\n",
    "nodelist = list(G.node.keys())\n",
    "print(nodelist)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# each node is itself a dictionary with node attributes as key,value pairs\n",
    "print(type(G.node[nodelist[0]]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# edges are also contained in a dictionary\n",
    "print(type(G.edge))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# we can see all the edges going out of this node\n",
    "# each edge is a dictionary inside this dictionary with a key \n",
    "# corresponding to the target user_id\n",
    "e = G.edge[nodelist[0]]\n",
    "print(e)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# so we can access the edge using the source user_id and the target user_id\n",
    "G.edge[nodelist[0]][list(e.keys())[0]]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Some basic properties of the Network:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "G.number_of_nodes()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "G.number_of_edges()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# listing all nodes \n",
    "nodelist = G.nodes()\n",
    "nodelist[:3]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# degree of a node\n",
    "print(G.degree(nodelist[2]))\n",
    "print(G.in_degree(nodelist[2]))\n",
    "print(G.out_degree(nodelist[2]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# dictionary with the degree of all nodes\n",
    "all_degrees = G.degree(nodelist) # this is the degree for undirected edges\n",
    "in_degrees = G.in_degree(nodelist)\n",
    "out_degrees = G.in_degree(nodelist)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# average degree\n",
    "2*G.number_of_edges()/G.number_of_nodes()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "np.array(list(all_degrees.values())).mean()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "np.array(list(in_degrees.values())).mean()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "np.array(list(out_degrees.values())).mean()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# maximum degree\n",
    "max(all_degrees.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# we want to make a list with (user_id, username, degree) for all nodes\n",
    "degree_node_list = []\n",
    "for node in G.nodes_iter():\n",
    "    degree_node_list.append((node, G.node[node]['name'], G.degree(node)))\n",
    "    \n",
    "print('Unordered user, degree list')    \n",
    "print(degree_node_list[:10])\n",
    "\n",
    "# sort the list according the degree in descinding order\n",
    "degree_node_list = sorted(degree_node_list, key=lambda x:x[2], reverse=True)\n",
    "print('Ordered user, degree list')    \n",
    "print(degree_node_list[:10])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# we need to import matplolib for making plots\n",
    "# and numpy for numerical computations\n",
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "%matplotlib inline"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Network components\n",
    "\n",
    "For **directed** graphs we can define two types of components:\n",
    "- Weakly connected components\n",
    "- Strongly connected components\n",
    "\n",
    "Weakly connected component (WCC): maximal set of nodes where there exists a path in at least one direction between each pair of nodes.\n",
    "\n",
    "Strongly connected component (SCC): maximal set of nodes where there exists a path in both directions between each pair of nodes.\n",
    "\n",
    "Weakly connected giant (largest) component (WCGC): Largest WCC\n",
    "Strongly connected giant (largest) component (SCGC): Largest SCC\n",
    "\n",
    "<img src=\"network_components.svg\" style=\"width: 250px;\"/>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# this returns a list of set of nodes belonging to the \n",
    "# different (weakly) connected components\n",
    "components = list(nx.weakly_connected_components(G))\n",
    "\n",
    "# sort the component according to their size\n",
    "components = list(sorted(components, key=lambda x:len(x), reverse=True))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# make a list with the size of each component\n",
    "comp_sizes = []\n",
    "for comp in components:\n",
    "    comp_sizes.append(len(comp))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# plot the histogram of component sizes\n",
    "hist = plt.hist(comp_sizes, bins=100)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# histogram with logarithmic y scale\n",
    "hist = plt.hist(comp_sizes, bins=100, log=True)\n",
    "tx = plt.xlabel('component size')\n",
    "ty = plt.ylabel('number of components')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# sizes of the ten largest components\n",
    "comp_sizes[:10]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# let's make a new graph which is the subgraph of G corresponding to \n",
    "# the largest connected component\n",
    "# let's find the largest component\n",
    "largest_comp = components[0]\n",
    "LCC = G.subgraph(largest_comp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "G.number_of_nodes()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "LCC.number_of_nodes()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# let's plot the degree distribution inside the LCC\n",
    "degrees = nx.degree(LCC)\n",
    "degrees"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "degree_array = np.array(list(degrees.values()))\n",
    "hist = plt.hist(degree_array, bins=100)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# using logarithmic scales\n",
    "hist = plt.hist(degree_array, bins=100, log=True)\n",
    "plt.xscale('log')\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# logarithmic scale with logarithmic bins\n",
    "N, bins, patches = plt.hist(degree_array, bins=np.logspace(0,np.log10(degree_array.max()+1), 20), log=True)\n",
    "plt.xscale('log')\n",
    "tx = plt.xlabel('k - degree')\n",
    "ty= plt.ylabel('number of nodes')\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Degree probability distribution (P(k))\n",
    "\n",
    "# since we have logarithmic bins, we need to\n",
    "# take into account the fact that the bins \n",
    "# have different lenghts when normalizing\n",
    "bin_lengths = np.diff(bins) # lenght of each bin\n",
    "\n",
    "summ = np.sum(N*bin_lengths)\n",
    "normalized_degree_dist = N/summ\n",
    "\n",
    "# check normalization:\n",
    "print(np.sum(normalized_degree_dist*bin_lengths))\n",
    "\n",
    "hist = plt.bar(bins[:-1], normalized_degree_dist, width=np.diff(bins))\n",
    "plt.xscale('log')\n",
    "plt.yscale('log')\n",
    "tx = plt.xlabel('k (degree)')\n",
    "ty = plt.ylabel('P(k)')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise: do the same for the Graph comprising only retweet, replies, quote and mentions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Percolation of the Giant Component"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "\n",
    "def getGCsize(G):\n",
    "    \"\"\" returns the size of the largest component of G\"\"\"\n",
    "        \n",
    "    comps = nx.connected_components(G)\n",
    "    return max([len(comp) for comp in comps])\n",
    "    \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Random Attack:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# list that will contain the size of the GC as we remove nodes\n",
    "rnd_attack_GC_sizes = []\n",
    "\n",
    "# we will take into account the undirected version of the graph\n",
    "LCCundirected = nx.Graph(LCC)\n",
    "\n",
    "nodes_list = LCCundirected.nodes()\n",
    "\n",
    "\n",
    "while len(nodes_list) > 1:\n",
    "    # add the size of the  current GC\n",
    "    rnd_attack_GC_sizes.append(getGCsize(LCCundirected))\n",
    "    \n",
    "    # pick a random node\n",
    "    rnd_node = random.choice(nodes_list)\n",
    "    # remove from graph\n",
    "    LCCundirected.remove_node(rnd_node)\n",
    "    # remove from node list\n",
    "    nodes_list.remove(rnd_node)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# convert list to numpy array\n",
    "rnd_attack_GC_sizes = np.array(rnd_attack_GC_sizes)\n",
    "\n",
    "# normalize by the initial size of the GC\n",
    "GC_rnd = rnd_attack_GC_sizes/rnd_attack_GC_sizes[0]\n",
    "\n",
    "# fraction of removed nodes\n",
    "q = np.linspace(0,1,num=GC_rnd.size)\n",
    "\n",
    "plt.plot(q,GC_rnd)\n",
    "tx = plt.xlabel('q')\n",
    "ty = plt.ylabel('GC')\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### High degree attack:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# high degree attack\n",
    "LCCundirected = nx.Graph(LCC)\n",
    "\n",
    "# list of pairs (node, degree) sorted according the degree\n",
    "node_deg_dict = nx.degree(LCCundirected)\n",
    "nodes_sorted = sorted(node_deg_dict, key=node_deg_dict.get)\n",
    "\n",
    "# list that will contain the size of the GC as we remove nodes\n",
    "hd_attack_GC_sizes = []\n",
    "\n",
    "while len(nodes_sorted) > 1:\n",
    "    \n",
    "    hd_attack_GC_sizes.append(getGCsize(LCCundirected))\n",
    "    \n",
    "    #remove node according to their degree\n",
    "    node = nodes_sorted.pop()\n",
    "    LCCundirected.remove_node(node)\n",
    "    \n",
    "    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "hd_attack_GC_sizes = np.array(hd_attack_GC_sizes)\n",
    "GC_hd = hd_attack_GC_sizes/hd_attack_GC_sizes[0]\n",
    "q = np.linspace(0,1,num=GC_hd.size)\n",
    "\n",
    "plt.plot(q,GC_rnd, label='random attack')\n",
    "plt.plot(q,GC_hd, label='High-Degree attack')\n",
    "tx = plt.xlabel('q')\n",
    "ty = plt.ylabel('GC')\n",
    "plt.legend()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Exercise: implement the High-Degree Adaptative (HDA) attack where at each step the node with the highest degree of the remaining graph is removed."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### PageRank"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#teleportation probability\n",
    "alpha = 0.15\n",
    "\n",
    "#adjacency matrix\n",
    "nodelist = G.nodes()\n",
    "A = nx.to_numpy_matrix(G, nodelist=nodelist)\n",
    "\n",
    "#diagonal matrix of out degrees\n",
    "D = np.matrix(np.diag([float(max(G.out_degree()[n],1)) for n in nodelist]))\n",
    "\n",
    "# teleportation transition matrix\n",
    "N = A.shape[1]\n",
    "S = np.matrix(np.ones((N,N))*1/N)\n",
    "\n",
    "# full transition matrix\n",
    "M = (1-alpha)*np.matmul(D**-1,A) + alpha*S\n",
    "\n",
    "# dangling nodes (nodes with no out links) have a uniform prob to connect to any other nodes\n",
    "dangling_nodes = np.where(A.sum(axis=1) == 0)[0]\n",
    "for node in dangling_nodes:\n",
    "    M[node] = 1/N\n",
    "\n",
    "#initial walker distribution and 1st iteration\n",
    "p_last = np.ones((1,N))*1/N\n",
    "p = np.matmul(p_last, M)\n",
    "\n",
    "# iterate until sufficient convergence\n",
    "eps = 1.0e-8\n",
    "i = 1\n",
    "while np.linalg.norm(p - p_last, 2) > eps:\n",
    "        p_last = p\n",
    "        p = np.matmul(p, M)\n",
    "        i += 1\n",
    "\n",
    "print(i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "p = np.array(p).reshape(N)\n",
    "pg_ranking = np.array(np.argsort(p)[::-1])\n",
    "\n",
    "pagerank_values = p[pg_ranking]\n",
    "nodes_pagerank = [nodelist[r] for r in pg_ranking]\n",
    "nodes_pagerank[:10]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "names_pagerank = [G.node[n]['name'] for n in nodes_pagerank]\n",
    "names_pagerank[:10]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "hist = plt.bar(np.arange(p.shape[0]),np.sort(p)[::-1])\n",
    "ty = plt.ylabel('PageRank value')\n",
    "tx = plt.xlabel('PageRank ranking')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "pagerank_values\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.draw(G, nodelist=nodes_pagerank[:100], node_size=4000*pagerank_values[:100],width=0.5, arrows=False)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Save the graph to a GraphML file:\n",
    "\n",
    "GraphML is file format based on XML useful for exchanging files between softwares.\n",
    "\n",
    "http://graphml.graphdrawing.org/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.write_graphml(LCC, 'twitter_lcc.graphml')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can now open the file with [Gephi](https://gephi.org/) to vizualize the graph"
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}