超图上高维随机游走的张量模型研究
摘要
图上的随机游走是组合图论中的经典问题，图上的随机游走是一种离散的马尔可
夫链，表现为图上的点沿边的随机运动形成的点边序列，与图论的许多研究分支有密
切的关系，其基本性质研究源于图谱理论，图的电阻距离理论。在数据科学中图上的
随机游走是提取信息的重要技术，也可以用来度量网络中节点的中心性等。1998年前
后Brin和Page利用图上的随机游走建立了Google搜索引擎的PageRank算法，开启
了基于随机游走的算法研究热潮。图上的随机游走模型广泛应用于网络信息检索与生
物信息数据挖掘中，也是检测网络社团结构的一种重要方法，图上的随机游走理论为
谱聚类算法概率解释提供了基础。
近年来，许多专家学者将图上的随机游走发展到了超图上，由此可见，超图上的
随机游走是十分重要的,在前人研究的基础之上，本文主要介绍了依赖边的顶点加权的
超图(V,E,w,r)在本文所定义的顶点walk上的随机游走的一些相关结论，先给出
s
了概率转移张量，通过求极限的方式，得到了随机游走的稳态分布；又利用概率转移
张量和由稳态分布的元素构成的对角张量构造了拉普拉斯张量，进而得到了规范拉普
拉斯张量，再通过规范拉普拉斯张量倒数第二小特征值和本文所定义的Cheeger常数，
得到张量版本的Cheeger不等式；又由于超图上的随机游走是顶点上的马尔可夫链，
因此，如果两个随机游走具有相同的概率转移张量，则它们是等价的，得出了关于超
图上的等价随机游走的一些结果。
关键词：超图；张量；Cheeger不等式；依赖边的顶点加权的随机游走
超图上高维随机游走的张量模型研究
ABSTRACT
Randomwalkonagraphisaclassicproblemincombinatorialgraphtheory.Therandom
walkonthegraphisadiscreteMarkovchain,whichismanifestedasasequenceofpointsand
edgesformedbyrandommovementofpointsalongedgesonagraph.Itiscloselyrelatedto
manybranchesofgraphtheory,anditsbasicpropertiesarestudiedfromgraphtheoryand
resistancedistancetheoryofgraph.Indatascience,therandomwalkonthegraphisan
importanttechnologytoextractinformation,andcanalsobeusedtomeasurethecentralityof
nodesinthenetwork,etc.Around1998,BrinandPageusedtherandomwalkonthegraphto
establishthePageRankalgorithmofGooglesearchengine,whichstartedthecrazeof
algorithmresearchbasedonrandomwalk.Therandomwalkmodeliswidelyusedinnetwork
informationretrievalandbiologicalinformationdatamining,andisalsoanimportantmethod
todetectthestructureofnetworkcommunity.Therandomwalktheoryonthegraphprovides
thebasisforprobability