Influence maximization (IM) is a fundamental task in social network analysis. Typically, IM aims at selecting a set of seeds for the network that influences the maximum number of individuals. Motivated by practical applications, in this paper we focus on an IM variant, where the owner of multiple competing products wishes to select seeds for each product so that the collective influence across all products is maximized. To capture the competing diffusion processes, we introduce an Awareness-to-Influence (AtI) model. In the first phase, awareness about each product propagates in the social graph unhindered by other competing products. In the second phase, a user adopts the most preferred product among those encountered in the awareness phase. To compute the seed sets, we propose GCW, a game-theoretic framework that views the various products as agents, which compete for influence in the social graph and selfishly select their individual strategy. We show that AtI exhibits monotonicity and submodularity; importantly, GCW is a monotone utility game. This allows us to develop an efficient best-response algorithm, with quality guarantees on the collective utility. Our experimental results suggest that our methods are effective, efficient, and scale well to large social networks.

Social networks offer services such as recommendations of social events, or delivery of targeted advertising material to certain users. In my thesis, I focus on a specific type of services modeled as constrained graph partitioning (CGP). CGP assigns nodes of a graph 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 node and its class, whereas the social cost is measured in terms of neighbors that are assigned to different classes. I investigate two solutions for CGP: the first utilizes a game-theoretic framework, while the second employs local search. I show that the two approaches can be unified under a common framework, and develop a number of optimization techniques to improve result quality and facilitate efficiency. Experiments with real datasets demonstrate that the proposed methods outperform the state-of-the art in terms of solution quality, while they are significantly faster.

In Geo-Social Event Organization (GSEO), each user of a geo-social network is assigned to an event, so that the distance and social costs are minimized. Specifically, the distance cost is the total distance between every user and his assigned event. The social cost is measured in terms of the pairs of friends in different events. Intuitively, users should be assigned to events in their vicinity, which are also recommended to their friends. Moreover, the events may have constraints on the number of users that they can accommodate. GSEO is an NP-Hard problem. In this paper, we utilize a game-theoretic framework, where each user constitutes a player that wishes to minimize his own social and distance cost. We demonstrate that the Nash Equilibrium concept is inadequate due to the capacity constraints, and propose the notion of pairwise stability, which yields better solutions. In addition, we develop a number of optimization techniques to achieve 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 one order of magnitude faster.