网络中的排名 rank and centrality

排名一直是网络研究中的一个永恒不变的话题，这个研究由来已久，在上世纪60，70对社会网络的研究中就提出了排名的概念，称为centrality。用来表示一个人在社会网络中的地位。不过网络排名算法真正让大众知道却是google的pagerank提出之后，这个算法从数学上并没有太大的创新，他的思想主要源于马尔可夫矩阵的稳态计算问题，不过google赋予给这个算法的解释，诸如民主投票之类的，却让这个算法非常出名。本文主要总结一下现有的各种排名算法，并分析他们的利弊以及实现的复杂程度。

所谓网络排名其实就是计算各个顶点的重要程度，一个顶点如果和很多顶点拥有联系，无疑是比较重要的，这个思想就产生了最简单排名：根据顶点的度排名，也就是说
rank(v) = deg(v)
这个排名相当简单，不过也相当的不精确，因为它仅仅利用了顶点的本地属性，而没有对网络的整体观察，也就是说，这个排名仅仅考虑了顶点和他的几个邻居而已，属于local property,而没有考虑到顶点和他邻居意外的点之间的联系。

那么如果考虑网络的全局结构，考虑一个顶点和网络中其他所有点之间的联系，那么就出现了第二种排名，也就是基于最短路径的排名
rank(v) = |V| / sum{d(v,u) : u in V(G)}
这个定义的分母的意思是顶点v到图中所有点的最短距离和。 显然，如果一个顶点到图中其他顶点的平均距离越小，这个顶点就越靠近图的中心，比如一个圆盘，只有圆心是到所有点的平均距离最小的。上面这个排名也被称作Closeness centrality。

基于最短路径的排名定义还有graph centrality，他的定义是
rank(v) = 1 / max{d(v,u) : u in V(G)}

另外还有一种利用最短路径定义排名的方法，这中方法不利用最短路径长度，而是利用最短路径本身，考虑图中的3个顶点s,t,v. s,t之间的最短路径可能有很多条，假设有sigma(s,t)条，这些最短路径中，经过顶点v的最短路径有sigma(s,t,v)条,那么betweenness centrality定义为
rank(v) = sum{sigma(s,t,v) / sigma(s,t)}, s,t,v in V(G) and s != v != t



最短路径是图中的一个重要度量，以上三种基于最短路径的算法考虑了图的全局熟悉，可以比较精确的反应出图中顶点的重要性。但是以上三种算法的具体实现有依赖于解决全源最短路径问题(ASSP)，目前最快的ASSP的算法时间负责度是O(VElogV)，这个算法要利用二叉堆(heap)的数据结构。对于大规模图来说，这个时间复杂图显然是太高了，所以以上三种基于最短路径的排名算法在大规模网络中无法实际应用。

尽管ASSP问题的时间负责度太高，但是还是有一些基于网络采样的随机算法能够给出上述排名的估计。有些近似算法的结果还是不错的。

另外一种排名算法是基于网络中的随机游走，pagerank算法从数学上讲也属于这种算法。他的主要思想是，如果考虑在一个网络中随机游走，那么重要的顶点一定会经常访问到。通过计算每个顶点的访问概率，来确定每个顶点的重要程度。 对于网络中的随机游走，可以用网络的Markov矩阵来表示转移概率。那么每个顶点的访问概率对于与Markov的稳态分布。

我们以无向图举一个例子G(V,E)，图的Markov矩阵 M定义为
m[i,j] = 1 / deg(vi)
每个顶点的最终访问概率向量是P，那么P的稳态分布对应于
M'P = P


未完待续...

参考文献
http://en.wikipedia.org/wiki/Centrality
http://zh.wikipedia.org/wiki/Pagerank
https://nwb.slis.indiana.edu/community/?n=AnalyzeData.BetweennessCentralitySiteAmpEdge