CFP last date
20 June 2024
Reseach Article

Random Walk-based Recommendation with Restart using Social Information and Bayesian Transition Matrices

by Suchit Pongnumkul, Kazuyuki Motohashi
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 114 - Number 9
Year of Publication: 2015
Authors: Suchit Pongnumkul, Kazuyuki Motohashi
10.5120/20009-1960

Suchit Pongnumkul, Kazuyuki Motohashi . Random Walk-based Recommendation with Restart using Social Information and Bayesian Transition Matrices. International Journal of Computer Applications. 114, 9 ( March 2015), 32-38. DOI=10.5120/20009-1960

@article{ 10.5120/20009-1960,
author = { Suchit Pongnumkul, Kazuyuki Motohashi },
title = { Random Walk-based Recommendation with Restart using Social Information and Bayesian Transition Matrices },
journal = { International Journal of Computer Applications },
issue_date = { March 2015 },
volume = { 114 },
number = { 9 },
month = { March },
year = { 2015 },
issn = { 0975-8887 },
pages = { 32-38 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume114/number9/20009-1960/ },
doi = { 10.5120/20009-1960 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T22:52:17.016483+05:30
%A Suchit Pongnumkul
%A Kazuyuki Motohashi
%T Random Walk-based Recommendation with Restart using Social Information and Bayesian Transition Matrices
%J International Journal of Computer Applications
%@ 0975-8887
%V 114
%N 9
%P 32-38
%D 2015
%I Foundation of Computer Science (FCS), NY, USA
Abstract

A recommendation system is an information retrieval system that employs user, product, and other related information to infer relationships among data to offer product recommendations. The basic assumption is that friends or users with similar behavior will have similar interests. The large number of products available today makes it impossible for any user to explore all of them and increases the importance of recommendation systems. However, a recommendation system normally requires comprehensive data relating users and products. Insufficiently comprehensive data creates difficulties for creating good recommendations. Recommendation systems for incomplete data have become an active research area. One approach to solve this problem is to use random walk with restart (RWR), which significantly reduces the quantity of data required and has been shown to outperform collaborative filtering, the currently popular approach. This study explores how to increase the efficiency of the RWR approach by replace transition matrices that use information regarding relationships between user, usage, and tags with transition matrices that use Bayesian probabilities, and compare the efficiency of the two approaches using mean average precision. An experiment was conducted using music information data from last. fm. The result shows that the proposed approach provides better recommendations.

References
  1. C. Anderson, The Long Tail: Why the Future of Business Is Selling Less of More, ser. Hyperion Books. Hyperion, 2006.
  2. I. Konstas,V. Stathopoulos,andJ. M. Jose,"Onsocialnetworksandcollaborative recommendation," in Proceedings of the 32nd international ACM SIGIR conference on Research and development in information retrieval, ser. SIGIR '09. New York, NY, USA: ACM, pp. 195–202, 2009.
  3. Wikipedia. (2013, May) Information retrieval - wikipedia, the free encyclopedia. [Online; accessed 27-May-2013]. [Online]. Available:http://en. wikipedia. org/wiki/ Information_retrieval
  4. C. J. V. Rijsbergen, Information Retrieval, 2nd ed. Newton, MA, USA: Butterworth-Heinemann, 1979.
  5. C. D. Manning, P. Raghavan, and H. Sch¨utze, Introduction to Information Retrieval. New York, NY, USA: Cambridge University Press, 2008.
  6. A. Rajaraman and J. D. Ullman, Mining of Massive Datasets. New York, NY, USA: Cambridge University Press, 2011.
  7. F. Ricci, L. Rokach, B. Shapira, and P. B. Kantor, Recommender Systems Handbook, 1st ed. New York, NY, USA: Springer-Verlag New York, Inc. , 2010.
  8. D. Jannach, M. Zanker, A. Felfernig, and G. Friedrich, Recommender Systems: An Introduction, 1st ed. New York, NY, USA: Cambridge University Press, 2010.
  9. T. Hennig-Thurau, A. Marchand, and P. Marx, "Can automated group recommender systems help consumers make better choices?" Journal of Marketing, vol. 76, no. 5, pp. 89–109, 2012.
  10. R. Typke, F. Wiering, and R. C. Veltkamp, "A survey of music information retrieval systems," in IN ISMIR, pp. 153–160, 2005.
  11. A. Ansari, S. Essegaier, and R. Kohli, "Internet recommendation systems," Journal of Marketing Research, vol. 37, no. 3, pp. 363–375, 2000.
  12. F. M. Harper, X. Li, Y. Chen, and J. A. Konstan, "An economic model of user rating in an online recommender system," in Proceedings of the 10th international conference on User Modeling, ser. UM'05. Berlin, Heidelberg: Springer-Verlag, pp. 307–316, 2005.
  13. X. Su and T. M. Khoshgoftaar, "A survey of CF techniques," Advances in Artificial Intelligence, vol. 2009, pp. 4:2–4:2, 2009.
  14. Y. H. Cho, J. K. Kim, and S. H. Kim, "A personalized recommender system based on web usage mining and decision tree induction," Expert Systems with Applications, vol. 23, no. 3, pp. 329–342, 2002.
  15. J. K. Kim, H. K. Kim, H. Y. Oh, and Y. U. Ryu, "A group recommendation system for online communities," International Journal of Information Management, vol. 30, no. 3, pp. 212–219, 2010.
  16. R. Baraglia and F. Silvestri, "An online recommender system for large web sites," in Web Intelligence, 2004. WI 2004. Proceedings. IEEE/WIC/ACM International Conference on, 2004, pp. 199–205.
  17. E. -H. S. Han and G. Karypis, "Feature-based recommendation system," in Proceedings of the 14th ACM international conference on Information and knowledge management, ser. CIKM '05. New York, NY, USA: ACM, pp. 446–452, 2005.
  18. R. Burke, "Hybrid recommender systems: Survey and experiments," User Modeling and User-Adapted Interaction, vol. 12, no. 4, pp. 331–370, 2002.
  19. M. de Klepper, E. Sleebos, G. van de Bunt, and F. Agneessens, "Similarity in friendship networks: Selection or influence? the effect of constraining contexts and non-visible individual attributes," Social Networks, vol. 32, no. 1, pp. 82–90, 2010.
  20. D. Crandall, D. Cosley, D. Huttenlocher, J. Kleinberg, and S. Suri,"Feedback effects between similarity and social influence in online communities," in Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, ser. KDD '08. New York, NY, USA: ACM, pp. 160–168, 2008.
  21. C. C. Aggarwal, Social Network Data Analytics, 1st ed. Springer Publishing Company, Incorporated, 2011.
  22. I. Peters, Folksonomies. Indexing and Retrieval in Web 2. 0, 1st ed. Hawthorne, NJ, USA: Walter de Gruyter & Co. , 2009.
  23. M. riitta Koivunen, "Semantic authoring by tagging with annotea social bookmarks and topics," in In The 5th International Semantic Web Conference (ISWC2006) - 1st Semantic Authoring and Annotation Workshop (SAAW2006, 2006).
  24. A. Hotho, R. J¨aschke, C. Schmitz, and G. Stumme, "Information retrieval in folksonomies: Search and ranking," in The Semantic Web: Research and Applications, ser. Lecture Notes in Computer Science, Y. Sure and J. Domingue, Eds. Springer Berlin Heidelberg, vol. 4011, pp. 411–426, 2006.
  25. S. Hayman, "Folksonomies and tagging: New developments in social bookmarking," in Ark Group Conference: Developing and Improving Classification Schemes. Citeseer, 2007.
  26. J. Trant, "Studying social tagging and folksonomy: A review and framework," Journal of Digital Information, vol. 10, no. 1, 2009.
  27. R. Angelova, M. Lipczak, E. Milios, and P. Pralat, "Investigating the properties of a social bookmarking and tagging network," International Journal of Data Warehousing and Mining, vol. 6, no. 1, pp. 1–19, 2010.
  28. P. Bhattacharyya, A. Garg, and S. Wu, "Analysis of user keyword similarity in online social networks," Social Network Analysis and Mining, vol. 1, no. 3, pp. 143–158, 2011.
  29. M. Strohmaier, "Purpose tagging: capturing user intent to assist goal oriented social search," in Proceedings of the 2008 ACM workshop on Search in social media, ser. SSM '08. New York, NY, USA: ACM, pp. 35–42, 2008.
  30. R. Lambiotte and M. Ausloos, "Collaborative tagging as a tripartite network," in Computational Science ICCS 2006, ser. Lecture Notes in Computer Science, V. Alexandrov, G. Albada, P. Sloot, and J. Dongarra, Eds. Springer Berlin Heidelberg, vol. 3993, pp. 1114–1117, 2006.
  31. P. Mika, "Ontologies are us: A unified model of social networks and semantics," in The Semantic Web ISWC 2005, ser. Lecture Notes in Computer Science, Y. Gil, E. Motta, V. Benjamins, and M. Musen, Eds. Springer Berlin Heidelberg, vol. 3729, pp. 522–536, 2005.
  32. P. Heymann, G. Koutrika, and H. Garcia-Molina, "Can social bookmarking improve web search?" in Proceedings of the 2008 International Conference on Web Search and Data Mining, ser. WSDM '08. New York, NY, USA: ACM, pp. 195–206, 2008.
  33. L. B. Marinho, A. Hotho, R. Jschke, A. Nanopoulos, S. Rendle, L. Schmidt-Thieme, G. Stumme, and P. Symeonidis, Recommender Systems for Social Tagging Systems. Springer Publishing Company, Incorporated, 2012.
  34. F. Durao and P. Dolog, "A personalized tag-based recommendation in social web systems," Adaptation and Personalization for Web, vol. 2, p. 40, 2009.
  35. K. Bischoff, C. S. firan, W. Nejdl, and R. Paiu, "Can all tags be used for search?" in Proceedings of the 17th ACM conference on Information and knowledge management, ser. CIKM '08. New York, NY, USA: ACM, pp. 193–202, 2008.
  36. I. Guy, N. Zwerdling, I. Ronen, D. Carmel, and E. Uziel, "Social media recommendation based on people and tags," in Proceedings of the 33rd international ACM SIGIR conference on Research and development in information retrieval, ser. SIGIR '10. New York, NY, USA: ACM, pp. 194–201, 2010.
  37. Z. Huang, D. Zeng, and H. Chen, "A link analysis approach to recommendation under sparse data," in Proc. 2004 Americas Conf. Information Systems, 2004.
  38. C. M. Grinstead and J. L. Snell, Introduction to probability. American Mathematical Soc. , 1998.
  39. K. Pearson, "The problem of the random walk," Nature, vol. 72, no. 1865, pp. 294, 1905.
  40. L. Page, S. Brin, R. Motwani, and T. Winograd, "The pagerank citation ranking: Bringing order to the web. " Stanford InfoLab, Technical Report 1999-66, November 1999, previous number = SIDL-WP-1999-0120.
  41. D. Aldous and J. fill, "Reversible markov chains and random walks on graphs," 2002.
  42. L. Lov´asz, "Random walks on graphs: A survey," Combinatorics, Paul erdos is eighty, vol. 2, no. 1, pp. 1–46, 1993.
  43. L. Lov´asz, "Random walks on graphs: A survey," in Combinatorics, Paul Erd?os is Eighty, D. Mikl´os, V. T. S´os, and T. Sz?onyi, Eds. Budapest: J´anos Bolyai Mathematical Society, vol. 2, pp. 353–398, 1996.
  44. J. Xia, D. Caragea, and W. Hsu, "Bi-relational network analysis using a fast random walk with restart," in Data Mining, 2009. ICDM '09. Ninth IEEE International Conference on, 2009, pp. 1052–1057.
  45. H. Tong, C. Faloutsos, and J. -Y. Pan, "Random walk with restart: fast solutions and applications," Knowl. Inf. Syst. , vol. 14, no. 3, pp. 327–346, 2008.
  46. M. Clements, A. P. de Vries, and M. J. Reinders, "Optimizing single term queries using a personalized markov random walk over the social graph," in Workshop on Exploiting Semantic Annotations in Information Retrieval (ESAIR), 2008.
  47. N. Craswell and M. Szummer, "Random walks on the click graph," in Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, ser. SIGIR '07. New York, NY, USA: ACM, pp. 239–246, 2007.
  48. M. Brand, "A random walks perspective on maximizing satisfaction and profit," in SIAM International Conference on Data Mining, pp. 12–19, 2005.
  49. F. Fouss, A. Pirotte, J. -M. Renders, and M. Saerens, "Random-walk computation of similarities between nodes of a graph with application to collaborative recommendation," IEEE Transactions on Knowledge and Data Engineering, vol. 19, no. 3, pp. 355–369, 2007.
  50. M. Nakatsuji, Y. Fujiwara, A. Tanaka, T. Uchiyama, and T. Ishida, "Recommendations over domain specific user graphs," in Proceedings of the 2010 conference on ECAI 2010: 19th European Conference on Artificial Intelligence. Amsterdam, The Netherlands, The Netherlands: IOS Press, pp. 607–612, 2010.
  51. F. D´?ez, J. E. Chavarriaga, P. G. Campos, and A. Bellog´?n, "Movie recommendations based in explicit and implicit features extracted from the filmtipset dataset," in Proceedings of the Workshop on Context Aware Movie Recommendation, ser. CAMRa '10. New York, NY, USA: ACM, pp. 45–52, 2010.
  52. Z. Wang, Y. Tan, and M. Zhang, "Graph-based recommendation on social networks," in Web Conference (APWEB), 2010 12th International Asia-Pacific, pp. 116–122, 2010.
  53. Y. Shi, M. Larson, and A. Hanjalic, "Mining relational context-aware graph for rater identification," in Proceedings of the 2nd Challenge on Context-Aware Movie Recommendation, ser. CAMRa '11. New York, NY, USA: ACM, pp. 53–59, 2011.
  54. B. Liu and Z. Yuan, "Incorporating social networks and user opinions for collaborative recommendation: local trust network based method," in Proceedings of the Workshop on Context-Aware Movie Recommendation, ser. CAMRa '10. New York, NY, USA: ACM, pp. 53–56, 2010.
  55. Z. Wang, M. Zhang, Y. Tan, W. Wang, Y. Zhang, and L. Chen, "Recommendation algorithm based on graph-model considering user background information," in Creating, Connecting and Collaborating through Computing (C5), 2011 Ninth International Conference on, pp. 32–39, 2011.
  56. J. Tang, S. Wu, J. Sun, and H. Su, "Cross-domain collaboration recommendation," in Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining, ser. KDD '12. New York, NY, USA: ACM, pp. 1285–1293, 2012.
  57. C. Lucchese, R. Perego, F. Silvestri, H. Vahabi, and R. Venturini, "How random walks can help tourism," in Advances in Information Retrieval, ser. Lecture Notes in Computer Science, R. Baeza-Yates, A. Vries, H. Zaragoza, B. Cambazoglu, V. Murdock, R. Lempel, and F. Silvestri, Eds. Springer Berlin Heidelberg, vol. 7224, pp. 195–206, 2012.
  58. Y. Fujiwara, M. Nakatsuji, M. Onizuka, and M. Kitsuregawa, "Fast and exact top-k search for random walk with restart," Proc. VLDB Endow. , vol. 5, no. 5, pp. 442–453, 2012.
  59. M. Bayes and M. Price, "An essay towards solving a problem in the doctrine of chances. by the late rev. mr. bayes, f. r. s. communicated by mr. price, in a letter to john canton, a. m. f. r. s. " Philosophical Transactions, vol. 53, pp. 370–418, 1763.
Index Terms

Computer Science
Information Sciences

Keywords

Recommendation system random walk with restart mean average precision