Random Walk Based Ranking in Signed Social Networks:
Model and Algorithms


How can we rank nodes in signed social networks? Relationships between nodes in a signed network are represented as positive (trust) or negative (distrust) edges. Many social networks have adopted signed networks to express trust between users. Consequently, ranking friends or enemies in signed networks has received much attention from the data mining community. The ranking problem, however, is challeng- ing because it is difficult to interpret negative edges. Traditional random walk based methods such as PageRank and Random Walk with Restart cannot provide effective rankings in signed networks since they assume only positive edges. Although several methods have been proposed by modifying traditional ranking models, they also fail to account for proper rankings due to the lack of ability to consider complex edge re- lations. In this paper, we propose Signed Random Walk with Restart (SRWR), a novel model for personalized ranking in signed networks. We introduce a signed ran- dom surfer so that she considers negative edges by changing her sign for walking. Our model provides proper rankings reflecting signed edges based on the signed random walk. We develop two methods for computing SRWR: SRWR-Iter and SRWR-Pre which are iterative and preprocessing methods, respectively. SRWR-Iter naturally fol- lows the definition of SRWR, and iteratively updates SRWR scores until convergence. SRWR-Pre enables fast ranking computation which is important for the performance of applications of SRWR. Through extensive experiments, we demonstrate that SRWR achieves the best accuracy (up to 87%) for sign prediction, and predicts trolls 4× more accurately than other ranking models. In terms of efficiency, SRWR-Pre preprocesses a signed network 4.5× faster, and requires 11× less memory space than other prepro- cessing methods; furthermore, SRWR-Pre computes SRWR scores up to 14× faster than other methods in the query phase


Our approaches are described in the following paper:


The binary codes used in the paper are available. [Download]


Epinions131,828841,372 Trust social network TRUSTLET Link
Slashdot79,120515,397 Trust social network DAI-LABOR Link
Wikipedia7,118103,675 Trust voting network SNAP Link