问题驱动的算法设计 作业：KMP证明；PageRank综述报告

ECNU

---

谷歌学术

谷歌学术：https://scholar.google.com.hk/
sci-hub：https://sci-hub.shop/
两者综合：https://gfsoso.99lb.net/

作业二选一，6月13前交：
1. 对一个具体问题设计一个算法
2. 对某类具体算法写一个综述报告

---

KMP算法证明

描述性的证明，非数学证明。

KMP的代码实现

void GetFail(char *s)//pattern
{
    int m=strlen(s+1);
    for(int i=2,j=0; i<=m; ++i)
    {
        while(j && s[i]!=s[j+1]) j=fail[j];
        fail[i]=s[i]==s[j+1]?++j:0;
    }
}
void Match(char *p,char *s)
{
    int j=0,n=strlen(s+1),m=strlen(p+1);
    for(int i=1; i<=n; ++i)
    {
        while(j && s[i]!=p[j+1]) j=fail[j];
        if(s[i]==p[j+1]) ++j;
        if(j==m) printf("%d\n",i-m+1);
    }
}

KMP正确性证明

首先说明一些定义：$s$为文本串，$p$为模式串，$s[l...r]$表示$s[l],s[l+1],...,s[r]$构成的子串。
字符串$S$的$border$定义为：$border(S)=\{s\mid s为S的前缀 且 s为S的后缀\}$。
定义$border(S)$中最长子串的长度，即$S$最长的前缀等于后缀的子串长度，为：$\mathbb{fail}(|S|)$或$\mathbb{next}(|S|)$。

GetFail的证明

GetFail函数用来求$p$的$fail$。

• $i=1$时，$fail[1]=0$，算法正确。
• 设$i=k$时算法正确，即$fail[1],...,fail[k]$计算正确，则$i=k+1$时：
  设$j$为$fail[i]$：
  
  • 若$j=0$则正确性显然。
  • 若$j\neq 0$，由定义知$s[1...j]=s[i-j+1...i]$。有两种情况：
    
    1. $s[j+1]=s[i+1]$，则由定义知$s[1...j+1]=s[i-j+1...i+1]$，则$fail[i+1]=j+1$；
    2. $s[j+1]\neq s[i+1]$，算法中令$j=fail[j]$，尝试$s[fail[j]+1]$是否与$s[i+1]$相等，即重新判断情况1,2，直至$j=0$。
       因为此时不匹配，，一定有$fail[i+1]\leq fail[j]+1$，所以$j=fail[j]$不会使结果变小。又情况1和$j=0$正确，所以$fail[i+1]$的计算正确。

总上，该函数正确。

Match的证明

Match函数利用$p$的$fail$，判断$p$在$s$中出现的位置。
设$j$为当前$s[1...i]$已匹配的$p$的前缀长度。

• $i=0$时，$j=0$，算法正确。
• 设$i=k$时算法正确，即$s[i-j+1...i]=p[1...j]$，则$i=k+1$时：
  
  • 若$j=0$则正确性显然。
  • 若$j\neq 0$，有两种情况：
    
    1. $s[i+1]=p[j+1]$，则$j=j+1$。
    2. $s[i+1]\neq p[j+1]$，算法中令$j=fail[j]$，尝试$p[fail[j]+1]$是否与$s[i+1]$相等，即重新判断情况1,2，直至$j=0$。
       因为此时不匹配，一定有$j+1\leq fail[j]+1$，所以$j=fail[j]$不会使结果变小。又情况1和$j=0$正确，所以$j$的计算正确。

综上，该函数正确。

KMP复杂度证明

由上证明可知，两函数的计算过程本质是一样的。所以只对GetFail函数进行证明。

记势函数$\phi=j$。
对于算法的两种操作：
1. $s[i+1]=s[j+1]$，使$\phi$增加$1$。
2. $j=fail[j]$，该操作会使$\phi$减少$j-fail[j]$（$j-fail[j]\gt 0$）。

