Study On Tensor Models Of High-dimensional Random Walks On Hypergraphs

Random walk on a graph is a classic problem in combinatorial graph theory.The random walk on the graph is a discrete Markov chain,which is manifested as a sequence of points and edges formed by random movement of points along edges on a graph.It is closely related to many branches of graph theory,and its basic properties are studied from graph theory and resistance distance theory of graph.In data science,the random walk on the graph is an important technology to extract information,and can also be used to measure the centrality of nodes in the network,etc.Around 1998,Brin and Page used the random walk on the graph to establish the Page Rank algorithm of Google search engine,which started the craze of algorithm research based on random walk.The random walk model is widely used in network information retrieval and biological information data mining,and is also an important method to detect the structure of network community.The random walk theory on the graph provides the basis for probability interpretation of spectral clustering algorithm.In recent years,many experts and scholars have developed the random walk on the graph to the hypergraph.Thus,it can be seen that the random walk on the hypergraph is very important.On the basis of previous studies,this thesis mainly introduces some relevant conclusions about the random walk on the defined hypergraph =(V,E,w,r)with vertices weighted by edges.By calculating the limit,the steady-state distribution of the random walk is obtained,and the Laplace tensor is constructed by using the probabilistic transfer tensor and the diagonal tensor composed of the elements of the steady-state distribution,and then the normalized Laplace tensor is obtained.Then,by the penultimate smallest eigenvalue of the normalized Laplace tensor and the Cheeger constant defined in this paper,A tensor version of the Cheeger inequality is obtained.Since the random walks on hypergraphs are Markov chains on vertices,two random walks are equivalent if they have the same probabilistic transfer tensor.Some results about the equivalent random walks on hypergraphs are obtained.