Clustering for time-evolving social graphs

Abstract

This doctoral dissertation presents COTILES, a novel algorithm for simultaneous detection of communityand outliers in evolving social graphs that takes advantage of both structural and content-based information. Traditional community detection methods often rely solely on structural properties, potentially overlooking important aspects related to the content. COTILES addresses this limitation by integrating content constraints, ensuring the formation of communities that are structurally cohesive and thematically consistent. Key contributions of this work include the development of the COTILES algorithm, which extends the TILES algorithm to incorporate content-based constraints, and the introduction of label management mechanisms to maintain the relevance of community content over time. We also propose severalvariations of COTILES, including Strict COTILES, COTILES with Enhanced Content (EC), and a hybrid approach, each tailored to different application requirements. These variations allow flexibility in balancing topological and semantic features, making the algorithm adaptable to various contexts andneeds. Additionally, a significant part of the Thesis consists of extending COTILES to detect outliers by assigning an outlier score to each node, based on both structural and content criteria. This scorehelps identify nodes with deviant behavior and can be used for future behavior predictions. The outlierdetection mechanism is crucial to identify anomalies in social networks, which can have significant implications for security, fraud detection, and understanding user behavior.Extensive experiments using real-world datasets, such as StackExchange and MovieLens, demonstrate that COTILES outperforms traditional methods in forming more cohesive and content-focused communities. The results show that COTILES achieves better content stability within communitiesover time, reduces the percentage of highly overlapping communities, and provides a comprehensive measure of outlierness. Furthermore, experimental results validate that enforcing content constraints incurs minimal computational overhead; by maintaining a small, dynamic semantic footprint, COTILESpreserves the near-linear time complexity required for streaming environments. The empirical evaluation highlights the algorithm’s ability to adapt to the dynamic nature of social networks, ensuring that communities remain relevant and cohesive as the network evolves. The contributions of this dissertation have significant implications for various domains, including marketing, social network analysis, and security. In marketing, understanding community structures can lead to more effective targeting and engagement strategies. In social network analysis, the ability todetect and analyze evolving communities provides deeper insight into user interactions and influence patterns. In security, identifying outliers can help in early detection of fraudulent activities or security breaches. Future research directions include incorporating additional content types, such as multimedia data, to enhance thematic analysis of communities. Improving the scalability and efficiency of the algorithm is also a priority given the increasing size and complexity of social networks. Extending the methodologyto other types of networks, such as biological or transportation networks, could provide valuable insights and applications in those domains. Additionally, enhancing the algorithm to support real-time analysis and detection of communities and outliers would be particularly useful for applications requiringimmediate insights and actions. This work provides a robust framework for analyzing dynamic social networks, providing valuable insights into community evolution and outlier behavior. The COTILES algorithm and its variations represent a significant advancement in the field of social network analysis, addressing the limitationsof traditional methods by incorporating structural and content-based information. The findings of this dissertation pave the way for future research and practical applications, contributing to a deeper understanding of the complex dynamics within social networks.