因为操作1有$O(n)$个，所以势函数的总变化量为$O(n)$，所以操作2的总次数也为$O(n)$，均摊复杂度$O(1)$。

所以算法总复杂度为$O(n)$或$O(n+m)$。

PS

KMP算法不只能用于字符串字符的匹配，还能用于数列中数的相对大小关系的匹配，即将相等关系$s[i]=p[i]$，替换为，$s[i]$在$s$串中的排名 等于 $p[i]$在$p$串中的排名。如这道题。
这个想法感觉很妙，不知道在实际生活中，是否有这种相对大小关系的匹配需求，以及KMP的此类应用？

---

PageRank算法及优化 综述报告

看完这些论文的感觉：Google提出了PageRank，之后十几年 一人改一点，就能一人写一篇论文（雾）。
你一改 我一改 大家明天都能毕业
但WPR(VOL)和EWPR(VOL)真的毫无创新性，上一个算法提出后隔年就发出来了，感觉好水。

说是综述报告，其实就是为了作业随便写的，随便看看就好。

---

前言

关于PageRank的研究成果有很多，但与无权图相比带权图的算法仍然较少。
因为个人目前水平和时间问题，只对PageRank及Weighted PageRank优化方向的几个简单算法进行介绍。

Simplified PageRank

L. Page, S. Brin等¹于1998年提出简化的PageRank算法：

$$PR(u)=c\sum_{v\in B(u)}\frac{PR(v)}{N_v}$$

其中：$u$表示某个网页，$PR(u),PR(v)$分别为$u,v$网页的排序值（网页的排名得分，即rank score），$B(u)$为连向$u$的网页集合，$N_v$为$v$的出度，$c=1.0$为factor used for normalization（标准化参数？）。

所有网页的排序值$PR(x)$可以通过迭代若干次计算。
但是，当一个网络中存在两个点及以上的环，且该环没有出边时，这个环会积累其它网页的排序值而不会传递出去，使得所有连向该环的网页的排序值变为$0$，不合实际。这个问题叫做rank sink。

PageRank

为解决rank sink，L. Page, S. Brin等¹根据随机游走将简化的PageRank改为：

$$PR(u)=(1-d)+d\sum_{v\in B(u)}\frac{PR(v)}{N_v}$$

其中：$d$为dampening factor（不跳出概率？），通常设为$0.85$。

相比Simplified PageRank，该算法考虑了用户在浏览网页时有概率跳出当前浏览的网页，而任意再选择其它网页的情况，从而避免了rank sink。
作者测试了该算法，大概在$O(\log n)$次迭代后排序值会收敛。

Weighted PageRank (WPR)

PageRank算法的每次迭代，将每个网页的排序值平均分给了它指向的网页。但在实际中，同一网页指向的不同链接的重要性可能不同，分到的排序值也应不同。
Wenpu Xing, Ali Ghorbani²在2004年发表Weighted PageRank Algorithm，提出了Weighted PageRank(WPR)算法：

$$PR(u)=(1-d)+d\sum_{v\in B(u)}PR(v)W_{(v,u)}^{in}W_{(v,u)}^{out}$$

$W_{(v,u)}^{in}$表示：考虑$u$的入度和$v$连向的所有点的入度，$v\to u$这条边该分配$v$的多少权值：

$$W_{(v,u)}^{in}=\frac{I_u}{\sum_{p\in R(v)}I_p}$$

其中：$I_u$表示$u$的入度，$R(v)$表示$v$连向点的集合。

$W_{(v,u)}^{out}$表示：考虑$u$的出度和$v$连向的所有点的出度，$v\to u$这条边该分配$v$的多少权值：

$$W_{(v,u)}^{out}=\frac{O_u}{\sum_{p\in R(v)}O_p}$$

其中：$O_u$表示$u$的出度，$R(v)$表示$v$连向点的集合。

