Influence Maximization in Public Private Social Networks

Abstract

The public-private model is very relevant to social networks today, such as Facebook, Twitter, Google+, etc. In these social networks, some information is public, and some information is private to each user because of privacy settings. In this model, the network is different from each user's perspective, i.e., the union of the public graph and the user's private graph. Algorithmic analysis on such networks has to be adapted to each user's perspective to ensure privacy guarantees. In this work, we propose an Influence Maximization algorithm, to find a most influential seed set of a given size in public-private model of social networks. This algorithm is extended from a sketch based influence maximization algorithm. The proposed algorithm, while upholding privacy requirements, gives better influence estimate on networks having privacy settings.