Exploring behavioral data in online social media with focus on user connectivity and mobility

With the booming development of online social media in recent years, massive and variety of behavioral data, such as social interactions data and user's E-travel sharing data, are generated by the users throughout the world everyday. Exploring and analyzing such data helps to understand users' preferences, unearth the contained tremendous knowledge, and identify new problems and business opportunities, thus is beneficial for social media users, service providers, etc. In this thesis, we are specifically interested in the user connectivity/interaction behaviors, e.g., friendship creation, and the mobility behaviors, e.g., check-in sequence at Point-of-Interest (POIs), that involve rich semantic information on nodes and edges of the social networks, and study three practical problems in different applications. We first analyze users' social connectivity behaviors from a new angle and study a problem of mining non-homophily social ties, aiming at discovering interesting but unexpected group-level social ties that do not follow the homophily phenomenon. We propose a novel ranking metric to identify such social ties and develop an efficient mining algorithm specifically for the new metric. In our second work, we explore users' check-in sequences or travel routes, and study a problem of personalized trip recommendation meets real-world constraints, by considering personalized rating on POIs and multiple constraints such as the time budget, the time window for the POI availability, the uncertainty of traveling time between POIs. We develop two efficient optimal solutions and two heuristic solutions for finding "good trips" with a significantly better runtime. Finally, in consideration of the sparsity of users' historical rating data and people's dynamically changed mind over time, we further study an on-demand route search problem with personalized diversity requirement on POIs, where users can specify their preferred features for the route and a personalized quantity (number of POIs) and variety (the coverage of the specified features) trade-offs. We propose to model users' personalized route diversity requirement by submodular functions that support the diminishing marginal utility property. We design generic and elegant optimal algorithm as well as heuristic algorithms. Comprehensive empirical evaluations on real life data sets demonstrate the effectiveness and efficiency of our methods.