作者认为，一个网页越受欢迎，连向它的网页和它连出的网页越多。所以WPR根据$v$指向网页集合$R(v)$中点的出度和入度，分配$v$的排序值。这样$v$排序值会更多地分配到更受欢迎的网页上，而不是均分。
作者实验表明：将WPR用于搜索，得到的结果的相关性高于传统PageRank算法。

PageRank based on Visits of Links (VOL)

Gyanendra Kumar等³在2011年发表Page Ranking Based on Number of Visits of Web Pages，提出了Page Ranking based on Visits of Links(VOL)算法：

$$PR(u)=(1-d)+d\sum_{v\in B(u)}\frac{L_uPR(v)}{TL(v)}$$

其中$L_u$表示用户通过链接$v\to u$访问$u$的次数，$TL(v)$表示$\sum_{u\in R(v)}L_u$，即用户通过$v$上的链接访问其它网页的总次数。

该算法考虑了用户的浏览倾向，根据用户的实际浏览行为（链接的访问数）决定哪个网页更受欢迎，将更多的排序值分配到用户浏览最多（更受欢迎）的网页上。
VOL与之前算法相比具有如下特点：
1. 具有动态性，更符合网页搜索的特性。
2. 结果不是仅与网络结构相关，还与用户行为有关，更具目标导向性；而之前算法中，网页的排序值与用户实际访问该网页的情况无关。
3. 用户可以在搜索的同时提高该算法的准确性。
4. 一大问题是，需要动态统计每个网页上用户的浏览行为。

综上，VOL比传统PageRank的搜索结果更相关，但也带来了具体实现的问题。

Weighted PageRank based on Visits of Links (WPR(VOL))

Neelam Tyagi, Simple Sharma⁴在2012年发表Weighted Page Rank Algorithm Based on Number of Visits of Links of Web Page，提出了Weighted PageRank based on Visits of Links(WPR(VOL))算法：

$$WPR_{VOL}(u)=(1-d)+d\sum_{v\in B(u)}\frac{L_uWPR_{VOL}(v)W_{(v,u)}^{in}}{TL(v)}$$

其中：$WPR_{VOL}(u)$是WPR(VOL)算法计算出的$u$的重要性$PR(u)$，$W_{(v,u)}^{in}$是WPR中，考虑$u$的入度和$v$连向的所有点的入度，$v\to u$这条边该分配$v$的多少权值：

$$W_{(v,u)}^{in}=\frac{I_u}{\sum_{p\in R(v)}I_p}$$

因为VOL算法中考虑了出度影响的受欢迎程度（即$\frac{L_u}{TL(v)}$），作者没有使用$W_{(v,u)}^{out}=\frac{O_u}{\sum_{p\in R(v)}O_p}$。
该算法将WPR（网页的受欢迎程度）与VOL（用户的实际浏览行为/链接的访问数）结合，按照另一种比例分配排序值。
WPR(VOL)的特点、问题与VOL基本相同，但搜索结果相关性更强。

但是作者在论文所给例子的计算过程中，$R(u)$与$B(u)$搞混了，结果都是错的，这也能发论文吗。（下面EWPR(VOL)中这里没有错）
该算法实际只是毫无技术水平的两算法结合。

Enhanced Weighted PageRank based on Visits of Links (EWPR(VOL))

Sonal Tuteja⁵在2013年发表Enhancement in Weighted PageRank Algorithm Using VOL，对WPR(VOL)算法进行了优化：

$$EWPR_{VOL}(u)=(1-d)+d\sum_{v\in B(u)}WPR_{VOL}(v)W_{(v,u)}^{in}W_{(v,u)}^{out}$$

改进的原因是，作者认为WPR(VOL)算法中没有考虑$W_{(v,u)}^{out}$（事实上考虑过这点），需要加上，于是就乘了个$W_{(v,u)}^{out}$然后发了篇新论文。
但是，论文中表述有问题，公式中的$WPR_{VOL}$是指WPR(VOL)还是EWPR(VOL)中的网页排序值？

