Scalable Algorithms to Measure User Influence in Social Networks

Measuring user influence in social networks is crucial for a variety of applications. While traditional centrality metrics evaluate structural graph importance, a more recent metric known as the \(\psi \) -score takes into account users’ posting and re-posting activities to provide richer information. The \(\psi \) -score is a powerful tool that generalizes PageRank for non-homogeneous node activity. However, for large datasets with N users, it becomes computationally expensive, requiring solving N linear systems of N equations. To tackle this issue, we propose three new scalable algorithms that can quickly approximate the \(\psi \) -score. The Power- \(\psi \) and Push- \(\psi \) algorithms are based on a novel equation that shows it is sufficient to solve one system of equations of size N to calculate the \(\psi \) -score. These algorithms take advantage of the fact that the solution of such a system can be recursively and distributedly approximated. Consequently, the \(\psi \) -score, which summarizes the nodes’ structural and behavioral information, can be computed as quickly as PageRank. The third proposed algorithm is Push-NF. Despite aiming to solve all N systems to extract additional information on the information dynamics, it still manages to converge to the accurate user ranking faster than the current state-of-the-art alternative. To validate the effectiveness of our proposed algorithms, we release them as an open-source Python library and test them on various real-world datasets.