THESIS
2015
xii, 117 pages : illustrations ; 30 cm
Abstract
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.
Post a Comment