Personalized Ranking in Signed Networks using Signed Random Walk with Restart

Overview

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 challenging because it is difficult to interpret negative edges. Traditional random walk based methods such as PageRank and Random Walk with Restart (RWR) cannot provide effective rankings in signed networks since they assume only non-negative edges.
In this work, we propose Signed Random Walk with Restart (SRWR), a novel ranking model for personalized ranking in signed networks. We introduce a signed random surfer so that she considers negative edges by changing her sign for walking. Our model provides appropriate rankings reflecting intricate edge relationships based on the signed random surfer.

Paper

SRWR is described in the following paper:

Code

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

Datasets

Name#Nodes#EdgesDescriptionSourceDownload
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

People