Link prediction.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Link Prediction in the Greek Web\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this notebook we are dealing with the problem of link prediction in graphs.Specifically we have a subset of the Greek web and we are trying to predict missing edges.\n",
    "The approach we are going to follow is to deal with the problem as a binary classification task, where each edge is a candidate new edge for the graph. \n",
    "In the specific dataset there are 2041 nodes and 2683 edges and we are trying to predict the 453 edges that have been manually removed from the graph. We also have a dataset of different texts available from the hosts."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "First we extract the raw text from the hosts"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "loaded from pickle\n"
     ]
    }
   ],
   "source": [
    "import os\n",
    "import zipfile\n",
    "import nltk\n",
    "import pickle\n",
    "\n",
    "if os.path.isfile('cache/processed_text.pickle'):\n",
    "    with open('cache/processed_text.pickle', 'rb') as pfile:\n",
    "        text_data = pickle.load(pfile)\n",
    "        print \"loaded from pickle\"\n",
    "else:\n",
    "    filenames = os.listdir('dataset/hosts')\n",
    "    raw_text = {}\n",
    "    for zipfilename in filenames:\n",
    "        with zipfile.ZipFile('dataset/hosts/'+zipfilename) as z:\n",
    "            text = \"\"\n",
    "            for filename in z.namelist():\n",
    "                if not os.path.isdir(filename):\n",
    "                    with z.open(filename) as f:\n",
    "                        for line in f:\n",
    "                            text += line.decode(\"utf-8\").upper()\n",
    "                            text += \" \"\n",
    "            raw_text[zipfilename[:-4]] = text\n",
    "    text_data = process_text(raw_text)\n",
    "    with open('cache/processed_text.pickle', 'wb') as pfile:\n",
    "        pickle.dump(text_data, pfile)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The function process_word is used for stemming as well as to remove tones from the greek text."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import stemmer as st\n",
    "def process_word(word):\n",
    "    \"\"\"detone and stem word\n",
    "    \"\"\"\n",
    "    new_word = []\n",
    "    tones = { u'Ά' : u'A' , u'Έ': u'Ε', u'Ί': u'Ι', u'Ϊ': u'Ι',\n",
    "             u'Ύ': u'Υ', u'Ϋ': u'Υ', u'Ό' : u'Ο', u'Ή': u'Η', u'Ώ': u'Ω'}\n",
    "    for letter in word:\n",
    "        try:\n",
    "            new_word.append(tones[letter])\n",
    "        except KeyError:\n",
    "            new_word.append(letter)\n",
    "    detoned = ''.join(l for l in new_word)\n",
    "    return st.stem(detoned)\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The function process_text is being used to remove stopwords, punctuation, numbers as well as use the above function for detoning and stemming."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import string\n",
    "def process_text(data):\n",
    "    with open('dataset/greekstopwords.txt', 'r') as fp:\n",
    "        stopwords = []\n",
    "        for line in fp:\n",
    "            stopwords.append(line.strip().decode('utf-8').upper())\n",
    "    for domain in data.keys():\n",
    "        text = data[domain]\n",
    "        # remove punctuation\n",
    "        punctuation = set(string.punctuation)    \n",
    "        doc = ''.join([w for w in text if w not in punctuation])\n",
    "        # remove stopwords\n",
    "        doc = [w for w in doc.split() if w not in stopwords]\n",
    "        doc = [w for w in doc if not re.match(r\"$\\d+\\W+|\\b\\d+\\b|\\W+\\d+$\", w)]\n",
    "        doc = ' '.join(process_word(w) for w in doc)\n",
    "        data[domain] = doc\n",
    "    return data        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# assign each domain to the number. \n",
    "domain_number = {}\n",
    "for i, domain in enumerate(text_data.keys()):\n",
    "    domain_number[domain] = i"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Afterwards we extract tfidf features from the websites. We choose 500 words as features and we compute the pairwise cosine similarity for all the websites. Below we also print those features."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "ABOUT ALL AND ARE AT ATHENS AΔΕΙ AΛΛ AΝΘΡΩΠ AΡΘΡ AΤΟΜ BLOG BY COMMENT COMMENTS CONTACT COOKIES COPYRIGHT DE DESIGN EMAIL FACEBOOK FM FOR FROM GOOGLE GREECE GREEK HOME HOT IN IS IT JULY LED LIFESTYLE LIKE LIVE MAY MEDIA MORE NEW NEWS NEWSLETTER NO OCTOBER OF ON ONLINE OR OUT POST POSTED POWERED RADIO READ RESERVED RIGHTS RSS SEARCH SEPTEMBER SHARE SITE THE THIS TO TOP TWEET TWITTER US VIDEO VIEW WEB WITH YOU YOUR ΑΓ ΑΓΟΡ ΑΓΟΡA ΑΓΩΝ ΑΘΗΝ ΑΘΛΗΤ ΑΘΛΗΤΙΣΜ ΑΚΟΛΟΥΘ ΑΚΟΜ ΑΛΛ ΑΛΛA ΑΝAΠΤΥΞ ΑΝΑΖΗΤΗΣ ΑΝΑΚΟΙΝΩΣ ΑΝΘΡΩΠ ΑΠ ΑΠAΝΤΗΣ ΑΠΟ ΑΠΟΣΤΟΛ ΑΠΟΤΕΛ ΑΠΟΤΕΛΕΣΜ ΑΠΟΦAΣ ΑΠΟΦΑΣ ΑΠΟΨ ΑΠΡΙΛ ΑΠΡΙΛΙ ΑΡΘΡ ΑΡΙΘΜ ΑΡΧ ΑΡΧΕΙ ΑΣΦAΛΕΙ ΑΤΤ ΑΥΓ ΑΥΓΟΥΣΤ ΑΥΤ ΑΥΤA ΑΥΤΟΚΙΝΗΤ ΑΦ ΒAΣ ΒΑΘΜΟΛΟΓ ΒΙΒΛ ΒΙΒΛΙ ΒΙΝΤΕ ΒΟΛ ΒΡ ΒΡΙΣΚ ΓΕΝ ΓΕΡΜΑΝ ΓΕΩΡΓΙ ΓΙAΝΝ ΓΙΑΤ ΓΙΝ ΓΙΩΡΓ ΓΝΩΣΤ ΓΟΝ ΓΡAΦ ΓΡΑΦΕΙ ΓΡΗΓΟΡ ΓΥΝΑΙΚ ΔΕ ΔΕΔΟΜΕΝ ΔΕΚ ΔΕΚΕΜΒΡ ΔΗΛΩΣ ΔΗΜ ΔΗΜΗΤΡ ΔΗΜΙΟΥΡΓ ΔΗΜΟΣ ΔΗΜΟΣΙ ΔΗΜΟΣΙΕΥΘ ΔΗΜΟΣΙΕΥΣ ΔΗΜΟΤ ΔΗΜΟΦΙΛ ΔΙAΒΑΣ ΔΙAΡΚΕΙ ΔΙAΦΟΡ ΔΙΑΒAΣ ΔΙΑΒAΣΤ ΔΙΑΓΩΝΙΣΜ ΔΙΑΤΡΟΦ ΔΙΑΦΗΜΙΣ ΔΙΑΧΕΙΡΙΣ ΔΙΕΘΝ ΔΙΕΥΘΥΝΣ ΔΙΚΑΙ ΔΙΚΑΙΩΜ ΔΙΚΤΥ ΔΙΝ ΔΙΟΙΚΗΣ ΔΡAΣ ΔΡΑΣΤΗΡΙΟΤΗΤ ΔΡΟΜ ΔΥΝΑΜ ΔΥΝΑΤΟΤΗΤ ΔΥΟ ΔΥΣΚΟΛ ΔΩΡΕAΝ ΕΒΔΟΜAΔ ΕΓΓΡΑΦ ΕΓΙΝ ΕΔΩ ΕΘΝ ΕΙΔ ΕΙΔΗΣ ΕΙΚΟΝ ΕΙΜΑΣΤ ΕΙΝΑ ΕΙΠ ΕΙΧ ΕΚ ΕΚΔΗΛΩΣ ΕΚΔΟΣ ΕΚΕΙΝ ΕΚΘΕΣ ΕΚΛΟΓ ΕΚΠΑΙΔΕΥΣ ΕΚΠΑΙΔΕΥΤ ΕΚΤ ΕΛΕΓΧ ΕΛΕΥΘΕΡ ΕΛΛAΔ ΕΛΛΑΔ ΕΛΛΗΝ ΕΛΛΗΝΙΚ ΕΝ ΕΝΑ ΕΝΕΡΓΕΙ ΕΝΗΜΕΡΩΣ ΕΝΟΤΗΤ ΕΝΩ ΕΝΩΣ ΕΞΩΤΕΡ ΕΠΙ ΕΠΙΚΑΙΡΟΤΗΤ ΕΠΙΚΟΙΝΩΝ ΕΠΙΛΟΓ ΕΠΙΣ ΕΠΙΣΚΕΨ ΕΠΙΤΡΕΠ ΕΠΙΤΡΟΠ ΕΠΙΧΕΙΡΗΣ ΕΠΟΜΕΝ ΕΠΟΧ ΕΡΓ ΕΡΓΑΣ ΕΡΓΑΣΙ ΕΡΕΥΝ ΕΡΧ ΕΡΩΤΗΣ ΕΤ ΕΤΑΙΡ ΕΤΑΙΡΕΙ ΕΤΣ ΕΥΚΟΛ ΕΥΡ ΕΥΡΩΠ ΕΥΡΩΠΑΙΚ ΕΦΑΡΜΟΓ ΕΦΗΜΕΡΙΔ ΕΧ ΕΩΣ ΖΗΤ ΖΩ ΖΩΗ ΗΛΕΚΤΡΟΝ ΗΜΕΡ ΗΠΑ ΗΤ ΘΕΑΤΡ ΘΕΛ ΘΕΜ ΘΕΣ ΘΕΣΣΑΛΟΝ ΘΕΣΣΑΛΟΝΙΚ ΘΕΩΡ ΙΑΤΡ ΙΔ ΙΔΙ ΙΔΙΑΙΤΕΡ ΙΟΥΛ ΙΟΥΛΙ ΙΟΥΝ ΙΟΥΝΙ ΙΣΤΟΡ ΙΣΤΟΣΕΛΙΔ ΚAΘ ΚAΝ ΚAΠΟΙ ΚAΤ ΚΑΘ ΚΑΙΡ ΚΑΛ ΚΑΛAΘ ΚΑΝ ΚΑΤA ΚΑΤΑΣΚΕΥ ΚΑΤΗΓΟΡ ΚΑΤΗΓΟΡΙ ΚΑῚ ΚΕΝΤΡ ΚΙΝ ΚΛΙΚ ΚΟΙΝ ΚΟΙΝΟΤΗΤ ΚΟΙΝΩΝ ΚΟΣΜ ΚΡΗΤ ΚΡΙΣ ΚΥΒΕΡΝΗΣ ΚΥΠΡ ΚΥΡΙ ΚΥΡΙΑΚ ΚΩΔ ΚΩΝΣΤΑΝΤΙΝ ΛΕ ΛΕΙΤΟΥΡΓ ΛΙΓ ΛΙΣΤ ΛΟΓ ΛΟΓΑΡΙΑΣΜ ΛΥΣ ΜAΘ ΜAΙ ΜAΡΤΙ ΜΑΐ ΜΑΖ ΜΑΘΗΤ ΜΑΡ ΜΑΡΤ ΜΕΓAΛ ΜΕΓΑΛ ΜΕΛ ΜΕΡ ΜΕΣ ΜΕΤA ΜΕΤΑΞ ΜΕΤΡ ΜΕΧΡ ΜΗΝ ΜΗΝΥΜ ΜΙΑ ΜΙΚΡ ΜΜ ΜΟΙΡΑΣΤ ΜΟΝ ΜΟΝAΔ ΜΟΥΣ ΜΟΥΣΕΙ ΜΠΟΡ ΝΕ ΝΕΑ ΝΕΟ ΝΙΚΟΛΑ ΝΟΕΜΒΡ ΝΟΜ ΞΕΚΙΝ ΞΕΝΟΔΟΧΕΙ ΞΕΡ ΟΔΗΓ ΟΙΚΟΓΕΝΕΙ ΟΙΚΟΝΟΜ ΟΙΚΟΝΟΜΙΚ ΟΚΤ ΟΚΤΩΒΡ ΟΚΤΩΒΡΙ ΟΛ ΟΛΑ ΟΛΗ ΟΛΟΚΛΗΡ ΟΛΥΜΠΙΑΚ ΟΜ ΟΜAΔ ΟΜΙΛ ΟΝΟΜ ΟΠ ΟΠΟΙ ΟΡ ΟΡΓΑΝΙΣΜ ΟΣ ΟΣΟ ΟΤΙ ΟΥΤ ΟΧΙ ΠAΝ ΠAΝΤ ΠAΡ ΠΑΓΚΟΣΜ ΠΑΓΚΟΣΜΙ ΠΑΙΔ ΠΑΙΔΙA ΠΑΙΧΝΙΔ ΠΑΡΑΓΩΓ ΠΑΡΑΣΚΕΥ ΠΕΜΠΤ ΠΕΡ ΠΕΡΙΕΧΟΜΕΝ ΠΕΡΙΟΔ ΠΕΡΙΟΧ ΠΕΡΙΠΤΩΣ ΠΕΡΙΣΣ ΠΕΡΙΦΕΡΕΙ ΠΗΓ ΠΛΕ ΠΛΗΡΟΦΟΡΙ ΠΜ ΠΟΔΟΣΦΑΙΡ ΠΟΙΟΤΗΤ ΠΟΛ ΠΟΛΙΤ ΠΟΛΙΤΙΚ ΠΟΛΙΤΙΣΜ ΠΟΛΛ ΠΟΛΛA ΠΟΣ ΠΟΤ ΠΡΑΓΜΑΤΟΠΟΙ ΠΡΕΠ ΠΡΟΒΛΗΜ ΠΡΟΒΟΛ ΠΡΟΓΡAΜΜ ΠΡΟΓΡΑΜΜ ΠΡΟΕΔΡ ΠΡΟΗΓΟΥΜΕΝ ΠΡΟΙΟΝΤ ΠΡΟΣΚΛΗΣ ΠΡΟΣΦΑΤ ΠΡΟΣΦΕΡ ΠΡΟΣΦΟΡ ΠΡΟΣΩΠ ΠΡΟΤAΣ ΠΡΩΤ ΠΩΣ ΣAΒΒΑΤ ΣΕΛΙΔ ΣΕΠ ΣΕΠΤΕΜΒΡ ΣΕΠΤΕΜΒΡΙ ΣΗΜΕΙ ΣΗΜΕΡ ΣΠΙΤ ΣΤΑΘΜ ΣΤΗΛ ΣΤΙΓΜ ΣΤΟΙΧΕΙ ΣΤΟΧ ΣΥΓΚΕΚΡΙΜΕΝ ΣΥΛΛΟΓ ΣΥΜΒΟΥΛ ΣΥΜΒΟΥΛΙ ΣΥΜΜΕΤΟΧ ΣΥΜΦΩΝ ΣΥΝAΝΤΗΣ ΣΥΝΔΕΣ ΣΥΝΔΕΣΜ ΣΥΝΕΔΡΙ ΣΥΝΕΔΡΙΑΣ ΣΥΝΕΝΤΕΥΞ ΣΥΝΕΧΕΙ ΣΥΝΤΑΓ ΣΥΡΙΖ ΣΥΣΤΗΜ ΣΧΕΔ ΣΧΕΣ ΣΧΕΤΙΚA ΣΧΟΛ ΣΧΟΛΕΙ ΣΧΟΛΙ ΣΧΟΛΙΑΣΜ ΣΩΜ ΤΑΚΤ ΤΑΞΙΔ ΤΕΛ ΤΕΛΕΥΤΑΙ ΤΕΤAΡΤ ΤΕΥΧ ΤΕΧΝ ΤΕΧΝΟΛΟΓ ΤΗΛ ΤΗΛΕΦΩΝ ΤΙΜ ΤΙΤΛ ΤΜΗΜ ΤΟ ΤΟΠ ΤΟΣ ΤΟΤ ΤΟΥΡΙΣΜ ΤΟΥΡΚ ΤΟῦ ΤΡ ΤΡAΠΕΖ ΤΡΑΓΟΥΔ ΤΡΙΤ ΤΡΟΠ ΤΣΙΠΡ ΤΥΠ ΤΩΡ ΥΓΕΙ ΥΛ ΥΠAΡΧ ΥΠΗΡΕΣ ΥΠΗΡΕΣΙ ΥΠΟΥΡΓ ΥΨΗΛ ΦΕΣΤΙΒAΛ ΦΙΛ ΦΟΡ ΦΟΡA ΦΥΣΙΚ ΦΩΤ ΦΩΤΟΓΡΑΦ ΦΩΤΟΓΡΑΦΙ ΧAΡΤ ΧΡΕ ΧΡΗΣ ΧΡΗΣΙΜ ΧΡΗΣΙΜΟΠΟΙ ΧΡΗΣΤ ΧΡΟΝ ΧΡΥΣ ΧΩΡ ΧΩΡΙΣ ΩΡ ΩΡΑ\n"
     ]
    }
   ],
   "source": [
    "from sklearn.feature_extraction.text import TfidfVectorizer\n",
    "from sklearn.metrics.pairwise import cosine_similarity\n",
    "\n",
    "vec = TfidfVectorizer(max_df=0.90, min_df=5, max_features=500,lowercase=False ,\n",
    "                      analyzer = 'word')\n",
    "x = vec.fit_transform(text_data.values())\n",
    "for word in vec.get_feature_names():\n",
    "    print word,\n",
    "cosine = cosine_similarity(x)    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.4863206743113806"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# testing the text similarity of two websites\n",
    "cosine[domain_number['news247.gr'], domain_number['newsit.gr']]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from __future__ import division\n",
    "import networkx as nx\n",
    "import pprint\n",
    "import random\n",
    "import numpy as np\n",
    "from scipy import sparse\n",
    "from sklearn.model_selection import train_test_split\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def text_similarity(src, dst):\n",
    "    return cosine[domain_number[src], domain_number[dst]]  \n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Topic Extraction and Document Clustering"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# from time import time\n",
    "# from sklearn.decomposition import NMF, LatentDirichletAllocation\n",
    "# tfidf_vec = TfidfVectorizer(max_df=0.90, min_df=5, max_features=500,lowercase=False ,\n",
    "#                           analyzer = 'word')\n",
    "# tfidf = tfidf_vec.fit_transform(text_data.values())\n",
    "# tf_vec = TfidfVectorizer(max_df=0.90, min_df=5, max_features=500,lowercase=False ,\n",
    "#                           analyzer = 'word')\n",
    "# tf = tf_vec.fit_transform(text_data.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# t0 = time()\n",
    "# nmf = NMF(n_components=50, random_state=1,\n",
    "#           alpha=.1, l1_ratio=.5).fit(tfidf)\n",
    "# print(\"done in %0.3fs.\" % (time() - t0))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# def print_top_words(model, feature_names, n_top_words):\n",
    "#     for topic_idx, topic in enumerate(model.components_):\n",
    "#         print(\"Topic #%d:\" % topic_idx)\n",
    "#         print(\" \".join([feature_names[i]\n",
    "#                         for i in topic.argsort()[:-n_top_words - 1:-1]]))\n",
    "#     print()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# print(\"\\nTopics in NMF model:\")\n",
    "# tfidf_feature_names = tfidf_vec.get_feature_names()\n",
    "# print_top_words(nmf, tfidf_feature_names, 10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# lda = LatentDirichletAllocation(n_topics=605, max_iter=5,\n",
    "#                                 learning_method='online',\n",
    "#                                 learning_offset=50.,\n",
    "#                                 random_state=0)\n",
    "# t0 = time()\n",
    "# lda.fit(tf)\n",
    "# print(\"done in %0.3fs.\" % (time() - t0))\n",
    "\n",
    "# print(\"\\nTopics in LDA model:\")\n",
    "# tf_feature_names = tf_vec.get_feature_names()\n",
    "# # print_top_words(lda, tf_feature_names, 10)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# dist = 1 -cosine\n",
    "# from sklearn.cluster import KMeans\n",
    "\n",
    "# num_clusters = 605\n",
    "# km = KMeans(n_clusters=num_clusters)\n",
    "# km.fit(tfidf)\n",
    "# cluster_assignment = km.labels_.tolist()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# clusters = {i : [] for i in cluster_assignment}\n",
    "# for node, cluster in enumerate(cluster_assignment):\n",
    "#     clusters[cluster].append(G.nodes()[node])\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# import pprint\n",
    "# pprint.pprint(clusters,width=80)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Graph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "At first we create the directed graph from the 'edgelist.txt'."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2041  number of nodes\n",
      "2683  number of edges\n"
     ]
    }
   ],
   "source": [
    "import networkx as nx\n",
    "import pprint\n",
    "\n",
    "G = nx.read_edgelist('dataset/edgelist.txt', delimiter='\\t', create_using=nx.DiGraph())\n",
    "print len(G.nodes()), \" number of nodes\"\n",
    "print len(G.edges()), \" number of edges\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# random.seed(1)\n",
    "# edges = []\n",
    "# with open('dataset/edgelist.txt', 'r')as fp:\n",
    "#     for line in fp:\n",
    "#         edges.append((line.split()[0], line.split()[1]))\n",
    "# print len(edges)\n",
    "# nodes = set([node for _tuple in edges for node in _tuple])\n",
    "# print len(nodes)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Train and Test Data\n",
    "\n",
    "Training Set: For the training set we use 20760 edges that we are sure they do not exist (given in the 'non_existing_edges.txt' as the 1nd category and we use the 2683 edges from the graph which are the 2nd category for our classification problem.\n",
    "\n",
    "Test Set: We use the 4160957 edges that do not exist in the graph. From those we remove the 20760 edges that we know that don't exist to end up with 4140197 candidate edges. \n",
    "\n",
    "For the edges available in the test set we will use a classifier to predict the class for each edge(0 or 1). We are interested in the probability that an edge exists. Afterwards we sort these probabilities and obtain the top 453 edges that are used for the submission.  \n",
    "An alternate approach would be to use a number of random edges for the training set as nonexistent edges assuming that since the selective rate of such a set would be small that it would not affect as much the accuracy score.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "20760"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#load the edges that do not exist\n",
    "non_existent_edges = {}\n",
    "with open('dataset/not_existing_edges.txt', 'r')as fp:\n",
    "    for line in fp:\n",
    "        non_existent_edges[((line.split()[0], line.split()[1]))] = 0\n",
    "len(non_existent_edges)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4140197"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "non_edges = [edge for edge in list(nx.non_edges(G)) if not non_existent_edges.has_key(edge)]\n",
    "#4160957\n",
    "len(non_edges)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# #new test with random edges\n",
    "# #non_edges = [edge for edge in list(nx.non_edges(G))]\n",
    "# non_existent_edges = {}\n",
    "# random_numbers = [random.randint(0,len(non_edges)) for i in range(150000)]\n",
    "# for i in random_numbers:\n",
    "#     non_existent_edges[((non_edges[i][0], non_edges[i][1]))] = 0\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Extracting Features\n",
    "We use networkx to help us extract useful features for each node of the graph"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "pagerank = nx.pagerank(G)\n",
    "betweeness = nx.betweenness_centrality(G)\n",
    "closeness = nx.closeness_centrality(G)\n",
    "eigenvector = nx.eigenvector_centrality(G)\n",
    "degree = nx.degree_centrality(G)\n",
    "in_degree = G.in_degree()\n",
    "out_degree = G.out_degree()\n",
    "katz = nx.katz_centrality(G)\n",
    "core_number = nx.core_number(G)\n",
    "triangles = nx.triangles(G.to_undirected())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Converge after 20 iterations (eps=0.000100).\n"
     ]
    }
   ],
   "source": [
    "import graphsim as gs\n",
    "simrank = gs.simrank(G)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import math\n",
    "def adamic_adar(src, dst):\n",
    "    score = 0\n",
    "    common = list(set(G.neighbors(src)).intersection(G.neighbors(dst)))\n",
    "    return sum(1 / math.log(G.degree(w))\n",
    "                   for w in common)     \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3.0020540579927957"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "adamic_adar(u'news247.gr', u'contra.gr')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "un_g = G.to_undirected()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Community Detection\n",
    "We perform community detection on the graph using the louvain method. We obtain 605 number of communities. By examining them that some of them are really similar. For example they may belong to the same company, or they may have semantic similarity.\n",
    "We use these communities to extract two features:  \n",
    "Partition_common: declares the number of nodes from one's nodes neighborhood that exist in the same community as the other.  \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import igraph as ig\n",
    "import louvain_igraph as louvain\n",
    "G_new = ig.Graph()\n",
    "G_new.add_vertices(G.nodes())\n",
    "G_new.add_edges(G.edges())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "opt = louvain.Optimiser()\n",
    "partition = opt.find_partition(graph=G_new,partition_class=louvain.SignificanceVertexPartition)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "613\n"
     ]
    }
   ],
   "source": [
    "partition = list(partition)\n",
    "partition_names = []\n",
    "for com in partition:\n",
    "    new_com = []\n",
    "    for node_id in com:\n",
    "        new_com.append(G_new.vs[node_id]['name'])\n",
    "    partition_names.append(new_com)\n",
    "# extract names\n",
    "partitions = { node : [] for node in G.nodes()}\n",
    "for com in partition_names:\n",
    "    for node in com:\n",
    "        partitions[node].extend(com)\n",
    "print len(partition)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0  :  politikanet.gr , katafylli.gr , skopelosonline.gr , inital.gr , arcadiasports.gr , bookone1.gr , oraiokastro24.gr , siriosfm.gr , sdeeth.gr , mypatra.gr , radioamfilochia.gr , ekriti.gr , paok-athens.gr , sarakis.gr , venceremos33.blogspot.gr , sportcyclades.gr , omospondiadaniolipton.gr , pireasnow.gr , radiomanos.gr , katanalotis.gr , nexusmanagementconsultants.gr , misitimi.gr , erassitexnikopodosfairo.blogspot.gr , pkteam.gr , betforthewinners.gr , eplski.gr , oragiaspor-dramas.gr , epskastorias.gr , frontpages.gr ,\n",
      "1  :  tourist-guides.gr , mpass.gr , theacropolismuseum.gr , gbroofgarden.gr , cna.org.cy , grandebretagne.gr ,\n",
      "2  :  fiat.gr , fiatprofessional.gr ,\n",
      "3  :  left.gr , candianews.gr , papaioannou-giannis.net , epohi.gr , nonews-news.blogspot.gr , iskra.gr , pekp.gr , fisy.gr , pandiera.gr , fylosykis.gr , ekdohi.gr , alterthess.gr , rizospastis.gr ,\n",
      "4  :  archelon.gr , 360photo.gr , lakepamvotis.gr , kerkini.gr , callisto.gr , siniparxi.gr , cob.gr ,\n",
      "5  :  plantron.gr , terracom.gr , apostolata.gr , advance-it.gr , asterishotel.gr ,\n",
      "6  :  mamafromgreece.blogspot.gr , pallinipress.blogspot.gr , axortagos.gr , a-pistefto.blogspot.gr , stinplatia.gr , greek-sites.gr , mag.xirafi.gr , bloggertricks.gr , carblogger.gr , pallinotropio.gr ,\n",
      "7  :  hoteleuropa.gr , secureshop.gr , perantinostravel.gr ,\n",
      "8  :  tsig.gr , moustakasbikes.gr , dermatologist.gr , zozef.gr , gna.gr , eoskorinthou.gr , acs.gr , myxolargos.gr , homecareshop.gr , ec-goc.gr , orange-kosmima.gr , praktikesidees.gr , housevilla.gr , exhibit.gr , astrawoman.gr , monotech.gr , egynaika.gr , off-road.gr , site-com.gr , 3lykeiolamias.gr , siamakis-lawyers.gr , ledcosmos.gr , ihomeservice.gr , efarmakeio.gr , kapadiatrofi.gr , imcmodels.gr , amanites.gr , danagennisi.gr , narlis.gr , moto-plus.gr , tselepis-zaxos.gr , agoraseto.gr , selasenergy.gr , myvillage.gr , vimatizo.gr , open365.gr , mlsshop.gr , google.gr , driveandtravel.gr , onisimos.gr , vassaras.gr , interfox.gr , sagiakos.gr ,\n",
      "9  :  motoadv.gr , madnomad.gr ,\n",
      "10  :  psychinfo.gr , eirinika.gr , regionalpress.gr , imerisia-ver.gr ,\n",
      "11  :  arcon.gr , fsth.gr , oraio.gr , seniorcare.gr , mikrouli.gr , lifelinehellas.gr ,\n",
      "12  :  ekabnews.gr , dimokratiki.gr , 12ne.gr , futuremedia.gr , fire.gr , ygeia360.gr ,\n",
      "13  :  opopilis.gr , kroupi.gr , dimospylis.gr ,\n",
      "14  :  eviarchitects.gr , paravouniotissa.gr , eleftherostypos.gr , naevias.gr , eretrianews.gr ,\n",
      "15  :  atticocollege.gr , anatropionline.gr , ereportaz.gr , grafts.gr ,\n",
      "16  :  prokirixi.gr , eni-eopyy.gr , forologikanea.gr , poes.gr , et.gr , doe.gr , housepro.gr , katraslaw.gr , aneaed.gr ,\n",
      "17  :  xalatsiscare.gr , patmos.gr , itbiz.gr , inlarissa.gr , vedi.gr , dimosagias.gr , valglass.gr , dimosfarsalon.gr ,\n",
      "18  :  kairos123.gr , sport-news24gr.blogspot.gr , wres.gr , gossiptime.gr , pegasus-bio.gr , omorfisterea.gr , greekcook.gr , agones.gr , kavalagoal.gr , kethea-alfa.gr , asteiakia.gr , thermides.gr , elenkw.gr , mavrogiannistravel.gr , paixnidia24.gr , manivoice.gr ,\n",
      "19  :  panionianea.gr , postin.gr , hellas-now.com , tilegrafima.gr , greveniotis.gr , aoristies.gr , greek-inews.gr , vatolakkiotis.blogspot.gr , happytv.gr , epsilontv.gr , staratalogia.blogspot.gr , epixirimatias.gr , inveria.gr , verikoko.net , sfedona.gr , cityvoice.gr , zeidoron.blogspot.gr , dimiwise.gr , kanapedatos.blogspot.gr , hysteria.gr , i-diadromi.gr , voreini.gr , 4news.gr , loutrakiblog.gr , e-diseis.gr , altsantiri.gr , aetos-grevena.blogspot.gr , ekorinthos.gr , oxafies.com , svouranews.gr , epirus-tv-news.gr , anekshghta.blogspot.gr , kokoria.gr , parakato.gr , thessi.gr , freddonews.gr , epirus-ellas.gr ,\n",
      "20  :  antikythira-enosi.gr , scorernews.gr , kithiraikanea.blogspot.gr , kythirionpolitia.gr , ip.gr , antikythera-mechanism.gr , enimerosis.gr ,\n",
      "21  :  eastmedyachtshow.gr , newhealthsystem.gr , iatrikodiavalkaniko.gr , travelling.gr , iatriko.gr , iatrikopsychikou.gr , mononews.gr ,\n",
      "22  :  aixmi-news.gr , sinidisi.gr , prototypia.gr , epoxi.gr , weatheronline.gr , agrinionews.gr , thermo.gov.gr , e-maistros.gr , allsportsagrinio.gr ,\n",
      "23  :  sofihotel.gr , ferries.gr ,\n",
      "24  :  opcmagazine.gr , ioniantv.gr , alphafreepress.gr , peristerinews.gr , alterinfo.gr , vimanews.gr , startmedia.gr , ellhnonfos.blogspot.gr , akroama.gr , newspao.gr , nonpapernews.gr , pess.gr , creteplus.gr , protoselidaefimeridon.gr , apokoronaslife.gr , hortiatis570.gr , glyfadaweb.gr , eypspkm.gr ,\n",
      "25  :  now24.gr , mitatomasaouti.gr ,\n",
      "26  :  sainiaa.blogspot.gr , pinnokio.gr , dekaneisplaka.gr ,\n",
      "27  :  akadimiesbasket.gr , ymca.gr , coachbasketball.gr , fryganiotis.gr , ae-dikaioubc.gr ,\n",
      "28  :  gazohori.gr , naftemporiki.gr , avatonpress.gr , franchiseportal.gr , replicant.gr , clickatlife.gr , naousanews.gr ,\n",
      "29  :  nb.org , greekjustice.gr , odee.gr ,\n",
      "30  :  elde.gr , laneshealth.gr , care24.gr , formamag.gr , logodiatrofis.gr ,\n",
      "31  :  expo-world.gr , kosnet.gr , kosinfo.gr ,\n",
      "32  :  photorallypress.gr , sportaltv.gr , speedforce.gr , peristeras-tyres.gr , kartnews.gr , kokkinhshmaia.gr ,\n",
      "33  :  lamiatimes.gr , cretablog.gr , newsn.wordpress.com , tokarfi.gr , parapolitika.gr ,\n",
      "34  :  athjcom.gr , palamidi.gr , fnews.gr , kozanimedia.gr , epoli.gr , 24wro.com.gr , sierafm.gr , bovis-oliveoil.gr , iefimerida.gr , pasonop.gr , kozan.gr , tsotilion.blogspot.gr ,\n",
      "35  :  monopatiapolitismou.gr , aeiforosxoleio.gr , teiep.gr , greeklanguage.gr , realvalue.gr , help-forward.gr , certh.gr , ellinikamarket.gr ,\n",
      "36  :  paliokastro.gr , arhontiko-predari.gr , archontikofiamegou.gr , iliovasillema.gr , peraalonia.gr , oreinikorinthia.gr ,\n",
      "37  :  borioipirotika.blogspot.gr , lougantina.blogspot.gr , kranosgr.blogspot.gr , xespao.gr , orthodoxia-ellhnismos.gr , lithosfotos.blogspot.gr , attikanea.blogspot.gr , aetoshal.blogspot.gr , kapistri.blogspot.gr , redskywarning.blogspot.gr , ammosimathia.blogspot.gr ,\n",
      "38  :  redking.gr , redpress.gr , olympiacos.org , redopinion.gr ,\n",
      "39  :  ede.gr , esperides.gr , tzaniodiabetes.gr , tool.gr , hesmo.gr , eiep.gr , mednet.gr ,\n",
      "40  :  xronometro.com , protothema.gr , newsauto.gr , scoops.gr , a-special-edition.blogspot.gr , agrinionet.gr , dramini.gr , on-news.gr , epirusblog.gr ,\n",
      "41  :  e-psychology.gr , eanagnosis.gr , money-money.gr , happymind.gr , vysinimelissa.gr , newsitamea.gr , kountouris.gr , cosmictelegram.gr , alekati.gr , odigostoupoliti.eu , sotostips.gr , botanologia.blogspot.gr , tastefull.gr ,\n",
      "42  :  ptolemaida.gr , karanik.gr , neaptolemaidas.gr ,\n",
      "43  :  ertopen.com , prn.gr , omniatv.com , kethea.gr , goodnet.gr , mitsosbet.gr , tokeli.gr ,\n",
      "44  :  edupame.gr , kanep-gsee.gr , pamehellas.gr , oiele.gr , fle.gr , syndikatooikodomonathinas.gr ,\n",
      "45  :  info-sterea.gr , business-line.gr , info-greece.gr , topodigos.gr , info-kriti.gr , info-thessalia.gr ,\n",
      "46  :  ekpizo.gr , inka.gr , siaperaslaw.gr ,\n",
      "47  :  bankingnews.gr , taxydromeio.gr , fpress.gr , makedonianews.gr , paratiritis-news.gr , flashnews.gr , healthview.gr , pak-elta.gr , evianews.com , xaxa.gr ,\n",
      "48  :  e-camping.gr , rise.gr , athensmagazine.gr , tilestwra.com , newsone.gr , youweekly.gr , david-avramidis.gr , diaforetiko.gr , fimes.gr , masternews.gr , viralcity.gr ,\n",
      "49  :  salamisol.gr , independent.gr , theatromania.gr , totrenostorouf.gr , mousikes-diadromes.gr , artic.gr , musicity.gr ,\n",
      "50  :  athenstimeout.gr , techfrog.gr ,\n",
      "51  :  minfin.gr , sethess.gr , dake-yppot.gr ,\n",
      "52  :  melisagraphics.gr , ebiskoto.gr ,\n",
      "53  :  blacknews.gr , pythari.gr , sport-fm.com.cy , tvnea.com , filoksenos.blogspot.gr ,\n",
      "54  :  durostick.gr , mastrobob.gr , melihourtis.gr ,\n",
      "55  :  logiastarata.gr , online-pressblog.blogspot.gr , silktech.gr , anasfalistoi-oaee.gr , thebest.gr , onestopdeals.gr , thrakitoday.com ,\n",
      "56  :  interprom.gr , athleticlarissa.gr ,\n",
      "57  :  karageorgosphotography.gr , dreamsbyplatinum.gr , kanokratisi.com , vgainoexo.gr , seleo.gr , europeanbabyschool.gr , kanokratisi.gr ,\n",
      "58  :  iteam.gr , symmaxiagiatinellada.gr , italia.gr ,\n",
      "59  :  florinapress.gr , meteorologos.gr , efpalio.wordpress.com , pergamoshotel.gr , toxwni.gr ,\n",
      "60  :  firstevent.gr , cretadeal.gr , grelia.gr ,\n",
      "61  :  infokids.gr , saveandwin.gr , nethall.gr , eimaimama.gr , deal-deal.gr , pigolampides.gr , babysmart.gr , frameout.gr ,\n",
      "62  :  my-tv.gr , kritikosfm.gr ,\n",
      "63  :  tracerclub.gr , pressaris.gr , cycladesguide.gr , alphafm.gr , press724.gr , fuelprices.gr , sony.gr , tyreshop.gr , anglers.gr ,\n",
      "64  :  onsports.gr , newsbomb.gr , cnn.gr , gossip-tv.gr , astrology.gr ,\n",
      "65  :  dinfo.gr , kollima.gr , videoman.gr , mixanitouxronou.gr , apofasizo.gr ,\n",
      "66  :  mediforma.gr , patsialas.gr , ophthalmiatreio.gr , iatreion.gr ,\n",
      "67  :  veteranos.gr , newshellas.blogspot.gr , logiosermis.net , creteisland.gr ,\n",
      "68  :  thermo-portal.gr , neanews.gr , jokestream.blogspot.gr , adiexodos.gr ,\n",
      "69  :  kanarienhaus.gr , klouvi.gr , alop.gr , canaries.gr ,\n",
      "70  :  trelokouneli.gr , markos.tv , belladonna.gr , botilia.gr , markostv.gr , enikos.gr , e-citymap.gr , maxperrychocolates.gr ,\n",
      "71  :  ford-sfakianakis.gr , sfakianakis.gr ,\n",
      "72  :  tsakbam.gr , fashionstyles.gr , astra-oneira.gr ,\n",
      "73  :  djchriskaltsas.gr , xenonasmazaraki.gr , lifo.gr , parallaximag.gr , diavasame.gr , politeianet.gr , kritiki.gr , bookpress.gr , bookbar.gr ,\n",
      "74  :  tosynergeio.gr , heliev.gr ,\n",
      "75  :  inevia.gr , xreiazomai.gr ,\n",
      "76  :  arkadiapress.gr , arcadia-news.gr , arcadiaportal.gr , spartakos-dei.gr , kafeneio-megalopolis.gr , e-gortynia.gr ,\n",
      "77  :  iator.gr , pertsemlidis.gr , asxetos.gr , gourmelia.gr , dietup.gr , ipop.gr ,\n",
      "78  :  ellinikabaharika.gr , ellinikabotana.gr , salveotea.gr ,\n",
      "79  :  alpamayopro.gr , flabouri.gr , savvaskonstantinidis.gr ,\n",
      "80  :  ekdromi.gr , tourismawards.gr , nespresso-pro.gr , traveldailynews.gr , globeone.gr ,\n",
      "81  :  volleyleague.gr , euromedica.gr , cartridgeworld.gr ,\n",
      "82  :  kalimeraellada.gr , anexartitos.gr , vitamelia.gr , cyclades24.gr , travelstyle.gr , pets-friends.gr ,\n",
      "83  :  dimosmaroneiassapon.gr , enterprise-hellas.gr ,\n",
      "84  :  techgear.gr , prasinanea.gr , news247.gr , 24media.gr , oneman.gr , sport24.gr , huffingtonpost.gr , macuser.gr , ladylike.gr , contra.gr , redplanet.gr , olapaok.gr ,\n",
      "85  :  autotriti.gr , museum-hotel.gr ,\n",
      "86  :  shootandgoal.com , briefingnews.gr , ikypros.com , tothemaonline.com , riknews.com.cy , lay-out.gr , dialogos.com.cy , onlycy.com , cyprusnet.gr , pafospress.com , sae.gr , cyprusrodos.gr , offsite.com.cy , cyprusnews.eu ,\n",
      "87  :  artishard.gr , enthemata.wordpress.com , rednotebook.gr , cancelletto.gr ,\n",
      "88  :  baby.gr , k-mag.gr , cooktherapy.gr , astrolife.gr , cookbox.gr , babytips.gr , kissmygrass.gr ,\n",
      "89  :  leathermall.eu , claires.gr , villagecinemas.gr , themallathens.gr ,\n",
      "90  :  tuned.gr , trustradio.gr ,\n",
      "91  :  dimoszirou.gr , dimosvoiou.gr , dimosprevezas.gr , apdattikis.gov.gr , php.gov.gr , amyntaio.gr , apdhp-dm.gov.gr , nestorio.gr , damt.gov.gr , apdaigaiou.gov.gr , dimos-deskatis.gr , dimospargas.gr , pogoni.gr , pallini.gr ,\n",
      "92  :  redfm.gr , zoornalistas.blogspot.gr , nrg95.gr , cretetv.gr , pcmaster.gr , thecaller.gr , koutipandoras.gr , trikkipress.gr , efimerides.eu , goalpost.gr , arouraios.gr , hotdoc.gr , sportit.gr , topnews.gr , boro.gr , olympia.gr , official.gr , patrisnews.com , el.gr , nextdeal.gr , axiaplus.gr , to-kounavi.gr , zappit.gr , superbasket.gr ,\n",
      "93  :  perierga.gr , toratora.gr , notfaq.gr , topi.gr , messiniaradio.gr , gazzetta.gr ,\n",
      "94  :  slimmingpills.gr , greencoffeeextract.gr , lipodialites.gr ,\n",
      "95  :  filippoupolitis.gr , saveltrade.gr ,\n",
      "96  :  grand-forest.gr , biomedicinlab.gr , urogyn.gr , xeirourgiki-thorakos.gr , createyourself.gr , medicalhellas.gr , vougioukasv.gr , podologie.gr , laserdentalclinic.gr , voyatzimaria.gr , nevroepistimes.gr , dr-arsenis.gr , drpolyzos.gr , pmanolakou.gr , christoforidou.gr , poulakaki.gr , drstratis.gr , microcheck.gr , borousas.gr ,\n",
      "97  :  abtax.gr , pim.gr ,\n",
      "98  :  poeyps.gr , aep.gr ,\n",
      "99  :  oneirokritis.org , herblife.gr , sidages.gr ,\n",
      "100  :  freecinema.gr , aiff.gr , eyelands.gr , ellet.gr ,\n",
      "101  :  bestpharmacy.gr , safesales.gr , snif.gr , holidayland.gr ,\n",
      "102  :  cookshop.gr , deneinaiparamithi.gr , electrocycle.gr , fasois.gr ,\n",
      "103  :  drive.gr , krini-kalamaria.blogspot.gr , avmag.gr , alldaynews.gr , newsit.gr ,\n",
      "104  :  styleiconboutique.com , irokids.gr , troumpoukis.gr , toys.gr , zarkaditools.gr , kmtools.gr , kalavroyzioti.gr , justshop.gr , mandis.gr , tshoes.gr , moraitopoulos.gr , bestprice.gr , greekbooks.gr , watchoutlet24.com , mustshop.gr , agorazoome.gr ,\n",
      "105  :  reportaznet.gr , totalfitness.gr , techblog.gr , cambiabooks.gr , parapona-rodou.blogspot.gr , videocosmos.gr , bloodyfever.com , lobbystas.gr , antipagkosmiopoihsh.gr , tsantiri.gr , thesecretrealtruth.blogspot.gr , press-gr.com , sahiel.gr , katohika.gr , newsalamina.net , indeepanalysis.gr , click4money.gr , filonoi.gr , greki-gr.blogspot.gr , tampouloukia.gr , olafree-gr.blogspot.gr , dikigorosergatologos.gr , zoomblog.org , neadiatrofis.gr , alexiptoto.com , booksmania.gr , papatzides.blogspot.gr , typologies.gr , neogr.blogspot.gr , anekdotakiastv.blogspot.gr ,\n",
      "106  :  dsnafpliou.gr , nafplionfestival.gr , fougaro.gr , amfitriti-pension.gr , argolidalife.gr , nafplio.gr ,\n",
      "107  :  dentallist.gr , atticahealth.gr , business-cards.gr , health-line.gr ,\n",
      "108  :  11888.gr , ioannina24.gr ,\n",
      "109  :  sofikoukouvagia.gr , ideostato.gr , kala-nea.gr , peopleandideas.gr , ebooks4greeks.gr , openbook.gr , saitapublications.gr ,\n",
      "110  :  dimos-amfiklias-elatias.gr , aliartos.gov.gr , malian.gov.gr , greek-tourism.gr , kimis-aliveriou.gr , tanagra.gr , mwlos.gr , stylida.gr , eretria.gr ,\n",
      "111  :  zografiki.com , humor.gr , postokano.gr , diafimistika.com ,\n",
      "112  :  fouit.gr , koolnews.gr , thestival.gr ,\n",
      "113  :  kissamostv.gr , agonaskritis.gr , cretalive.gr , epofek.gr ,\n",
      "114  :  archipelago.gr , ikariamag.gr ,\n",
      "115  :  melodia.gr , e-tetradio.gr , agorapress.gr , fm100.gr , arttv.info , goodradio.gr , arenafm.gr , alpha965.gr , store.paokfc.gr ,\n",
      "116  :  elta-courier.gr , agrotek.gr , e-agri.gr , xenonlights.gr , autoflan.gr , psselta.gr , airgunshop.gr , myaroma.gr ,\n",
      "117  :  hcmc.gr , teletrade-dj.gr ,\n",
      "118  :  otishop.gr , action24.gr ,\n",
      "119  :  sky.gr , tastv.gr ,\n",
      "120  :  bathingwaterprofiles.gr , eidiseis-simera.gr ,\n",
      "121  :  koufa.gr , mag24.gr , allnewsgr.eu , olympiaodos.gr , aegeanmotorway.gr , polispark.gr , aragma.gr , stoxasmos-politikh.blogspot.gr , diekpereoseis.gr , tokoulouri.com , ellaktor.gr ,\n",
      "122  :  hamogelo.gr , rethymnoguide.gr , thatsit.gr , eodathens.gr , trazeras.gr , edok.gr , tzivas-epipla.gr , greekrowers.blogspot.gr , sportsfeed.gr ,\n",
      "123  :  fractal.gr , zclub.gr ,\n",
      "124  :  alexwebradiotv.blogspot.gr , zantemats.gr , panetolikos.gr , pameproedre.blogspot.gr , fmvoice.gr , gavros.gr , novasports.gr , autovision.gr ,\n",
      "125  :  myblogs.gr , allweirdstories.gr , tinostoday.gr , anagnostis.org , froyros.blogspot.gr , moriasnow.gr , gnomikilkis.blogspot.gr , musicpress.gr , inkomotini.gr ,\n",
      "126  :  bigstore.gr , christmastore.gr ,\n",
      "127  :  komotinipress.gr , kavalapress.gr , ioanninapress.gr ,\n",
      "128  :  chalket.gr , museduc.gr , gourmed.gr , kipi.gr , birds.gr , wwf.gr , arnos.gr , elkosmas.gr , neo.gr , grafoulis.gr , chiourea.gr , mazigiatopaidi.gr , protaki.gr ,\n",
      "129  :  epimlas.gr , pepkritis.gr ,\n",
      "130  :  why.gr , wrohellas.gr ,\n",
      "131  :  ktel-lakonias.gr , ktelattikis.gr , rodosisland.gr , monopoli.gr , aion.gr , livingingreece.gr , praktiker.gr , kariera.gr , ktelvolou.gr , network-sam.blogspot.gr ,\n",
      "132  :  armeniakos.gr , medicalland.gr , financialbox.gr , crashonline.gr ,\n",
      "133  :  4troxoi.gr , capital.gr , breakthroughgreece.gr , shape.gr , 2cvclub.gr , steliosparliaros.gr , yupiii.gr , atticamediagroup.gr ,\n",
      "134  :  northmeteo.gr , zooradio.gr , ibizaclub.gr , dynati-ellada.gr ,\n",
      "135  :  diadoseto.blogspot.gr , amaliadanews.gr , paradrasi.gr , echedoros-a.gr , ihunt.gr , mikroskopio.gr , greekalert.com , hellasforce.com , stoxos.gr , presspublica.gr , amynastospiti.gr , ekeo.gr ,\n",
      "136  :  xionati.gr , kantas.gr ,\n",
      "137  :  lamiareport.gr , thermoydravliki-galaneika.gr ,\n",
      "138  :  mdahellas.gr , missbloom.gr , greecevirtual.gr , pnoe.gr , cityofathens.gr , singleparent.gr , kalyterizoi.gr , goldmum.gr , theophilos.gr , paidorama.com , nestlenoiazomai.gr , kea-hara.gr ,\n",
      "139  :  klinikiagiosloukas.gr , babyswimthessaloniki.gr ,\n",
      "140  :  pefni.gr , moh.gov.gr , pomitedy.gr , piraeuspress.gr , hivaids.gr , 2dype.gr , amea-blog.blogspot.gr , iatrikoprofil.gr ,\n",
      "141  :  nafsimedon.gr , ippoliti.gr ,\n",
      "142  :  koukles.gr , bitros.gr , arhon.gr , kalco.gr , bcom.gr ,\n",
      "143  :  greekradios.gr , citylife24.gr ,\n",
      "144  :  miltech.gr , infognomonpolitics.blogspot.gr , militaire.gr , elladasimera.blogspot.gr , pentapostagma.gr ,\n",
      "145  :  panteion.gr , topa.gr ,\n",
      "146  :  online-shopping.gr , filiatravoice.blogspot.gr , ypodomes.com , dimostrifylias.gr , coffeeisland.gr , dailyarticle.gr ,\n",
      "147  :  publishitmagazine.gr , artion.gr , metronanalysis.gr , artapress.gr , psichogios.gr , connect-line.gr ,\n",
      "148  :  inaoussa.gr , kerkidasport.gr ,\n",
      "149  :  trekking.gr , bluepalace.gr , navigator.gr , mastoremata.gr , electrahotels.gr , insquash.gr , kraftpaints.gr , sete.gr , kepeth.gr ,\n",
      "150  :  creativityfilms.gr , enachannel.gr , videotex.gr ,\n",
      "151  :  pliroforiodotis.gr , 3guys.gr ,\n",
      "152  :  enosy.blogspot.gr , 136.gr , antonisliakos.gr , nostimonimar.gr , contra-xreos.gr , crradio.gr ,\n",
      "153  :  info-war.gr , tiniakos.gr , parosnews.gr , jungle-report.blogspot.gr , unfollow.com.gr , ellinofreneianet.gr , fanaripress.gr , imerodromos.gr ,\n",
      "154  :  onar-andros.gr , moca-andros.gr ,\n",
      "155  :  zoisthanos.gr , visit-trikala.gr , visit-sporades.gr ,\n",
      "156  :  supersyntages.gr , koytsompolio.gr ,\n",
      "157  :  maresei.gr , nea-acropoli-thes.gr , nea-acropoli.gr , cityportal.gr , kerdiseto.gr ,\n",
      "158  :  vipnews.gr , lifestyle-gr.blogspot.gr , derpouli.gr ,\n",
      "159  :  pontos-news.gr , sportdog.gr , insider.gr , yiannislucacos.gr , sigmalive.com , cyta.gr , wedia.gr , ixoripansi.gr ,\n",
      "160  :  bullyshop.gr , sikushop.gr ,\n",
      "161  :  cleverstore.gr , afasia.gr ,\n",
      "162  :  greekarchitects.gr , profil.gr , vakalo.gr ,\n",
      "163  :  sixdogs.gr , roleplay.gr , athensfixedgear.gr , idillivillas.gr , ticketservices.gr , popaganda.gr , summercinemas.gr , dominos.gr , avopolis.gr ,\n",
      "164  :  plantech.gr , dodoni.gr , eex.gr , panagiotisathanasopoulos.gr , stcatherines.gr , uoi.gr , epiruspost.gr , positivity.gr ,\n",
      "165  :  humangrid.gr , elliniko-argyroupoli.gr , dad.gr , agapotonalimo.gr , dimotikosafari.blogspot.gr , organosi20.gr , silvercity.gr ,\n",
      "166  :  mysolution.gr , 10deco.gr ,\n",
      "167  :  report24.gr , korinthiakoi-orizontes.blogspot.gr , statesmen.gr , lykavitos.gr , kalavrytanews.com , archontiko.gr , ysterografa.gr , freddotv.gr ,\n",
      "168  :  freerider.gr , snowguide.gr ,\n",
      "169  :  grnet.gr , gr-ix.gr ,\n",
      "170  :  stavento.gr , missouras.gr , oasth.gr , akto.gr ,\n",
      "171  :  freemeteo.gr , paiania.gov.gr , oraiokastro.gr , martiriko-kommeno.gr , dimosdelta.gr , kek-nefeli.gr ,\n",
      "172  :  fileleutheros.net , antiparos.gr , esparou.gr ,\n",
      "173  :  vg24.gr , octavaradio.gr ,\n",
      "174  :  fertilitycrete.gr , greenbusiness.gr ,\n",
      "175  :  xn--mxaefpbee9acbbtbudhf0a7a.gr , rinoplastiki.gr , lipoanarofisi.gr ,\n",
      "176  :  dealnow.gr , ftina-aeroporika-eisitiria.gr , paketadiakopon.gr ,\n",
      "177  :  meleniko.gr , aposerres.gr ,\n",
      "178  :  indrama.gr , astrosnews.gr , iatropedia.gr , toys-shop.gr ,\n",
      "179  :  polydroso.gr , webtv.ert.gr , alcopolls.gr , spartathlon.gr , ert.gr , kilkis24.gr ,\n",
      "180  :  bluebig.wordpress.com , agiazoni.gr , floga.gr , antikleidi.com , mikrasiatis.gr , alopsis.gr ,\n",
      "181  :  cooktime.gr , hellasbusinessbook.gr , my-magazine-gr.blogspot.gr , chefoulis.gr , oikaliteressyntagesmou.blogspot.gr ,\n",
      "182  :  tribalworldwide.gr , edenred.gr , gpma.gr ,\n",
      "183  :  beautetinkyriaki.gr , fanpage.gr , tsakoseto.blogspot.gr ,\n",
      "184  :  wehellas.gr , casino.gr , bluearena.gr , foxbet.gr , onlarissa.gr ,\n",
      "185  :  radiocafe.gr , onradio.gr , mouzakinews.gr , gavdos-dimos.com , radio-lehovo.gr , gavdosfm.gr , aquariusfm.gr ,\n",
      "186  :  alibinisis.gr , coffeerepublic.gr , deliolanis.gr , athensgo.gr , carglass.gr , kritikos-sm.gr , violanta.gr , unescopireas.gr , kafkas.gr , noratex.gr , freshline.gr , gounelas.gr ,\n",
      "187  :  paramarketing.gr , polisinthesi.gr , fragoulakis.gr ,\n",
      "188  :  astro.gr , venus-spell.gr ,\n",
      "189  :  toolfinder.gr , manioudakis-machines.gr ,\n",
      "190  :  dimosedessas.gov.gr , gng.gr , skydra.gr , elga.gr ,\n",
      "191  :  archaiologia.gr , elzoni.gr , hcg.gr , koutouzis.gr , byzantinemuseum.gr , thetoc.gr ,\n",
      "192  :  idkaramanlis.gr , thanos-plevris.gr , kedikoglou.gr , ndthessaloniki.gr , giakoumatos.gr , adonisgeorgiadis.gr , xverginis.gr , stavros-kalafatis.gr , nd.gr ,\n",
      "193  :  roulismaroulis.wordpress.com , harryklynn.blogspot.gr , odontiatriki.gr , neanea.gr , gagarin205.gr , thehellenicmail.gr , avgi.gr ,\n",
      "194  :  online-royxa.gr , online-rouxa.gr ,\n",
      "195  :  osekk.gr , ebasket.gr ,\n",
      "196  :  roi-kadoglou.gr , exploria.gr ,\n",
      "197  :  play247.gr , buldoza.gr , simplyburgers.gr , arcadialive.gr , e-shop.gr , thess.gr , oneiros.gr , citybranding.gr , mydrupal.gr , greekestate.gr , radiobubble.gr , insurancemarket.gr , kalamatain.gr , nylon.gr , beetroot.gr , opencoffee.gr , baas.gr ,\n",
      "198  :  robotstore.gr , xyloioniki.gr , aristotleracing.gr , ktelthes.gr , mihail-fas.gr , dasteri.gr , henkel.gr , pg-plaisio.gr , autospark.gr ,\n",
      "199  :  nrgweb.gr , stoplekto.gr , asterasnikaias.gr , kompodema.gr , topiko24.gr , olympiakosneonliosion1952.blogspot.gr , sportactive.gr ,\n",
      "200  :  ledomagazo.gr , mdigitalphoto.gr , cptpapadakisphoto.gr ,\n",
      "201  :  bee.gr , dimitra.gr , anthropomania.gr ,\n",
      "202  :  porphyrios.gr , orthmad.gr ,\n",
      "203  :  readfree.gr , myastro.gr , theskati.gr ,\n",
      "204  :  katerini.gr , festivalolympou.gr , dion-olympos.gr ,\n",
      "205  :  iskavalas.gr , isx.gr , islesv.gr , nlg.gr , ispatras.gr , xanthinews.gr , presidency.gr , bioethics.gr , cancer-society.gr , nchr.gr ,\n",
      "206  :  businessclub.gr , panargiakosfc.gr ,\n",
      "207  :  cybereddie.gr , thevoyager.gr ,\n",
      "208  :  nightwalk.gr , apergia.gr , trainose.gr , osy.gr ,\n",
      "209  :  prismaradio.gr , lefkadatoday.gr ,\n",
      "210  :  livefootball.gr , multi-news.gr ,\n",
      "211  :  iskilkis.gr , iatroi.eu , idika.gr ,\n",
      "212  :  theatronostimies.gr , enlefkofestival.gr , ianos.gr ,\n",
      "213  :  trikalacity.gr , milosxotikon.gr ,\n",
      "214  :  24radio.gr , radiomelodia.gr , e-ptolemeos.gr ,\n",
      "215  :  bios.gr , bitcoinx.gr , voria.gr , maxfm.gr , e-food.gr , dimokratianews.gr , efimeridaki.gr ,\n",
      "216  :  nikaia-church.gr , christianity.gr , eaep-kastoria.gr ,\n",
      "217  :  amiad.gr , herma-dramatherapy.gr , bessistextiles.gr ,\n",
      "218  :  carp-matchfishing.gr , psarema.gr ,\n",
      "219  :  attikiourologia.gr , huanet.gr ,\n",
      "220  :  petinoshotel.gr , saintjohn.gr , hotelnissaki.gr ,\n",
      "221  :  niceandneat.gr , beer.gr ,\n",
      "222  :  dete.gr , metropolisradio.gr , deliveras.gr , douvris.gr , velvet968.gr ,\n",
      "223  :  paidagogiki.gr , paidagogikiprotoporia.gr ,\n",
      "224  :  3ystra.gr , tromero.eu , enwsi.gr , ktelfthiotidos.gr , tvaek.blogspot.gr , gkordis.com , tweetyblogs.gr ,\n",
      "225  :  doxato.gr , prosotsani.gr , diaamath.gr , eeth.gr , europeanyouthcard.gr ,\n",
      "226  :  irealty.gr , mydir.gr ,\n",
      "227  :  progamerz.gr , animeplanet.gr , comicworld.gr , goradio.gr , animehouse.gr , gameslife.gr ,\n",
      "228  :  greekexporters.gr , visitgreece.gr , houdishouses.gr , symi-hotel-aliki.gr , dimos-symis.gr , aopoligirou.gr , basket.gr , iasonstudios.gr , eooa.gr ,\n",
      "229  :  zontanonero.gr , godtube.gr ,\n",
      "230  :  albatros.gr , taxireservations.gr ,\n",
      "231  :  paramithia-gia-paidia.gr , proskliseis-kartes.gr , kidsfun.gr ,\n",
      "232  :  igniteathens.gr , salamina-123.gr , agiannopoulos.gr , dealnews.gr , safershop.gr , dimos-neaszixnis.gr , press-time.gr , skai.gr , insomnia.gr ,\n",
      "233  :  okana.gr , radiopeirasmos.gr , patrasevents.gr , xarisezoi.gr ,\n",
      "234  :  advanced-endoscopy.gr , bonstudio.gr , survival.gr , digital4u.gr , eligast.gr ,\n",
      "235  :  platonkek.gr , dimoskarditsas.gov.gr , esmjt.gr , statuskek.gr , karditsa-city.gr , infotaxis.gr , oaed.gr ,\n",
      "236  :  likovrisipefki.gr , enypografa.gr , penteli.gov.gr , edsna.gr ,\n",
      "237  :  bigman.gr , ullapopken.gr ,\n",
      "238  :  youandme.gr , tepostone.gr ,\n",
      "239  :  postwave.gr , inner-ear.gr ,\n",
      "240  :  culturenow.gr , allaboutfestivals.gr , kefalonitikanea.gr , afoistefatou.gr , geoservice.gr , alphatv.gr , saristrafestival.gr , greekfestival.gr , athina984.gr ,\n",
      "241  :  e-yliko.gr , pdeamth.gr , pe19.gr , theodoramavridou.blogspot.gr , paspa.gr ,\n",
      "242  :  xsa.gr , epirusgate.blogspot.gr , thespot.gr , happyweek.gr , kitespots.gr ,\n",
      "243  :  agroticanews.gr , exelixinews.gr , e-volos.gr , programmatileorasis.gr , photoscrete.gr , lcitynews.blogspot.gr , hfaistos.blogspot.gr ,\n",
      "244  :  childit.gr , e-mesara.gr , kindykids.gr , babyradio.gr ,\n",
      "245  :  starsports.gr , lamiastar.gr , beachtennisgreece.gr ,\n",
      "246  :  alouminia-fousekas.gr , primasystems.gr , moisiadis-publications.gr , alounet.gr ,\n",
      "247  :  rodosreport.gr , secretrhodes.gr ,\n",
      "248  :  newsrebel.gr , e-oro.gr , starsmile.gr , atticalawyers.gr ,\n",
      "249  :  ringsofpain.gr , inout.gr ,\n",
      "250  :  agriniotimes.gr , omonoia-nafpaktou.gr , diogenis-press.gr , gnomiartas.gr , newsbeast.gr , kalamadata.gr , epirushotels.gr ,\n",
      "251  :  toperiodiko.gr , humbazine.gr , pgeole.gr ,\n",
      "252  :  canava.gr , redgas.gr ,\n",
      "253  :  life2day.gr , enternity.gr , radioin.gr , flix.gr , tpdy.gr ,\n",
      "254  :  enduro.gr , 2stroke.gr ,\n",
      "255  :  dealistic.gr , seofuture.gr ,\n",
      "256  :  pdm.gov.gr , fskozani.gr , easytech.gr ,\n",
      "257  :  agriniopress.gr , e-thessalia.gr , kynoclub.gr , seisaxthia.wordpress.com , topontiki.gr , ilioupoligiaolous.gr , realestatenews.gr , atpreveza.gr ,\n",
      "258  :  ipathessaloniki.gr , yperdiavgeia.gr , ierapetra.gov.gr ,\n",
      "259  :  paradise-hotel.gr , alonissos.gr ,\n",
      "260  :  gynae4u.gr , euroclinic.gr , hsccp.gr ,\n",
      "261  :  pem.gr , narcohypnosis.wordpress.com , nomikithess.gr , aiesec.gr , gge.gr , auth.gr , teloglion.gr ,\n",
      "262  :  fyta-arkadias.gr , plakakia-xoubavlis.gr ,\n",
      "263  :  soulouposeto.gr , thalassoksila.blogspot.gr ,\n",
      "264  :  fishing-mastro.gr , mrkteo.gr , redgoal.gr , tonerhellas.com ,\n",
      "265  :  zois.gr , barracuda.gr , marinco.gr ,\n",
      "266  :  srortanthoussa.blogspot.gr , epsprevezas-lefkadas.gr ,\n",
      "267  :  atomizer.gr , bestof.gr ,\n",
      "268  :  myfreeshop.gr , offerspot.gr ,\n",
      "269  :  newmoney.gr , adapokrites.gr , fumara.gr , nafpaktianews.gr , piperies.gr , makeleio.gr , magicnews.gr ,\n",
      "270  :  aenol.gr , dimoselassonas.gr , polygyros.gr , ots.gr , pavlosmelas.gr ,\n",
      "271  :  web-mate.gr , glaveris.gr ,\n",
      "272  :  liberal.gr , evenizelos.gr , intechs.gr , pasok.gr , moraitisthanos.gr , mageirikesdiadromes.gr ,\n",
      "273  :  tv4e.gr , synaxipalaiochoriou.blogspot.gr , antibaro.gr , imelef.gr ,\n",
      "274  :  statbank.gr , traveltimes.gr ,\n",
      "275  :  hlektronikatsigara.com.gr , esmoke.gr ,\n",
      "276  :  rockandroll.gr , kyttarolive.gr ,\n",
      "277  :  istorikathemata.com , rimse.gr , aekfans21.com , molwlave.blogspot.gr , greeknation.blogspot.gr , dexiextrem.blogspot.gr , eglimatikotita.gr , antifonitis.gr , symvolinews.gr , sitalkisking.blogspot.gr , onalert.gr ,\n",
      "278  :  weirdnews.gr , iwrite.gr ,\n",
      "279  :  pamth.gov.gr , fsevrou.gr , evros24.gr , thrakifm.gr , alexpolisonline.com , thrakisport.gr , sferikos.gr ,\n",
      "280  :  avek.gr , coffeebean.gr ,\n",
      "281  :  meteo-news.gr , pireasnews.gr , meteoliosia.gr ,\n",
      "282  :  sportshero.gr , basketblog.gr , weplayball.gr , 5clean.gr , gsap.gr , womensports.gr , makripodis.gr ,\n",
      "283  :  theomana.gr , argolikeseidhseis.gr , amen.gr ,\n",
      "284  :  themelio-her.gr , uth.gr , esos.gr , toergastirisxediou.gr , dimosvolos.gr , doepap.gr , pe03.gr ,\n",
      "285  :  mekarta.gr , orthomedicare.gr , cverros.gr , ploigos.gr , copyexpress.gr , iatrica.gr , kifissia24.gr ,\n",
      "286  :  supernaturalgreece.gr , abouttvseries.gr , tv-island.blogspot.gr , cinetv-world.blogspot.gr , walking-dead-in-greece.blogspot.gr ,\n",
      "287  :  bmwriders.gr , carparadise.gr ,\n",
      "288  :  cyclingworld.gr , triathlonworld.gr ,\n",
      "289  :  save4you.gr , autopro.gr ,\n",
      "290  :  ggde.gr , adeies-xeiriston.gr ,\n",
      "291  :  makmarine.gr , waterboys.gr ,\n",
      "292  :  emst.gr , photobiennale-greece.gr , artnews.gr , art-athina.gr ,\n",
      "293  :  haniotika-nea.gr , eparxiakofos.gr , stcloris.gr ,\n",
      "294  :  freebets.gr , greekaffiliates.gr ,\n",
      "295  :  enarxikospolitis.blogspot.gr , kilkistoday.gr , thema-xronou.gr ,\n",
      "296  :  agsavvas-hosp.gr , physio.gr , craniosacral.gr , eeef.gr , psf.org.gr ,\n",
      "297  :  dramania.gr , mycoffees.gr , trikalasportiva.gr ,\n",
      "298  :  zeolithos.gr , naturam.gr ,\n",
      "299  :  elsyn.gr , nestos.gr , dimosnet.gr ,\n",
      "300  :  temposport.gr , petrogaz.gr , panionios.gr ,\n",
      "301  :  siteline.gr , karakiza-tsampika.gr , happyparenting.gr , wtmnews.gr , ellak.gr ,\n",
      "302  :  babyfeat.gr , pamebolta.gr , ikk.gr , domokos.gr , tanea.gr , sevipa.gr ,\n",
      "303  :  greekwineland.gr , wineroads.gr ,\n",
      "304  :  agiamoni.gr , jahoo.gr , pontarisma.gr ,\n",
      "305  :  joytv.gr , follifollie.gr , game20.gr , pantso.gr , petas.gr ,\n",
      "306  :  thassosisland.gr , golden-beach-inn.gr ,\n",
      "307  :  mommywiki.gr , oloutoukosmouoidiaskeyes.wordpress.com , kallisblog.gr , spoon-stories.com , argiro.gr , best-sites.gr , all4blogs.gr ,\n",
      "308  :  cuba.gr , deals.touristorama.com ,\n",
      "309  :  2810.gr , radioepirus.gr , dos.gr , e-sterea.gr ,\n",
      "310  :  pste.gov.gr , moliotis.gr , lamia.gr , lamiarunfestival.gr ,\n",
      "311  :  saiti.gr , lavaron.gr ,\n",
      "312  :  autoparts-batteries.gr , newcottonplanet.gr , softways.gr ,\n",
      "313  :  aekfc.gr , aek.gr , chessfed.gr , nokchess.gr ,\n",
      "314  :  elliniko-panorama.gr , athensvoice.gr , trollingstone.gr ,\n",
      "315  :  tennisnews.gr , kalamatatennis.gr , avis.gr , tennisforum.gr , efoa.gr ,\n",
      "316  :  eiead.gr , ngodiastasi.gr ,\n",
      "317  :  ivfathenscenter.gr , kiveli.gr ,\n",
      "318  :  respentza.blogspot.gr , parapolitiki.com ,\n",
      "319  :  spitoskylo.gr , away.gr , couchpotato.gr ,\n",
      "320  :  energ.gr , adtherm.gr ,\n",
      "321  :  romfea.gr , imkastorias.gr , ioannis-kapodistrias.gr ,\n",
      "322  :  footballpro.gr , footballleaguenews.gr ,\n",
      "323  :  xeirotexnes.gr , bebeautylicious.gr ,\n",
      "324  :  pythagoreandiet.blogspot.gr , kalliergo.gr ,\n",
      "325  :  grms.gr , laskaridou.gr ,\n",
      "326  :  gpatoulis.gr , isathens.gr , athinorama.gr , matrix24.gr , aisxylia.gr , teosagapo7.com ,\n",
      "327  :  policenet.gr , pitsirikidotnet.gr , kourdistoportocali.com ,\n",
      "328  :  limnosgreece.gr , emprosnet.gr , lesvosgreece.gr , olivenews.gr , lesvosbooks.gr ,\n",
      "329  :  live24.gr , loveradio.gr , ellinilatris.blogspot.gr ,\n",
      "330  :  ameliko.gr , rafting-athletic-center.gr ,\n",
      "331  :  apogee.gr , ktelmakedonia.gr , greekwinefederation.gr ,\n",
      "332  :  prv2014thess.gr , kzervas.gr ,\n",
      "333  :  web-electric.gr , bitamin.gr ,\n",
      "334  :  faysbook.gr , gimnastirio.gr ,\n",
      "335  :  pirsosfiliatra.gr , filiatranews.blogspot.gr , moriasnews.gr ,\n",
      "336  :  asterastripolis.gr , drt915.gr , 5ae.gr ,\n",
      "337  :  optofashion.gr , makelife.gr , swanocean.gr ,\n",
      "338  :  eltrun.gr , iheartdigital.gr ,\n",
      "339  :  flipside.gr , pythagoras.gr , portareto.gr ,\n",
      "340  :  pentelikonews.gr , enter2life.gr , techteam.gr ,\n",
      "341  :  gossip-news.gr , entertv.gr , all4mama.gr ,\n",
      "342  :  movienight.gr , games4free.gr ,\n",
      "343  :  teicrete.gr , teiath.gr , mignatiou.com , philenews.com , epikaira.gr , korinthiaki.gr , express.gr , teamgr.gr , tpd.gr ,\n",
      "344  :  photo.gr , poukamisas.gr , zagori.gov.gr , katogi-strofilia.gr , kyklostravel.gr , weddingphoto.gr , vovousafestival.gr ,\n",
      "345  :  lazareto.gr , traveltripolis.gr , ehmi.gr , mytheatro.gr ,\n",
      "346  :  iatrikos-velonismos-segredou.gr , kifisianews.gr ,\n",
      "347  :  womensoccer.gr , inpaok.com , diaitisia.gr ,\n",
      "348  :  bloko.gr , nooz.gr , doubleteam.gr , cobrasports.gr , ixthis-12.blogspot.gr ,\n",
      "349  :  xmall.gr , paixnidia-stratigikis.gr , beerblog.gr , todaynews.gr ,\n",
      "350  :  nautilia.gr , protevousa.gr ,\n",
      "351  :  nkclinic.gr , nutrilabs.gr ,\n",
      "352  :  vimatisko.gr , e-click.gr ,\n",
      "353  :  amotoe.gr , e-amotoe.gr ,\n",
      "354  :  diagnovet.gr , zoetis.gr ,\n",
      "355  :  ips.gr , toolservice.gr ,\n",
      "356  :  almyros.gr , xiromeritis-epiplo.gr ,\n",
      "357  :  redhoops.gr , redbasketzone.blogspot.gr ,\n",
      "358  :  ghosthouse.gr , athensweekly.gr ,\n",
      "359  :  safecase.gr , grafix.gr ,\n",
      "360  :  whitedesign.gr , mosaiko.gr ,\n",
      "361  :  hot-and-new.gr , ediva.gr , pestaola.gr ,\n",
      "362  :  pellanet.gr , ktel-imathias.gr ,\n",
      "363  :  mariayannakaki.gr , newspolis.gr , palema.gr ,\n",
      "364  :  studios-arsenis.gr , go-thassos.gr ,\n",
      "365  :  mylefkada.gr , symol.gr ,\n",
      "366  :  ant1south.gr , epslak.gr ,\n",
      "367  :  in-arachova.gr , in-karpenisi.gr ,\n",
      "368  :  physicsbook.gr , safedriving.gr , school.gr ,\n",
      "369  :  karditsalive.net , domainemessenicolas.gr ,\n",
      "370  :  pseh.gr , aepseh.gr ,\n",
      "371  :  diet4me.gr , girly-blog.gr , psychology-blog.gr ,\n",
      "372  :  funkycook.gr , thefoodiecorner.gr ,\n",
      "373  :  tipoukeitos.gr , eandith.gr ,\n",
      "374  :  e-fimerida.gr , dikaiologitika.gr , neanika.gr , marinedeals.gr ,\n",
      "375  :  greektips.gr , zo2.gr , jit.gr , market-in.gr ,\n",
      "376  :  thf.gr , paspif.gr ,\n",
      "377  :  poulantzas.gr , greeninstitute.gr , rosalux.gr ,\n",
      "378  :  3dvision.gr , kavalawebnews.gr ,\n",
      "379  :  to-gamato.gr , mama365.gr , in2life.gr ,\n",
      "380  :  fatepaketo.gr , empisteutiko.gr , proklitiko.gr , gigagora.gr , barista-shop.gr , paspartounews.blogspot.gr ,\n",
      "381  :  eviazoom.gr , fnl-guide.com , iekpraxis.gr ,\n",
      "382  :  farosradio.gr , pyramisnews.gr ,\n",
      "383  :  skoap.gr , shooters.gr ,\n",
      "384  :  dearlife.gr , pinky.gr , spartoo.gr , fashionway.gr ,\n",
      "385  :  olashoes.gr , tsimpato.gr ,\n",
      "386  :  newlifestyle.gr , fortunegreece.com , instyle.gr ,\n",
      "387  :  pamepreveza.gr , provocateur.gr , newpost.gr , mko-dro.gr , analitis.gr ,\n",
      "388  :  panathinaikos24.gr ,\n",
      "389  :  playradio.gr , radioact.gr , aerasnews.gr , patratora.gr ,\n",
      "390  :  neolaia.gr , alkal.gr , studenthouse.gr ,\n",
      "391  :  ski.gr , 3-5pigadia.gr ,\n",
      "392  :  stegastra.gr , greatdeals.gr ,\n",
      "393  :  protagon.gr , realpolitics.gr , freepen.gr ,\n",
      "394  :  apn.gr , highoctane.gr , giparakis.gr , dailyfix.gr ,\n",
      "395  :  karditsaportal.gr , bookmaniashop.gr ,\n",
      "396  :  zero-project.gr , artcom.gr ,\n",
      "397  :  my-mosxato.blogspot.gr , makthes.gr , espressonews.gr ,\n",
      "398  :  eco-flame.gr , pellet-stove.gr ,\n",
      "399  :  immspartis.gr , catichisis.gr , imchiou.gr , augoustinos-kantiotis.gr , in-agiounikolaoutouneou.gr ,\n",
      "400  :  direction.gr , advertising.gr , businessnews.gr ,\n",
      "401  :  rossdaly.gr , creta-oil.gr , laditsouderos.gr , centralparking.gr , skaikritis.gr , metrovista.gr ,\n",
      "402  :  iporta.gr , rodosblog-xrisostomos.blogspot.gr , verena.gr ,\n",
      "403  :  ggda.gr , designmag.gr ,\n",
      "404  :  exostispress.gr , greencookie.gr , mic.gr ,\n",
      "405  :  corfuland.gr , ekepee.gr ,\n",
      "406  :  filippos-veria.gr , libver.gr ,\n",
      "407  :  alfapiprint.gr , pella-lemoni.gr , infoscope.gr , enallaktikos.gr ,\n",
      "408  :  karate.gr , epszakynthou.gr ,\n",
      "409  :  esyf.gr , axivenpestcontrol.gr ,\n",
      "410  :  meteo2day.gr , dailyweb.gr ,\n",
      "411  :  magnesiasports.gr , magnesianews.gr , eme-mag.gr ,\n",
      "412  :  festivalandros.gr , androsportal.gr , hitandrun.gr ,\n",
      "413  :  foreignaffairs.gr , marketnews.gr ,\n",
      "414  :  sptmte-dei.gr , seenp.gr , genop.gr ,\n",
      "415  :  greece-wedding-photography.gr , gianneris.gr ,\n",
      "416  :  fx3.gr , digi1.gr ,\n",
      "417  :  kalavrita.gr , greenhotels.gr , kastriacave.gr , dmko.gr ,\n",
      "418  :  newcult.gr , ntynomai.gr ,\n",
      "419  :  all-restaurants.gr , krystallisrestaurant.gr ,\n",
      "420  :  flynews.gr , vekrakos.gr ,\n",
      "421  :  volleyball.gr , greenmood.gr , liberovolley11.blogspot.gr , panathinaikoswomensvolleyball.blogspot.gr ,\n",
      "422  :  weddingblog.gr ,\n",
      "423  :  kscatering.gr , nyfikaks.gr ,\n",
      "424  :  sab.gr , easp.gr ,\n",
      "425  :  antlies.gr , kelekis.gr ,\n",
      "426  :  axdw.gr , seve.gr ,\n",
      "427  :  edulll.gr , yperia.gr ,\n",
      "428  :  aigialeia.gov.gr , filodimos.gr ,\n",
      "429  :  kteokorinthias.gr , kteohellas.gr ,\n",
      "430  :  axelnet.gr , deltaconsulting.gr ,\n",
      "431  :  otticacenter.gr , odigos.gr ,\n",
      "432  :  toxrisimo.gr , ftiaxno.gr ,\n",
      "433  :  speedslalom.gr , karavi.gr ,\n",
      "434  :  lvlup.gr , ledmall.gr ,\n",
      "435  :  macland.gr , techingreek.com , greekiphone.gr , trifiliworld.gr ,\n",
      "436  :  rednews24.gr , redvoice.gr ,\n",
      "437  :  serres.gr , serrescircuit.gr ,\n",
      "438  :  erato.gr , tind.gr , ch3.gr ,\n",
      "439  :  geneticsunit.gr , aranitis.gr ,\n",
      "440  :  aigaiolive.gr , syros-ermoupolis.gr ,\n",
      "441  :  e-fixit.gr , hometools.gr ,\n",
      "442  :  arionradio.com , nextweb.gr , e-agenda.gr ,\n",
      "443  :  antarsya.gr , narnet.gr , anypotaxtos-mathitis.gr , nka.gr ,\n",
      "444  :  dkracing.gr , mxin.gr , motoway.gr ,\n",
      "445  :  thefoodproject.gr , hrcc.gr , opentourism.gr ,\n",
      "446  :  tropikos.gr , petsite.gr ,\n",
      "447  :  larissathal.gr , chaniathal.gr ,\n",
      "448  :  hotels-zakynthos.gr , kefalonia-hotels.gr , hotels-kalavrita.gr ,\n",
      "449  :  ktelmacedonia.gr , protiserron.gr ,\n",
      "450  :  asrigasferaios.blogspot.gr , accountclub.gr ,\n",
      "451  :  melissokomos.gr , bionews.gr ,\n",
      "452  :  rollout.gr , tandemngo.gr , noesi.gr ,\n",
      "453  :  ledopolis.gr , digicraft.gr ,\n",
      "454  :  zoiforos.gr , petheol.gr ,\n",
      "455  :  odigosevia.gr , oddy.gr ,\n",
      "456  :  antidiaploki.gr , europeone.gr ,\n",
      "457  :  waterpolonews.gr , nov.gr ,\n",
      "458  :  kprint.gr , rethemnosnews.gr ,\n",
      "459  :  orthotrauma.gr , edoeap.gr ,\n",
      "460  :  tire-shop.gr , beautylook.gr , dataspot.gr ,\n",
      "461  :  costaslapavitsas.blogspot.gr , livanis.gr ,\n",
      "462  :  8web.gr , kympritis.gr ,\n"
     ]
    }
   ],
   "source": [
    "for i, com in enumerate(partition_names):\n",
    "    if com:\n",
    "        print i, \" : \",\n",
    "        for n in com:\n",
    "            print n,\",\",\n",
    "        print"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "17"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "def partition_common(src, dst):\n",
    "    counter = 0\n",
    "    for neigh in G.neighbors(src):\n",
    "        if neigh in partitions[dst]:\n",
    "            counter+=1\n",
    "    for neigh in G.neighbors(dst):\n",
    "        if neigh in partitions[src]:\n",
    "            counter+=1\n",
    "    return counter\n",
    "\n",
    "def partition_check(src, dst):\n",
    "    if src in partitions[dst]:\n",
    "        return 1\n",
    "    else:\n",
    "        return 0\n",
    "    \n",
    "partition_common('news247.gr', 'ladylike.gr')\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def second_neighbors(src, dst):\n",
    "    \"\"\"\n",
    "    returns the number of common second level neighbors between two nodes\"\"\"\n",
    "    level1_src = G.neighbors(src)\n",
    "    level1_dst = G.neighbors(dst)\n",
    "    score = 0\n",
    "    level2_src = []\n",
    "    level2_dst = []\n",
    "    for w in level1_src:\n",
    "        level2_src.extend(G.neighbors(w))\n",
    "    for w in level1_dst:\n",
    "        level2_dst.extend(G.neighbors(w))\n",
    "    common = list(set(level2_src).intersection(level2_dst))\n",
    "    return len(common)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "15"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "second_neighbors('news247.gr', 'contra.gr')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "pagerank DescribeResult(nobs=2041, minmax=(0.00029761511829001677, 0.019530823306958298), mean=0.00048995590396864249, variance=5.1484022288357726e-07, skewness=16.593681826353492, kurtosis=379.97825697924446)\n",
      "closeness DescribeResult(nobs=2041, minmax=(0.0, 0.043706197338373103), mean=0.0011057427491154147, variance=1.0548295767353478e-05, skewness=6.840389761601526, kurtosis=62.844402531343476)\n",
      "betweeness DescribeResult(nobs=2041, minmax=(0.0, 0.0013256810816528672), mean=5.1837164079498881e-06, variance=3.5261533531813181e-09, skewness=16.489608369782463, kurtosis=294.5096041003185)\n",
      "eigenvector DescribeResult(nobs=2041, minmax=(0.0, 0.37735422231142191), mean=0.0017948109226848491, variance=0.00048697315309188523, skewness=13.386178390197925, kurtosis=183.2693369063938)\n",
      "text similarity DescribeResult(nobs=2041, minmax=(array([ 0.,  0.,  0., ...,  0.,  0.,  0.]), array([ 1.,  1.,  1., ...,  1.,  1.,  1.])), mean=array([ 0.14081705,  0.11499577,  0.19841769, ...,  0.18956786,\n",
      "        0.16056721,  0.03456392]), variance=array([ 0.00814462,  0.0042941 ,  0.01530137, ...,  0.01352619,\n",
      "        0.01198027,  0.00277865]), skewness=array([ 1.13119908,  1.64330689,  0.9237617 , ...,  0.47913089,\n",
      "        0.79946699,  6.66819173]), kurtosis=array([  4.41391101,  15.89084406,   1.30397545, ...,   0.49640679,\n",
      "         1.50261023,  81.78381561]))\n"
     ]
    }
   ],
   "source": [
    "from scipy import stats\n",
    "print \"pagerank\", stats.describe(pagerank.values())\n",
    "print \"closeness\", stats.describe(closeness.values())\n",
    "print \"betweeness\", stats.describe(betweeness.values())\n",
    "print \"eigenvector\", stats.describe(eigenvector.values())\n",
    "print \"text similarity\", stats.describe(cosine)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "('news247.gr', 'contra.gr', 3.9275702562794277)"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nx.adamic_adar_index(un_g, [('news247.gr', 'contra.gr')]).next()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def feature_extraction(edge):\n",
    "    \"\"\"The function returns the feature vector of the edge\n",
    "    \"\"\"\n",
    "    src, dst = edge\n",
    "    f_vector = []\n",
    "    f_vector.append(text_similarity(src, dst)) \n",
    "    f_vector.append(len(set(G.neighbors(src)).intersection(G.neighbors(dst))))\n",
    "    f_vector.append(second_neighbors(src, dst))    \n",
    "    f_vector.append(G.out_degree(src))\n",
    "    f_vector.append(G.in_degree(dst))\n",
    "    f_vector.append(pagerank[src])    \n",
    "    f_vector.append(pagerank[dst])\n",
    "    f_vector.append(eigenvector[src])\n",
    "    f_vector.append(eigenvector[dst])\n",
    "    f_vector.append(betweeness[src])\n",
    "    f_vector.append(betweeness[dst])\n",
    "    f_vector.append(closeness[src])\n",
    "    f_vector.append(closeness[dst])\n",
    "    f_vector.append(katz[src])\n",
    "    f_vector.append(katz[dst])\n",
    "    f_vector.append(core_number[src])\n",
    "    f_vector.append(core_number[dst])\n",
    "    f_vector.append(triangles[src])\n",
    "    f_vector.append(triangles[dst])\n",
    "    f_vector.append(simrank[domain_number[src], domain_number[dst]])\n",
    "    f_vector.append(nx.adamic_adar_index(un_g, [(src, dst)]).next()[2])\n",
    "    f_vector.append(nx.jaccard_coefficient(un_g, [(src, dst)]).next()[2])\n",
    "    f_vector.append(nx.preferential_attachment(un_g, [(src, dst)]).next()[2])\n",
    "    f_vector.append(nx.resource_allocation_index(un_g, [(src, dst)]).next()[2])\n",
    "    f_vector.append(partition_check(src, dst))\n",
    "    f_vector.append(partition_common(src, dst))\n",
    "    if G.has_edge(dst,src):\n",
    "        f_vector.append(1)\n",
    "    else:\n",
    "        f_vector.append(0) \n",
    "    return f_vector\n",
    "\n",
    "feature_names = [\"text\",\"#common_neighbors\",\"#_of_second_neighbors\", \"G.out_degree(src)\",\"G.in_degree(dst)\",\n",
    "                 \"pagerank[src]\",\"pagerank[dst]\",\"eigenvector[src]\",\"eigenvector[dst]\",\"betweeness[src]\",\n",
    "                 \"betweeness[src]\",\"betweeness]dst\",\"closeness[src]\",\"closeness[dst]\",\"katz[src]\",\"katz[dst]\",\n",
    "                 \"core_number[src]\",\"core_number[dst]\",\"triangles[src]\",\"triangles[dst]\",\"simrank\", \"adamic_adar\",\n",
    "                 \"jaccard_coefficient\",\"preferential_attachment\",\"resource_allocation_index\",\n",
    "                 \"partition_check\", \"opposite_edge\"]\n",
    "\n",
    "# def feature_extraction(edge):\n",
    "#     src, dst = edge\n",
    "#     f_vector = []\n",
    "#     f_vector.append(text_similarity(src, dst))\n",
    "#     f_vector.append(G.out_degree(src))\n",
    "#     f_vector.append(G.in_degree(dst))\n",
    "#     f_vector.append(pagerank[src])\n",
    "#     f_vector.append(eigenvector[src])\n",
    "#     f_vector.append(eigenvector[dst])\n",
    "#     f_vector.append(pagerank[dst])\n",
    "#     f_vector.append(betweeness[src])\n",
    "#     f_vector.append(betweeness[dst])\n",
    "#     f_vector.append(closeness[dst])\n",
    "#     f_vector.append(closeness[src])\n",
    "#     f_vector.append(adamic_adar(src, dst))\n",
    "#     f_vector.append(second_neighbors(src, dst))\n",
    "#     f_vector.append(partition_check(src, dst))\n",
    "#     if G.has_edge(dst,src):\n",
    "#         f_vector.append(1)\n",
    "#     else:\n",
    "#         f_vector.append(0)    \n",
    "#     return f_vector\n",
    "    \n",
    "    \n",
    "# def feature_extraction(edge):\n",
    "#     np.random.seed(seed)\n",
    "#     src, dst = edge\n",
    "#     feature_names = [\"text\", \"second_neighbors\",\"G.out_degree(src)\",\"G.in_degree(dst)\",\"pagerank[src]\"\n",
    "#                      , \"eigenvector[dst]\",\"betweeness[src]\",\"closeness[dst]\",\"preferential_attachment\",\n",
    "#              \"resource_allocation_inde\",\"partition_check\"]\n",
    "#     f_vector = []\n",
    "#     f_vector.append(text_similarity(src, dst))\n",
    "#     #f_vector.append(len(set(G.neighbors(src)).intersection(G.neighbors(dst))))\n",
    "#     f_vector.append(second_neighbors(src, dst))    \n",
    "#     f_vector.append(G.out_degree(src))\n",
    "#     f_vector.append(G.in_degree(dst))\n",
    "#     f_vector.append(pagerank[src])    \n",
    "#     #f_vector.append(pagerank[dst])\n",
    "#     #f_vector.append(eigenvector[src])\n",
    "#     f_vector.append(eigenvector[dst])\n",
    "#     f_vector.append(betweeness[src])\n",
    "#     #f_vector.append(betweeness[dst])\n",
    "#     f_vector.append(closeness[dst])\n",
    "#     #f_vector.append(closeness[src])\n",
    "#     #f_vector.append(adamic_adar2(src, dst))\n",
    "#     #f_vector.append(nx.adamic_adar_index(un_g, [(src, dst)]).next()[2])\n",
    "#     #f_vector.append(nx.jaccard_coefficient(un_g, [(src, dst)]).next()[2])\n",
    "#     f_vector.append(nx.preferential_attachment(un_g, [(src, dst)]).next()[2])\n",
    "#     f_vector.append(nx.resource_allocation_index(un_g, [(src, dst)]).next()[2])\n",
    "#     f_vector.append(partition_check(src, dst))\n",
    "#     #return np.random.choice(f_vector,num),seed, names\n",
    "#     return f_vector\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "seed = np.random.randint(1,4000000) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "ename": "NameError",
     "evalue": "name 'feature_extraction' is not defined",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mNameError\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[1;32m<ipython-input-2-5836b7c0190a>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m()\u001b[0m\n\u001b[0;32m      1\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      2\u001b[0m \u001b[1;31m#vector,seed,names = feature_extraction(('news247.gr','contra.gr'),5 ,seed)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m----> 3\u001b[1;33m \u001b[0mvector\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mfeature_extraction\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;34m'news247.gr'\u001b[0m\u001b[1;33m,\u001b[0m\u001b[1;34m'contra.gr'\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m      4\u001b[0m \u001b[1;32mif\u001b[0m \u001b[0mlen\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mfeature_names\u001b[0m\u001b[1;33m)\u001b[0m \u001b[1;33m!=\u001b[0m \u001b[0mlen\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mvector\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      5\u001b[0m  \u001b[1;32mraise\u001b[0m \u001b[0mException\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;31mNameError\u001b[0m: name 'feature_extraction' is not defined"
     ]
    }
   ],
   "source": [
    "   \n",
    "#vector,seed,names = feature_extraction(('news247.gr','contra.gr'),5 ,seed)\n",
    "vector = feature_extraction(('news247.gr','contra.gr'))\n",
    "if len(feature_names) != len(vector):\n",
    "    raise Exception\n",
    "print vector"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "X_train = []\n",
    "y_train = []\n",
    "for edge in G.edges():\n",
    "    X_train.append(feature_extraction(edge))\n",
    "    y_train.append(1)\n",
    "for edge in non_existent_edges:\n",
    "    X_train.append(feature_extraction(edge))\n",
    "    y_train.append(0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# from sklearn.model_selection import train_test_split\n",
    "# X_train, X_predict, y_train, y_test = train_test_split( X_train, y_train, test_size=0.10, random_state=42)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "X_predict = []\n",
    "for edge in non_edges:\n",
    "    X_predict.append(feature_extraction(edge))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "X_train_n = np.array(X_train)\n",
    "y_train_n = np.array(y_train)\n",
    "X_predict_n = np.array(X_predict)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# scale features\n",
    "from sklearn import preprocessing\n",
    "# from sklearn import preprocessing\n",
    "X_train_scaled = preprocessing.scale(X_train_n)\n",
    "X_predict_scaled = preprocessing.scale(X_predict_n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# PCA didnt work\n",
    "# from sklearn.decomposition import PCA\n",
    "# pca = PCA(n_components=10)\n",
    "# X_train_n = pca.fit_transform(X_train)\n",
    "# X_predict_n = pca.fit_transform(X_predict)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "np.save(\"cache/X_train_new.npy\", X_train_n)\n",
    "np.save(\"cache/y_train_new.npy\", y_train_n)\n",
    "np.save(\"cache/X_test_new.npy\", X_predict_n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(23443, 27)\n",
      "(23443,)\n",
      "(4140197, 27)\n"
     ]
    }
   ],
   "source": [
    "print X_train_n.shape\n",
    "print y_train_n.shape\n",
    "print X_predict_n.shape"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Feature Selection\n",
    "\n",
    "There are four approaches that can be followed for feature selection:  \n",
    "\n",
    "1. Do manual feature selection using the code below. We print some statistics about each feature to see if some of them have low variance. Afterwards we also calculate the pearson correlation between each pair of features and choose to remove one of the features in each pair that shows a high correlation. High correlation between two features can make our model really unstable.  \n",
    "2. Use the feature_selection package available in scikit learn to do feature selection.  \n",
    "3. Use a model that provides feature importance (eg Random Forests).  \n",
    "4. Do no feature selection and use all features in a neural network of a tree based model  \n",
    "\n",
    "We experiment with all the choices we have, but doing feature selection is important and produces a more robust model than using all avalable features."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from scipy import stats\n",
    "from tabulate import tabulate\n",
    "\n",
    "\n",
    "#print tabulate(range(0,18), feature_names, tablefmt=\"grid\")\n",
    "feats = {}\n",
    "for i, name in enumerate(feature_names):\n",
    "    feats[name]={}\n",
    "    feats[name][\"mean\"]=stats.describe(X_train_n[:,i]).mean\n",
    "    feats[name][\"min_max\"]=stats.describe(X_train_n[:,i]).minmax\n",
    "    feats[name][\"variance\"]=stats.describe(X_train_n[:,i]).variance\n",
    "\n",
    "for name, _dict in feats.iteritems():\n",
    "    print name, tabulate(_dict.items())\n",
    "\n",
    "from itertools import combinations\n",
    "f_combs = list(combinations(range(len(feature_names)), 2))\n",
    "\n",
    "from scipy.stats import pearsonr\n",
    "pearson_corr = np.zeros((len(f_combs),len(f_combs)))\n",
    "for f1, f2 in f_combs:\n",
    "    pearson_corr[f1, f2] = pearsonr(X_train_n[:2683,f1], X_train_n[:2683,f2])[0]\n",
    "    pearson_corr[f2, f1] = pearson_corr[f1, f2] \n",
    "\n",
    "\n",
    "    \n",
    "\n",
    "#for f1, f2 in f_combs:\n",
    "    #print feature_names[f1], feature_names[f2], pearson_corr[f1, f2]\n",
    "for i, name in enumerate(feature_names):\n",
    "    print name, feature_names[np.argmax(pearson_corr[i, :])] ,pearson_corr[i,np.argmax(pearson_corr[i, :])]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# we save the numpy arrays to be able to run classification algorithms \n",
    "# again without running all the above processes\n",
    "np.save(\"cache/X_train.npy\", X_train_n)\n",
    "np.save(\"cache/y_train.npy\", y_train_n)\n",
    "np.save(\"cache/X_test.npy\", X_predict_n)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Classification\n",
    "\n",
    "For classication we test several cases. At first we use logistic regression, SVM and a neural network classifier.  \n",
    "As we have rather small data opposed to the candidate space (2683 true edges opposed to ~4m edges) we have to be very careful with regularization because most models tend to overfit the training data.  \n",
    "Afterward we experiment with Random Forests as well as ensemble methods such as Gradient boosting, XGBoost which are methods that have gained much attendance lately, especially due to their high performance in Kaggle contests.  \n",
    "However such models require very good tuning because of the high parameter space they have, so we perform Grid Search to find the optimal parameters for the Random Forest model as well as XGBoost with all the candidate features. Unfortunately because of the computational complexity of such a task we did not perform Grid Search to models with different features.\n",
    "In the end we also run a voting classifier with the best tuning for XGBoost and Random Forest.  \n",
    "We want to use classification algorithms that implement the predict_proba method, because we are interested in the probability that an edge will exist in our graph. Because of the small dataset and the overfitting that happens we must balance the classifiers uncertainty. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The highest (reproducible) score (10,15%) was obtained using XGBoost and the following feature vector function:\n",
    "\n",
    "def feature_extraction(edge):  \n",
    "        src, dst = edge  \n",
    "        f_vector = []  \n",
    "        f_vector.append(text_similarity(src, dst))  \n",
    "    f_vector.append(pagerank[src])  \n",
    "    f_vector.append(eigenvector[src])  \n",
    "    f_vector.append(eigenvector[dst])  \n",
    "    f_vector.append(pagerank[dst])  \n",
    "    f_vector.append(betweeness[src])  \n",
    "    f_vector.append(betweeness[dst])  \n",
    "    f_vector.append(closeness[dst])  \n",
    "    f_vector.append(closeness[src])  \n",
    "    f_vector.append(adamic_adar(src, dst))  \n",
    "    f_vector.append(partition_check(src, dst))  \n",
    "    return f_vector  \n",
    "    \n",
    "We also scored a 10.31% but it was with a Random Forest without saving the random seed."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# if we have not ran everything above we can just run this to load the Train/Test data.\n",
    "X_train_n = np.load('cache/X_train.npy')\n",
    "y_train_n = np.load('cache/y_train.npy')\n",
    "X_predict_n = np.load('cache/X_test.npy')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from sklearn.linear_model import LogisticRegression\n",
    "reg = LogisticRegression(C= 0.00001)\n",
    "reg.fit(X_train_scaled, y_train_n)\n",
    "pred_reg = reg.predict_proba(X_predict_scaled)\n",
    "probs_reg = []\n",
    "for t in pred_reg:\n",
    "    probs_reg.append(t[1])\n",
    "indices = sorted(range(len(probs_reg)), key=lambda k: probs_reg[k])[::-1][:453]\n",
    "print [probs_reg[indices[i]] for i in range(len(indices))]\n",
    "predicted_edges_reg = []\n",
    "for i in range(len(indices)):\n",
    "    predicted_edges_reg.append(non_edges[indices[i]])\n",
    "\n",
    "with open('predicted_edges_logReg.txt', 'w') as fp:\n",
    "    for site_1, site_2 in predicted_edges_reg:\n",
    "        fp.write(site_1+'\\t'+site_2+'\\n')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0.97901864078349621, 0.97900787000814349, 0.97882682877148808, 0.97840794708899659, 0.97823033746886889, 0.97810362026197262, 0.97808123062086427, 0.97786971299010994, 0.97773346557348706, 0.97762762585553464, 0.97750833549185578, 0.97740563756198873, 0.97724291215797465, 0.9767270076136827, 0.97662736365929903, 0.97657315537475375, 0.97656403267067127, 0.97638297734625878, 0.976237173163782, 0.97620190113319327, 0.97612054867394571, 0.97609972633630671, 0.97606677149329202, 0.97604964689049878, 0.97594805038454757, 0.97591506552841489, 0.97588742658462413, 0.97569148829363928, 0.97567270131228134, 0.97565904456945485, 0.9755847453796529, 0.9755712860807827, 0.97550156016625644, 0.97549143585434728, 0.97547221850980037, 0.97540926469948397, 0.9753597840774102, 0.97534116264717818, 0.97526771951401292, 0.97506885972940593, 0.97499665661450308, 0.97497378454650097, 0.97494297191504908, 0.97494109821434149, 0.97492532285980538, 0.97491389806070838, 0.97488353491760027, 0.97487496821057218, 0.97484805521529905, 0.97481851599183988, 0.97476259667067811, 0.97472774243306937, 0.97472569917482466, 0.97469758827335684, 0.97465958159022414, 0.97465170261660394, 0.97460838752622425, 0.97456707374174856, 0.97448097893716124, 0.97446627966631416, 0.97442995012028877, 0.9743956905576433, 0.9743666508133676, 0.9743552269361303, 0.97428021846918589, 0.97422827522759847, 0.97422292610695238, 0.97421069449716247, 0.97419878274225802, 0.97419794677619287, 0.97416701322566679, 0.97413515983298049, 0.97411372087767301, 0.97410402634513904, 0.97409565288873567, 0.97406144514493043, 0.97406029416963935, 0.97398259995991188, 0.97395405532478407, 0.97392759370852733, 0.97391904461511669, 0.97389726847306279, 0.97389452867085902, 0.97389394076605906, 0.97387622435481347, 0.97387074584304523, 0.97386405416855637, 0.97369507500711927, 0.97364739254690758, 0.97356634649553653, 0.9735288238126415, 0.97349346778414381, 0.97344356486987382, 0.9734277624779698, 0.97337792763203113, 0.97337611287906789, 0.9733733560827329, 0.97334532129486317, 0.97331866599454964, 0.97329356806784084, 0.97328642168872948, 0.9732558228645849, 0.97319863171896248, 0.97317961492317395, 0.97316995883563095, 0.97315559659508166, 0.97310650795800657, 0.97308975806945652, 0.97308954655700186, 0.97304116079855696, 0.97303653110259836, 0.97300029121688159, 0.97298465693090375, 0.97296089760124838, 0.97296024297412542, 0.97295020857810155, 0.9729297186283582, 0.97289621043459551, 0.97287824916878107, 0.97287612187035721, 0.97287236476848238, 0.9728699171242069, 0.97283513390594978, 0.9728333848783618, 0.97283296492111915, 0.97282588581296936, 0.97282131513044201, 0.97281618475937792, 0.97279130463861696, 0.97279079969028059, 0.97278489027996495, 0.9727605889048162, 0.97275742701931789, 0.97274268541463182, 0.97271588746014437, 0.97271527303072669, 0.97270652054345086, 0.97269874066020967, 0.97266501382122461, 0.9726554104069487, 0.97260895885368293, 0.97260218310626878, 0.97257853706958608, 0.97257415428436467, 0.97256924855673521, 0.97255967971117541, 0.97254947513326473, 0.97254852982421303, 0.97252153992838519, 0.97250477366289811, 0.97250116311042345, 0.97248895052724971, 0.97246549121460146, 0.97246336978802872, 0.97243905085925475, 0.97241996865024527, 0.97241298984524094, 0.97241036500981604, 0.97239417636667269, 0.97236769083843566, 0.9723319224657706, 0.97232537095040072, 0.97231520402797977, 0.97230596083901011, 0.97228969089606265, 0.97226620247930762, 0.97224111863852447, 0.97223029386502935, 0.97220974648669389, 0.97219636359368944, 0.97219266998892417, 0.97214705457066541, 0.97207548022962431, 0.97207293261512473, 0.9720411808793834, 0.97199887922328532, 0.97197092495678894, 0.97196182009027876, 0.97195559015872479, 0.97194834754442949, 0.97193465556157144, 0.97193339343419516, 0.97191977719273359, 0.97190079384809902, 0.97184141906855881, 0.97179330103624006, 0.97178441126551374, 0.97175292366546406, 0.97171850078639432, 0.9716439767658468, 0.97164340061555288, 0.97163789926617949, 0.97163555504602694, 0.97163038266290114, 0.97154922058879423, 0.97154424999627376, 0.97154128977571219, 0.97152460374696659, 0.9714201911842224, 0.97139882345974438, 0.97139453457287128, 0.97138999828457273, 0.97132235654953991, 0.97131707329389494, 0.97126909409753559, 0.97126225535393396, 0.97125315147712132, 0.97122483903167833, 0.97122343433680491, 0.97118161162558203, 0.9711572087266046, 0.97114629544751396, 0.97113207605487895, 0.97111957768522705, 0.97110831175699541, 0.97110729653913053, 0.97109835669295541, 0.97109083788668049, 0.97105596761614166, 0.97105516488235377, 0.97104531960162355, 0.97100651166181284, 0.9710018529761576, 0.97097350604633659, 0.97096267747118981, 0.97091461049341399, 0.97086320124066527, 0.97082147042463607, 0.97080043016942752, 0.97079634126140935, 0.97079047728500245, 0.97077819430628665, 0.97077567633218853, 0.97075800081916497, 0.97075247653400565, 0.97074531521002616, 0.97073817579320432, 0.97067619729147403, 0.97067217611219281, 0.97067154766396291, 0.97066919407748398, 0.97059920818312295, 0.97057509680346166, 0.97056036570340154, 0.9705481256054338, 0.97053317812369633, 0.97045868380208722, 0.97044693436299134, 0.97042485437714276, 0.97041922669987291, 0.97041754689814674, 0.97040674132263249, 0.97038015871922356, 0.97036430909442528, 0.97036326874921086, 0.97029445782657808, 0.97029421881107758, 0.97027192046811228, 0.97026137346849706, 0.97021321761420476, 0.97020745513057682, 0.97019187117724248, 0.9701658557185362, 0.97013161018787386, 0.97011995272193852, 0.97007825163987305, 0.97007275292063755, 0.97006186349843138, 0.97003604034300495, 0.97002948066302219, 0.97002878602209919, 0.97001877832903605, 0.97000812656119062, 0.97000192240478889, 0.96997404952947863, 0.96996236155832827, 0.96995901046719979, 0.96995747115209752, 0.96992722342477089, 0.96990259581597438, 0.96988805095245756, 0.96986563508215884, 0.96985722328934643, 0.96985336921068988, 0.96985318719000746, 0.9698365871972624, 0.96982805570156017, 0.96981550518389237, 0.96981170075952783, 0.9697870792741522, 0.96977931404969542, 0.96976721024055346, 0.96976495179354116, 0.96976013495723989, 0.96974485146464939, 0.9697432462416935, 0.9697332541063538, 0.96973009869331661, 0.96972551476761393, 0.96972476905296934, 0.96972095637380762, 0.96969602795098309, 0.96969420305782783, 0.96968660955789387, 0.96965679633668522, 0.96965245741594897, 0.9696342625845632, 0.96962893296410302, 0.96962584035413912, 0.96961772203449526, 0.96961341030334369, 0.96961035077283853, 0.96960957191024466, 0.96960786837861535, 0.96959667169695463, 0.96958419492145531, 0.96958181690243506, 0.9695487062019893, 0.96954564908049434, 0.96953698751670414, 0.9695295103799686, 0.96952912655822332, 0.96949292753881766, 0.96947960817091539, 0.96944093816593635, 0.96943742206970851, 0.96943350585938459, 0.96943295794526962, 0.96942441891842024, 0.96941884829070368, 0.96941170855521575, 0.96940554292985781, 0.96940461755616691, 0.96939205822199004, 0.96938937131957081, 0.96938668528245675, 0.96936131224975741, 0.96935936665280875, 0.96932568852075296, 0.96931855730071503, 0.96931493218189979, 0.96929428599639167, 0.96929399026618923, 0.96928169307725209, 0.96927685360939775, 0.96927570069264224, 0.96927460016415246, 0.96927041478093767, 0.96926845705177656, 0.9692160729790682, 0.96921601963803461, 0.96920288874285321, 0.96918630754608392, 0.96918612257478631, 0.96918453339602006, 0.96916952942735601, 0.96916332533136007, 0.96914721869106479, 0.96913626286026378, 0.96912981142292853, 0.96911654362708266, 0.96910604277125678, 0.96909520295430729, 0.96907872824591534, 0.96903831986664313, 0.96902677735943921, 0.96901976204554696, 0.96899627440728331, 0.96898863779942757, 0.9689828676844997, 0.9689761883188055, 0.96896981618351019, 0.96896852092669827, 0.96895757698399332, 0.96894134034616308, 0.96894109874937051, 0.96893550138200801, 0.96892054461099031, 0.96890610805132871, 0.96888510946963002, 0.9688811204401504, 0.96884879111854616, 0.96884639488480429, 0.96884362480822939, 0.96879383889619275, 0.96877803916589789, 0.96877208920173419, 0.96875474743517398, 0.96873857421096599, 0.96867110625545816, 0.96864932938974979, 0.96864380781869042, 0.96862502502701153, 0.96862033623196353, 0.96860524416024907, 0.96860184366262503, 0.96859608852142653, 0.9685780271417227, 0.96856641310636349, 0.96855905542370324, 0.96852298197174502, 0.96851597859446392, 0.96850022535598901, 0.96848486662594702, 0.96847324632912546, 0.96846969199173916, 0.96846060264529488, 0.96845714237819192, 0.96845199847160091, 0.96843973744267187, 0.96843040939342007, 0.9684262275999288, 0.96841737214353973, 0.96840073542312921, 0.96839820678021482, 0.96839617183423155, 0.96839331083569336, 0.96835914191055772, 0.96835894403212597, 0.96831637271369575, 0.96830207351913, 0.96827324736840248, 0.96826468743142213, 0.96826302516344787, 0.96826137627419018, 0.96826016859113806, 0.96825369599839739, 0.96825311045521811, 0.96823858435159571, 0.96823151671951568, 0.96822888480943625, 0.96822568550444221, 0.96821016490273482, 0.96816761671170803, 0.96814628333570751, 0.96812835308035583, 0.96812363857191486, 0.96811976028428481, 0.9680679644216279, 0.96806052627783923, 0.96805881114225245, 0.96804524979976092, 0.9680377056818017, 0.96801327031776174, 0.96799577363692912, 0.96798278162150186, 0.96796668750935877, 0.9679427797246446, 0.96793474121358636, 0.96792881454808799, 0.96791887335881543, 0.96791601134026983, 0.96791303461327916]\n"
     ]
    }
   ],
   "source": [
    "from sklearn.svm import SVC\n",
    "svm = SVC(probability=True, C=0.00001)\n",
    "svm.fit(X_train_scaled, y_train_n)\n",
    "pred_svm = svm.predict_proba(X_predict_scaled)\n",
    "probs_svm = []\n",
    "for t in pred_svm:\n",
    "    probs_svm.append(t[1])\n",
    "indices = sorted(range(len(probs_svm)), key=lambda k: probs_svm[k])[::-1][:453]\n",
    "print [probs_svm[indices[i]] for i in range(len(indices))]\n",
    "predicted_edges_svm = []\n",
    "for i in range(len(indices)):\n",
    "    predicted_edges_svm.append(non_edges[indices[i]])\n",
    "\n",
    "with open('predicted_edges_svm.txt', 'w') as fp:\n",
    "    for site_1, site_2 in predicted_edges_svm:\n",
    "        fp.write(site_1+'\\t'+site_2+'\\n')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0.99572798653903372, 0.99572683582710653, 0.99572408430148485, 0.99571609751201484, 0.99570666296802701, 0.99570116739280645, 0.99569966061595672, 0.99569700186883647, 0.99569661753706207, 0.99568995443535835, 0.99568982096971548, 0.99568886473806872, 0.99568692254321234, 0.99568446010303457, 0.9956829321210825, 0.99568288307922515, 0.99568260987182033, 0.99567854601430028, 0.99567844418002593, 0.99567747196495182, 0.99567730348051042, 0.99567644968647839, 0.99567533676972697, 0.99567438943883479, 0.99567163199951292, 0.995671352394361, 0.99567015420532512, 0.99566837887559689, 0.99566824913641216, 0.99566728402721738, 0.99566716139559008, 0.99566675212841027, 0.99566669088915782, 0.99566591003979377, 0.99566548038504021, 0.9956638349073178, 0.9956635966913584, 0.99566358957283962, 0.99566321020750648, 0.99566314071243756, 0.99566250880255858, 0.99566207634205084, 0.99566194308706335, 0.99566150627167083, 0.99566091901115195, 0.99565916003407151, 0.99565882351286128, 0.9956580318624243, 0.99565785345411917, 0.99565672786345383, 0.995656164412418, 0.99565582698676813, 0.99565578394052101, 0.99565558964049616, 0.99565540203580327, 0.99565539340328324, 0.99565438231615311, 0.99565381007857767, 0.99565327168409057, 0.99565311003916424, 0.99565298324933338, 0.99565277407233743, 0.9956522839901446, 0.99565151816205422, 0.99565128152645666, 0.99564965003465433, 0.9956495609454189, 0.9956490695162058, 0.99564847171009341, 0.99564781967346627, 0.99564709470989698, 0.9956457271248752, 0.99564550102737803, 0.99564536110740831, 0.99564488361117875, 0.99564468917157323, 0.99564388788773805, 0.99564363177923632, 0.99564350835685633, 0.99564349770482474, 0.99564344715201891, 0.99564305704167544, 0.99564256637239734, 0.99564240706391505, 0.99564229057428133, 0.99564195421940382, 0.99564182394414158, 0.99564150778650828, 0.995641229066069, 0.99564075220376091, 0.99564049897205287, 0.99563989226687022, 0.99563941149005186, 0.9956386833652463, 0.99563832504170047, 0.99563817510035546, 0.99563615712542353, 0.9956361570264588, 0.99563550886901819, 0.99563489557348916, 0.99563485419673992, 0.99563469987872744, 0.99563465291907627, 0.99563417198554183, 0.99563412795165973, 0.99563407353764699, 0.99563402165048942, 0.9956339487071415, 0.99563394692097862, 0.99563365954109706, 0.99563311205310812, 0.99563283515729917, 0.99563243719786887, 0.99563187443627099, 0.99563159424005532, 0.99563147421524056, 0.99563105819000097, 0.99563055763408692, 0.99563049413278937, 0.99563046847616965, 0.99563025874494482, 0.99563012958574459, 0.99563009929076396, 0.99562998350796772, 0.99562985704577478, 0.99562961297888652, 0.99562951861884541, 0.99562950907438752, 0.99562921660927495, 0.99562868203780941, 0.99562846965104179, 0.99562833881232693, 0.99562818032539824, 0.9956273711746505, 0.99562726933289059, 0.99562722018937555, 0.99562684666820533, 0.99562684429475434, 0.99562684146010016, 0.99562647988320419, 0.99562627513853352, 0.99562624852567405, 0.99562600038135596, 0.99562593483332096, 0.99562583307318209, 0.99562568099247095, 0.99562551506256636, 0.99562539991416488, 0.99562535760633486, 0.99562511035142476, 0.99562498146288325, 0.99562483025351856, 0.99562454101335451, 0.99562439324467844, 0.99562431742500657, 0.99562427081339322, 0.99562409351660708, 0.99562407548075604, 0.9956238484198342, 0.99562378117929995, 0.99562345121955986, 0.99562300216250421, 0.99562299706035373, 0.99562257464529358, 0.99562241949813157, 0.99562241743940882, 0.99562223011516404, 0.99562190180732002, 0.99562181925589943, 0.99562153282084631, 0.99562126792219929, 0.99562114974149718, 0.99562111083213067, 0.99562056514632113, 0.99562015385069069, 0.99561962284719163, 0.99561912893700477, 0.9956190959181519, 0.99561906871016481, 0.99561877305005897, 0.99561872554622943, 0.99561871181552242, 0.99561849528682667, 0.99561845621486877, 0.99561840135345181, 0.99561834198091748, 0.99561793867209147, 0.99561791652840981, 0.99561788131758377, 0.99561702196415236, 0.99561679362824196, 0.99561666731600496, 0.99561601599090288, 0.99561595210368259, 0.99561589709911291, 0.9956154614833097, 0.99561544634245591, 0.9956152273050155, 0.99561517205723038, 0.99561492008661989, 0.9956148953386077, 0.99561486502577157, 0.9956141924004891, 0.99561414884239141, 0.99561366399701767, 0.99561364876938152, 0.99561343348553621, 0.99561339702962937, 0.99561333488629422, 0.99561297382029901, 0.99561287887583116, 0.99561272471437323, 0.99561250512187549, 0.99561247557115828, 0.99561233467834664, 0.99561224198928089, 0.99561169554628959, 0.99561155974213589, 0.99561149037628616, 0.99561138984952213, 0.99561107411662053, 0.99561101444885902, 0.99561079647490625, 0.99561060193687145, 0.99561043052256071, 0.99561038752669062, 0.99561021606119682, 0.99560974241566658, 0.99560965141512703, 0.99560961469060238, 0.99560956900165132, 0.99560954031637794, 0.9956094966893192, 0.99560899874278164, 0.9956089842413165, 0.99560835834198014, 0.99560817786854983, 0.99560817030823412, 0.99560815462290386, 0.99560808260891076, 0.99560794834809185, 0.99560742416583725, 0.99560740457544439, 0.99560737894853801, 0.99560716133294647, 0.99560702475442808, 0.99560683200826727, 0.99560663573539943, 0.99560624871913117, 0.99560611591727155, 0.99560580892623474, 0.99560566874894585, 0.99560548487076916, 0.99560539512970481, 0.99560537990372289, 0.99560528572063545, 0.99560505379779352, 0.99560502591521349, 0.9956048360706361, 0.99560474076856875, 0.99560467927023677, 0.99560467474018666, 0.99560442906111757, 0.99560432249708319, 0.99560417244799315, 0.99560399217656126, 0.9956039001954704, 0.99560367948434381, 0.99560366169943759, 0.99560362357098409, 0.99560352378440309, 0.99560340803023051, 0.9956033805855522, 0.99560326597181537, 0.99560307664986492, 0.99560291785268196, 0.99560266706345901, 0.99560261968377961, 0.99560252054344789, 0.99560242420888556, 0.99560241160982155, 0.99560235564369148, 0.99560225723025986, 0.99560225297009697, 0.99560209369034391, 0.99560207635317155, 0.99560183862261886, 0.99560127492319839, 0.99560112176693571, 0.99560109824261511, 0.99560107297351186, 0.99560094766721652, 0.99560079590003436, 0.99560071833746999, 0.99560048337893292, 0.99560047312797595, 0.99560042020075123, 0.99560012068884751, 0.99559967382297265, 0.99559952015908759, 0.99559948636715201, 0.99559922290366876, 0.99559915912940145, 0.99559913001371569, 0.99559903065883959, 0.99559895875774529, 0.99559846154954812, 0.99559833753832661, 0.99559810452011721, 0.99559808434142327, 0.99559800852081815, 0.99559794900364096, 0.99559793347419279, 0.99559788100446001, 0.99559782145702314, 0.9955977292771202, 0.99559762614456426, 0.99559760574593958, 0.99559753863708045, 0.99559747161408751, 0.99559711264253581, 0.9955970481074462, 0.9955970317938817, 0.99559703034377878, 0.99559702995060129, 0.99559698747925274, 0.99559691596846045, 0.99559680075414136, 0.99559678457675371, 0.99559672856487025, 0.99559671674314065, 0.99559654168550915, 0.99559653447310514, 0.99559640485498035, 0.99559639163476177, 0.9955963686649274, 0.99559627649774285, 0.99559627280817353, 0.99559617440485959, 0.99559614365062554, 0.99559612432941635, 0.99559599983800295, 0.99559598711162844, 0.99559579844058099, 0.99559566848996162, 0.99559553071541385, 0.99559527588573271, 0.99559519777354688, 0.99559517475352921, 0.99559499258865125, 0.9955949249849495, 0.99559489618189023, 0.99559472327082754, 0.99559471500803332, 0.99559469518959687, 0.99559454227586042, 0.99559449766038433, 0.99559414441513194, 0.9955940675940419, 0.99559382823593923, 0.99559374843386983, 0.9955935239724828, 0.99559348153109839, 0.99559337249710578, 0.99559325924281417, 0.99559325750693106, 0.99559320292930864, 0.99559308738597996, 0.9955930290585896, 0.99559299658412226, 0.99559291490751523, 0.99559288774645094, 0.99559269032070452, 0.99559262269276472, 0.99559242877319654, 0.99559238692589602, 0.99559224826676995, 0.99559213851318229, 0.99559213077840225, 0.99559204068252527, 0.99559196142879969, 0.99559195488100505, 0.99559191205303788, 0.99559189253233238, 0.99559185653656213, 0.99559182702352056, 0.99559178659941827, 0.99559176141427275, 0.99559171721186557, 0.99559150300564114, 0.9955914867083705, 0.99559130898580495, 0.99559121065285772, 0.99559118544830449, 0.9955910959914025, 0.99559099102257542, 0.99559094803244474, 0.99559089298117187, 0.99559080147456802, 0.99559058561572056, 0.99559045978656324, 0.9955904361852459, 0.99559032242773604, 0.9955902046368641, 0.99559014490425224, 0.99559008998755782, 0.9955900290627544, 0.99558944593454457, 0.99558941436777537, 0.99558940801965057, 0.99558940668388707, 0.99558925932437647, 0.99558923590752479, 0.99558919060754858, 0.99558918343369307, 0.99558917688096649, 0.99558894037595891, 0.99558879819618928, 0.99558872587409664, 0.99558871047454645, 0.99558865193135959, 0.99558859593824267, 0.99558856898505865, 0.99558844141424274, 0.99558832358908833, 0.99558831654626301, 0.9955882854601763, 0.99558798660259318, 0.99558775569015046, 0.99558773962303504, 0.99558764125840438, 0.99558751511472643, 0.99558747277356918, 0.99558743911968584, 0.99558717493055171, 0.99558716818482751, 0.99558715464044623, 0.99558706190911084, 0.99558705437654726, 0.9955870352898184, 0.99558696397881119, 0.99558674951167869, 0.99558672080734101, 0.99558656965875958, 0.99558648907028402, 0.99558647429651692, 0.99558639063110832, 0.99558632578582407, 0.99558629516247032, 0.99558629373353313, 0.99558621787147417, 0.99558612281055714, 0.99558602025853571]\n"
     ]
    }
   ],
   "source": [
    "from sklearn.neural_network import MLPClassifier\n",
    "mlp = MLPClassifier(activation = 'logistic',solver='sgd', alpha=0.2, hidden_layer_sizes=(80,40), random_state=1)\n",
    "\n",
    "mlp.fit(X_train_scaled, y_train_n) \n",
    "\n",
    "pred_mlp = mlp.predict_proba(X_predict_scaled)\n",
    "\n",
    "probs_mlp = []\n",
    "for t in pred_mlp:\n",
    "    probs_mlp.append(t[1])\n",
    "indices = sorted(range(len(probs_mlp)), key=lambda k: probs_mlp[k])[::-1][:453]\n",
    "print [probs_mlp[indices[i]] for i in range(len(indices))]\n",
    "\n",
    "predicted_edges_mlp = []\n",
    "for i in range(len(indices)):\n",
    "    predicted_edges_mlp.append(non_edges[indices[i]])\n",
    "\n",
    "with open('predicted_edges_mlp.txt', 'w') as fp:\n",
    "    for site_1, site_2 in predicted_edges_mlp:\n",
    "        fp.write(site_1+'\\t'+site_2+'\\n')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import random\n",
    "X_train_n = np.load('cache/X_train.npy')\n",
    "y_train_n = np.load('cache/y_train.npy')\n",
    "X_predict_n = np.load('cache/X_test.npy')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3491082\n"
     ]
    }
   ],
   "source": [
    "from sklearn.ensemble import RandomForestClassifier\n",
    "np.random.seed(10)\n",
    "seed = np.random.randint(1,4000000)\n",
    "print seed\n",
    "#{'bootstrap': False, 'min_samples_leaf': 3, 'min_samples_split': 10, 'criterion': 'gini', \n",
    "                #'max_features': 4, 'max_depth': 8}\n",
    "    #'bootstrap': True, 'min_samples_leaf': 3, 'min_samples_split': 2, 'criterion': 'entropy',\n",
    "    #'max_features': 8, 'max_depth': 8}\n",
    "#forest = RandomForestClassifier(random_state=seed,n_estimators=80, min_samples_split=10,\n",
    "                                #max_features=4, max_depth=8, min_samples_leaf=3,criterion='gini')\n",
    "# Parameters: {'bootstrap': True, 'min_samples_leaf': 3, 'min_samples_split': 2, 'criterion': 'gini',\n",
    "#              'max_features': 3, 'max_depth': 8}\n",
    "\n",
    "forest = RandomForestClassifier(random_state=seed, n_estimators=120, min_samples_split=3, min_samples_leaf=3,\n",
    "                                bootstrap=False,  max_features=3, max_depth=8, criterion='gini')\n",
    "\n",
    "forest.fit(X_train_n, y_train_n)\n",
    "pred_forest = forest.predict_proba(X_predict_n)\n",
    "probs_forest = []\n",
    "for t in pred_forest:\n",
    "    probs_forest.append(t[1])\n",
    "indices = sorted(range(len(probs_forest)), key=lambda k: probs_forest[k])[::-1][:453]\n",
    "predicted_edges_forest = []\n",
    "for i in range(len(indices)):\n",
    "        predicted_edges_forest.append(non_edges[indices[i]])\n",
    "print [probs_forest[indices[i]] for i in range(len(indices))]\n",
    "with open('predicted_edges_forest.txt', 'w') as fp:\n",
    "    for site_1, site_2 in predicted_edges_forest:\n",
    "        fp.write(site_1+'\\t'+site_2+'\\n')\n",
    "f_ind = np.argsort(forest.feature_importances_)[::-1]\n",
    "for i in f_ind:\n",
    "    print \"\\n\",feature_names[i],forest.feature_importances_[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "/home/lias/PycharmProjects/link-prediction/venv/lib/python2.7/site-packages/sklearn/cross_validation.py:44: DeprecationWarning: This module was deprecated in version 0.18 in favor of the model_selection module into which all the refactored classes and functions are moved. Also note that the interface of the new CV iterators are different from that of this module. This module will be removed in 0.20.\n",
      "  \"This module will be removed in 0.20.\", DeprecationWarning)\n"
     ]
    },
    {
     "ename": "NameError",
     "evalue": "name 'X_train_n' is not defined",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mNameError\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[1;32m<ipython-input-1-71bf5854c9c9>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m()\u001b[0m\n\u001b[0;32m      1\u001b[0m \u001b[1;32mimport\u001b[0m \u001b[0mxgboost\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      2\u001b[0m \u001b[0mxgb\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mxgboost\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mXGBClassifier\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m----> 3\u001b[1;33m \u001b[0mxgb\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mfit\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mX_train_n\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0my_train_n\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m      4\u001b[0m \u001b[0mpred_xgb\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mxgb\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mpredict_proba\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mX_predict_n\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      5\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;31mNameError\u001b[0m: name 'X_train_n' is not defined"
     ]
    }
   ],
   "source": [
    "import xgboost\n",
    "xgb = xgboost.XGBClassifier()\n",
    "xgb.fit(X_train_n, y_train_n)\n",
    "pred_xgb = xgb.predict_proba(X_predict_n)\n",
    "\n",
    "f_ind = np.argsort(xgb.feature_importances_)[::-1]\n",
    "for i in f_ind:\n",
    "    print feature_names[i],xgb.feature_importances_[i]\n",
    "\n",
    "probs_xgb = []\n",
    "for t in pred_xgb:\n",
    "    probs_xgb.append(t[1])\n",
    "indices = sorted(range(len(probs_xgb)), key=lambda k: probs_xgb[k])[::-1][:453]\n",
    "predicted_edges_xgb = []\n",
    "counter=0\n",
    "for i in range(len(indices)):\n",
    "    predicted_edges_xgb.append(non_edges[indices[i]])\n",
    "print [probs_xgb[indices[i]] for i in range(len(indices))]\n",
    "with open('predicted_edges_xgb.txt', 'w') as fp:\n",
    "    for site_1, site_2 in predicted_edges_xgb:\n",
    "        fp.write(site_1+'\\t'+site_2+'\\n')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "## Gradient Boosting"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "231237\n",
      "[0.99990616443726688, 0.99989693841848748, 0.9998922135588949, 0.99988683938769096, 0.99987787698348329, 0.99987527473687998, 0.99986852023662576, 0.99986574054235766, 0.99986418456194326, 0.99986177513969532, 0.99986072271133863, 0.99985814661859973, 0.99985128516004773, 0.99984314385779904, 0.99984074948899948, 0.99983943596107994, 0.99983458566184436, 0.99982975321975842, 0.99981782635897509, 0.99981782635897509, 0.99980833273367997, 0.99980272558311034, 0.99979805495144802, 0.99979786179723296, 0.99979750946688462, 0.99979728275942537, 0.99979706372470112, 0.99979704778274203, 0.99979115408838937, 0.9997877920283178, 0.99978345264977553, 0.99978236365253526, 0.9997782472990473, 0.99977650717199418, 0.99977091796561324, 0.99977026501521715, 0.99976628134892487, 0.99976570637735251, 0.99976212216886828, 0.99975728058394364, 0.99975464400733816, 0.99975206550359208, 0.99975199676534676, 0.99975065085003945, 0.99974980430906424, 0.99974702336200116, 0.99974622879314978, 0.99974430519227464, 0.99974055445966936, 0.9997339632902642, 0.9997337941815726, 0.99972801740269668, 0.99972176009705793, 0.99972091590271051, 0.99971925021096109, 0.99971878239691769, 0.99970894489728312, 0.99970793731141883, 0.99970542695326003, 0.99970350938160546, 0.99970270649280324, 0.99970215296517806, 0.99970159683629567, 0.99970010029054357, 0.9996985727551515, 0.99969622306146544, 0.99969503723870512, 0.99969472210583044, 0.99969399818891302, 0.99969377267391624, 0.99969174724650955, 0.99969065369846022, 0.99969006640783742, 0.99968670703348017, 0.99968657727379029, 0.99968497095888875, 0.99968475876546425, 0.99968366007076326, 0.99968262322001966, 0.99968020097827159, 0.99967741368717256, 0.99967701513714013, 0.9996744498496748, 0.99967394835487211, 0.99967258660288816, 0.99967258660288816, 0.99967258660288816, 0.99967143235733968, 0.99967143235733968, 0.9996713523473757, 0.99967123078654541, 0.99967123078654541, 0.99966758038411474, 0.99966501016646014, 0.9996641873648926, 0.99966372243160062, 0.99966353183968581, 0.99966301052478157, 0.99966292024903358, 0.99966114155379349, 0.99966062371980147, 0.99965875064543364, 0.99965813662197756, 0.99965552118175416, 0.99965540547961718, 0.99965402005159931, 0.99965319743764514, 0.99965200961634215, 0.99963945384692787, 0.99963565924998021, 0.99962967570579675, 0.99962943265662596, 0.99962906891644776, 0.99962569191669937, 0.99962458876999882, 0.99962320135446747, 0.99962086333217948, 0.99962019476100195, 0.99961730998509257, 0.99961385246647416, 0.99961300049544843, 0.99961253318298904, 0.9996092182789813, 0.99960540823535016, 0.99960360537237603, 0.99959993699165939, 0.99959783319979545, 0.99959777381443371, 0.99959751466338953, 0.99959751466338953, 0.9995974594133159, 0.9995953147939316, 0.99959457848779432, 0.99959141560264664, 0.99958622850046808, 0.99958580713955392, 0.99957964418799139, 0.99957861627286515, 0.99957409024507848, 0.99957042577542721, 0.99957038979284196, 0.99956954535896869, 0.99956929375520454, 0.99956928130912348, 0.99956828206573023, 0.99956551624641632, 0.9995588928934046, 0.99955776895796056, 0.9995563291995182, 0.99955592089224077, 0.99955505482831608, 0.99955430089627351, 0.99955316035792396, 0.99955242547679912, 0.99955128448824715, 0.99954908590461478, 0.99954566153195434, 0.99954337323277553, 0.99954325637999353, 0.99954050537122185, 0.9995391107890379, 0.99953878123122142, 0.99953839154958113, 0.99953791408674675, 0.99953600643315288, 0.99952818268039256, 0.99952780548216591, 0.99952555431817125, 0.99952522822690759, 0.99952463105682121, 0.99952064465501922, 0.99951632184552841, 0.99951495597762552, 0.99951364417661737, 0.99951290928728898, 0.99950956149456727, 0.99950728414027146, 0.99950451735516421, 0.9995043901345082, 0.99950288546789212, 0.99949812414403461, 0.99949708279436889, 0.9994959106033775, 0.999493973382927, 0.99948903400790845, 0.99948903400790845, 0.99948675052847891, 0.99947970337448222, 0.99947949852442497, 0.99947195818923962, 0.99947102082181205, 0.99946735758223637, 0.99946550603267115, 0.99946203446158577, 0.9994585230188493, 0.9994572901419031, 0.99945712418316868, 0.9994545211360516, 0.99945452050984274, 0.99945148213481827, 0.99945060589817558, 0.99944667838929691, 0.99944428724962775, 0.99944414212913268, 0.9994430044717828, 0.99944197192531448, 0.99943856284271682, 0.99943556287658897, 0.99943383696632382, 0.99943173314699663, 0.99943135112004289, 0.99943120470492453, 0.99942809459325355, 0.99942768484382993, 0.99942697509616452, 0.99942697509616452, 0.99942549223313015, 0.9994213526457254, 0.99941913586297471, 0.9994179651024222, 0.99941659572654895, 0.99941543145276468, 0.9994103212736043, 0.9994079484313978, 0.9994043675047577, 0.99940434779388676, 0.9994024360091579, 0.99940125828119997, 0.99940110565594942, 0.99939914075385672, 0.99939868927628017, 0.99939842323780248, 0.9993937372588404, 0.99939302511907435, 0.99939198726542977, 0.99938735717293836, 0.99938696937948568, 0.9993869088248839, 0.99938269425046666, 0.99938228778856664, 0.99938143821055758, 0.99937973919295831, 0.99937950569283707, 0.99937756148338208, 0.99937747779162189, 0.99937715595440468, 0.99937687760245952, 0.9993752143447352, 0.99937486783671314, 0.99937137338430027, 0.99936602188987356, 0.99936602188987356, 0.99936602188987356, 0.99936378625510602, 0.99936331205215756, 0.99936255536950491, 0.99936194580556392, 0.99936194580556392, 0.99936109197027345, 0.99936085516686135, 0.99935785403297872, 0.99935204061367588, 0.99935145648566548, 0.99935141878992484, 0.99934980725384581, 0.99934952318303127, 0.99934948950195279, 0.99934797002576192, 0.99934516794789807, 0.99934253121726324, 0.99933950455047271, 0.99933859580890116, 0.99933859580890116, 0.99933843959603619, 0.99933315389179167, 0.99933295052316362, 0.99933295052316362, 0.99933222948028877, 0.99933079133647151, 0.99932738014543765, 0.99932296628601025, 0.99932124270508171, 0.99932050496216251, 0.9993128728786409, 0.99930973387560773, 0.99930910938047479, 0.99930848355854973, 0.99930639572137114, 0.99930421126253199, 0.99930390952219494, 0.9993036983836544, 0.99930138579404804, 0.99930049858553616, 0.99929669853823522, 0.99929347210236408, 0.9992908672505606, 0.99928763265363185, 0.99928446804421545, 0.99928379664505895, 0.99927966916826516, 0.9992777331962468, 0.99927770526082871, 0.99927709912345042, 0.99927687784140939, 0.99927224403575499, 0.99927207381077532, 0.99927181930939668, 0.99927002405933529, 0.99926908938443504, 0.99926814509754935, 0.99926209779624953, 0.99926172380053946, 0.99925879119599137, 0.9992571369164428, 0.99925543023108332, 0.99925473720415281, 0.99925405395476996, 0.99925178999752895, 0.99925125033947604, 0.99925013286192921, 0.99924986905882585, 0.99924920028530995, 0.99923968754348436, 0.99923459485965249, 0.99923241759069392, 0.99923169120387256, 0.99923147007507351, 0.99923145687656278, 0.9992314203186744, 0.99923001155843205, 0.9992299356422919, 0.99922857165852641, 0.99922832480079427, 0.9992273500647455, 0.99922571599553478, 0.99922459451110823, 0.99921887338915638, 0.99921824076136967, 0.99921799594534877, 0.99921422026249507, 0.99921416096958182, 0.99921393693880856, 0.99921214289007565, 0.99921195686836362, 0.99921173124936069, 0.99921079697872917, 0.99921079697872917, 0.99920969500112589, 0.99920657459600304, 0.99920576086905555, 0.99920135875615668, 0.9991993742113634, 0.99919707596521645, 0.99919679106323123, 0.9991939647148993, 0.99919331365926711, 0.9991930358487181, 0.9991923802174385, 0.99919132428795265, 0.99919132428795265, 0.99918955771530427, 0.99918834621728014, 0.99918695370659827, 0.99918480952742272, 0.99918451502854677, 0.99918305007907804, 0.99918133673865761, 0.99918098513372355, 0.99918034218612761, 0.99917569778832072, 0.99917522695365169, 0.99916961245898184, 0.99916931706102308, 0.99916622564542223, 0.99916400288973939, 0.9991631373558626, 0.99916242662796628, 0.9991604393401492, 0.99916009288511676, 0.99915988743055761, 0.99915624601000708, 0.99915571972563622, 0.99915453494146989, 0.9991533890068125, 0.9991533890068125, 0.99915138899877165, 0.99915071061430993, 0.99914943422113622, 0.99914910630512976, 0.99914821757101679, 0.99914747612953936, 0.99914526898419131, 0.99914345069949917, 0.99914258223564578, 0.99914247592550098, 0.99914247592550098, 0.99914247592550098, 0.99913919563374143, 0.99913892889970923, 0.99913764187338072, 0.99913725337530013, 0.99912506869755624, 0.99912418991131657, 0.99912353284281963, 0.99912268442805241, 0.99912256080636441, 0.99912108785916554, 0.99912050872385605, 0.99911905183607319, 0.99911501556416027, 0.99911303344124747, 0.99911173570904621, 0.99911151344865179, 0.99910901512122019, 0.99910901512122019, 0.99910861114278593, 0.99910858072160447, 0.99910029008761669, 0.99909659875563084, 0.9990946029105443, 0.99909419787430709, 0.99908972705942611, 0.99908890213348012, 0.99908798052834036, 0.99908727386792895, 0.99908547235992129, 0.999085060271661, 0.99908271261939152, 0.99908264836421112, 0.99908170787971429, 0.99908147352610988, 0.99907734374010371, 0.99907641536622394, 0.99907617260113535, 0.99907617260113535, 0.99907614887870355, 0.99907257552267292, 0.99907070081257165, 0.99907033448020688, 0.99906677172080538, 0.99906058279850363, 0.99906009578503574, 0.99905822837622016, 0.99905749278512224, 0.99905733427040067, 0.99905709346181493, 0.99905622754399681, 0.99905530607072113, 0.99905530102905693, 0.99905508843879676, 0.99905483638272063, 0.99905149868934995, 0.99905018462860118]\n",
      "partition_check 0.313528187507\n",
      "text 0.0834377172733\n",
      "G.out_degree(src) 0.0628446766328\n",
      "betweeness]dst 0.0599220057035\n",
      "pagerank[dst] 0.0558229140606\n",
      "adamic_adar 0.0553131422464\n",
      "katz[src] 0.0525179131836\n",
      "#_of_second_neighbors 0.0506366055407\n",
      "jaccard_coefficient 0.0409049809179\n",
      "closeness[src] 0.0371667200002\n",
      "preferential_attachment 0.0370983238516\n",
      "core_number[dst] 0.0323039599418\n",
      "triangles[src] 0.0268836141642\n",
      "simrank 0.0182836311094\n",
      "resource_allocation_index 0.0166539282838\n",
      "betweeness[src] 0.0146181730748\n",
      "core_number[src] 0.0138756436239\n",
      "betweeness[src] 0.0113781693658\n",
      "eigenvector[dst] 0.0101702169503\n",
      "pagerank[src] 0.00517274745943\n",
      "G.in_degree(dst) 0.000772876820505\n",
      "#common_neighbors 0.000693852288768\n",
      "katz[dst] 0.0\n",
      "closeness[dst] 0.0\n",
      "eigenvector[src] 0.0\n",
      "triangles[dst] 0.0\n"
     ]
    }
   ],
   "source": [
    "class CompatClassifier(RandomForestClassifier):\n",
    "   def predict(self, X):\n",
    "       return self.predict_proba(X)[:, 1][:,np.newaxis]\n",
    "seed = random.randint(1, 400000)\n",
    "print seed   \n",
    "#278753\n",
    "\n",
    "base_estimator = CompatClassifier(random_state=3808056, n_estimators=10, min_samples_split=3, min_samples_leaf=3,\n",
    "                                bootstrap=False,  max_features=3, max_depth=8, criterion='gini')\n",
    "#min_samples_split=10,\n",
    "                                #max_features=4, max_depth=8, min_samples_leaf=3,criterion='gini'\n",
    "from sklearn.ensemble import GradientBoostingClassifier\n",
    "gbc = GradientBoostingClassifier(random_state=3808056,init=base_estimator,n_estimators=150)\n",
    "\n",
    "gbc.fit(X_train_n,y_train_n)\n",
    "preds_gbc = gbc.predict_proba(X_predict_n)\n",
    "probs_gbc = []\n",
    "for t in preds_gbc:\n",
    "    probs_gbc.append(t[1])\n",
    "indices = sorted(range(len(probs_gbc)), key=lambda k: probs_gbc[k])[::-1][:453]\n",
    "predicted_edges_gbc = []\n",
    "for i in range(len(indices)):\n",
    "        predicted_edges_gbc.append(non_edges[indices[i]])\n",
    "print [probs_gbc[indices[i]] for i in range(len(indices))]\n",
    "with open('predicted_edges_gbc.txt', 'w') as fp:\n",
    "    for site_1, site_2 in predicted_edges_gbc:\n",
    "        fp.write(site_1+'\\t'+site_2+'\\n')\n",
    "f_ind = np.argsort(gbc.feature_importances_)[::-1]\n",
    "for i in f_ind:\n",
    "    print \"\\n\",feature_names[i],gbc.feature_importances_[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from sklearn.ensemble import RandomForestClassifier\n",
    "from sklearn.model_selection import GridSearchCV\n",
    "from scipy.stats import randint as sp_randint\n",
    "from time import time\n",
    "# build a classifier\n",
    "clf = RandomForestClassifier(n_estimators=50, n_jobs=4)\n",
    "# Utility function to report best scores\n",
    "def report(results, n_top=3):\n",
    "    for i in range(1, n_top + 1):\n",
    "        candidates = np.flatnonzero(results['rank_test_score'] == i)\n",
    "        for candidate in candidates:\n",
    "            print(\"Model with rank: {0}\".format(i))\n",
    "            print(\"Mean validation score: {0:.3f} (std: {1:.3f})\".format(\n",
    "                  results['mean_test_score'][candidate],\n",
    "                  results['std_test_score'][candidate]))\n",
    "            print(\"Parameters: {0}\".format(results['params'][candidate]))\n",
    "            print(\"\")\n",
    "\n",
    "# use a full grid over all parameters\n",
    "param_grid = {\"max_depth\": range(3, 9),\n",
    "              \"max_features\": range(2, 9),\n",
    "              \"min_samples_split\": [2, 3, 10],\n",
    "              \"min_samples_leaf\": [1, 3, 10],\n",
    "              \"bootstrap\": [True, False],\n",
    "              \"criterion\": [\"gini\", \"entropy\"]}\n",
    "\n",
    "# run grid search\n",
    "grid_search = GridSearchCV(clf, param_grid=param_grid)\n",
    "start = time()\n",
    "grid_search.fit(X_train_n, y_train_n)\n",
    "\n",
    "print(\"GridSearchCV took %.2f seconds for %d candidate parameter settings.\"\n",
    "      % (time() - start, len(grid_search.cv_results_['params'])))\n",
    "report(grid_search.cv_results_)\n",
    "with open('grid_forest.pickle', 'wb') as pfile:\n",
    "        pickle.dump(grid_search.cv_results_, pfile)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import xgboost\n",
    "from sklearn.model_selection import GridSearchCV\n",
    "from scipy.stats import randint as sp_randint\n",
    "from time import time \n",
    "# build a classifier\n",
    "clf = xgboost.XGBClassifier()\n",
    "# Utility function to report best scores\n",
    "def report(results, n_top=3):\n",
    "    for i in range(1, n_top + 1):\n",
    "        candidates = np.flatnonzero(results['rank_test_score'] == i)\n",
    "        for candidate in candidates:\n",
    "            print(\"Model with rank: {0}\".format(i))\n",
    "            print(\"Mean validation score: {0:.3f} (std: {1:.3f})\".format(\n",
    "                  results['mean_test_score'][candidate],\n",
    "                  results['std_test_score'][candidate]))\n",
    "            print(\"Parameters: {0}\".format(results['params'][candidate]))\n",
    "            print(\"\")\n",
    "\"\"\"(base_score=0.5, colsample_bylevel=1, colsample_bytree=1,\n",
    "       gamma=0, learning_rate=0.1, max_delta_step=0, max_depth=3,\n",
    "       min_child_weight=1, missing=None, n_estimators=100, nthread=-1,\n",
    "       objective='binary:logistic', reg_alpha=0, reg_lambda=1,\n",
    "       scale_pos_weight=1, seed=0, silent=True, subsample=1)>\"\"\"\n",
    "# use a full grid over all parameters\n",
    "param_grid = {\n",
    "    \"learning_rate\": np.arange(0.15, 0.25, 0.05),\n",
    "    \"max_depth\": range(4, 6),\n",
    "    \"max_delta_step\": np.arange(0, 0.15, 0.05),\n",
    "    \"gamma\": np.arange(0, 0.15, 0.05),\n",
    "    \"max_delta_step\": np.arange(0, 0.15, 0.05),\n",
    "    \"subsample\": np.arange(0.7, 1, 0.1),\n",
    "    \"min_child_weight\": np.arange(0.8, 1.20, 0.1),}\n",
    "\n",
    "# run grid search\n",
    "grid_search = GridSearchCV(clf, param_grid=param_grid)\n",
    "start = time()\n",
    "grid_search.fit(X_train_n, y_train_n)\n",
    "\n",
    "print(\"GridSearchCV took %.2f seconds for %d candidate parameter settings.\"\n",
    "      % (time() - start, len(grid_search.cv_results_['params'])))\n",
    "report(grid_search.cv_results_)\n",
    "with open('grid_xgb.pickle', 'wb') as pfile:\n",
    "        pickle.dump(grid_search.cv_results_, pfile)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from sklearn.ensemble import VotingClassifier\n",
    "xgb = xgboost.XGBClassifier()\n",
    "forest = RandomForestClassifier(random_state=seed,n_estimators=80, max_features=6, max_depth=7, min_samples_leaf=3,oob_score=True)\n",
    "eclf1 = VotingClassifier(estimators=[('forest', forest), ('xgb', xgb)], voting='soft')\n",
    "\n",
    "eclf1 = eclf1.fit(X_train_n, y_train_n)\n",
    "voting_pred = eclf1.predict_proba(X_predict_n)\n",
    "\n",
    "probs_vote = []\n",
    "for t in voting_pred:\n",
    "    probs_vote.append(t[1])\n",
    "indices = sorted(range(len(probs_vote)), key=lambda k: probs_vote[k])[::-1][:453]\n",
    "predicted_edges_vote = []\n",
    "for i in range(len(indices)):\n",
    "    predicted_edges_vote.append(non_edges[indices[i]])\n",
    "print [probs_vote[indices[i]] for i in range(len(indices))]\n",
    "with open('predicted_edges_voting.txt', 'w') as fp:\n",
    "    for site_1, site_2 in predicted_edges_vote:\n",
    "        fp.write(site_1+'\\t'+site_2+'\\n')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Mining data from external sources (cheating?)\n",
    "\n",
    "Because of the public dataset we could not stand but try to obtain information from the data source (the Web!). So we downloaded/parsed the homepage of each host and obtained the links to other webpages that exist in the dataset. The search was not exhaustive(we set a strict response timeout) because it was supposed to be just a test, mostly trying to see how high such an (illegal) method would score. I believe that scoring 23% accuracy with this way proved the problems difficulty."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import ssl\n",
    "import requests\n",
    "import re\n",
    "from urlparse import urlparse\n",
    "from bs4 import BeautifulSoup\n",
    "def get_links(url):\n",
    "    try:\n",
    "        resp = requests.get('http://'+url,verify=False, timeout=(5,20))\n",
    "    except Exception as e:\n",
    "        print e\n",
    "        return []\n",
    "    html = resp.text\n",
    "    soup = BeautifulSoup(html, \"html5lib\")\n",
    "    links = soup.findAll(\"a\")\n",
    "    reg = '^(www.)'\n",
    "    try:\n",
    "        links = [re.sub(reg, '', urlparse(link.get('href')).netloc) for link in links]\n",
    "    except AttributeError:\n",
    "        pass\n",
    "    return list(set([link for link in links if G.has_node(link) and not G.has_edge(url, link) and link !=url] ))\n",
    "\n",
    "if os.path.isfile('cache/crawled_data.pickle'):\n",
    "    with open('cache/crawled_data.pickle', 'rb') as pfile:\n",
    "        text_data = pickle.load(pfile)\n",
    "        print \"loaded from pickle\"\n",
    "else:    \n",
    "    missing = {}\n",
    "    for node in G.nodes():    \n",
    "        # Start the timer. Once 5 seconds are over, a SIGALRM signal is sent.\n",
    "        signal.alarm(25)    \n",
    "        # This try/except loop ensures that \n",
    "        #   you'll catch TimeoutException when it's sent.\n",
    "        try:\n",
    "            print node,\n",
    "            missing[node]=get_links(node) # Whatever your function that might hang\n",
    "        except TimeoutException:\n",
    "            continue # continue the for loop if function A takes more than 5 second\n",
    "        else:\n",
    "            # Reset the alarm\n",
    "            signal.alarm(0)\n",
    "    with open('cache/crawled_data.pickle', 'wb') as pfile:\n",
    "        pickle.dump(missing, pfile)\n",
    "\n",
    "counter  = 0\n",
    "for key,value in missing.iteritems():\n",
    "    if len(value)>0:\n",
    "        counter+=len(value)\n",
    "print counter\n",
    "\n",
    "crawled = []\n",
    "for src, links in missing.iteritems():\n",
    "    for dst in links:\n",
    "        crawled.append((src,dst))\n",
    "\n",
    "\n",
    "with open('predicted_edges_crawled.txt', 'w') as fp:\n",
    "    for site_1, site_2 in crawled:\n",
    "        fp.write(site_1+'\\t'+site_2+'\\n')\n",
    "    for site_1, site_2 in predicted_edges_xgb:\n",
    "        if (site_1,site_2) not in crawled:\n",
    "            fp.write(site_1+'\\t'+site_2+'\\n')"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}