Socio-aware content allocation in complex networks via efficient monitoring of information dissemination

Abstract

This dissertation focuses on the analysis and design of content placement approaches in complex networked systems, i.e., cyber and cyber-physical networks, via efficient monitoring and inference of its constituents’ interplay. Despite the fact that the types of networks under examination exhibit diverse and distinctive features, the proposed methods share a common objective, namely the utilization of minimal amount of resources in order to track, infer or predict the explicit and implicit interactions among the entities of a network, which are governed by complex constraints. Inspired by methodologies employed to solve problems of coverage in physical networks, such as Wireless Sensor Networks (WSNs), this thesis extends, through Social Network Analysis (SNA), the notion of coverage in cyber and cyber-physical networks. Problems of information tracking and inference, along with influence maximization and content allocation are mapped to covering and packing problems of combinatorial optimization, which are known to be NP-hard. To address the former, heuristic approaches as well as algorithms with provable approximation guarantees are designed and analysed.The concept of coverage is introduced in WSNs as an important metric, which measures how well the network monitors a region of interest. In this thesis, the problem of computing a minimal amount of WSN resources to monitor an obstructed field of interest is formulated as a topology control problem. A framework based on computational geometry is introduced and two algorithms, a centralized and a distributed one, adjust the sensors’ sensing ranges in order to maximize the ratio of covered area to consumed energy, while ensuring a minimum coverage percentage.Monitoring in cyber networks, such as Online Social Networks (OSNs) is the process of tracking the users’ interactions, as captured by the information flow. In networks of billions of users, it is of great significance to reduce the resources required to infer the developing diffusion dynamics. The problem of finding a minimal set of monitoring nodes is mapped to finding a maximal independent set. A greedy approach is developed for its solution, followed by a graph coloring scheme that enables information tracking and a statistical learning technique, which infers the information diffusion graph.Approaches of monitoring or inference of information propagation can be integrated into Recommendation Systems (RSs). These RSs are known as Information Diffusion Aware Recommendation Systems (IDARS). This dissertation treats information diffusion aware recommendations as a content allocation problem with user coverage constraints. An IDARS is designed to find a subset of users to assign them various types of content, such that eventually every user achieves a coverage goal, i.e., all users in the network receive, via information dissemination, at least a minimum number of recommendations, while the total relevance of users to the recommended items is maximized. This is translated to a generalization of the Minimum Weighted Set Cover Problem and a greedy approximation algorithm is proposed for its solution.In Mobile Social Networks (MSNs) and platforms of streaming services the information on users’ features is frequently acquired by RSs. This information along with the users’ mobility patterns are exploited to derive local communities and encourage collaboration in content sharing. According to the users’ physical and social ties and by acknowledging the impact of recommendations in users’ content requests, the problem of content placement at edge caching networks and content sharing via Device-to-Device (D2D) communication is investigated under various objectives. At first, allocating items to a physical network, i.e., a caching network, is mapped to a problem of cache hit ratio maximization and the solution is approximated by a dynamic programming based approach. Next, content allocation is studied in a cyber-physical network formed by a caching network and a platform of streaming services. In particular, D2D-based opportunistic offloading is studied jointly with cache aware recommendations. Multiple criteria based on user mobility patterns are proposed to determine the user equipment participating in the offloading. Expressing the user Quality of Experience (QoE) as a function of user-content relevance and its expected delivery delay, the problem of caching and recommendations is treated as a user QoE maximization problem. It is addressed by a framework that solves sequentially the problems of minimum delay content delivery, content placement in caches and cache-aware recommendations, ensuring that each user will be recommended of highly preferred content with minimum delivery delay.