Αυτή η Διδακτορική Διατριβή παρουσιάζει τον COTILES, έναν καινοτόμο αλγόριθμο για την ταυτόχρονη ανίχνευση κοινοτήτων (communities) και ακραίων τιμών (outliers) σε εξελισσόμενους κοινωνικούς γράφους, ο οποίος αξιοποιεί τόσο δομικές πληροφορίες όσο και πληροφορίες που βασίζονται στο περιεχόμενο. Οι παραδοσιακές μέθοδοι ανίχνευσης κοινοτήτων βασίζονται συχνά αποκλειστικά σε δομικές ιδιότητες, παραβλέποντας ενδεχομένως σημαντικές πτυχές που σχετίζονται με το περιεχόμενο. Ο COTILES αντιμετωπίζει αυτόν τον περιορισμό ενσωματώνοντας περιορισμούς περιεχομένου, διασφαλίζοντας τον σχηματισμό κοινοτήτων που είναι δομικά συνεκτικές και θεματικά συνεπείς. Οι κύριες συνεισφορές αυτής της εργασίας περιλαμβάνουν την ανάπτυξη του αλγορίθμου COTILES, ο οποίος επεκτείνει τον αλγόριθμο TILES ώστε να ενσωματώνει περιορισμούς βασισμένους στο περιεχόμενο, καθώς και την εισαγωγή μηχανισμών διαχείρισης ετικετών (label management) για τη διατήρηση της συνάφειας του περιεχομένου της κοινότητας με την πάροδο του χρόνου. Προτείνουμε επίσης παραλλαγές του COTILES, συμπεριλαμβανομένων των Strict COTILES, COTILES με Ενισχυμένο Περιεχόμενο (Enhanced Content - EC) και μιας υβριδικής προσέγγισης, καθεμία προσαρμοσμένη σε διαφορετικές απαιτήσεις εφαρμογών. Αυτές οι παραλλαγές παρέχουν ευελιξία στην εξισορρόπηση των τοπολογικών και σημασιολογικών χαρακτηριστικών, καθιστώντας τον αλγόριθμο προσαρμόσιμο σε διάφορα πλαίσια και ανάγκες. Επιπρόσθετα, ένα σημαντικό μέρος της Διατριβής αποτελείται από την επέκταση του COTILES για την ανίχνευση ακραίων τιμών, αποδίδοντας ένα σκορ απόκλισης (outlier score) σε κάθε κόμβο, βασισμένο σε κριτήρια τόσο δομής όσο και περιεχομένου. Αυτό το σκορ βοηθά στον εντοπισμό κόμβων με αποκλίνουσα συμπεριφορά και μπορεί να χρησιμοποιηθεί για μελλοντικές προβλέψεις συμπεριφοράς. Ο μηχανισμός ανίχνευσης ακραίων τιμών είναι κρίσιμος για τον εντοπισμό ανωμαλιών στα κοινωνικά δίκτυα, γεγονός που μπορεί να έχει σημαντικές επιπτώσεις στην ασφάλεια, την ανίχνευση απάτης και την κατανόηση της συμπεριφοράς των χρηστών. Εκτενή πειράματα με χρήση πραγματικών συνόλων δεδομένων, όπως το StackExchange και το MovieLens, καταδεικνύουν ότι ο COTILES ξεπερνά τις παραδοσιακές μεθόδους στον σχηματισμό πιο συνεκτικών και εστιασμένων στο περιεχόμενο κοινοτήτων. Τα αποτελέσματα δείχνουν ότι ο COTILES επιτυγχάνει καλύτερη σταθερότητα περιεχομένου εντός των κοινοτήτων με την πάροδο του χρόνου, μειώνει το ποσοστό των κοινοτήτων με μεγάλη επικάλυψη (highly overlapping communities) και παρέχει ένα ολοκληρωμένο μέτρο της απόκλισης (outlierness). Επιπλέον, τα πειραματικά αποτελέσματα επιβεβαιώνουν ότι η επιβολή περιορισμών περιεχομένου επιφέρει ελάχιστη υπολογιστική επιβάρυνση· διατηρώντας ένα μικρό, δυναμικό σημασιολογικό αποτύπωμα, ο COTILES διατηρεί τη σχεδόν γραμμική χρονική πολυπλοκότητα που απαιτείται για περιβάλλοντα ροής (streaming). Η πειραματική αξιολόγηση υπογραμμίζει την ικανότητα του αλγορίθμου να προσαρμόζεται στη δυναμική φύση των κοινωνικών δικτύων, διασφαλίζοντας ότι οι κοινότητες παραμένουν σχετικές και συνεκτικές καθώς το δίκτυο εξελίσσεται. Οι συνεισφορές αυτής της Διατριβής έχουν σημαντικές επιπτώσεις σε διάφορους τομείς, συμπεριλαμβανομένου του μάρκετινγκ, της ανάλυσης κοινωνικών δικτύων και της ασφάλειας. Στο μάρκετινγκ, η κατανόηση των δομών των κοινοτήτων μπορεί να οδηγήσει σε πιο αποτελεσματικές στρατηγικές στόχευσης και εμπλοκής. Στην ανάλυση κοινωνικών δικτύων, η ικανότητα ανίχνευσης και ανάλυσης εξελισσόμενων κοινοτήτων παρέχει βαθύτερη γνώση σχετικά με τις αλληλεπιδράσεις των χρηστών και τα πρότυπα επιρροής. Στην ασφάλεια, ο εντοπισμός ακραίων τιμών μπορεί να βοηθήσει στην έγκαιρη ανίχνευση δόλιων δραστηριοτήτων ή παραβιάσεων ασφαλείας. Οι μελλοντικές ερευνητικές κατευθύνσεις περιλαμβάνουν την ενσωμάτωση πρόσθετων τύπων περιεχομένου, όπως δεδομένων πολυμέσων, για την ενίσχυση της θεματικής ανάλυσης των κοινοτήτων. Η βελτίωση της κλιμάκωσης (scalability) και της αποδοτικότητας του αλγορίθμου αποτελεί επίσης προτεραιότητα δεδομένου του αυξανόμενου μεγέθους και της πολυπλοκότητας των κοινωνικών δικτύων. Η επέκταση της μεθοδολογίας σε άλλους τύπους δικτύων, όπως τα βιολογικά δίκτυα ή τα δίκτυα μεταφορών, θα μπορούσε να προσφέρει πολύτιμες γνώσεις και εφαρμογές σε αυτούς τους τομείς. Επιπλέον, η ενίσχυση του αλγορίθμου ώστε να υποστηρίζει ανάλυση και ανίχνευση κοινοτήτων και ακραίων τιμών σε πραγματικό χρόνο θα ήταν ιδιαίτερα χρήσιμη για εφαρμογές που απαιτούν άμεσες πληροφορίες και δράσεις. Αυτή η Διατριβή παρέχει ένα ισχυρό πλαίσιο για την ανάλυση δυναμικών κοινωνικών δικτύων, προσφέροντας πολύτιμες γνώσεις για την εξέλιξη των κοινοτήτων και τη συμπεριφορά των ακραίων τιμών. Ο αλγόριθμος COTILES και οι παραλλαγές του αντιπροσωπεύουν μια σημαντική πρόοδο στο πεδίο της ανάλυσης κοινωνικών δικτύων, αντιμετωπίζοντας τους περιορισμούς των παραδοσιακών μεθόδων ενσωματώνοντας δομικές πληροφορίες και πληροφορίες περιεχομένου. Τα ευρήματα αυτής της Διατριβής ανοίγουν τον δρόμο για μελλοντική έρευνα και πρακτικές εφαρμογές, συμβάλλοντας σε μια βαθύτερη κατανόηση της περίπλοκης δυναμικής εντός των κοινωνικών δικτύων.