Communities are basic structures for understanding the organization of many real-world networks, such as social networks, knowledge graphs, and biological networks. Many approaches have been developed for identifying communities; these approaches essentially segment networks based on topological structure or the attribute similarity of vertices, while few approaches consider the spatial character of the networks. They can yield communities whose members are far away from each other. In some location-based services, like setting up events, it is important to find groups of people who are both socially and physically close to each other. Thus, the relations among vertices are defined not only by their connections but also by the spatial distance between them. In this thesis, we propo...[ Read more ]

Communities are basic structures for understanding the organization of many real-world networks, such as social networks, knowledge graphs, and biological networks. Many approaches have been developed for identifying communities; these approaches essentially segment networks based on topological structure or the attribute similarity of vertices, while few approaches consider the spatial character of the networks. They can yield communities whose members are far away from each other. In some location-based services, like setting up events, it is important to find groups of people who are both socially and physically close to each other. Thus, the relations among vertices are defined not only by their connections but also by the spatial distance between them. In this thesis, we propose a density-based model to detect communities that are both socially and spatially cohesive in geo-social networks. After formally defining the model and the geo-social distance measure it relies on, we present efficient algorithms for its implementation. Then, we propose efficient optimization techniques to reduce computation cost. We evaluate the effectiveness of our model via a case study on real data; In addition, we design three quantitative measures, called community score, radius and aveDist to evaluate the quality of the discovered communities. The efficiency of our algorithms is also evaluated experimentally.