The proliferation of GPS-enabled mobile devices and the popularity of social networking have recently led to the rapid growth of Geo-Social Networks (GeoSNs). GeoSNs have created a fertile ground for novel location-based social interactions, advertising and market analysis. In this thesis we introduce: i) a general framework for Geo-Social query processing, ii) GeoSN queries, which extract useful information combining both the social relationships and the current location of the users, iii) Geo-Social Ranking (GSR) problem that ranks the users based on their social and spatial attributes, and iv) Real-Time Multi-criteria Graph Partitioning (RMGP) task for partitioning the social graph of a GeoSN.

Initially, we propose a general framework for Geo-Social query processing that offe...[ Read more ]

The proliferation of GPS-enabled mobile devices and the popularity of social networking have recently led to the rapid growth of Geo-Social Networks (GeoSNs). GeoSNs have created a fertile ground for novel location-based social interactions, advertising and market analysis. In this thesis we introduce: i) a general framework for Geo-Social query processing, ii) GeoSN queries, which extract useful information combining both the social relationships and the current location of the users, iii) Geo-Social Ranking (GSR) problem that ranks the users based on their social and spatial attributes, and iv) Real-Time Multi-criteria Graph Partitioning (RMGP) task for partitioning the social graph of a GeoSN.

Initially, we propose a general framework for Geo-Social query processing that offers flexible data management and algorithmic design. It segregates the social, geographical and query processing modules. Then, each GeoSN query is processed via a transparent combination of primitive queries issued to the social and geographical modules. We demonstrate the power of our framework by introducing several basic and advanced query types, and devising various solutions for each type.

GSR ranks the users of a GeoSN based on their distance to a given query location q, the number of their friends in the vicinity of q, and possibly the connectivity of those friends. We propose four GSR functions that assign scores in different ways: i) LC, which is a weighted linear combination of social (i.e., friendships) and spatial (i.e., distance to q) aspects, ii) RC, which is a ratio combination of the two aspects, iii) HGS, which considers the number of friends in coincident circles centered at q, and iv) GST, which takes into account triangles of friends in the vicinity of q. We investigate the behavior of the functions, qualitatively assess their results, and study the effects of their parameters. Moreover, for each ranking function, we design a query processing technique that utilizes its specific characteristics to efficiently retrieve the top-k users.

RMGP groups the users based on their social connectivity and their distance to a set of input geographical points that represent the locations of social events. We consider RMGP as an on-line graph partitioning task, which may be frequently performed for different query parameters (e.g., social events). In order to overcome the serious performance issues associated with the large social graphs found in practice, we develop solutions based on a game theoretic framework. Specifically, we consider each user as a player, whose goal is to find the class that optimizes his objective function. We propose algorithms based on best-response dynamics and analyze their properties.

Finally, we perform an exhaustive experimental evaluation for all proposed methods with real and synthetic datasets in centralized and decentralized settings. Our results confirm the viability of our approaches in typical large-scale GeoSNs.