Research And Application Of Random Walk Algorithm Based On Distance

ABSTRACT: Recently. Many datasets of interest are best described as a linked collection of interrelated objects. Examples of homogeneous networks include single mode social networks, such as people connected by friendship links, or the WWW, a collection of linked web pages. These may represent homogeneous networks, contained a single-object type and link type, or richer, heterogeneous networks, in which there may be multiple object and link types, like those in medical domains describing patients, diseases, treatments and contacts, or in bibliographic domains describing publications, authors, and venues. An area called link mining has emerged from the larger area of data mining, whose purpose is to extract hidden knowledge from large, linked data sets.Link mining encompasses a wide range of tasks; however our review only will cover two branches. Our goal is to introduce the random walk idea based on distance between nodes.Firstly, we give a brief summary on random walk on complex networks and discuss some possible research issues. We propose a theorem about probability arriving for hitting time based on distance between nodes.In this paper, we review several methods for link prediction. Then we proposed an improved link prediction method LRWD (Local Random Walk with Distance) based on existing LRW (Local Random Walk) with the shortest distance. In LRWD, our hypothesis is that probability of the random walker reaching a destination node for the first time makes a major contribution to link establishment. To meet this assumption, we replace the optimal step of LRW methods with the distance of node pairs. The optimal step is specified as local properties not overall features of network. Random walkers walk in their own pace with new criteria not walk simultaneously in the whole network. This change not only provides the new perspectives and methods in link prediction for researchers, but also demonstrates the role of shortest distance in complex network. Then we propose distance frequency distribution and distribution entropy to analyze the evolution of the complex networks.Next, we transplant this random walk idea into another branch; object clustering based on link information. We use Euclidean distance to build complex network. The walker steps base on the distance between node pair and updates the distance of node pair. We have the approximate stationary transition probability distribution. And use this distribution to build new clustering similarity. After that we build criterion function with K-L distance.