A New PageRank-Based Method for Influence Maximization in Signed Social Networks

Influence maximization is one of the most important topics in the social network analysis field. As all the social networks can be considered signed, explicitly or implicitly, assessing influence maximization in these networks is inevitable. Due to the NP-hard nature of this problem, the category of node-ranking-based solutions is of concern, where, the PageRank algorithm is outstanding. Original PageRank is merely defined based on the trust relationships and it is not applicable in signed social networks. Upon an agreement on the scheme of trust propagation, where trust propagates step by step in the social network, the two main schemes of distrust propagation are: a) distrust propagates step by step throughout the social network, and b) distrust propagates up to one step of the neighborhood. Despite the claims made by related researches that scheme (b) is the dominant behavior compared to (a); available PageRank algorithms are updated to incorporate scheme (a). In this study, a new PageRank-based method, which adopts scheme (b) to model the distrust-based influence propagation in signed social networks, is proposed. Accordingly, the importance of each node is computed considering that every node propagates the received influence from its trusted neighbors to other nodes, while it blocks the received influence from its untrusted neighbors. Assessments run on the three real datasets reveal the superiority of this proposed method over other existing PageRank algorithms in maximizing influence in signed social networks. The outperformance is between ۲۲% to ۴۶% considering all experimental settings in comparison with the most effective benchmark method.

Keywords:

influence , Centrality measure , Distrust , Signed networks , Node ranking