Random walk-based ranking in signed social networks: model and algorithms

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