Fast Random Walk with Restart over a Signed Graph

Jaeseok Myung, Junho Shim, Bomil Suh


RWR (Random Walk with Restart) is frequently used by many graph-based ranking algorithms, but it does not consider a signed graph where edges may have negative weight values. In this paper, we apply the Balance Theory by F. Heider to RWR over a signed graph and propose a novel RWR, Balanced Random Walk (BRW). We apply the proposed technique into the domain of recommendation system, and show by experiments its effectiveness to filter out the items that users may dislike. In order to provide the reasonable performance of BRW in the domain, we modify the existing Top-k algorithm, BCA, and propose a new algorithm, Bicolor-BCA. The proposed algorithm yet requires employing a threshold. In the experiment, we show how threshold values affect both precision and performance of the algorithm.

Full Text:



Avrachenkov, K., Litvak, N., Nemirovsky, D. A., Smirnova, E., and Sokol, M., “Monte Carlo Methods for Top-k Personalized PageRank Lists and Name Disambiguation,” INRIA Research Report No.7367, 2010.

Bahmani, B., Chakrabarti, K., and Xin, D., “Fast Personalized PageRank on MapReduce,” Proceedings of the 2011 ACM SIGMOD International Conference on Management of data, 2011.

Balmin, A. and Hristidis, V., “ObjectRank: authority-based keyword search in databases,” Proceedings of the Thirtieth international conference on Very large data bases, 2004.

Berkhin, P., “Bookmark-coloring approach to personalized pagerank computing,” Internet Mathematics, 2006.

Chakrabarti, S., Pathak, A., and Gupta, M., “Index Design and Query Processing for Graph Conductance Search,” The VLDB Journal, 2011.

Clements, M., Vries, A. P., and Reinders, M. J. T., “Exploiting Positive and Negative Graded Relevance Assessments for Content Recommendation,” Algorithms and Models for the Web-Graph, Lecture Notes in Computer Science, 2009.

Fogaras, D., Rácz, B., Csalogány, K., and Sarlós, T., “Towards Scaling Fully Personalized PageRank: Algorithms, Lower Bounds, and Experiments,” Internet Mathematics, 2005.

Fusiwara, Y., Nakatsuji, M., Yamamuro, T., Shiokawa, H., and Onizuka, M., “Efficient Personalized PageRank with Accuracy Assurance,” Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data minin, 2012.

Heider, F., The Psychology of Interpersonal Relations, John Wiley & Sons, 2013.

Jeh, G. and Widom, J., “SimRank: a measure of structural-context similarity,” Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, 2002.

Kang, S. and Shim, J., “Empirical Analysis on the Shortcut Benefit Function and its Factors for Triple Database,” Journal of Society for e-Business Studies, Vol 19, No 1, Society for e-Business Studies, 2014.


Page, L., Brin, S., Motwani, R., and Winograd, T., “The PageRank Citation Ranking: Bringing Order to the Web,” Technical Report, Stanford InfoLab,

Su, X. and Khoshgoftaar, T. M., “A Survey of Collaborative Filtering Techniques,” Journal Advances in Artificial Intelligence, 2009.

Tong, H., Faloutsos, C., and Pan, J., “Fast Random Walk with Restart and Its Applications,”, 2006.


  • There are currently no refbacks.