2016 · 62 citations · 16 references
ComputingData ScienceData MiningRecommender SystemsWeb AnalyticsGraph-based LearningSocial Network AnalysisSocial Network MiningSocial NetworksAccuracyPersonalized RankingRanking ModelsSigned GraphsSigned Networks
How can we rank users 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 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 relations. In this paper, we propose Signed Random Walk with Restart, a novel 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 proper rankings reflecting signed edges based on the signed surfer. 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.
16
The PageRank Citation Ranking : Bringing Order to the Web
Lawrence M. Page, Sergey Brin, Rajeev Motwani et al. · 1999 · 12.7K citations
Authoritative sources in a hyperlinked environment
Jon Kleinberg · Journal of the ACM · 1999 · 9.1K citations · Full text
Structural balance: a generalization of Heider's theory.
Dorwin Cartwright, Frank Harary · Psychological Review · 1956 · 2.6K citations
Taher H. Haveliwala · 2002 · 1.5K citations