Large graphs are prominent in several domains including data management, computer vision and language modeling. In this thesis, we target common scenarios related to Geo-Social networks. In particular, we focus on two fundamental problems: i) multi-criteria partitioning in the presence of constraints and ii) influence maximization for the case of several competitors.

Initially, we introduce a robust agent-based framework that tackles the Constrained Graph Partitioning (CGP) problem. CGP can be useful for recommendations of social events, or delivery of targeted advertising material to certain users. It assigns users of a social network to a set of classes with bounded capacities so that the similarity and the social costs are minimized. The similarity cost is proportional to the dis-si...[ Read more ]

Large graphs are prominent in several domains including data management, computer vision and language modeling. In this thesis, we target common scenarios related to Geo-Social networks. In particular, we focus on two fundamental problems: i) multi-criteria partitioning in the presence of constraints and ii) influence maximization for the case of several competitors.

Initially, we introduce a robust agent-based framework that tackles the Constrained Graph Partitioning (CGP) problem. CGP can be useful for recommendations of social events, or delivery of targeted advertising material to certain users. It assigns users of a social network to a set of classes with bounded capacities so that the similarity and the social costs are minimized. The similarity cost is proportional to the dis-similarity between a user and his class, whereas the social cost is measured in terms of friends that are assigned to different classes. We investigate two solutions for CGP. The first utilizes a game-theoretic framework, where each user constitutes a player that wishes to minimize his own social and similarity cost. The second employs local search, and aims at minimizing the global cost. We show that the two approaches can be unified under a common agent-based framework that allows for two types of deviations. In a unilateral deviation an agent switches to a new class, whereas in a bilateral deviation a pair of agents exchange their classes. We develop a number of optimization techniques to improve result quality and facilitate efficiency. Our experimental evaluation on real datasets demonstrates that the proposed methods always outperform the state-of-the art in terms of solution quality, while they are up to an order of magnitude faster.

For the second case, we focus on competitive influence maximization, where multiple competitors wish to influence the users of a social network; e.g., advertisers marketing similar products. In addition, we consider that users have weights according to their importance (e.g., users whose profile or demographic characteristics match the advertised product have high weights). Therefore, we introduce the novel Competitive Weighted Influence Maximization CWIM problem. We first present an Awareness-to-Influence (ATI) model that distinguishes the concepts of awareness and influence. ATI is motivated by the fact that usually users do not blindly follow the first influence; instead they collect information, reproduce it and finally decide. We then prove that ATI also exhibits monotonicity and submodularity, which facilitate tight quality guarantees. Next we develop algorithms based on a game theoretic framework, considering that each competitor is a player that chooses a strategy (i.e., seed set) in order to maximize his own benefit. Our experimental findings suggest that the proposed method outperform considerably some benchmarks and scale very well to large social networks.