Ανάλυση Κοινωνικών Δικτύων (Ε-ΨΜΑΔ)

Το μάθημα αποτελεί μια εισαγωγή στην ανάλυση σύνθετων και κοινωνικών δικτύων. Πρόκειται για μια εισαγωγή σε ένα διεπιστημονικό κλάδο που συνδυάζει τις επιστήμες της Πληροφορικής, των Μαθηματικών και της Φυσικής για τη μελέτη δικτύων από διαφορετικά πεδία εφαρμογών, π.χ. τηλεπικοινωνιών, βιολογίας, κοινωνικά και οικονομικά. Βασιζόμενο στις θεμελιώδεις γνώσεις της θεωρίας γραφημάτων, χρησιμοποιεί τα αναλυτικά και προγραμματιστικά διαθέσιμα εργαλεία για διεπιστημονικές αναλύσεις. Η ύλη στοχεύει στην εισαγωγή των σπουδαστών στις βασικές έννοιες και σε χρήσιμα αποτελέσματα της θεωρίας γραφημάτων και την αξιοποίησή τους στη μελέτη προβλημάτων διαφορετικών πεδίων. Ιδιαίτερη έμφαση δίνεται στη μελέτη εκείνων των χαρακτηριστικών δικτύων που αντιστοιχούν σε «κοινωνική συμπεριφορά», όπως αυτή ορίζεται κατά πεδίο εφαρμογής.

Ολοκληρώνοντας το μάθημα, στόχος είναι οι σπουδαστές να έχουν τις βασικές γνώσεις θεωρίας γραφημάτων, να μπορούν να τις αξιοποιήσουν στην ανάλυση δικτύων ανεξαρτήτου εφαρμογής και να μπορούν να χρησιμοποιήσουν απτά προγραμματιστικά εργαλεία αναλύοντας τοπολογίες διαφορετικών μεγεθών και εφαρμογών.

Συνοπτικά το περιεχόμενο του μαθήματος καλύπτει τις βασικές έννοιες και τους βασικούς ορισμούς που άπτονται των γράφων και των δικτύων. Μετά από μια σύντομη εισαγωγή στη θεωρία γραφημάτων (ώστε να δημιουργηθεί κοινό υπόβαθρο στους φοιτητές που δεν έχουν παρακολουθήσει σχετικό μάθημα), το μάθημα συνεχίζει με διάφορες τεχνικές ανάλυσης σύνθετων ή κοινωνικών δικτύων, αξιοποιώντας μεγέθη όπως ο συντελεστής συσσωμάτωσης και οι κεντρικότητες. Χρησιμοποιώντας την κατανομή του βαθμού του κόμβου, γίνεται διαχωρισμός των τοπολογιών δικτυών σε πέντε κατηγορίες. Στη συνέχεια χρησιμοποιούνται όλα τα παραπάνω στοιχεία σε σημαντικά προβλήματα της ανάλυσης σύνθετων δικτύων, όπως η εύρεση κοινοτήτων, η εξατομικευμένη αναζήτηση, η διάδοση κακόβουλου λογισμικού και πληροφοριών, και η αναζήτηση μοτίβων. Το μάθημα φιλοδοξεί οι φοιτητές και φοιτήτριες να εκτεθούν στη χρήση θεωρητικών εννοιών και προγραμματιστικών εργαλείων σε πραγματικά προβλήματα που διαφέρουν ως προς το πεδίο εφαρμογής, αποκτώντας διεπιστημονικές ικανότητες και εμπειρία.

Σε επίπεδο εβδομαδιαίας διδασκαλίας, το περιεχόμενο οργανώνεται ως εξής:

1η εβδομάδα:

Ανασκόπηση θεωρίας γραφημάτων: βασικοί ορισμοί (γράφος, υπογράφος), μονοπάτια, αποστάσεις, κύκλοι, πίνακας γειτνίασης, ιδιοτιμές/ιδιοδιανύσματα, ισομορφισμός.

2η εβδομάδα:

Ανασκόπηση θεωρίας γραφημάτων: δένδρα, αναπαράσταση γράφων, επίπεδα γραφήματα, χρωματισμός, κάλυψη.

3η εβδομάδα: Δένδρα

Μετρικές ανάλυσης κοινωνικών δικτύων: κατανομή βαθμού κόμβου, μέσο μήκος μονοπατιού, συντελεστής συσσωμάτωσης

4η εβδομάδα:

Μετρικές ανάλυσης κοινωνικών δικτύων: Κεντρικότητες

5η εβδομάδα:

Τοπολογίες σύνθετων δικτύων: πλέγματα, τυχαίοι γράφοι, τυχαίοι γεωμετρικοί γράφοι, δίκτυα μικρού-κόσμου, δίκτυα χωρίς κλίμακα.

6η εβδομάδα:

Τυχαίοι περίπατοι σε γράφους

7η εβδομάδα:

Εξατομικευμένη αναζήτηση στο web - Pagerank

8η εβδομάδα:

Ανίχνευση κοινοτήτων: spectral clustering, modularity maximization, Girvan-Newman

9η εβδομάδα:

Ανίχνευση κοινοτήτων: node2vec

10η εβδομάδα:

Πρόβλεψη ακμών σε δίκτυα

11η εβδομάδα:

Παροχή συστάσεων βασισμένη σε δεδομένα δικτύου

12η εβδομάδα:

Διάδοση ιών και κακόβουλου λογισμικού σε δίκτυα

13η εβδομάδα:

Διάδοση ειδήσεων και φημών σε δίκτυα

1. Θεωρία και Αλγόριθμοι Γράφων, Ιωάννης Μανωλόπουλος, Απόστολος Παπαδόπουλος, Κωνσταντίνος Τσίχλας.
2. ΑΛΓΟΡΙΘΜΙΚΗ ΘΕΩΡΙΑ ΓΡΑΦΗΜΑΤΩΝ, ΣΤΑΥΡΟΣ ΝΙΚΟΛΟΠΟΥΛΟΣ, ΓΕΩΡΓΙΑΔΗΣ ΛΟΥΚΑΣ, ΠΑΛΗΟΣ ΛΕΩΝΙΔΑΣ
3. Graph Theory [electronic resource], Reinhard Diestel

Δια ζώσης διδασκαλία + εξαμηνιαία εργασία

• Χρήση ηλεκτρονικών σημειώσεων
• Υποστήριξη διδασκαλίας μέσω της ηλεκτρονικής πλατφόρμας e-class

Γραπτή εξέταση + εξαμηνιαία εργασία