Design of a recommendation system based on the transition graph

Authors

DOI:

https://doi.org/10.15587/1729-4061.2021.233501

Keywords:

recommendation system, web graph, transition graph, Markov chain, random walk

Abstract

A recommendation system has been built for a web resource’s users that applies statistics about user activities to provide recommendations. The purpose of the system operation is to provide recommendations in the form of an orderly sequence of HTML pages of the resource suggested for the user. The ranking procedure uses statistical information about user transitions between web resource pages. The web resource model is represented in the form of a web graph; the user behavior model is shown as a graph of transitions between resource pages. The web graph is represented by an adjacency matrix; for the transition graph, a weighted matrix of probabilities of transitions between the vertices of the graph has been constructed. It was taken into consideration that user transitions between pages of a web resource may involve entering a URL in the address bar of a browser or by clicking on a link in the current page. The user’s transition between vertices in a finite graph according to probabilities determined by the weight of the graph’s edges is represented by a homogeneous Markov chain and is considered a process of random walk on the graph with the possibility of moving to a random vertex. Random Walk with Restarts was used to rank web resource pages for a particular user. Numerical analysis has been performed for an actual online store website. The initial data on user sessions are divided into training and test samples. According to the training sample, a weighted matrix of the probability of user transitions between web resource pages was constructed. To assess the quality of the built recommendation system, the accuracy, completeness, and Half-life Utility metrics were used. On the elements of the test sample, the accuracy value of 65‒68 % was obtained, the optimal number of elements in the recommendation list was determined. The influence of model parameters on the quality of recommendation systems was investigated.

Author Biographies

Natalia Guk, Oles Honchar Dnipro National University

Doctor of Physical and Mathematical Sciences, Professor, Head of Department

Department of Computer Technologies

Olga Verba, Oles Honchar Dnipro National University

Senior Lecturer

Department of Computer Technologies

Vladyslav Yevlakov, Oles Honchar Dnipro National University

Postgraduate Student

Department of Computer Technologies

