Hidden community identification in location-based social network via probabilistic venue sequences

Location-based Social Networks (LBSN) such as Foursquare have become ubiquitous due to the vast spread of smart mobile devices. The users of LBSN can check in at any locations, write tips, share comments, etc. LBSN has attracted much research attention due to the fact that the large volume of check-ins provides an unprecedented channel to connect users' online world to their offline physical activities. An essential analysis task is to identify hidden community from these check-ins, i.e., the community not explicitly defined based on the online links in LBSN but implicitly exist in the mobility patterns from these check-ins. The current state-of-the-art systems explore user check-ins to extract the visited venues; analyze the semantic information of the visited venues to model user behaviour patterns; cluster the users with similar patterns into the same community. They assume that users' check-ins specify the exact venues they visited. However, it has been observed that more than half of users' check-ins, e.g., in Twitter and Foursquare, are venueless (i.e., exact venues visited are unknown). Motivated by this observation, this work as the first attempt investigates the hidden community detection by exploring all check-ins (i.e., check-ins with/without exact venues). The idea is to identify a list of nearby venues around venueless check-ins. To obtain unfailing regularity even though it is uncertain on which venues have been eventually visited, we develop methods based on the probabilistic venue sequences. By tackling a number of unique technical challenges, the rich and comprehensive information disclosed from all check-ins allows us to uncover communities with high modularity which cannot be achieved by state-of-the-art systems. Empirical study conducted on both real-world and synthetic datasets show the efficiency and effectiveness of our methods.