如果是前者，那代入后完整公式应为：

$$EWPR_{VOL}(u)=(1-d)+d\sum_{v\in B(u)}\frac{L_uEWPR_{VOL}(v)\big(W_{(v,u)}^{in}\big)^2W_{(v,u)}^{out}}{TL(v)}$$

为什么$W_{(v,u)}^{in}$就要算两次？作者没有说明$W^{in},W^{out}$为什么不同。

如果是后者，那EWPR(VOL)与WPR算法不一样吗？

下面有作者给出的例子，例子与介绍VOL算法中的例子相同，包含visit of links。但是，给出的计算过程中没有出现形如$\frac{L_u}{TL(v)}$的对visits的考虑。所以上面问题答案是后者，那例子中的EWPR(VOL)就是WPR（迷惑起来了）。
然后作者给出了WPR与EWPR(VOL)在$d$取不同值时的不同结果，这个不同结果是如何得出来的？所以个人认为是作者的例子计算过程写错了，公式也有问题。
公式应为：

$$EWPR_{VOL}(u)=(1-d)+d\sum_{v\in B(u)}\frac{L_uEWPR_{VOL}(v)W_{(v,u)}^{in}W_{(v,u)}^{out}}{TL(v)}$$

该算法实际又是毫无技术水平的两算法结合+无意义的改进。
可能是我水平低吧，我认为这篇论文/这算法和CtrlCV没区别，还有问题，这期刊随便发吗。

局部近似算法（基于$Push$操作的APXPR算法）

彭茂、张媛⁶在2016年发表《带权网络的个性化PageRank计算_彭茂》，提出了基于$Push$操作的PageRank计算方法，其时间复杂度优于传统迭代算法。

记$s$为PageRank中各点排序值构成的向量，$p(s)$为计算后的$s$向量，$W$为状态转移矩阵，$\alpha=1-d$为跳出概率。则可知$p(s)$为如下方程的唯一解：

$$p(s)=\alpha s+(1-\alpha)p(s)W$$

传统迭代算法可表示为：

$$p^{k}=\alpha s+(1-\alpha)p^{k-1}W$$

算法的误差限通常定义为：$||p^k-p^{k-1}||\leq\varepsilon$，时间复杂度为$O\left(\frac{m\log\varepsilon}{\log(1-\alpha)}\right)$。

作者给出了带权图的一个近似PageRank计算方法，复杂度上界为$O\left(\frac{\Delta}{\varepsilon\alpha}\right)$，其中$\Delta$为图顶点的最大出度。算法如下。

若$r$为非负向量，且对任意顶点$v$有$r(v)\leq\varepsilon\cdot outdgree(v)$，则称向量$p(s-r)$为PageRank向量$p(s)$的$\varepsilon-$近似。
该算法持续更新一个向量对$(p,r)$，使其始终满足：

$$p(I-(1-\alpha)W)=\alpha(s-r)$$

即

$$r=s-p\left(\frac{1}{\alpha}I-\frac{1-\alpha}{\alpha}W\right)$$

算法初始时$p=0,r=s$，$p,r$通过如下$Push$操作更新（记$p',r'$为$Push$操作后所得向量）：

对某个点$u$：
1. $p'(u)=p(u)+\alpha\cdot\beta\cdot r(u)$
2. $r'(u)=r(u)-\beta\cdot r(u)+(1-\alpha)w_{u,u}\cdot\beta\cdot r(u)$
3. $r'(v)=r(v)+(1-\alpha)w_{u,v}\cdot\beta\cdot r(u)$（对所有满足$(u,v)\in E$的$v$）
未更新的$p'=p,r'=r$。
若$W=D^{-1}A=(w_{ij})_{n\times n}$为转移矩阵，则$w_{u,u}=0$；$\beta$为预设值，默认为$\frac12$。