Η παρούσα διδακτορική διατριβή επικεντρώνεται στην ανάλυση και το σχεδιασμό τεχνικών ανάθεσης περιεχομένου σε σύνθετα δίκτυα, μέσω της αποδοτικής παρακολούθησης και του συμπερασμού της λειτουργίας των συστατικών τους μερών. Παρά το γεγονός ότι οι εξεταζόμενοι τύποι δικτύων παρουσιάζουν ετερογενή χαρακτηριστικά, οι προτεινόμενες μέθοδοι αναπτύσσονται σε ένα κοινό πλαίσιο που υπαγορεύει την ελαχιστοποίηση των χρησιμοποιούμενων πόρων για την παρακολούθηση, την πρόβλεψη ή το συμπερασμό των αλληλεπιδράσεων μεταξύ των οντοτήτων που τα συνιστούν. Με έναυσμα την ανάπτυξη μεθοδολογιών για την επίλυση προβλημάτων κάλυψης σε δίκτυα του φυσικού χώρου, όπως αυτά των Ασύρματων Αισθητήρων (ΑΔΑ), η έννοια της κάλυψης επανεξετάζεται μέσω της Ανάλυσης Κοινωνικών Δικτύων και επεκτείνεται σε άλλους τύπους δικτύων όπως τα δίκτυα του κυβερνοχώρου καθώς και τα κυβερνο - φυσικά δίκτυα (ΚΦΔ). Προβλήματα ιχνηλάτησης και συμπερασμού της διάδοσης πληροφορίας, μεγιστοποίησης επιρροής, ανάθεσης περιεχομένου στους χρήστες ηλεκτρονικών και κινητών μέσων κοινωνικής δικτύωσης καθώς και προσωρινής αποθήκευσης αυτού στα άκρα του δικτύου αντιστοιχίζονται σε γνωστά NP-δύσκολα (NP-hard) προβλήματα κάλυψης και συσκευασίας, για την επίλυση των οποίων, διατυπώνονται, αναλύονται και αξιολογούνται μέσω προσομοιώσεων, ευρετικοί και προσεγγιστικοί αλγόριθμοι.H έννοια της κάλυψης συναντάται στα Ασύρματα Δίκτυα Αισθητήρων ως σημαντική μετρική για την αξιολόγηση της απόδοσής τους στην παρακολούθηση/καταγραφή φυσικών ή περιβαλλοντικών συνθηκών σε μια περιοχή ενδιαφέροντος. Λειτουργικοί και ενεργειακοί περιορισμοί των αισθητήρων καθώς και γεωμετρικές ιδιαιτερότητες των περιοχών ενδιαφέροντος συνιστούν σημαντικές προκλήσεις στη βελτιστοποίηση της απόδοσης των ΑΔΑ. Λαμβάνοντας υπόψη τους παραπάνω περιορισμούς, διατυπώνεται ένα πλαίσιο για τη βέλτιστη κάλυψη μη κυρτών περιοχών από ΑΔΑ, τα οποία συγκροτούνται από αισθητήρες με μεταβαλλόμενες ακτίνες αίσθησης. Το προτεινόμενο πλαίσιο επιλύει ένα πρόβλημα ελέγχου τοπολογίας με στόχο τη ρύθμιση των ακτίνων αίσθησης των αισθητήρων για την ελαχιστοποίηση της ενεργειακής κατανάλωσης του δικτύου. Αξιοποιώντας μεθόδους της υπολογιστικής γεωμετρίας, δύο άπληστοι αλγόριθμοι, ένας συγκεντρωτικός και ένας κατανεμημένος, στοχεύουν στη μεγιστοποίηση του λόγου της καλυπτόμενης επιφάνειας προς το αντίστοιχο ενεργειακό κόστος, υπό τον περιορισμό της διατήρησης ενός ελάχιστου ποσοστού κάλυψης της περιοχής ενδιαφέροντος.Η ιχνηλάτηση σε δίκτυα του κυβερνοχώρου και συγκεκριμένα στα ηλεκτρονικά μέσα κοινωνικής δικτύωσης, αναφέρεται στη διαδικασία της παρακολούθησης-παρατήρησης των αλληλεπιδράσεων των χρηστών, όπως αυτές αποτυπώνονται μέσα από την ανταλλαγή πληροφορίας. Σε δίκτυα που απαρτίζονται από δισεκατομμύρια χρήστες με ποικίλα χαρακτηριστικά, κρίνεται απαραίτητη η ανάπτυξη μεθοδολογιών προσδιορισμού των πόρων για αποδοτική παρατήρηση των αλληλεπιδράσεων και συμπερασμού των μηχανισμών διάδοσης πληροφορίας. Στην παρούσα διατριβή, ο προσδιορισμός των πόρων αντιμετωπίζεται ως πρόβλημα εύρεσης ενός μεγιστικού ανεξάρτητου συνόλου κόμβων και ένας ευρετικός αλγόριθμος διατυπώνεται για την επίλυσή του. Η παρακολούθηση της πληροφοριακής διάδοσης πραγματοποιείται με ένα σχήμα χρωματισμού ακμών σε γράφους ενώ, για το συμπερασμό της δυναμικής της, αναπτύσσεται μια τεχνική στατιστικής μάθησης.Tεχνικές συμπερασμού ή πρόβλεψης της πληροφοριακής διάδοσης μπορούν να ενσωματωθούν στα συστήματα συστάσεων (ΣΣ) που λειτουργούν σε πλατφόρμες κοινωνικής δικτύωσης. Αυτά είναι γνωστά ως συστήματα συστάσεων με επίγνωση της διάχυσης πληροφορίας (ΣΣΕΔΠ). Η ανταλλαγή πληροφορίας μεταξύ των χρηστών αξιοποιείται από ένα ΣΣΕΔΠ ως επικουρικός μηχανισμός συστάσεων. Υπό αυτό το πρίσμα, η σύσταση περιεχομένου στους χρήστες μέσων κοινωνικής δικτύωσης διατυπώνεται ως πρόβλημα προσδιορισμού ενός συνόλου χρηστών για την ανάθεση περιεχομένου με τρόπο ώστε να μεγιστοποιείται, μέσω της πληροφοριακής διάχυσης, η συνολική σχετικότητα χρήστη-περιεχομένου στο δίκτυο, εξασφαλίζοντας παράλληλα για κάθε χρήστη, έναν ελάχιστο αριθμό προτάσεων. Αυτό αντιστοιχίζεται σε ένα γνωστό NP-hard πρόβλημα κάλυψης σε γράφους για το οποίο αναπτύσσεται και αναλύεται θεωρητικά ένας προσεγγιστικός αλγόριθμος. Με βάση τις προτιμήσεις των χρηστών σε περιεχόμενο, όπως αυτές εξάγονται και διαμορφώνονται από τα συστήματα συστάσεων, εξετάζεται η ανάθεση περιεχομένου σε δίκτυα στο φυσικό χώρο. Συγκεκριμένα, μελετάται η προσωρινή αποθήκευση περιεχομένου στα άκρα του δικτύου, η παράδοσή του στους χρήστες κινητών μέσων κοινωνικής δικτύωσης ή πλατφορμών περιεχομένου ροής και ο διαμοιρασμός του μεταξύ των χρηστών μέσω της απευθείας επικοινωνίας των "έξυπνων" συσκευών τους. Για τον καθορισμό των σχέσεων των χρηστών εξετάζονται πέρα από τις προτιμήσεις τους, η θέση τους στο φυσικό χώρο και οι τεχνικοί περιορισμοί των συσκευών τους. Βάσει αυτών, διατυπώνονται κριτήρια επιλογής συσκευών για προσωρινή αποθήκευση περιεχομένου. Στη συνέχεια εξετάζεται η τοποθέτηση περιεχομένου στα άκρα του δικτύου ως πρόβλημα μεγιστοποίησης του λόγου ευστοχίας της προσωρινής αποθήκευσης. Αυτό εκφράζεται ως ένα γνωστό πρόβλημα συσκευασίας και επιλύεται με μια προσεγγιστική μέθοδο δυναμικού προγραμματισμού. Τέλος, η ανάθεση περιεχομένου μελετάται σε κυβερνο-φυσικά δίκτυα ως δισδιάστατο πρόβλημα κάλυψης, με την πρώτη διάσταση να αφορά σε δίκτυα που σχηματίζονται στο φυσικό χώρο και τη δεύτερη σε δίκτυα του κυβερνοχώρου. Αναγνωρίζοντας την επίδραση των συστάσεων στη διαμόρφωση των προτιμήσεων ενός χρήστη, η τοποθέτηση περιεχομένου στα άκρα του δικτύου αντιμετωπίζεται από κοινού με την πραγματοποίηση συστάσεων στους χρήστες κινητών μέσων κοινωνικής δικτύωσης. Στη φυσική διάσταση, ερευνάται η περίπτωση της περιστασιακής εκφόρτωσης δεδομένων σε συσκευές χρηστών. Στην περίπτωση αυτή, οι χρήστες είναι διατεθειμένοι να περιμένουν ένα εύλογο χρονικό διάστημα έως ότου συναντήσουν κάποια συσκευή που έχει αποθηκευμένο προτεινόμενο περιεχόμενο. Σκοπός είναι η μεγιστοποίηση της ποιότητας της εμπειρίας τους, η οποία εκφράζεται ως συνάρτηση της σχετικότητάς τους στο προτεινόμενο περιεχόμενο και του αναμενόμενου χρόνου παράδοσής του. Το πλαίσιο που αναπτύσσεται επιλύει διαδοχικά τα προβλήματα του ελάχιστου χρόνου παράδοσης περιεχομένου, της ανάθεσης περιεχομένου στις προσωρινές μνήμες και των συστάσεων στους χρήστες. Μέσω αυτού εξασφαλίζεται πως κάθε χρήστης θα λάβει, στον ελάχιστο δυνατό χρόνο, ένα συγκεκριμένο αριθμό συστάσεων με περιεχόμενο της προτίμησής του.