Community detection and resource assignment in interdependent systems via complex network analysis

Abstract

The aim of this thesis is to develop novel approaches for inferring relations and hidden similarities among the actors of complex systems that consist of various types of devices and users, as well as approaches for assigning content to them. In order to accomplish this, the developed methods take into account the interdependency and the various relationships of the multiple types of actors found in these systems. These approaches rely on tools and techniques from the fields of complex networks and social network analysis. Such systems are commonly observed in current interconnected environments, such as Smart Cities, and are expected to become even more prevalent in the future. These systems combine the operation of large infrastructure with the actions and requirements of people that have access to it. For the unobstructed operation of such topologies, network operators need to be able to monitor the generated data, detect possible redundancies, discover similar regions. Moreover, people using such environments need to have fast access to data and learn about relevant applications that keep their perceived quality of experience high. These entities (people, devices, data measurements) being the actors of such complex systems, are related in multiple ways, forming multi-layer complex networks, and highlighting the need to employ proper tools for their analysis. Aiming to provide a framework for achieving the aforementioned goals, this thesis focuses on the problems of community detection and resource allocation in interconnected and interdependent environments. The identification of important problems observed in these areas and the development of suitable solutions can aid in identifying groups of similar devices operating within the interconnected environment, groups of similar users, and also distinguish the most influential ones in terms of information diffusion. In particular, in order to deal with the problems of detecting clusters of generated data from the infrastructure and also communities of people in Online Social Networks (OSNs) existing in interdependent and complex systems, a novel community detection algorithm is developed. A new framework is presented for mapping the problem of data clustering to a community detection one. The proposed algorithm manages to discover meaningful clusters of data, outperforming some traditional data clustering approaches in terms of accuracy and also detect communities in OSNs resulting in high modularity scores. Inspired by the well-known Girvan-Newman (GN) algorithm, it manages to perform many operations faster, leveraging on network embedding in hyperbolic space and by introducing a new approximative network metric for estimating the edge betweenness centrality. Combined with the removal of more edges per iteration instead of a single one as in the case of GN and coupled with a graph database, it marks a more scalable approach than GN for large networks that are oftentimes observed in realistic complex systems. Τhe evaluation process on both synthetic and real data, showcases the benefits of adopting the proposed approach. The people that use the facilities of such interdependent systems, interact with each other by using OSNs. Focusing on these social relations and studying their interactions can reveal the manners in which information flows throughout the network. The monitoring of the information diffusion across the network arises as one of the most crucial aspects for estimating the possible outcome of seeding sets of users with units of information (recommendations). Considering that each user displays a relevance score towards each available item for recommendation, the problem of assigning recommendations to users is formed as a relevance maximization one. Contrary to other works, in this approach, the tolerance of a user to different levels of recommendations is considered as a major factor for the development of the recommender system for the first time. Complex constraints on the amount of duplicate and distinct recommendations are imposed per user. The maximization problem is proven to be computationally difficult, as it consists of an NP-hard problem with added constraints. In order to overcome this computational obstacle, the problem is divided into two sub-problems treated with greedy algorithms, and their combination produces high relevance scores, while respecting all the imposed constraints. Aspiring to provide users with fast access to data that increases the users' quality of experience, various schemes for caching at the network edge by utilizing limited memory space in the User Equipment (UE), are examined . Knowledge obtained from recommender systems about each user's preferences can be applied in order to predict future requests. In order to decide the optimal content to cache in each UE, the problem of content placement is formulated as a cache hit maximization one. Algorithms that employ either the full set or only a portion of the set of users as caches, while caching contents either proactively or reactively, are examined and compared in terms of the overall cache hit ratio obtained. The increased obtained cache-hit ratio proves the benefits of utilizing caching at the UEs instead of just caching at special devices. Also, from these comparisons, the need to take into consideration the probabilities of request for more than one's self in order to design more accurate caching schemes is highlighted. Finally, leveraging users' mobility and by taking into account the impact that recommendations have on users' requests and the ability of dedicated devices and selected users' UEs to cache and offload content, a caching and recommendation scheme is developed. Modeling the perceived user's Quality of Experience (QoE) as a function of the delay experienced by the user for retrieving a requested item and the relevance of the recommended items to her preferences, the problem is formulated as QoE maximization one. Knowing that this problem is NP-hard, a heuristic method is developed and compared to an approximative algorithm showcasing its benefits in terms of balancing the achieved QoE score for each user and the execution time needed, marking it as a computationally feasible approach able to yield results of high QoE. In the following, the proposed methods are presented, alongside with a discussion on the main contributions of this thesis. Then, each Chapter focuses on one of the aforementioned problems, presenting related work on the field and introducing the developed solutions together with some indicative evaluation that justifies the benefits of their adoption.