References

  1. Jansen, B. J., Booth, D. L., Spink, A. (2008). Determining the informational, navigational, and transactional intent of Web queries. Information Processing & Management, 44 (3), 1251–1266. doi: https://doi.org/10.1016/j.ipm.2007.07.015
  2. Adomavicius, G., Tuzhilin, A. (2005). Toward the next generation of recommender systems: a survey of the state-of-the-art and possible extensions. IEEE Transactions on Knowledge and Data Engineering, 17 (6), 734–749. doi: https://doi.org/10.1109/tkde.2005.99
  3. Meleshko, Е. V., Semenov, S. G., Khokh, V. D. (2018). Research of methods of building advisory systems on the internet. Control, Navigation and Communication Systems, 1 (47), 131–136. doi: https://doi.org/10.26906/sunz.2018.1.131
  4. Aizawa, A. (2003). An information-theoretic perspective of tf–idf measures. Information Processing & Management, 39 (1), 45–65. doi: https://doi.org/10.1016/s0306-4573(02)00021-3
  5. Parfenenko, Y., Kovtun, A., Verbytska, A. (2019). Recommended information system for video search. Transactions of Kremenchuk Mykhailo Ostrohradskyi National University, 5 (118), 97–102. doi: https://doi.org/10.30929/1995-0519.2019.5.97-102
  6. Candillier, L., Jack, K., Fessant, F., Meyer, F. (2009). State-of-the-Art Recommender Systems. Collaborative and Social Information Retrieval and Access, 1–22. doi: https://doi.org/10.4018/978-1-60566-306-7.ch001
  7. Uschold, M., Gruninger, M. (2004). Ontologies and semantics for seamless connectivity. ACM SIGMOD Record, 33(4), 58–64. doi: https://doi.org/10.1145/1041410.1041420
  8. Covington, P., Adams, J., Sargin, E. (2016). Deep Neural Networks for YouTube Recommendations. Proceedings of the 10th ACM Conference on Recommender Systems. doi: https://doi.org/10.1145/2959100.2959190
  9. Stotts, P. D., Furuta, R. (1988). Adding browsing semantics to the hypertext model. Proceedings of the ACM Conference on Document Processing Systems - DOCPROCS ’88. doi: https://doi.org/10.1145/62506.62516
  10. Ol'shevskiy, A. I., Kondrat'eva, A. A. (2008). Opisanie sposobov predstavleniya web-saytov v vide freymovoy modeli dlya realizatsii funktsional'nyh operatsiy v Internet-klientskih sistemah. Iskusstvennyy Intellekt, 1, 110–116. Available at: http://dspace.nbuv.gov.ua/handle/123456789/6551
  11. Brin, S., Page, L. (1998). The anatomy of a large-scale hypertextual Web search engine. Computer Networks and ISDN Systems, 30 (1-7), 107–117. doi: https://doi.org/10.1016/s0169-7552(98)00110-x
  12. Herlocker, J. L., Konstan, J. A., Terveen, L. G., Riedl, J. T. (2004). Evaluating collaborative filtering recommender systems. ACM Transactions on Information Systems, 22 (1), 5–53. doi: https://doi.org/10.1145/963770.963772
  13. Tong, H., Faloutsos, C., Pan, J.-Y. (2007). Random walk with restart: fast solutions and applications. Knowledge and Information Systems, 14 (3), 327–346. doi: https://doi.org/10.1007/s10115-007-0094-2
  14. Huk, N., Dykhanov, S., Matiushchenko, O. (2020). Algorithm for building a website model. Bulletin of V.N. Karazin Kharkiv National University, series «Mathematical modeling. Information technology. Automated control systems», 47, 25–34. Available at: https://periodicals.karazin.ua/mia/article/view/16486
  15. Olson, D. L., Delen, D. (2008) Advanced Data Mining Techniques. Springer, 180. doi: https://doi.org/10.1007/978-3-540-76917-0
  16. Nasinnia krainy. Available at: http://semena-dnepr.org.ua/

Downloads

Published

2021-06-29

How to Cite

Guk, N., Verba, O., & Yevlakov, V. (2021). Design of a recommendation system based on the transition graph. Eastern-European Journal of Enterprise Technologies, 3(4 (111), 24–31. https://doi.org/10.15587/1729-4061.2021.233501

Issue

Vol. 3 No. 4 (111) (2021): Mathematics and Cybernetics - applied aspects

Section

Mathematics and Cybernetics - applied aspects

License

Copyright (c) 2021 Natalia Guk, Olga Verba, Vladyslav Yevlakov

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

The consolidation and conditions for the transfer of copyright (identification of authorship) is carried out in the License Agreement. In particular, the authors reserve the right to the authorship of their manuscript and transfer the first publication of this work to the journal under the terms of the Creative Commons CC BY license. At the same time, they have the right to conclude on their own additional agreements concerning the non-exclusive distribution of the work in the form in which it was published by this journal, but provided that the link to the first publication of the article in this journal is preserved.

A license agreement is a document in which the author warrants that he/she owns all copyright for the work (manuscript, article, etc.).
The authors, signing the License Agreement with TECHNOLOGY CENTER PC, have all rights to the further use of their work, provided that they link to our edition in which the work was published.
According to the terms of the License Agreement, the Publisher TECHNOLOGY CENTER PC does not take away your copyrights and receives permission from the authors to use and dissemination of the publication through the world's scientific resources (own electronic resources, scientometric databases, repositories, libraries, etc.).
In the absence of a signed License Agreement or in the absence of this agreement of identifiers allowing to identify the identity of the author, the editors have no right to work with the manuscript.
It is important to remember that there is another type of agreement between authors and publishers – when copyright is transferred from the authors to the publisher. In this case, the authors lose ownership of their work and may not use it in any way.