Τα τελευταία χρόνια έχει παρατηρηθεί ιδιαίτερο ερευνητικό ενδιαφέρον στη μελέτη δικτύων (γραφημάτων) που προκύπτουν από διάφορες κοινωνικές, τεχνολογικές και επιστημονικές δραστηριότητες. Χαρακτηριστικά παραδείγματα αποτελούν το γράφημα του Διαδικτύου, το γράφημα του Παγκοσμίου Ιστού, κοινωνικά δίκτυα αναπαράστασης της αλληλεπίδρασης των ατόμων στην κοινωνία ή των χρηστών σε υπηρεσίες κοινωνικής δικτύωσης, δίκτυα μοντελοποίησης της συνεργασίας μεταξύ οντοτήτων, βιολογικά δίκτυα, κ.α.. Βασικό χαρακτηριστικό των γραφημάτων αυτών αποτελεί το μεγάλο μέγεθός τους, κάτι που πολλές φορές δυσχαιρένει την ανάλυση και μελέτη τους. Επιπλέον, τα γραφήματα αυτά στις περισσότερες περιπτώσεις δεν είναι στατικά, αλλά εξελίσσονται στο χρόνο με την προσθήκη-διαγραφή κόμβων και ακμών. Έτσι, ορισμένα από τα ερωτήματα που προκύπτουν και έχουν απασχολήσει την ερευνητική κοινότητα είναι πώς μπορούμε να αναλύσουμε τέτοιου είδους γραφήματα και να εξάγουμε ενδιαφέρουσα πληροφορία, ποια είναι η δομή των γραφημάτων αυτών, καθώς και ο τρόπος με τον οποίο δομούνται και εξελίσσονται στο χρόνο.
Ένα σημαντικό θέμα που σχετίζεται με τη δομή των γραφημάτων αυτών, αποτελεί η έννοια της ανθεκτικότητας. Γενικά, ένα γράφημα χαρακτηρίζεται ως ανθεκτικό, αν έχει τη δυνατότητα να διατηρήσει τη δομή του και τις ιδιότητες συνεκτικότητας που κατέχει, ύστερα από την απώλεια ενός μέρους των κόμβων και ακμών του. Η ιδιότητα της ανθεκτικότητας σε πραγματικά γραφήματα είναι άμεσα συνυφασμένη με την έννοια της δομής κοινοτήτων (community structure), δηλαδή της οργάνωσης των κόμβων σε ομάδες με υψηλό πλήθος συνδέσεων μεταξύ κόμβων της ίδιας ομάδας και μικρό πλήθος μεταξύ κόμβων που ανήκουν σε διαφορετικές ομάδες.
Πώς μπορούμε να κάνουμε μια γρήγορη εκτίμηση των ιδιοτήτων ανθεκτικότητας ενός γραφήματος, χωρίς να επιτελέσουμε μια διαδικασία διαγραφής κόμβων και ακμών όπου σε κάθε βήμα υπολογίζεται η συνεκτικότητα; Με άλλα λόγια, υπάρχει κάποιος δείκτης (μετρική) που μπορεί να μας ενημερώσει τόσο για την ανθεκτικότητα όσο και για τις ιδιότητες δομής κοινοτήτων ενός γραφήματος, ο οποίος θα μπορεί να υπολογιστεί αρκετά γρήγορα ακόμα και για γραφήματα με εκατομμύρια κόμβους και ακμές; Επιπλέον, εάν το γράφημα εξελίσσεται στο χρόνο, τι μπορούμε να πούμε για την ανθεκτικότητά του και κατ' επέκταση, για τις ιδιότητες δομής κοινοτήτων που διαθέτει; Υπάρχει κάποια κοινή ιδιότητα (πρότυπο) στα κοινωνικά γραφήματα που σχετίζεται με τη χρονική εξέλιξη των ιδιοτήτων αυτών;
Στα πλαίσια της παρούσας εργασίας προσπαθούμε να απαντήσουμε τα παραπάνω ερωτήματα, μελετώντας τις ιδιότητες επέκτασης κοινωνικών γραφημάτων μεγάλης κλίμακας. Αρχικά παρουσιάζουμε μια μετρική που έχει τη δυνατότητα να χαρακτηρίσει τόσο την ανθεκτικότητα όσο και τις ιδιότητες δομής κοινοτήτων ενός γραφήματος και περιγράφουμε πώς μπορούμε να την υπολογίσουμε αποδοτικά και αποτελεσματικά εκμεταλλευόμενοι ορισμένες ιδιαίτερες φασματικές ιδιότητες των πραγματικών γραφημάτων. Στη συνέχεια, εφαρμόζουμε τη μετρική αυτή σε ένα μεγάλο πλήθος στατικών κοινωνικών γραφημάτων μεγάλης κλίμακας και παρατηρούμε ορισμένες ενδιαφέρουσες ιδιότητες που σχετίζονται με την ανθεκτικότητά του και κατ΄ επέκταση με τις ιδιότητες δομής κοινοτήτων που εμφανίζουν. Μελετάμε πώς οι ιδιότητες αυτές αλλάζουν στον χρόνο, καθώς το γράφημα εξελίσσεται και παρατηρούμε ορισμένα ενδιαφέροντα πρότυπα. Τέλος, παρουσιάζουμε πώς μπορούμε να εντοπίσουμε ανωμαλίες σε γραφήματα που εξελίσσονται στο χρόνο, μελετώντας τις ιδιότητες που σχετίζονται με την ανθεκτικότητά του. / Over the last few years there has been a lot of interest in the study of complex network
structures (or graphs) arising in many diverse settings. Characteristic examples
are networks from the domain of sociology (e.g., social networks), technological and
information networks (e.g., the Internet, the Web, email exchange networks, social
interaction networks over social media applications), biological networks (e.g., protein interactions), collaboration and citation networks (e.g., coauthorship networks), and many more. A basic characteristic of these networks is their large scale (size), which in many cases hinder their study. Moreover, the graphs usually are not static, but they evolve over time with the addition/deletion of nodes and edges. A large amount of research work has been devoted on understanding the structure, the organization and the evolution of these networks, with many interesting results.
One important aspect which is related to the structure of such graphs, is the notion of robustness. Generally, a graph is characterized as robust, if it is capable to retain its structure and its connectivity properties after the loss of a portion of its nodes and edges. The property of robustness in real-world graphs is closely related to the notion of community structure, where the network is organized based on a modular architecture, presenting well-defined clusters with large inter-cluster and small intra-cluster edge density. We expect that the robustness of a network with good community structure will be poor, since it can be easily become disconnected with the removal of
the edges which connect the different clusters.
How can we do this estimation quickly without removing edges and nodes and
measuring the connectivity? In other words, is there a robustness and community
structure index (metric) which can be computed fast enough, even for graphs with
millions of nodes and edges? Moreover, if the network evolves over time, what can we
say about its robustness, and as an extension, about its community structure? Is there a common pattern in social graphs that govern the time evolution of these properties?
In this thesis, we tackle the problem of estimating the robustness properties of a
graph quickly, studying the expansion properties of several real-world
time-evolving social graphs. First, we present a metric which can be used to characterize both the robustness and the community structure properties of a graph. We present how to efficiently and effectively compute this measure, exploiting the special spectral properties
of real-world graphs. Then, we apply this method to several large static social graphs,
and we observe some interesting properties that are related to their robustness. We
study how these properties change over time, while the graph evolves, and we observe
interesting patterns. Finally, we show how to spot outliers and detect anomalies in
graphs that evolve over time, examining the change of the robustness properties of a
graph.
| Identifer | oai:union.ndltd.org:upatras.gr/oai:nemertes:10889/4725 |
| Date | 07 October 2011 |
| Creators | Μαλλιαρός, Φραγκίσκος |
| Contributors | Μεγαλοοικονόμου, Βασίλειος, Malliaros, Fragkiskos, Γαλλόπουλος, Ευστράτιος, Ζαρολιάγκης, Χρήστος, Μεγαλοοικονόμου, Βασίλειος |
| Source Sets | University of Patras |
| Language | gr |
| Detected Language | Greek |
| Type | Thesis |
| Rights | 0 |
| Relation | Η ΒΚΠ διαθέτει αντίτυπο της διατριβής σε έντυπη μορφή στο βιβλιοστάσιο διδακτορικών διατριβών που βρίσκεται στο ισόγειο του κτιρίου της. |
Page generated in 0.0156 seconds