Η παρούσα διατριβή εστιάζει στην ανάπτυξη καινοτόμων τεχνικών με σκοπό την ανακάλυψη των σχέσεων και των κρυφών συσχετίσεων μεταξύ των οντοτήτων σύνθετων συστημάτων. Τα συστήματα αυτά αποτελούνται από διάφορους τύπους συσκευών αλλά και ανθρώπους. Ακόμα η διατριβή εστιάζει και στην ανάθεση πόρων στις οντότητες ενός σύνθετου συστήματος. Για να επιτευχθούν αυτοί οι στόχοι, οι προτεινόμενες μέθοδοι λαμβάνον υπόψιν την αλληλεξάρτηση και τις ποικίλες σχέσεις μεταξύ των πολλών διαφορετικών οντοτήτων. Αυτές οι μέθοδοι βασίζονται σε τεχνικές και εργαλεία από τους τομείς της θεωρίας γραφημάτων και της ανάλυσης κοινωνικών δικτύων. Συστήματα σαν αυτά που μελετώνται σε αυτήν τη διατριβή, παρατηρούνται σε σύγχρονα διασυνδεδεμένα περιβάλλοντα όπως αυτά που αποτελούν οι Έξυπνες Πόλεις και αναμένεται να γίνουν ακόμα περισσότερα στο μέλλον. Αυτά τα συστήματα συνδυάζουν τη λειτουργία μεγάλων υποδομών με τις ενέργειες και τις απαιτήσεις των ανθρώπων που αποκτούν πρόσβαση σε αυτές. Για την ανεμπόδιστη λειτουργία τέτοιων τοπολογιών, οι διαχειριστές του δικτύου πρέπει να είναι σε θέση να επιθεωρούν τα δεδομένα που παράγονται, να εντοπίζουν πιθανώς περιττό υλικό και να ανακαλύπτουν παρόμοιες περιοχές. Ακόμα, οι άνθρωποι που χρησιμοποιούν τέτοια περιβάλλοντα χρειάζεται να έχουν γρήγορη πρόσβαση σε δεδομένα αλλά και να έχουν τη δυνατότητα να μαθαίνουν σχετικά με εφαρμογές που θα κρατήσουν την ποιότητα της εμπειρίας που απολαμβάνουν σε υψηλά επίπεδα. Αυτές οι οντότητες (άνθρωποι, συσκευές, μετρήσεις) είναι τα στοιχεία που αποτελούν τα σύνθετα συστήματα και σχετίζονται μεταξύ τους με πολλούς τρόπους, δημιουργώντας πολυ-επίπεδα σύνθετα δίκτυα τα οποία χρειάζονται τα κατάλληλα εργαλεία για την ανάλυσή τους. Με σκοπό τη δημιουργία ενός πλαισίου μεθόδων που θα ικανοποιεί τους παραπάνω στόχους, αυτή η διατριβή εστιάζει στα προβλήματα της ανίχνευσης κοινοτήτων και της ανάθεσης πόρων σε αλληλοεξαρτώμενα και διασυνδεδεμένα περιβάλλοντα. Η ανακάλυψη σημαντικών προβλημάτων στις περιοχές αυτές και η ανάπτυξη κατάλληλων λύσεων μπορεί να βοηθήσει στην ανακάλυψη ομάδων από παραπλήσιες συσκευές οι οποίες λειτουργούν σε αυτά τα περιβάλλοντα, ομάδων από παρόμοιους χρήστες καθώς και να ξεχωρίσει τους πιο επιδραστικούς από αυτούς από τη σκοπιά της διάχυσης πληροφορίας. Για τον σκοπό της εξεύρεσης συστάδων από δεδομένα προερχόμενα από την υποδομή του περιβάλλοντος αλλά και της ανακάλυψης κοινοτήτων ατόμων σε Διαδικτυακά Κοινωνικά Δίκτυα (ΔΚΔ, Online Social Networks) τα οποία αποτελούν μέρος τέτοιων συστημάτων, παρουσιάζεται αλγόριθμος ανίχνευσης κοινοτήτων που έχει συνδεθεί με κατάλληλη βάση-γράφο για τη λειτουργία του. Ακόμα, παρουσιάζεται ένα νέο πλαίσιο με σκοπό τη μετατροπή ενός προβλήματος εξεύρεσης συστάδων σε πρόβλημα ανίχνευσης κοινοτήτων. Ο προτεινόμενος αλγόριθμος καταφέρνει να εντοπίζει συστάδες από δεδομένα που έχουν νόημα, υπερκεράζοντας σε ακρίβεια παραδοσιακές μεθόδους για τη συσταδοποίηση, καθώς και να ανιχνεύει κοινότητες σε ΔΚΔ που οδηγούν σε υψηλές τιμές αρθρωτότητας. Ο αλγόριθμος αυτός είναι εμπνευσμένος από τον γνωστό αλγόριθμο ανίχνευσης κοινοτήτων των Girvan-Newman (GN) και καταφέρνει να ολοκληρώνει γρηγορότερα αρκετές λειτουργίες βασιζόμενος στην ενσωμάτωση του δικτύου στον υπερβολικό γεωμετρικό χώρο και χρησιμοποιώντας μια προσεγγιστική μετρική για την εκτίμηση της κεντρικότητας ενδιαμεσικότητας ακμής. Σε συνδυασμό με την αφαίρεση ακμών κατά δέσμες, αντί για μοναδικής όπως στον GN και κάνοντας χρήση μιας βάσης δεδομένων-γράφο (graph database), αποτελεί μια πιο βιώσιμη προσέγγιση για μεγάλα δίκτυα από ότι ο GN. Μέσω της αξιολόγησης του αλγορίθμου σε πραγματικά και συνθετικά δεδομένα γίνονται ορατά τα πλεονεκτήματα της προτεινόμενης μεθόδου. Μελετώντας τις αλληλεπιδράσεις μεταξύ των χρηστών των διασυνδεδεμένων περιβαλλόντων που πραγματοποιούνται με τη διαμεσολάβηση των Κοινωνικών Δικτύων, το ζήτημα της μελέτης της διάδοσης της πληροφορίας εντός του κοινωνικού δικτύου ξεχωρίζει ως ένα από τα πλέον σημαντικά για την εκτίμηση της διάδοσης συστάσεων με αφετηρία ορισμένους κατάλληλα επιλεγμένους χρήστες. Θεωρώντας ότι κάθε χρήστης παρουσιάζει ένα ποσό συνάφειας με κάθε πιθανό αντικείμενο για σύσταση, το πρόβλημα της ανάθεσης συστάσεων μοντελοποιείται ως ένα πρόβλημα μεγιστοποίησης της συνάφειας αυτής. Σε αντίθεση με προηγούμενες δουλειές, για πρώτη φορά, ο σεβασμός της ανοχής του χρήστη σε συστάσεις αποτελεί κομβικό σημείο. Επιβάλλονται σύνθετοι περιορισμοί ανά χρήστη, τόσο ως προς το πλήθος των επαναλαμβανόμενων συστάσεων ανά αντικείμενο όσο και ως προς το πλήθος των διαφορετικών αντικειμένων που μπορούν να προταθούν. Το πρόβλημα αυτό αποδεικνύεται ότι είναι υπολογιστικά δύσκολο, καθώς αποτελείται από ένα πρόβλημα που ανήκει στην κλάση προβλημάτων NP-hard με επιπλέον περιορισμούς. Για να αντιμετωπιστεί αυτή η υπολογιστική δυσκολία, το πρόβλημα χωρίζεται σε δύο υπο-προβλήματα τα οποία επιλύονται με άπληστους αλγορίθμους με τον συνδυασμό τους να επιτυγχάνει υψηλό σκορ συνάφειας, ενώ παράλληλα σέβεται τους περιορισμούς. Με σκοπό την έγκαιρη λήψη δεδομένων από τους χρήστες, που οδηγεί στην αύξηση της ποιότητας της εμπειρίας (ΠτΕ, Quality of Experience), αναπτύχθηκαν διάφορα σχήματα για την προσωρινή αποθήκευση δεδομένων στα άκρα του δικτύου, τα οποία χρησιμοποιούν περιορισμένο χώρο μνήμης σε συσκευές χρηστών. Η γνώση που αποκομίζεται από τη λειτουργία συστημάτων συστάσεων για τις προτιμήσεις κάθε χρήστη είναι χρήσιμη για την πρόβλεψη της ζήτησης κάθε αντικειμένου. Για να αποφασιστεί η βέλτιστη κατανομή περιεχομένου σε κάθε συσκευή χρήστη επιλύεται ένα πρόβλημα μεγιστοποίησης της ευστοχίας του αποθηκευμένου περιεχομένου. Στο πλαίσιο της διατριβής εξετάζεται διαφορετικό πλήθος συσκευών με δυνατότητα αποθήκευσης αλλά και διαφορετικές πολιτικές ως προς τον χρόνο αποθήκευσης. Εξετάζονται τόσο πρακτικές προκαταβολικής αποθήκευσης (proactive caching) όσο και δυναμικής (reactive caching). Τα αυξημένα ποσοστά καταδεικνύουν τα πλεονεκτήματα της χρήσης χώρου μνήμης από τις συσκευές των χρηστών καθώς και την ανάγκη μια συσκευή να λαμβάνει υπ' όψιν τα πιθανά αιτήματα των γειτονικών της χρηστών. Επιπλέον, εξετάστηκε ο συνδυασμός των συστάσεων που παρέχονται από ένα σύστημα συστάσεων με το ζήτημα της προσωρινής αποθήκευσης σε ορισμένους χρήστες, λαμβάνοντας υπόψιν την κινητικότητα των χρηστών εντός του υπό εξέταση χώρου. Η ΠτΕ θεωρείται συνάρτηση του χρόνου αναμονής του χρήστη και της συνάφειας των συστάσεων που του γίνονται. Το πρόβλημα μεγιστοποίησης της ΠτΕ μοντελοποιείται ως ένα πρόβλημα της κλάσης πολυπλοκότητας NP-hard και προτείνεται ένας άπληστος αλγόριθμος για την επίλυσή του, ο οποίος συγκρίνεται με προσεγγιστικό αλγόριθμο. Κατά τη σύγκριση των μεθόδων αναλύονται τα πλεονεκτήματα του προτεινόμενου αλγορίθμου ως προς τον χρόνο εκτέλεσης αλλά και την ποιότητα της ευρισκόμενης λύσης ως προς τη συνολική παραγόμενη ΠτΕ. Στη συνέχεια, παρουσιάζονται συνοπτικά οι μεθοδολογίες, υπογραμμίζοντας τη συνεισφορά τους στη διατριβή. Έπειτα, κάθε Κεφάλαιο της διατριβής εστιάζει σε ένα από τα προαναφερθέντα προβλήματα, αναφέρονται συναφείς εργασίες στους αντίστοιχους τομείς και παρουσιάζονται λεπτομερώς οι προτεινόμενες λύσεις μαζί με ενδεικτικά αποτελέσματα που αποδεικνύουν τα πλεονεκτήματα που προκύπτουν από την υιοθέτησή τους.