Bridge Bounding: A Local Approach for Efficient Community Discovery in Complex Networks

Authors: Symeon Papadopoulos, Andre Skusa, Athena Vakali, Yiannis Kompatsiaris, and Nadine Wagner

Title: Bridge Bounding: A Local Approach for Efficient Community Discovery in Complex Networks

Appeared in: arXiv:0902.0871

Abstract: The increasing importance of Web 2.0 applications during the last years has created significant interest in tools for analyzing and describing collective user activities and emerging phenomena within the Web. Network structures have been widely employed in this context for modeling users, web resources and relations between them. However, the amount of data produced by modern web systems results in networks that are of unprecedented size and complexity, and are thus hard to interpret. To this end, community detection methods attempt to uncover natural groupings of web objects by analyzing the topology of their containing network. There are numerous techniques adopting a global perspective to the community detection problem, i.e. they operate on the complete network structure, thus being computationally expensive and hard to apply in a streaming manner. In order to add a local perspective to the study of the problem, we present Bridge Bounding, a local methodology for community detection, which explores the local network topology around a seed node in order to identify edges that act as boundaries to the local community. The proposed method can be integrated in an efficient global community detection scheme that compares favorably to the state of the art. As a case study, we apply the method to explore the topic structure of the LYCOS iQ collaborative question/answering application by detecting communities in the networks created from the collective tagging activity of users.

Περίληψη: Η αυξανόμενη σημασία των εφαρμογών Web 2.0 κατά τα τελευταία χρόνια έχει δημιουργήσει σημαντικό ενδιαφέρον για την ανάλυση και περιγραφή των συλλογικών δραστηριοτήτων των χρηστών και των φαινομένων που αναδύονται μέσα από αυτές. Οι δομές γράφων έχουν χρησιμοποιηθεί ευρέως σε αυτό το πλαίσιο για τη μοντελοποίηση χρηστών, πόρων και σχέσεων μεταξύ τους. Παρόλα αυτά, η ποσότητα των δεδομένων που παράγονται από τα σημερινά συστήματα παγκοσμίου ιστού οδηγεί σε γράφους εξαιρετικά μεγάλου μεγέθους και πολυπλοκότητας που είναι δύσκολο να ερμηνευτούν. Για αυτό το σκοπό, έχουν εμφανιστεί οι μέθοδοι ανίχνευσης κοινοτήτων που εντοπίζουν φυσικές ομαδοποιήσεις αντικειμένων με βάση την τοπολογία του γράφου που τα περιέχει ως κόμβους. Υπάρχουν πολλές τεχνικές που αντιμετωπίζουν το πρόβλημα της ανίχνευσης κοινοτήτων απαιτώντας την ανάλυση ολόκληρου του γράφου, με αποτέλεσμα να παρουσιάζουν ιδιαίτερη πολυπλοκότητα και να είναι δύσκολη η εφαρμογή τους σε πραγματικούς γράφους μεγάλου μεγέθους. Με σκοπό να δώσουμε μια τοπική προσέγγιση στο θέμα, παρουσιάζουμε τη μέθοδο Bridge Bounding, η οποία εξερευνά την τοπική γειτονιά γύρω από ένα κόμβο με σκοπό να εντοπίσει ακμές που λειτουργούν ως όρια στην τοπική κοινότητα κόμβων. Η προτεινόμενη μέθοδος μπορεί να ενσωματωθεί σε ένα αποδοτικό πλαίσιο αναγνώρισης κοινοτήτων σε ολόκληρο το γράφο, το οποίο παρουσιάζει συγκρίσιμη ή καλύτερη απόδοση σε σχέση με υπάρχουσες μεθόδους. Ως εφαρμογή, αναλύουμε τη θεματική δομή του συστήματος ερωτήσεων-απαντήσεων LYCOS iQ, εφαρμόζοντας τη μέθοδο ανίχνευσης κοινοτήτων στο δίκτυο από ετικέτες (tags) που χρησιμοποιούν οι χρήστες για να περιγράψουν τις ερωτήσεις τους.

Download paperViewPDF

View citations : ViewPDF