A Fast Algorithm for Ranking Users by their Influence in Online Social Platforms

International audienceMeasuring the influence of users in social networks is key for numerous applications. A recently proposed influence metric, coined as ψ-score, allows to go beyond traditional centrality metrics, which only assess structural graph importance, by further incorporating the rich information provided by the posting and re-posting activity of users. The ψ-score is shown in fact to generalize PageRank for non-homogeneous node activity. Despite its significance, it scales poorly to large datasets; for a network of N users it requires to solve N linear systems of equations of size N. To address this problem, this work introduces a novel scalable algorithm for the fast approximation of ψ-score, named Power-ψ. The proposed algorithm is based on a novel equation indicating that it suffices to solve one system of equations of size N to compute the ψ-score. Then, our algorithm exploits the fact that such system can be recursively and distributedly approximated to any desired error. This permits the ψ-score, summarizing both structural and behavioral information for the nodes, to run as fast as PageRank. We validate the effectiveness of the proposed algorithm on several real-world datasets