Random Walk Modeling for Retrieving Information on Semantic Networking

Document Type : Original Scientific Paper


1 Department of computational cognitive modeling, Institute of cognitive science study, Tehran, Iran

2 Department of financial mathematic, kharazmi university, Tehran, Iran.

3 University of Tehran,Institute for cognitive sciences studies

4 Department of computational cognitive modeling, Institute of cognitive science study, Tehran, Iran.


In this article, the famous random walk model is exploited as a model of stochastic processes to retrieve some specific words which are used in social media by users. By spreading activation on semantic networking, this model can predict the probability of the words' activation, including all probabilities in different steps. In fact, the trend of probability in different steps is shown and the result of two different weights, when the steps tend to infinity is compared. In addition, it is shown that the results of the random walk model are aligned with the experimental psychological tests, showing that, as a model for semantic memory, it is a suitable model for retrieving in social media.


[1] R. Baeza-Yates and R. Ribeiro-Neto, Modern Information Retrieval, ACM Press / Addison Wesley, 1999.
[2] R. K. Belew, Adaptive information retrieval: Using a connectionist representation to retrieve and learn about documents, 
In Belkin and van Rijsbergen,The 12th Annual International Conference on Research Development in Information Retrieval, (1989) 11 20.
[3] Y. Campbell, A. W. Lo and A. C. MacKinlay, 
The Econometrics of Financial Markets, Princeton University Press, Princeton, NJ, USA, 1996.
[4] F. Crestani, Application of spreading activation techniques in information retrieval, 
Artif. Intell. Rev. 11 (1997) 453 482.
[5] N. Craswell and M. Szummer, Random Walks on the Click Graph, 
Proc. of SIGIR, 2007.
[6] T. E. Doszkocs, J. A. Reggia and X. Lin, Connectionist models and information retrieval, 
Annu. Rev. Info. Sci. Technol. 25 (1990) 209 260. 
[7] M. E. Fisher, Shape of a self-avoiding walk or polymer chain, J. Chem. Phys. 44 (1966) 616 622.
[8] M. C. Guerrette, K. Guérard and J. Saint-Aubin, The role of overt language production in the Hebb repetition effect, 
Mem. Cognit. 45 (2017) 792 803.
[9] J. J. Hopfield and D. W. Tank, Computing with neural circuits: a model, 
Science 233 (1986) 625 633.
[10] O. Häggström, 
Finite Markov Chains and Algorithmic Applications, Cambridge University Press, Cambridge, UK, 2002. 
[11] J. Kounios, A. M. Osman and D. E. Meyer, Structure and process in semantic memory: new evidence based on speed–accuracy decomposition, 
J. Exp. Psychol. Gen. 116 (1987) 25.
[12] M. L. Minsky, 
Semantic Information Processing, The MIT Press, 1969.
[13] R. Mihalcea and P. Tarau, TextRank: bringing order into texts, 
Proceedings of the 2004 Conference on Empirical Methods in Natural Language Processing, Association for Computational Linguistics, (2006) 404 411.
[14] C. Ogden, I. Richards, B. Malinowski and F. Crookshank, 
The Meaning of Meaning, Routledge & Kegan Paul, London, 1949.
[15] Y. Ogawa, T. Morita and K. Kobayashi, A fuzzy document retrieval system using the keyword connection matrix and a learning method. Applications of fuzzy systems theory, 
Fuz. Sets Syst. 39 (1991) 163 179.
[16] L. Page, S. Brin, R. Motwani and T. Winograd, 
The PageRank Citation Ranking: Bringing Order to the Web, Technical report, Stanford Digital Library Technologies Project, 1998.
[17] K. Pearson, The problem of the random walk, 
Nature 72 (1) (1905) 294.
[18] J. M. Ponte and W. B. Croft, A language modeling approach to information retrieval, 
Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval98 (1998) 275 281.
[19] S. E. Robertson and K. Sparck Jones, Relevance Weighting of Search Terms, 
J. Am. Soc. Inf. Sci. 27 (1976) 129 146.
[20] G. Salton, 
Automatic Information Organization and Retrieval, McGraw Hill Text, 1968.
[21] G. Salton, 
The SMART Retrieval System: Experiments in Automatic Document Processing, Prentice -Hall Inc., 1971. 
[22] G. Salton and C. Buckley, Term-weighting approaches in automatic text retrieval. Inf. Process. Manag. 24 (1988) 513 523.
[23] G. Salton, 
Introduction to Modern Information Retrieval, Mcgraw-Hill College, 1983.
[24] S. Sabetghadam, M. Lupu and A. Rauber, Which one to choose: random walks or spreading  activation?
Multidisciplinary Information Retrieval8849 (2014) 112 119.
[25] H. Turtle and W. B. Croft, Evaluation of an inference network-based retrieval model, 
ACM Trans. Inf.  Syst. 9 (1991) 187 222.
[26] H. C. Tuckwell, 
Introduction to Theoretical Neurobiology, vol. 2, Nonlinear and Stochastic Theories, Cambridge University Press, Cambridge, 1988.
[27] E. Tulving, G. Bower and W. Donaldson, 
Organization of Memory, New York, Academic Press, 1972.
[28] M. Usher and J. L. McClelland, The time course of perceptual choice: The leaky, competing accumulator model,
Psychol. Rev. 108 (2001) 550 592.
[29] G. M. Viswanathan, S. V. Buldyrev, S. Havlin, M. G. E. da Luz, E. P. Raposo and H. E. Stanley, Optimizing the success of random searches,
Nature 401 (1999) 911 914.
[30] R. Wilkinson and P. Hingston, Using the cosine measure in a neural network for document retrieval, 
In Proceedings of the ACM SIGIR Conference on Research and Development in Information Retrieval202 210, Chicago, IL USA, 1991.
[31] H. Zheng, G. Xiao, G. Wang, G. Zhang and K. Jiang, Mean first passage time of preferential random walks on complex networks with applications, 
Math. Probl. Eng. 2017 Art. ID 8217361, 14 pp.