可知$p=p(s-r)\Rightarrow p'=p(s-r')$。
因为$Push$过程可以看做，$r$中的某些概率转移到了$p$中，所以对所有满足$r(u)\geq\varepsilon\cdot outdgree(u)$的点执行$Push$操作，可得到如下计算$\varepsilon-$近似PageRank向量方法：

ApxPR(s, α, ε)
    Let p=0 and r=s
    while r(u)>ε*outdgree(u) for some vertex u
        Pick any vertex u where r(u)>ε*outdgree(u)
        Apply Push(u)
    return p and r

作者证明了该APXPR算法时间复杂度为$O\left(\frac{\Delta}{\varepsilon\alpha}\right)$，其中$\Delta$为图顶点的最大出度，远优于迭代算法的$O\left(\frac{m\log\varepsilon}{\log(1-\alpha)}\right)$。

该算法也支持动态带权网络修改，更新网络一条边的复杂度为$O\left(\frac{\Delta}{\varepsilon\alpha^2}\right)$，且实际计算时间会小很多。而传统幂迭代法只能重新计算。动态网络的计算这里不再展开。

此外，作者介绍了蒙特卡洛策略计算PageRank向量的方法，也支持在线更新网络。对于一个$n$个顶点、$m$条边的图，保持$m$条边持续更新的复杂度为$O\left(\frac{nRf}{\alpha^2}\right)$。

作者通过实验得出：
1. 静态图中$Push$算法与蒙特卡洛算法均优于幂迭代法；图的稠密度较高时蒙特卡洛算法优于$Push$算法。
2. 动态图中，在图的更新量较少时，$Push$算法优于蒙特卡洛方法。

代码实现

对WPR(VOL)算法与ApxPR算法的简单实现（节点数较小时）。
在节点数、边数不大时，算法实现很简单，但当节点数很大，即现实中网页数非常多时，可能需要改进实现方法。

Weighted PageRank based on Visits of Links

每次迭代复杂度为$O(n+m)$。

/*
Sample Input:
3 4
1 3 2
3 1 2
1 2 1
2 3 2
Output:
WPR[1]=0.6319057
WPR[2]=0.2096800
WPR[3]=0.5669479
*/
#include <bits/stdc++.h>
#define pc putchar
#define gc() getchar()
#define pb emplace_back
typedef long long LL;
const int N=1e3+5;
const double d=0.85;
inline int read()
{
    int now=0,f=1; char c=gc();
    for(;!isdigit(c);c=='-'&&(f=-1),c=gc());
    for(;isdigit(c);now=now*10+c-48,c=gc());
    return now*f;
}
struct Edge
{
    int v,w;
};
struct Graph
{
    std::vector<int> e[N];
};
struct PageRank
{
    Graph R,B;
    int n,L[N][N],TL[N],I[N],O[N];
    double WPR[N],W_in[N][N],W_out[N][N];
    void AddEdge(int w,int v,int u)
    {
        R.e[u].pb(v), B.e[v].pb(u);
        ++I[v], ++O[u], L[u][v]+=w, TL[u]+=w;
    }
    void Output()
    {
        for(int i=1; i<=n; ++i) printf("WPR[%d]=%.7f\n",i,WPR[i]);
    }
    void WPRVOL()
    {
        for(int u=1; u<=n; ++u)
        {
            double sum=0;
            for(auto v:B.e[u]) sum+=L[v][u]*WPR[v]*W_in[v][u]/TL[v];
            WPR[u]=1-d+d*sum;
        }
    }
    void Calc()
    {
//Init WPR
        for(int i=1; i<=n; ++i) WPR[i]=1;
//Calc W_in W_out
        for(int u=1; u<=n; ++u)
        {
            if(!R.e[u].size()) continue;
            int sumI=0,sumO=0;
            for(auto v:R/*B*/.e[u]) sumI+=I[v], sumO+=O[v];//这里WPR(VOL)论文中使用的B(u) 
            for(auto v:R.e[u]) W_in[u][v]=1.0*I[v]/sumI, W_out[u][v]=1.0*O[v]/sumO;
        }
//Calc values iteratively
        for(int T=300,t=1; t<=T; ++t)//应该有一个校验误差是否满足的函数，不写了 
        {
            WPRVOL();
//          printf("\nIteration %d:\n",t), Output();
        }
        Output();
    }
    void Init()
    {
        n=read();
        for(int m=read(); m--; AddEdge(read(),read(),read()));
        Calc();
    }
}PR;
int main()
{
    PR.Init();
    return 0;
}

