PageRank and net structure analysis
Published:
如果你正在进行专业、大学、机构或者工作单位的挑选，但缺乏相关的信息，或信息混杂真伪难辨，不知道应该如何选择，可以尝试本文提供的方案来进行辅助判断。
本文提供的算法，能够通过公开的网络超链接信息，从相关组织的官网获得这个组织和其他组织的关系、组织的体量、组织的网络基础设施建设情况、组织的影响力等数据（通常这些数据都是隐藏不予公开的，或描述与实际情况不符）。完成这件事需要的仅仅是下载一些软件（Matlab），并按照文中的步骤运行脚本，即可得到结果。
文章提供了算法的数学基础、实现的代码、以及对”中国科学院大学”这个组织的分析结果，通过这个算法能得到的结果是一张势力分布图，从中可以看到组织关系（通过连线）、组织体量（通过节点数量）、组织影响力（通过范围）、组织网络基础设施建设情况（通过密集程度）。
其中组织缩写为
- CAS：中科院
- USTC: 中科大
- UCAS：中国科学院大学
- PKU：北大
- HIT：哈工大
- MOE：教育部
不难看出，在这个圈子里，CAS直接关联UCAS，而MOE几乎不直接参与UCAS：这符合UCAS直属于CAS的事实。另外，可以看出USTC具有巨大的影响力和体量、基础设施建设也十分完善集中，与PKU和HIT,MOE,CAS的关系也十分紧密。类似的，可以对USTC、PKU、HIT、MOE等组织进行分析，获得更全面的信息。
！免责声明：这类分析结果仅供参考，由于算法的局限性，单次运行的结果图未必能够完全反映组织的真实情况，仅提供一个新的视角和方法，从而帮助你更好地进行组织的选择和筛选。
排序算法与网络结构分析
前言：Google的网页排序算法PageRank是基于马尔科夫链的随机过程计算，其中涉及了网页跳转操作，是复杂网络中随机过程的一个典型例子，同时它包含了对网络结构的数据采集，这很容易在计算机上进行实验。本文主要通过Matlab实现这个排序算法，并以UCAS 的教学网站SEP为对象采集并分析其网络结构，从中也可以看出UCAS 和其他相关机构的关系，进而提供了一个新的视角和方法。
1 马尔科夫链算法
Google 的网页排序算法PageRank 是一种根据万维网的连接结构来决定网页排序的算法，它的计算过程不会包含任何网页的具体内容，而是通过每月一次的计算来给出网页的顺序。对于任何搜索的词条，Google会检索与之符合的网页，并按照PageRank给出的顺序进行排序展示。
算法的核心是考虑一个随机过程，用户每次从一个网页跳转到另外一个网页，如果该网页有指向其他网页的超链接，则它会随机选择其中一个。如果遇到了没有外链接的网页，将会从所有网页中随机选取一个进行跳转。于是，从网页i跳转到网页j的概率仅依赖于第i次所在的网页，而与之前访问的网页无关，用马尔科夫链可以描述这个过程。
1.1 网络拓扑结构
设W为所有网页的集合，其中的每个网页都可以从根网页开始经过有限步的跳转被访问。
$n=Card(W)$是网页的数量，对Google来说，这个数值随着时间变化，到2004年6月，n已经超过4千万。
定义G为$n\times n$的连接矩阵，满足$g_{ij}=1$如果网页i有指向网页j的链接。否则设为0.
它描述了互联网的拓扑结构，是一个非常巨大，但是很稀疏sparse 的矩阵。
实际上，矩阵中所有非零元的数量就是万维网中的超链接数量。
1.2 马尔可夫转移矩阵
用户在一个网页可能跟随下一个链接（概率p），也可能随机跳转到任何一个网页，因此可以得到转移概率矩阵
首先定义$r_i=\sum_j h_{ij}$，它是从i网页可以连出去的j网页的数量
那么可以得到转移概率矩阵W
$w_{ij}=ph_{ij}/r_{i}+(1-p)/n$,如果$r_{i}\ne0$，即i网页中存在超链接指向其他网页。
$w_{ij}=1/n$,如果$r_{i}=0$
注意到矩阵W是对连接矩阵行的求和的scaling ，此时得到的就是从一个网页跳转到另外一个网页的概率。实际上通常让$p=0.85$，考虑$n=4\times 10^9$，那么这里的每个值都是很小的。
由此我们得到了马尔可夫转移概率矩阵，其元素严格介于0和1，并且每行之和严格等于1（即必然会跳出这个网页）。
1.3 网站排序
计算网页的顺序，简单来说就是计算稳定的分布，并按照概率进行评分，即计算方程
\[Ax=x\]的解，其中$x$ 满足$\sum x_i=1$
实际运算时，一种可行的方案是从一个状态开始，不断的计算$x=Ax$，直到迭代的两个矢量的差的模长小于一个特定的值。
2 稀疏矩阵的幂运算
2.1 运算的化简
Goggle的实际运行方式其实根本不涉及幂运算，因为$A^k$的计算可以以通过更新超链接的权重进行
在Matlab中计算PageRank利用了马尔可夫矩阵的特定结构，以下的方法可以保持矩阵的稀疏性，将矩阵写为
\[A=pGD+ez^T\]其中矩阵$D$定义为：如果$r_i\ne0~,d_{ii}=1/r_i$，否则$d_{ii}=0$
而$e$为n维矢量，分量均为1.
$z$为n维矢量，分量满足$z_i=(1-p)/n$，如果$r_i\ne 0$,否则$z_i=1/n$
从而方程可写为
\[(I-pGD)x=\gamma e\]其中$γ = z^T x.$
虽然我们不知道$\gamma$的值，但是只要我们求解了$(1-pGD)x=e$的$x$，就可以通过$\sum x_i=1$直接确定满足的解。
因此问题转化为求解
\[(I-pGD)x=e\]3 一个小网站模型
3.1 初始条件
现在考虑几个例子，此时$n=6$，网页用被称为uniform resource locators(URL) 的字符串进行定位，大多数URL都会以http开始，因为他们使用了超链接协议。
在Matlab中，我们可以用如下的方式创建一个网络
U = {’http://www.alpha.com’
’http://www.beta.com’
’http://www.gamma.com’
’http://www.delta.com’
’http://www.rho.com’
’http://www.sigma.com’}
左侧是网络域名，右边是网络模型。
3.2 代码
这里的(i,j)对代表了存在的超链接，如(2,1),(6,1)
i = [ 2 6 3 4 4 5 6 1 1]
j = [ 1 1 2 2 3 3 3 4 6]
由此就可以生成一个$6\times 6$矩阵，其中只有9个为1，27个为0。
n = 6;
G = sparse(i,j,1,n,n);
full(G);
根据上面的算法，可以写出最终概率的计算方法
p=0.85
c=sum(G,1);%the sum of outgoing hyperlink
k=find(c~=0);
D = sparse(k,k,1./c(k),n,n);%sparse of c
e = ones(n,1);%n-D vector with entries =1
I = speye(n,n);%unit matrix
x = (I - p*G*D)\e;%solve
x = x/sum(x);%scaling
3.3 实验结果
用Matlab 执行后
得到矩阵$G$如下。这样形成的矩阵代表了上图给出的网络的拓扑结构。
G=
0 0 0 1 0 1
1 0 0 0 0 0
0 1 0 0 0 0
0 1 1 0 0 0
0 0 1 0 0 0
1 0 1 0 0 0
最终得到的结果是
x =
0.3210
0.1705
0.1066
0.1368
0.0643
0.2007
绘制为直方图可知，alpha,sigma,beta是最高排序的网站。
最终结果显示为
page-rank in out url
1 0.3210 2 2 http://www.alpha.com
6 0.2007 2 1 http://www.sigma.com
2 0.1705 1 2 http://www.beta.com
4 0.1368 2 1 http://www.delta.com
3 0.1066 1 3 http://www.gamma.com
5 0.0643 1 0 http://www.rho.com
4 UCAS SEP网站的结构
4.1 基本原理
考虑一个算法，它从一个网站开始，自动访问其他网页，尝试在网页上进行访问，直到它已经访问了n个网页。将这个算法多次执行后，就可以根据访问的结果给出一定范围内网络的URL和超链接矩阵。通过PageRank可以给出网页的排序，同时也能绘制出网络的拓扑结构图。
通过这种算法就可以很快的得知网站的权重和结构关系，某种程度上，这些关系能够反映维护网站的机构内部组织结构。
4.2 实现方法
Moley在Matlab中创建了函数surfer ，通过命令[U,G]=surfer('http://www.xxx.zzz',n)
系统可以从该URL开始，尝试在网页上进行访问，直到它已经访问了n个网页。
如果运行成功，它会返回一个$n\times 1$的URL数组U和一个$n\times n$的系数连接矩阵G。
实际上，自动访问网络是非常麻烦的，因为一些URL包含非法字体和访问错误。而且这个功能很容易被一直在响应的网页给卡住。这种访问非常消耗电脑内存，有时会导致软件无法响应。我在对www.baidu.com进行实验时曾多次发生这种情况，因此最后选用规模相对较小的UCAS 教务系统。
对返回的U，G数据，本文主要对他们进行绘图和PageRank的处理，得到网站的拓扑结构。
4.3 实验数据
执行访问操作，并打印超链接矩阵，其中(i,j)处的点代表从网站i到网站j存在超链接
[U,G]=surfer('http://sep.ucas.ac.cn/',500);
spy(G)%plot the Linking Matrix
其中存在着一条线和一些方块，线代表有大量的网站都指向到某几个特殊的网站，而方块则说明某些网站之间两两有连接，在局部形成了一个完全互通的网络结构。
执行排序»>PageRank(U,G,0.85)
这得到的是这个500个网站最后的概率分布直方图，可以看到其中存在一些“尖峰”和“高原”，这暗示着存在着某些主网站和并列网站，
通过操作
M=digraph(G) %convert G into graph M
plot(M,'NodeLabel',{},'NodeColor',[0.93 0.78 0],'Layout','force');
title('Websites linked to http://sep.ucas.ac.cn/')
得到了UCAS SEP的网站拓扑图，其中存在一些很特别的结构。
右图标出了最初的访问SEP访问网址。
下面是一些特殊结构
a) 一个节点，与它连接的大多数节点都指向它
b) 一个非常复杂的网络结构，彼此之间有很多的联系
4.4 讨论
对于a)，通过查询U中对应的URL:106后，我发现这个网站URL为http://www.moe.gov.cn/jyb_xwfb/xw_zt/moe_357/jyzt_2020n/2020_zt26/
它仅有1个向外的链接，而其他的全是指向它的链接。
打开后出现的页面是教育部“我和我的学校微视频接力活动”主页面。
这个网页内置了多个视频，每个视频都有一个返回这个主页的链接，因此呈现出这个放射结构。
对于b)，其中存在一个网页，它指向了45个链接，但只有一个链接指向它。查询的URL为http://www.bing.com/search
啊！是一个搜索引擎，难怪如此！
类似的，继续观察可以看到，两个巨大的团簇的域名中都包含USTC字样，说明是中科大的网站。
4.4 最终结果
最后，通过简单的聚类分析，可以大致得到一个网络“势力范围”图，其中的缩写分别代表
UCAS:UCAS
CAS：中科院
USTC: 中科大
PKU：北大
HIT：哈工大
MOE：教育部
给出的前五名最高分网站分别为
http://fgy.ustc.edu.cn %中科大首页-旧版网站
http://fc.ustc.edu.cn %中科大首页
http://www.ustc.edu.cn %中科大门户
http://www.moe.gov.cn %教育部首页
http://member.hit.edu.cn/main.htm %中国学位与研究生教育学部（网站备注为哈尔滨工业大学研究生院）
5 总结与展望
本文从排序算法出发，用Matlab进行了简单实验，以UCAS SEP教育网为起点，绘制了相关网站的结构图，得到了一些有趣的结论，最后得到的“势力范围”图可以做很多有趣的解读，例如“果壳”这所新生大学和中科大这所老牌大学的亲缘关系、中科院和教育部在其中的作用，北大、哈工大等友校与他们的交流互通……
在撰写这篇文章时，也看到了其他的一些网站的结构图。
做一个对比，右边是Matlab公司Mathwoks的网站结构，整体结构有序、对称。
直观来看，有序更容易带来高效，国内高校网站的复杂和无序的结构，与校园网络缓慢、容易溃之间是否存在显著的关联？对网站结构的不重视是否会给信息社会的建设埋下隐患？这些问题已经完全超过了这篇文章所能覆盖的范围，但引发了我的极大兴趣，希望之后还能做进一步的分析。
6 参考资料
本文主要参考了Math-Work网站提供的GooglePage-Rank文档和相关的Matlab工具包教程文档。
特别感谢中国科学院数学与系统科学研究院应用数学研究所所长，量子计算与量子信息处理研究中心主任-骆顺龙老师的教学PPT Markov-链-III.-Google-PageRank ，它让我明白了PageRank的工作原理。