popular网页的两个基于链接的特征

在web graph中，什么样的网页是popular的，也许有人说，PageRank高的是popular的。不过PageRank还是有很多缺点的。我们研究发现，popular网页有两个特征：

1. popular的网页和大多数网页的距离都很近
2. popular的网页和其他的网页连接很紧密

PageRank算法在上面两个特征上都有所反应，但反应的不够。

网络中顶点相似度的计算 node similarity measurement in network

Graph的一个最大好处，是他可以用尽量少的空间来存储物体(object)直接的相似度。如果我们有N个物体，要存储他们两两直接的相似度，需要用N*N的存储空间。但是用Graph可以节省很多空间，因为他可以将很多相似度隐含到网络的结构中去。

相似度图G(V,E,W).如果两个顶点直接有边连接，那么边的权重就代表两个顶点直接的相似度。那么如果两个顶点之间没有边连接呢？虽然没有边连接，但只要图是联通的，那么肯定有若干条路径连接，这就是前面所说的，顶点的相似度蕴含在图的结构当中。那么我们的相似度函数必须在考虑图的边的同时，还要考虑图中的路径。

以下是本文用到的一些记号
inv(A) : A的逆矩阵
pow(A,n) ：A的n次方

1.Katz的方法
A new status index derived from sociometric analysis 1953
如果G的邻接矩阵是A，a(i,j)是顶点i,j的相似度。那么Katz用一下的方法来度量相似度：
S = inv(I - pA) - I = pA + pow(pA,2) + ... + pow(pA,n) + ...
这个方法通过邻接矩阵的n次方来考虑图中小于n的路径。这个方法的优点是定义很简单，意义也很清楚。缺点就是，矩阵的求逆计算太耗时。 而且这个方法一次性的计算了图中所有顶点对之间的相似度，如果我们仅仅要知道两个顶点直接的相似度，复杂度就太高了。

2.RandomWalk 随机游走
这个方法首先计算出图的马尔可夫转移概率矩阵。然后在图中进行随机游走。假设从i开始随机游走，如果i,j之间有一条边，那么从i到j的转移概率是p(i,j). 那么我们考虑图中的任意一个点k，那么我们考虑如果从i出发，随机在图中游走，那么第一次走到k需要的平均步数，可以看作i,k之间的相似度。
Random-Walk Computation of Similarities between Nodes of a Graph with Application to Collaborative Recommendation. 2007 Francois Fouss


未完待续...

网络的划分 network partition

网络的划分是图研究中的一个热点，在集成电路设计中有很多应用。我们首先考虑图的平衡二分问题，也就是说给定一个图G(V,E)，把他的顶点划分成两个部分 C, V\C, 使得这两个顶点集的大小差不多，也就是|C|约等于|V\C|.而两个点集之间的边数最少，也就是 |{e(vi,vj) : vi in C and vj in V\C}|的大小最小化。

我们给顶点一个标号，如果vi属于C，那么t(vi)=0，否则t(vi)=1。那么我们定义两种边：
inter-edge(C,V\C) : {e(vi,vj) : t(vi) == t(vj)}
intra-edge(C,V\C) : {e(vi,vj) : t(vi) != t(vj)}

一般来说，图的b-二分问题定义为:
min intra-edge(C,V\C)
s.t. max{|C|,|V\C|} * 2 / |V| < b

未完待续...

网络属性的度量 network properties

考虑一个图 G(V,E)有n个顶点和m条边

1. degree distribution 顶点度的分布
p(k) = |{图中度为k的顶点数}| / n
对于大多数复杂网络，研究表明这个分布一般都满足指数形式，也就是：
p(k) = c k ^ (-r)
r是一个重要的参数，对于不同的复杂网络有不同的值。



2. clustring coefficient(cc)
对于图中的一个顶点，它的cc是用来度量这个点附近顶点的连通程度。定义cc首先要定义一个顶点处的三角形，对于一个顶点v，假设(v,x)(v,y)是图中的两条边，如果(x,y)也是图中的边，那么vxy就形成了一个三角形。
假设一个顶点v处的三角形数是 triangle(v),那么
cc(v) = triangle(v) / (deg(v)(deg(v)-1) / 2)
其中deg(v)是顶点v的度
其实这个度量表示,如果x,y和v相连，那么xy相连的概率

下面的图是一个示例


