In this paper, we consider how to maximize users' influence in Online Social Networks (OSNs). More specifically, we study how social relationships impact influence in both directed OSNs (such as Twitter or Google+) and indirected ones (such as Facebook). Our problem introduces some new twists in comparison to the classic influence maximization problem originally defined in [1], where K influential individuals have to be selected. First, even if the user follows or proposes its friendship to the most influential individuals, there is no guarantee that they will follow back or accept the friendship request, i.e. they may not reciprocate. Second, following or proposing friendship is a quite cheap operation in OSNs so that the user can easily change dynamically its set of connections. A third difference in comparison to the classic formulation is that we quantify the influence not only by the number of individuals who actively replicate the information but also who can see the information. We show that, despite these three differences, greedy algorithms have the same theoretical guarantees than in the standard influence maximization problem, i.e. they reach a (1 − 1/e) approximation ratio. These greedy algorithms require the knowledge of the whole topology and are computationally expensive because of the inherent cost of evaluating the effect of a cascade. We show by simulations on the complete Twitter graph that much more practical heuristics are almost as effective. For example, exploiting simply the knowledge of degree and reciprocation probability of each node i (respectively di and ri ), the strategy that selects the nodes with the largest product ri di performs at most 2% worse than the above mentioned greedy algorithm. Moreover, the even simpler random selection strategy requires only to know the set of users and achieves similar performance when the information replication probability of the cascade process is as large as 1%.