局部近似算法

/*
Sample Input:
3 4
1 3 2
3 1 2
1 2 1
2 3 2
Output:
PR[1]=1.2303706
PR[2]=0.4986050
PR[3]=1.2710243
*/
#include <bits/stdc++.h>
#define pc putchar
#define gc() getchar()
#define pb emplace_back
typedef long long LL;
const int N=1e3+5;
const double d=0.85;
const double alpha=1-d, beta=0.5, epsilon=1e-8;
inline int read()
{
    int now=0,f=1; char c=gc();
    for(;!isdigit(c);c=='-'&&(f=-1),c=gc());
    for(;isdigit(c);now=now*10+c-48,c=gc());
    return now*f;
}
struct Edge
{
    int v,w;
};
struct Graph
{
    std::vector<int> e[N];
};
struct PageRank
{
    Graph R,B;
    int n,I[N],O[N],A[N][N];
    double p[N],r[N],w[N][N];
    void AddEdge(int w,int v,int u)
    {
        R.e[u].pb(v), B.e[v].pb(u);
        ++I[v], ++O[u], A[u][v]+=w;
    }
    void Output()
    {
        for(int i=1; i<=n; ++i) printf("PR[%d]=%.7f\n",i,p[i]);
    }
    int Exist(double e)
    {
        for(int u=1; u<=n; ++u)
            if(r[u]>e*O[u]) return u;
        return 0;
    }
    void Push(int u,double a,double b)
    {
        p[u]=p[u]+a*b*r[u];
        for(auto v:R.e[u]) r[v]=r[v]+(1-a)*w[u][v]*b*r[u];
        r[u]=r[u]-b*r[u]+(1-a)*0*b*r[u];
    }
    void ApxPR(double a,double e,double b)
    {
//Init
        for(int i=1; i<=n; ++i) p[i]=0, r[i]=1;
//APXPR
        int u;
        while(u=Exist(e),u) Push(u,a,b);
    }
    void Init()
    {
        n=read();
        for(int m=read(); m--; AddEdge(read(),read(),read()));
//Calc wij
        for(int i=1; i<=n; ++i)
        {
            int D=0;
            for(int j=1; j<=n; ++j) D+=A[i][j];
            for(int j=1; j<=n; ++j) w[i][j]=1.0*A[i][j]/D;
        }
//ApxPR 
        ApxPR(alpha,epsilon,beta);
        Output();
    }
}PR;
int main()
{
    PR.Init();
    return 0;
}

总结

PageRank最初的几个算法虽然容易理解，但在当时确实很具有创新性，比如PageRank、Weighted PageRank和PageRank based on Visits of Links。
但是之后的提出的两个算法 WPR(VOL)和EWPR(VOL)，只是简单地将前面的算法进行结合，没太有创新性，且内容都有很大的错误，合理怀疑只是在水论文。
除了幂迭代法，还有很多其它算法，也比迭代法更复杂、有创意。

参考

• [1] 15036 The PageRank Citation Ranking

• [2] 710 weightedPageRank

• [3] 92 Page Ranking Based on Number of Visits of Web Pages

• [4] 79 Weighted Page Rank Algorithm Based on Number of Visits of Links of Web Page

• [5] 18 Enhancement in Weighted PageRank Algorithm Using VOL

• [6] 带权网络的个性化PageRank计算