|
|
|
|
|
|
|
In this talk, 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 undirected 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 guaran- tee 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 d_i and r_i), the strategy that selects the nodes with the largest product r_i d_i 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%. This research has been supported by the "Action Transverse" Network science. Auditors external to Inria should announce in advance their participation in order to inform the reception desk (simply write an email to giovanni.neglia@inria.fr)
|
|
|
|
|
|
|
|