1什么是超图？
图模型很好理解，由若干条边连接定点组成的图，我们称之为图。那么什么是超图呢？超图和图最大的不同是：一条边可以连接多个定点，图1（b）所示就是超图。
2随机游走
（1）随机游走算法在文本摘要、关键词提取、图像分割等方面有着重要的应用． 随机游走( Ｒandom Walk)是一种状态转移的过程，在图模型中，随机游走即从一个指定的顶点 u，随机的移动到一个相邻的顶点 v 的过程． 随机游走的随机过程{ s0，s1，s2，…，sn} 称为马尔可夫( Markov) 链，从一个状态 si转移到另一个状态 sj服从转移概率 P( u，v) = P( st + 1= v | st= u) ，即一个状态时刻 t 在 u 顶点，在时刻 t + 1 转移到 v 顶点． 对于任意顶点 u，转移到相邻顶点的概率之和为1，即∑vP( u，v) = 1．
将图的随机游走扩展到带权重的超图 H( V，E，W) ，那么随机游走可通过如下过程实现: 对于起始顶点 u，其中 u∈e，随机选取超边 e 的一个邻接超边 e'，然后在超边 e'中随机的选取一个顶点 v，其中 v∈e'． 因此定义从顶点 u 转移到顶点 v的概率转移 P( u，v) 为
其中 Dv、De和 We分别为顶点度矩阵、超边度矩阵，超边权重矩阵．
网友评论