Community understanding in location-based social networks

In recent years we have witnessed a flourish of location-based social media. Across the world, individuals share their footprints, opinions, experiences, and contribute assorted forms of location-specific multimedia contents through location-enabled smart phones. Such examples include Foursquare, Gowalla, Facebook Place, etc, which are collectively termed as location-based social networks (LBSNs). The boom in LBSNs opens up a vast range of possibilities to study location-oriented human interactions and collective behaviors on an unprecedented scale. In LBSNs, interactions are typically heterogeneous, representing disparate relations among multiple entities, while at the same time, they may contain no or limited user relationship information. In this chapter, we aim to detect and understand social communities in LBSNs by representing the heterogeneous interactions with a multimodality nonuniform hypergraph. Here, the vertices of the hypergraph are users, venues, textual comments, or photos and the hyperedges characterize the k-partite heterogeneous interactions such as posting certain comments or uploading certain photos while visiting certain places. We then view each detected social community as a dense subgraph within the heterogeneous hypergraph, where the user community is constructed by the vertices and edges in the dense subgraph and the profile of the community is characterized by the vertices related with venues, comments, and photos and their inter-relations. We present an efficient algorithm to detect the overlapped dense subgraphs, where the profile of each social community is guaranteed to be available by constraining the minimal number of vertices in each modality.