Detecting overlapping communities in LBSNs by fuzzy subtractive clustering

Abstract

This paper introduces a novel method for detecting overlapping communities in Location-Based Social Networks (LBSNs) by combining fuzzy logic with subtractive clustering. The study addresses a key limitation in prior community detection approaches, where cluster centers are often chosen randomly, leading to inconsistent results across different runs. By focusing on user-venue edges rather than nodes, and incorporating rich information from user check-ins and venue attributes, the proposed method offers a more stable and intelligent clustering solution.

The core contribution is the Multi-Mode Multi-Attribute Fuzzy Subtractive Clustering (M²-FS-clustering) algorithm. This hybrid approach intelligently determines cluster centers using subtractive clustering, which evaluates the potential of each data point based on the density of its neighbors. To further refine the process, fuzzy rules are applied to dynamically adjust key parameters—accept-ratio and reject-ratio—ensuring an appropriate number of clusters is identified without manual intervention. This combination overcomes the randomness inherent in previous methods like M²-clustering, which relied on k-means with randomly initialized centers.

For evaluation, the authors used real-world Foursquare datasets from New York City and Tokyo, comprising user check-ins, venue categories, and temporal patterns. The proposed algorithm consistently outperformed the baseline M²-clustering across multiple runs, achieving significant reductions in the clustering cost function—by approximately 61% for New York and 57% for Tokyo on average. This improvement indicates higher intra-cluster similarity and more accurate community detection. Moreover, the algorithm demonstrated greater stability and efficiency, with linear time complexity compared to the quadratic complexity of the baseline.

Beyond technical performance, the detected communities were analyzed to reveal cultural and behavioral insights about the two cities. For instance, the distribution of users across categories like bars, food, recreation, and work highlighted differences in lifestyle and social habits between New York and Tokyo, showcasing the practical utility of the method for urban and social analysis.

In summary, this research successfully integrates fuzzy logic and subtractive clustering to create a robust, intelligent framework for overlapping community detection in LBSNs. It not only improves accuracy and consistency but also provides a scalable foundation for applications in recommendation systems, marketing, and urban planning. The work opens avenues for future research, including addressing data sparsity, designing new similarity metrics, and developing comprehensive evaluation metrics for community trustworthiness in dynamic social networks.