当前位置:   article > 正文

超图上的随机游走_随机游走发现关键边

随机游走发现关键边

超图上的随机游走

一、超图

1、普通图的局限性

在普通的图中,一条边只能连接两个点。在超图中,一个超边内可以存在多个点。实际上,普通图其实是超图的一种特殊存在形式,即超图中任意一条边内只存在两个点的特殊情况。

​ 在普通图中,一条边只能储存两个点之间的关系,具有较大的局限性,无法将储存的信息将第三者相关联起来。例如,小张、小明和小王喜欢离散数学,小红和小明喜欢高等代数,若把同学作为点,课程作为边,只通过普通的图是无法将同学对课程的喜好关系准确地表达出来,强行表示必然会有信息的损失。在这种情况下,我们引入超图,把喜好课程作为超边,同学作为点,将同学与喜好课程之间的关系完整的表示出来。

2、超图的基本性质

下面我们来介绍超图的一些基本性质的定义。HG(V,E)为点集为V的,边集为E的超图。

​ 当v∈e时,称超边e与v相交。超图的关联矩阵H∈R(|V|x|E|)定义如下:
h ( v , e ) = { 1 i f v ∈ e 0 i f v ∉ e h(v,e) = \left\{

1ifve0ifve
\right. h(v,e)={1ifve0ifv/e
​ 点的度d(v)定义如下:
d ( v ) = ∑ e ∈ E w ( e ) h ( v , e ) d(v) =\sum_{e\in E}w(e)h(v, e)\\ d(v)=eEw(e)h(v,e)
​ 超边的的度δ(e)定义如下:
δ ( e ) = ∑ v ∈ V h ( v , e ) = ∣ e ∣ δ(e)=\sum_{v\in V}h(v, e)=|e| δ(e)=vVh(v,e)=e

二、随机游走

1、随机游走概念

​ 随机游走算法的基本思想是,从一个或一系列顶点开始遍历一张图。在任意一个顶点,遍历者将以概率1-a游走到这个顶点的邻居顶点,以概率a随机跳跃到图中的任何一个顶点,称a为跳转发生概率,每次游走后得出一个概率分布,该概率分布刻画了图中每一个顶点被访问到的概率。用这个概率分布作为下一次游走的输入并反复迭代这一过程。当满足一定前提条件时,这个概率分布会趋于收敛。收敛后,即可以得到一个平稳的概率分布。随机游走模型广泛应用于数据挖掘和互联网领域,PageRank算法可以看作是随机游走模型的一个实例。这里通过介绍PageRank算法实例来让大家了解普通图上的随机游走。

其实随机游走的过程就是求转移矩阵P的过程。因此这里主要介绍转移矩阵P的求法。

(1)未加权简单图随机游走:

从u到v的转移概率为:
P ( u , v ) = 1 d ( u ) P(u,v)=\frac{1}{d(u)} P(u,v)=d(u)1
矩阵表示:
P = D G − 1 H P=D^{-1}_GH P=DG1H
(2)加权简单图的随机游走:

从u到v的转移概率为:
P ( u , v ) = w ( u , v ) d ( u ) P(u,v)=\frac{w(u,v)}{d(u)} P(u,v)=d(u)w(u,v)
这里的 d ( u ) d(u) d(u)的定义改变了:
d ( u ) = ∑ w ( u , x ) d(u)=\sum_w(u, x) d(u)=w(u,x)

2、详解随机游走——以PageRank为例

​ 互联网用户在上网时,往往有类似的网络行为:输入网址,浏览页面,然后顺着页面的链接不断打开新的网页。随机游走模型就是针对浏览网页的用户行为建立的抽象概念模型。之所以要建立这个抽象概念模型,是因为包括PageRank 算法在内的很多链接分析算法都是建立在随机游走模型基础上的。

​ PageRank算法最早用于对网页进行“重要性”排序,它的算法逻辑可以使用随机游走模型来解释。在随机游走模型中,假设存在一个网络冲浪者,在每个时刻,该冲浪者停留在一个网页上,并且必须从以下行动中选取一个行动:一、从该网页的所有超链接中随机地选择一个链接,跳转到下一个页面。二、在浏览器的地址栏中输入一个新的网址,跳转到下一个页面。如果一直让该冲浪者重复这样的选择(即每次选择一个行动,跳转到下一个页面;然后又选择一个行动,再跳转到下一个页面),并记录该冲浪者对每个网页的访问次数。当这样的重复次数足够大时,每个网页被访问的频率逐渐趋于稳定。这时,用频率代替概率,便得到所有网页被冲浪者访问的概率,这些概率就是网页的PageRank值。

用公式表示就是:
P R ( i ) = 1 − d N + d ∑ j ∈ i n ( i ) P R ( j ) ∣ o u t ( j ) ∣ PR(i) = \frac{1-d}{N} + d\sum_{j\in in(i)}\frac{PR(j)}{|out(j)|} PR(i)=N1d+djin(i)out(j)PR(j)

变量表示含义
P R ( i ) PR(i) PR(i)网页i被访问到的概率
i n ( i ) in(i) in(i)所有指向网页i的网页集合
d d d用户继续访问网页的概率
o u t ( j ) out(j) out(j)网页j指向的其他网页集合
N N N所有网页的数量

​ 由此,我们便很容易理解

以网页 i i i作为起点,第一个被用户点击后停留在当前页面的概率:
1 − d N \frac{1-d}{N} N1d

用户点击其他网页后(无论网页 i i i是不是起点),再次跳转回到网页 i i i的概率:
d ∑ j ∈ i n ( i ) P R ( j ) ∣ o u t ( j ) ∣ d\sum_{j\in in(i)}\frac{PR(j)}{|out(j)|} djin(i)out(j)PR(j)
实际上,推导网页概率P的过程,就是得到转移矩阵T的过程,至此,我们还需要每个页面初始概率值。在一般情况下我们假定,用户初始时所处的网页是随机的,即每个网页的初始概率值为(1/N)。

注意这里转移矩阵T有以下几个特征:

(1)T为随机矩阵 即所有 T [ i ] [ j ] ≥ 0 T[i][j] \geq 0 T[i][j]0,且的所有列向量的元素加和为1,即 ∑ i = 1 n T [ i ] [ j ] = 1 \sum_{i=1}^{n} T[i][j]=1 i=1nT[i][j]=1

(2)T是不可约的 所谓不可约是说T所对应的图示强连通的,即图中任何一个节点都可以达到其他任何一个节点,它要求概率转移矩阵不存在某些特殊情况,比如某个列向量都为0,即有一个网页没有链接到任何其他网页,我们把这类情况又称为终止点;或者是在概率转移矩阵的主对角线上,存在有一个元素为1的情况,即这个网页链接只链接它自己,我们把这类情况又称为陷阱。

(3)T是非周期的 所谓周期性,体现在Markov链的周期性上。即若A是周期性的,那么这个Markov链的状态就是周期性变化的。

由此我们可以进行随机游走,得到网站的重要性排序:
V n = T ⋅ V n − 1 = T n ⋅ V 0 V_{n}=T \cdot V_{n-1}=T^{n} \cdot V_{0} Vn=TVn1=TnV0
但是,上述的随机游走过程并不能保证转移矩阵T是不可约的,因此,我们使用重启的随机游走算法来保证随机游走过程是不可约的。从而得到下面的重启随机游走。
V n = α T V n − 1 + ( 1 − α ) V 0 V_{n}=\alpha T V_{n-1}+(1-\alpha) V_{0} Vn=αTVn1+(1α)V0

三、超图上的随机游走

超图上的随机游走大致可分为两步,第一步是冲浪者从点u选择一条超边e,第二步则是在超边e中选择要游走到的点v。

根据超图中点和超边是否加权,可以将超图中的随机游走分为四大类。而每类随机游走的主要不同之处在于P矩阵的差异,因此在这里,我们着重来看P矩阵的构建过程。

1、点、超边都没有权重的超图

冲浪者从当前点u出发,等概率随机选择一条包含点u的超边e,再在超边e内等概率随机选择下一个点v。

由此,我们可以定义P转移概率为:
P ( u , v ) = 1 d ( u ) ∑ e ∈ E ( u ) ∩ E ( v ) 1 δ ( e ) P(u, v)=\frac{1}{d(u)} \sum_{e \in \mathcal{E}(u) \cap \mathcal{E}(v)} \frac{1}{\delta(e)} P(u,v)=d(u)1eE(u)E(v)δ(e)1
其矩阵表示为:
P = D v − 1 H D e − 1 H T P=D_{v}^{-1} H D_{e}^{-1} H^{T} P=Dv1HDe1HT

变量名含义
P ( u , v ) P(u, v) P(u,v)从点u到点v的转移概率
d ( u ) d(u) d(u)点u的度
δ ( e ) \delta(e) δ(e)超边e的度
E ( v ) \mathcal{E}(v) E(v)包含点v的所有超边集合
E ( u ) \mathcal{E}(u) E(u)包含点u的所有超边集合
P P P转移矩阵
D v D_{v} Dv点的度的对角矩阵
H H H邻接矩阵
D e D_{e} De边的度的对角矩阵

注意到这里转移矩阵P的每行和为1。

2、点没有加权、超边加权的超图

第二种情况和第一种情况的不同之处在于第一步从点u选择超边e的过程中,这里每条超边被选择的概率是与其权重成正比的。第二步从超边e出发选择点v则相同。

由此,我们可以定义P转移概率为:
P ( u , v ) = ∑ e ∈ E w ( e ) h ( u , e ) ∑ e ^ ∈ E ( u ) W ( e ^ ) h ( v , e ) δ ( e ) ( 1 ) P(u,v)=\sum_{e\in E}w(e)\frac{h(u,e)}{\sum_{\hat{e}\in E(u)}W(\hat{e})}\frac{h(v,e)}{δ(e)}\\ \quad (1) P(u,v)=eEw(e)e^E(u)W(e^)h(u,e)δ(e)h(v,e)1
其矩阵表示为:
P = D v − 1 H W e D e − 1 H T ( 2 ) P=D_v^{-1}HW_eD^{-1}_eH^T (2) P=Dv1HWeDe1HT2
W e W_{e} We为对角矩阵,其对角线上的元素是每条超边的权重。 D v D_{v} Dv的求法与第一种情况略有不同,其对角线上的元素是与点u相关联超边集 e ^ ∈ E ( u ) \hat{e}\in E(u) e^E(u)的权重相加。

在这里其实我们可以把这两个公式的每一项一一对应起来。

(1)中的 w ( e ) w(e) w(e)在(2)里面对应的是 W e W_{e} We h ( u , e ) 和 h(u,e)和 h(u,e) h ( v , e ) h(v,e) h(v,e)在(2)中以邻接矩阵H和他的转置的形式表现出来,这两个矩阵保证了第一步选择的超边e包含点u,也保证了第二步选择的点v包含于超边e中。 δ ( e ) {δ(e)} δ(e)也就是超边的度,在(2)中与 D v D_{v} Dv相对应。由于在分母上,因此在这里我们对 D v D_{v} Dv求逆。 ∑ e ^ ∈ E ( u ) W ( e ^ ) \sum_{\hat{e}\in E(u)}W(\hat{e}) e^E(u)W(e^)这一项的实现,我们通过重新定义点u的度实现。

3、点加权,超边没有加权的超图

这里与情况点不加权,边加权的超图有异曲同工之妙。第一步从点u选超边e与都没有加权的超图一样,第二步从超边选择点v的概率与每个点的权重成正比。

由此,我们可以定义P转移概率为:
P ( u , v ) = 1 d ( u ) ∑ e ∈ E ( u ) ∩ E ( v ) w ( v , e ) ∑ v ^ ∈ e w ( v ^ , e ) P(u,v)=\frac{1}{d(u)}\sum_{e\in E(u)\cap E(v)}\frac{w(v,e)}{\sum_{\hat{v}\in e}w(\hat{v},e)}\\ P(uv)=d(u)1eE(u)E(v)v^ew(v^,e)w(v,e)
其矩阵表示即转移矩阵P为:
P = D v − 1 H W e D v e − 1 H T P=D_v^{-1}HW_eD^{-1}_{ve}H^T P=Dv1HWeDve1HT
这里,由于我们给点加权,因此超边的度被重新定义,即超边度的对角矩阵 D v e D_{ve} Dve要做出相应的变化。

显然,这两个公式每一项是可以在实际意义上一一对应的,但由于在第二种情况中描述详细,在这里不加以赘述。

4、点加权、超边也加权的超图

我们可以把第四种情况看成前两种情况的的结合。第一步选择超边时每条超边被选择的概率与其权重成正比,第二步选择点时每个点被选择的概率与其权重成正比。

由此,我们可以定义P转移概率为:
P ( u , v ) = ∑ e ∈ E w ( e ) h ( u , e ) ∑ e ^ ∈ E ( u ) W ( e ^ ) w ( v , e ) ∑ v ^ ∈ e w ( v ^ , e ) P(u,v)=\sum_{e\in E}w(e)\frac{h(u,e)}{\sum_{\hat{e}\in E(u)}W(\hat{e})}\frac{w(v,e)}{\sum_{\hat{v}\in e}w(\hat{v},e)}\\ \quad P(u,v)=eEw(e)e^E(u)W(e^)h(u,e)v^ew(v^,e)w(v,e)
其矩阵表示即转移矩阵P为:
P = D v − 1 H W e D v e − 1 H T P=D_v^{-1}HW_eD^{-1}_{ve}H^T P=Dv1HWeDve1HT

5、超图随机游走

不同种超图的随机游走主要不同之处在于转移矩阵P的构建,超图和普通图随机游走的不同之处也在于P矩阵的构建,在这里我们将转移矩阵代入公式中的到每个点的重要性排序。

非重启随机游走: V n = P ⋅ V n − 1 = P n ⋅ V 0 V_{n}=P \cdot V_{n-1}=P^{n} \cdot V_{0} Vn=PVn1=PnV0

重启随机游走: V n = α P V n − 1 + ( 1 − α ) V 0 V_{n}=\alpha P V_{n-1}+(1-\alpha) V_{0} Vn=αPVn1+(1α)V0

声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:【wpsshop博客】
推荐阅读
相关标签
  

闽ICP备14008679号