assignment_2019_1.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Πυρηνική Αποσύνθεση\n",
    "\n",
    "Ως *$k$-πυρήνας* ενός γράφου ορίζεται ένας υπογράφος του τέτοιος ώστε όλοι οι κόμβοι που ανήκουν σε αυτόν τον υπογράφο είναι συνδεμένοι με τουλάχιστον $k$ άλλους κόμβους του υπογράφου. Ο *πυρηνικός αριθμός* (core number) ενός κόμβου είναι ο αριθμός του $k$-πυρήνα στον οποίο ανήκει με το μέγιστο $k$. Για παράδειγμα, στον παρακάτω γράφο μπορείτε να δείτε τους τρεις πυρήνες του (από το βιβλίο των Fouss, Saerens, και Shimbo, 2016, σ. 365, βλ. στις περισσότερες πληροφορίες):\n",
    "\n",
    "<img src=\"example_graph.png\" width=\"600\"/>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Οι πυρήνες ενός γράφου έχουν διάφορες εφαρμογές, από οπτικοποίηση (visualisation) δικτυακών δομών, μέχρι τη βιοπληροφορική, τον εντοπισμό influencers, την εξάπλωση οικονομικών κρίσεων, κ.λπ. Μπορείτε να δείτε το [σχετικό άρθρο της Wikipedia](<https://en.wikipedia.org/wiki/Degeneracy_(graph_theory)>)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Για να βρούμε τους $k$-πυρήνες ενός γράφου, για κάποιο συγκεκριμένο $k$, αρκεί να αφαιρέσουμε όλους τους κόμβους που έχουν λιγότερους από $k$ συνδέσμους. Οι κόμβοι που μένουν θα συνιστούν έναν ή παραπάνω γράφους, υπογράφους του αρχικού, ο καθένας από τους οποίους αποτελείται από κόμβους με τουλάχιστον $k$ συνδέσμους, άρα ο κάθε τέτοιος υπογράφος είναι $k$-πυρήνας. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Για να βρούμε τώρα τους πυρηνικούς αριθμούς όλων των κόμβων ενός γράφου εργαζόμαστε περίπου αντίστοιχα. Στην αρχή αφαιρούμε όλους τους κόμβους που έχουν έναν σύνδεσμο. Οι κόμβοι που μένουν ανήκουν σε έναν 2-πυρήνα. Στη συνέχεια αφαιρούμε όλους τους κόμβους που έχουν ένα σύνδεσμο, αφού αφαιρέθηκαν οι προηγούμενοι. Οι κόμβοι που μένουν ανήκουν σε έναν 3-πυρήνα, κ.ο.κ. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Μπορούμε να βρούμε τους πυρηνικούς αριθμούς των κόμβων ενός γράφου με πιο έξυπνο τρόπο. Πάλι θα βρίσκουμε και θα αφαιρούμε συγκεκριμένους κόμβους, αλλά θα χρησιμοποιήσουμε μια ουρά ελαχίστων για τον εντοπισμό του προς διαγραφή κόμβου. Επιπλέον, κάθε φορά που θα διαγράφουμε ένα κόμβο, θα ενημερώνουμε τους εν δυνάμει πυρηνικούς αριθμούς των γειτόνων του, λαμβάνοντας υπόψη τη μορφή που έχει ο γράφος μετά από κάθε διαγραφή."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"k_cores_algorithm.png\" width=\"600\"/>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ο αλγόριθμος χρησιμοποιεί έναν σωρό ελαχίστων $\\mathit{mh}$, τον οποίο δημιουργούμε στη γραμμή 1. Στη γραμμή 2 δημιουργούμε τον πίνακα $d$ στον οποίο θα αποθηκεύσουμε τον βαθμό (degree) κάθε κόμβου του γράφου. Στη γραμμή 3 δημιουργούμε τον πίνακα $p$ στον οποίο θα αποθηκεύσουμε τον εν δυνάμει (potential) πυρηνικό αριθμό κάθε κόμβου του γράφου. Στη γραμμή 4 δημιουργούμε τον πίνακα $\\mathit{core}$ στον οποίο θα αποθηκεύσουμε τα αποτελέσματα του αλγορίθμου. Στο τέλος της εκτέλεσής του, το στοιχείο $\\mathit{core}[i]$ θα περιέχει τον πυρηνικό αριθμό του κόμβου $i$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Στις γραμμές 5-10 προχωράμε σε αρχικοποιήσεις τιμών. Συγκεκριμένα, αρχικοποιούμε τον πίνακα $d$ (γραμμή 6) και τον πίνακα $p$. Η πρώτη εκτίμηση που έχουμε για τον πυρηνικό αριθμό ενός κόμβου είναι να είναι ίσος με το βαθμό του (γραμμή 7). Στη χειρότερη περίπτωση ο κόμβος μπορεί να έχει πυρηνικό αριθμό ίσο με μηδέν, που είναι η τιμή που δίνουμε στον πίνακα των τελικών αποτελεσμάτων (γραμμή 8). Ο αλγόριθμος θα χρησιμοποιήσει το σωρό ελαχίστων για να βρίσκουμε κάθε φορά τον κόμβο με τον ελάχιστο εν δυνάμει πυρηνικό αριθμό. Δημιουργούμε λοιπόν έναν πίνακα δύο στοιχείων $\\mathit{pn}$ (potential-node) που περιέχει τον εν δυνάμει πυρηνικό αριθμό κάθε κόμβου και τον ίδιο τον κόμβο (γραμμή 9) και εισάγουμε τον πίνακα στον σωρό ελαχίστων."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Το κύριο μέρος του αλγορίθμου είναι η επανάληψη στις γραμμές 11-20, η οποία εκτελείται όσο δεν είναι άδειος ο σωρός ελαχίστων (γραμμή 11). Ξεκινάμε βγάζοντας το ελάχιστο στοιχείο $t$ (top) από τον σωρό ελαχίστων (γραμμή 12). Το ελάχιστο στοιχείο είναι ένας πίνακας δύο στοιχείων με τον εν δυνάμει πυρηνικό αριθμό ($t[0]$) και τον αντίστοιχο κόμβο ($t[1])$. Αυτός είναι ο κόμβος με τον ελάχιστο εν δυνάμει πυρηνικό αριθμό."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Στην πρώτη επανάληψη, ο κόμβος αυτός είναι ο κόμβος με τον ελάχιστο αριθμό συνδέσμων (ή κάποιος από του κόμβους με τον ελάχιστο αριθμό συνδέσμων σε περίπτωση ισοπαλίας). Ο κόμβος αυτός δεν μπορεί να έχει πυρηνικό αριθμό μεγαλύτερο από τον αριθμό των συνδέσμων του, γιατί σε κάθε υπογράφο στον οποίο ανήκει οι υπόλοιποι κόμβοι έχουν ίσο ή μεγαλύτερο αριθμό συνδέσμων (θυμηθείτε ότι στην αρχικοποίηση, ο εν δυνάμει πυρηνικός αριθμός έγινε ίσος με το βαθμό του κόμβου). Έτσι, αποθηκεύουμε στον πίνακα των τελικών αποτελεσμάτων τον εν δυνάμει πυρηνικό αριθμό του κόμβου, αφού δεν είναι απλώς εν δυνάμει, αλλά ο πραγματικός πυρηνικός αριθμός του. Αφού το κάνουμε αυτό, ελέγχουμε αν, έχοντας αφαιρέσει ένα στοιχείο από το σωρό ελαχίστων, αυτός έχει αδειάσει (γραμμή 14). Στην περίπτωση αυτή δεν έχουμε κάτι άλλο να κάνουμε, βγαίνουμε από την επανάληψη, και επιστρέφουμε τα αποτελέσματα (γραμμή 21)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Εκτός όμως και αν ο γράφος μας έχει μόνο ένα κόμβο, δεν θα έχουμε τελειώσει, και στο σωρό ελαχίστων θα υπάρχουν οι υπόλοιποι κόμβοι. Για τους γείτονες του κόμβου τον οποίο εξεργαζόμαστε ισχύει το εξής. Είτε θα ανήκουν στον ίδιο $k$-πυρήνα με τον κόμβο που επεξεργαζόμαστε, είτε σε έναν διαφορετικό. Αν ο γείτονας ανήκει στον ίδιο $k$-πυρήνα με τον τρέχοντα κόμβο, τότε ο πυρηνικός αριθμός του θα είναι ίδιος με τον πυρηνικό αριθμό του τρέχοντα κόμβου.\n",
    "Αν ανήκει σε διαφορετικό, θα πρέπει να αφαιρέσουμε από τον αριθμό συνδέσμων του γείτονα ένα, γιατί ο σύνδεσμος με τον τρέχοντα κόμβο δεν θα ανήκει στον $k$-πυρήνα και θα πρέπει να αγνοηθεί. Αυτό το κάνουμε στη γραμμή 16, με την οποία διαγράφουμε, τόπο τινά, τον κόμβο από τον γράφο· προσέξτε ότι στην πραγματικότητα δεν τον διαγράφουμε, όπως στον αρχικό αλγόριθμο, αρκεί να μην τον μετράμε πλέον στους βαθμούς των υπόλοιπων κόμβων."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ο εν δυνάμει πυρηνικός αριθμός του γείτονα λοιπόν θα είναι ο μεγαλύτερος από τον πυρηνικό αριθμό του τρέχοντα κόμβου (αν ανήκει στον ίδιο $k$-πυρήνα με αυτόν) και τον ενημερωμένο βαθμό του γείτονα (αν δεν ανήκει στον ίδιο $k$-πυρήνα). Πριν προχωρήσουμε στην ενημέρωση του πυρηνικού αριθμού, κρατάμε σε μία μεταβλητή $\\mathit{opn}$ (old potential node) το υπάρχον στοιχείο του σωρού ελαχίστων που αντιστοιχεί στον γείτονα. Κατόπιν προχωρούμε στην ενημέρωση του πυρηνικού αριθμό σύμφωνα με τα όσα είπαμε, στη γραμμή 18. Αφού το κάνουμε αυτό, πρέπει να ενημερώσουμε την ουρά ελαχίστων. Δημιουργούμε τον νέο, ενημερωμένο κόμβο $\\mathit{npn}$ (new potential node, γραμμή 19), και ενημερώνουμε την ουρά, ζητώντας να αλλαχτεί ο παλιός, υπάρχον κόμβος, με τον νέο (γραμμή 20)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Με τον τρόπο αυτό, στο τέλος κάθε επανάληψης η ουρά ελαχίστων θα μπορεί να μας δίνει, στην επόμενη επανάληψη, τον κόμβο με τον ελάχιστο εν δυνάμει πυρηνικό αριθμό. Σκεφτόμενοι όπως και πριν, μπορούμε να δούμε ότι αυτός θα είναι και ο πραγματικός πυρηνικός αριθμός, γιατί αφού αφαιρούμε, έστω νοητικά, κόμβους από το γράφο, κάθε επανάληψη δρα σαν να ξεκινούσαμε από την αρχή σε ένα νέο γράφο, με έναν λιγότερο κόμβο, αρχικοποιημένο όπως πρέπει."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Απαιτήσεις Προγράμματος\n",
    "\n",
    "Κάθε φοιτητής θα εργαστεί σε αποθετήριο στο GitHub. Για να αξιολογηθεί μια εργασία θα πρέπει να πληροί τις παρακάτω προϋποθέσεις:\n",
    "\n",
    "* Για την υποβολή της εργασίας θα χρησιμοποιηθεί το ιδιωτικό αποθετήριο του φοιτητή που δημιουργήθηκε για τις ανάγκες του μαθήματος και του έχει αποδωθεί. Το αποθετήριο αυτό έχει όνομα του τύπου `username-algo-assignments`, όπου `username` είναι το όνομα του φοιτητή στο GitHub. Για παράδειγμα, το σχετικό αποθετήριο του διδάσκοντα θα ονομαζόταν `louridas-algo-assignments` και θα ήταν προσβάσιμο στο https://github.com/dmst-algorithms-course/louridas-algo-assignments. *Τυχόν άλλα αποθετήρια απλώς θα αγνοηθούν*.\n",
    "\n",
    "* Μέσα στο αποθετήριο αυτό θα πρέπει να δημιουργηθεί ένας κατάλογος `assignment-2019-1`.\n",
    "\n",
    "* Μέσα στον παραπάνω κατάλογο το πρόγραμμα θα πρέπει να αποθηκευτεί με το όνομα `k_cores.py`.\n",
    "\n",
    "* Δεν επιτρέπεται η χρήση έτοιμων βιβλιοθηκών γράφων ή τυχόν έτοιμων υλοποιήσεων των αλγορίθμων, ή τμημάτων αυτών, εκτός αν αναφέρεται ρητά ότι επιτρέπεται. \n",
    "\n",
    "* Επιτρέπεται η χρήση δομών δεδομένων της Python όπως στοίβες, λεξικά, κ.λπ.\n",
    "\n",
    "* Επιτρέπεται η χρήση της βιβλιοθήκης `sys` προκειμένου να διαβάσει το πρόγραμμα το όνομα του αρχείου που θα επεξεργαστεί.\n",
    "\n",
    "* Ένα βασικό σημείο του αλγορίθμου είναι η ενημέρωση ενός στοιχείου που βρίσκεται στο σωρό ελαχίστων. Για την υλοποίηση του σωρού ελαχίστων μπορείτε να χρησιμοποιήσετε τον κώδικα που περιγράφει την [υλοποίηση σωρού σε Python για τη συμπίεση Huffman](http://nbviewer.jupyter.org/urls/louridas.github.io/rwa/notebooks/chapter_03.ipynb).\n",
    "\n",
    "* *Αν η εργασία δεν υλοποιεί ουρά σωρό ελαχίστων δεν θα λαμβάνεται ως σωστή*.\n",
    "\n",
    "* Το πρόγραμμα θα πρέπει να είναι γραμμένο σε Python 3.\n",
    "\n",
    "* Το πρόγραμμα θα το καλεί ως χρήστης ως εξής (όπου `python` η κατάλληλη εντολή στο εκάστοτε σύστημα):\n",
    "\n",
    "```\n",
    "python k_cores.py <input_file>\n",
    "```\n",
    "\n",
    "Στην εντολή αυτή, η παράμετρος `<input_file>` είναι ένα όνομα αρχείου που περιέχει το γράφο που θα εξετάσουμε.\n",
    "\n",
    "Τα αρχεία των γράφων θα έχουν την εξής μορφή:\n",
    "```\n",
    "0 1\n",
    "0 2\n",
    "1 3\n",
    "2 3\n",
    "2 6\n",
    "2 7\n",
    "3 6\n",
    "3 7\n",
    "3 8\n",
    "4 5\n",
    "5 6\n",
    "5 10\n",
    "6 7\n",
    "7 8\n",
    "7 11\n",
    "8 9\n",
    "```\n",
    "Βλέπουμε δηλαδή ότι αποτελούνται από γραμμές, όπου η κάθε γραμμή δηλώνει τη σύνδεση δύο κόμβων. Οι γράφοι θεωρούνται ότι είναι μη κατευθυνόμενοι. Ο παραπάνω γράφος αντιστοιχεί στον γράφο που έχουμε απεικονίσει στην αρχή.\n",
    "\n",
    "Η έξοδος του προγράμματος θα είναι μία γραμμή ανά κόμβο και θα εμφανίζει τον κόμβο και τον πυρηνικό αριθμό του. Οι κόμβοι θα είναι ταξινομένοι σε αύξουσα σειρά."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Παραδείγματα Εκτέλεσης\n",
    " \n",
    "### Παράδειγμα 1\n",
    " \n",
    "Αν ο χρήστης καλέσει το πρόγραμμα για το αρχείο [example_graph.txt](example_graph.txt), που περιλαμβάνει το παραπάνω παράδειγμα, με τον ακόλουθο τρόπο:\n",
    "\n",
    "```\n",
    "python k_cores.py example_graph.txt\n",
    "```\n",
    "\n",
    "η έξοδος του προγράμματος θα πρέπει να είναι *ακριβώς* η παρακάτω:\n",
    "\n",
    "```\n",
    "0 2\n",
    "1 2\n",
    "2 3\n",
    "3 3\n",
    "4 1\n",
    "5 1\n",
    "6 3\n",
    "7 3\n",
    "8 2\n",
    "9 1\n",
    "10 1\n",
    "11 1\n",
    "```\n",
    "\n",
    "Μπορείτε να επιβεβαιώσετε ότι τα αποτελέσματα συμφωνούν με την εικόνα.\n",
    "\n",
    "### Παράδειγμα 2\n",
    "\n",
    "Αν ο χρήστης καλέσει το πρόγραμμα για το αρχείο [human_brain_functional_activations.txt](human_brain_functional_activations.txt) με τον ακόλουθο τρόπο:\n",
    "\n",
    "```bash\n",
    "python k_cores.py human_brain_functional_activations.txt\n",
    "```\n",
    "\n",
    "η έξοδος του προγράμματος θα πρέπει να είναι ακριβώς όπως το αρχείο [human_brain_functional_activations_solution.txt](human_brain_functional_activations_solution.txt).\n",
    "\n",
    "Το αρχείο [human_brain_functional_activations.txt](human_brain_functional_activations.txt) περιέχει ένα γράφο με 638 κόμβους και 18625 συνδέσμους. Οι κόμβοι αντιστοιχούν σε μέρη του ανθρώπινου εγκεφάλου και οι σύνδεσμοι δείχνουν ότι δύο μέρη ενεργοποιούνται από κοινού (όπως έχει βρεθεί σε πειράματα με μαγνητικές τομογραφίες). Δείτε το άρθρο των Crossley κ.ά. στις περισσότερες πληροφορίες· ο γράφος προέρχεται από το [Brain Connectivity Toolbox](https://sites.google.com/site/bctnet/datasets).\n",
    "\n",
    "### Παράδειγμα 3\n",
    "\n",
    "Αν ο χρήστης καλέσει το πρόγραμμα για το αρχείο [ebag.txt](ebag.txt) με τον ακόλουθο τρόπο:\n",
    "\n",
    "```bash\n",
    "python k_cores.py ebag.txt\n",
    "```\n",
    "\n",
    "η έξοδος του προγράμματος θα πρέπει να είναι ακριβώς όπως το αρχείο [ebag_solution.txt](ebag_solution.txt). Το αρχείο [ebag.txt](ebag.txt) περιέχει ένα γράφο με 999 κόμβους και 3582 συνδέσμους. Το αρχείο αντιπροσωπεύει έναν γράφο που έχει δημιουργηθεί με το μοντέλο [Barabási–Albert](https://en.wikipedia.org/wiki/Barab%C3%A1si%E2%80%93Albert_model). Για την ακρίβεια, έχει χρησιμοποιηθεί μία επέκταση του μοντέλου Barabási–Albert, άρα extended Barabási–Albert graph, εξ' ου και το όνομα του αρχείου· το μοντέλο Barabási–Albert έχει χρησιμοποιηθεί για τη μοντελοποίηση της εξέλιξης γράφων που απεικονίζουν διαφόρων ειδών δίκτυα, δείτε το άρθρο των Albert και Barabási στις περισσότερες πληροφορίες.\n",
    "\n",
    "Καλή Επιτυχία!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Για Περισσότερες Πληροφορίες\n",
    "\n",
    "Réka Albert,  Albert-László Barabási, 2000. Topology of Evolving Networks: Local Events and Universality, Physical Review Letters, 85 (24), 5234-5237, <http://barabasi.com/f/83.pdf>.\n",
    "\n",
    "Vladimir Batalgej, Matjaž Zaveršnik, 2011. Fast algorithms for determining (generalized) core groups in social networks, Advances in Data Analysis and Classification, 5 (2), 129-145, Preprints: [arXiv:0310049v1](https://arxiv.org/abs/cs/0310049v1), [arXiv:0202039v1](https://arxiv.org/abs/cs/0202039v1). \n",
    "\n",
    "Nicolas A. Crossley, Andrea Mechelli, Petra E. Vértes, Toby T. Winton-Brown, Ameera X. Patel, Cedric E. Ginestet, Philip McGuire, Edward T. Bullmore, 2013. Cognition and the brain coactivation network, Proceedings of the National Academy of Sciences, 110 (28), 11583-11588, https://doi.org/10.1073/pnas.1220826110.\n",
    "\n",
    "François Fouss, Marco Saerens, Masashi Shimbo, 2016. Algorithms and Models for Network Data and Link Analysis, Cambridge University Press, κεφάλαιο 8.5.\n",
    "\n",
    "J. Ignacio Alvarez-Hamelin, Luca Dall'Asta, Alain Barrat, and Alessandro Vespignani, 2005. Large scale networks fingerprinting and visualization using the k-core decomposition. In Proceedings of the 18th International Conference on Neural Information Processing Systems (NIPS'05), Y. Weiss, B. Schölkopf, and J. C. Platt (Eds.). MIT Press, Cambridge, MA, USA, 41-50, <https://papers.nips.cc/paper/2789-large-scale-networks-fingerprinting-and-visualization-using-the-k-core-decomposition.pdf>.\n",
    "\n",
    "Δείτε τα διαγράμματα μεγάλων πραγματικών γράφων στο: <http://lanet-vi.fi.uba.ar/gallery.php>."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}