对于整个图，假设图中度大于等于2的顶点是 V' = {v1,v2,...,vs}，那么图的cc定义为
cc(G) = [c(v1)+c(v2)+...+c(vs)]/s

3.eccentricity radius(半径) and diameter(直径)
顶点v的eccentricity表示v到图中其他顶点的最远距离
ecc(v) = max{d(v,u) | u in V}
其中d(u,v)表示u到v的最短路径

图的半径rad(G)和直径diam(G)定义如下
rad(G) = min{ecc(v) | v in V}
diam(G) = max{d(u,v) | u,v in V}

4.顶点的邻居
顶点的h-邻域定义为
neigh(v,h) = {u in V | d(u,v) <= h}

复杂网络分析中的一些问题

最近准备就前一段时间对复杂网络的研究做一个总结，先写一个目录吧。

1.网络属性的度量 network properties
2.网络中的随机游走 random walk
3.网络中的排名 rank and centrality
4.网络的划分 network partition
5.网络中顶点相似度的计算 vertex similarity measurement
6.网络的马尔可夫聚类 MCL
7.网络的特征值分析 Spectral analysis of network
8.网络的可视化 Network layout
9.图匹配和网络简化 Graph matching and coraseing

Multilevel Graph Layout

web graph一天比一天的大，传统的网络分析算法越来越不适应分析大规模的webgraph。90年代后期提出的multilevel方法是处理large scale network的一个比较实用的方法，它通过Graph Matching进行Graph Coarseing，来将图简化，然后在简化图上利用传统的方法来解决实际问题，最后将小规模图的结果映射到大规模图上。

MultiLevel Graph Layout 主要是首先对小规模图layout，然后将layout的结果还原到原图上。下面是一些结果。

多分辨率的图分割 multilevel graph partition

Multilevel Graph Partition(MGP)是图分割问题的一个重要方法，比较适用于顶点数>10000的大规模图的分割。
目前有这方面的专门工具，比如METIS，可以在这里下载
http://glaros.dtc.umn.edu/gkhome/views/metis

最近我实现了一下这个算法，这个算法的主要流程如下：
1.将图G通过边塌缩算法转化为一个小规模的图 coarse graph G0
2.用常见的分割算法，比如KL,spectral算法将G0分割
3.将对G0的分割转化到图G上
4.用KL算法对最终的结果进行局部优化 refine

以上的流程是对一次MGP的描述，但是由于GP是一个NP问题，所以每次进行MGP都会得到不同的分割结果，我们可以将这些分割结果作为初始种群，在这只上使用遗传算法，这时可以得到更好的结果。

关于图分割算法的测试集可以在这里找到 http://staffweb.cms.gre.ac.uk/~wc06/partition/

利用基于遗传算法的MGP,我们可以对测试集中的大多数图得出比较好的结果。

互联网网络结构的可视化

考虑互联网链接关系的无向图

Graph Partition Archieve

很多图的测试集
http://staffweb.cms.gre.ac.uk/~wc06/partition/

Graph Cluster（图的聚类）

基于图的可视化的那个软件，完成的图的顶点的聚类，这是一个图的基本的算法。

图的可视化

我准备把那个Graph可视化的软件做的更强大一点，下面是一个动画:

耐心的等一下...

Grpah and PageRank

自从PageRank算法产生以来，它已经被用到越来越多的地方。一般来说，有Graph的地方就有PageRank。

PageRank是一个基于图的排名算法，这一算法很像选举政治，一切实体的地位由投票决定。

有了图的rank算法，现在的主要问题就是如何把我们需要rank的东西转化为Graph，现在这个是很多人研究的领域。

1. WebPage通过url形成page之间的关系，从而构成图，最早的pagerank就是基于WebPage的排名提出的
2. 实体Entity之间通过在一张网页或者一篇文章中co-occurence产生联系，这方面比较著名的研究是 polyphonet an advanced social network extraction system from the web 一文。
3. 文本的图表示，我前面也说过，可以建立句子的图，或者词的图
4. 还有语义网络...

总之，Graph-based表示比以前的向量表示前进了一步，他更多的保留了物体的信息。和向量模型一样，Graph模型也需要解决以下问题。

1. 模型的建立，特征提取。
2. 模型的匹配，也就是模型的相似度计算，这涉及到分类器的设计。