网络的划分 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

未完待续...

网络中的排名 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

网络属性的度量 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的结果还原到原图上。下面是一些结果。

一个PHP+MYSQL的搜索引擎解决方案

帮同学弄了个网站，NBA搜索网站 http://www.8gnba.com/

因为NBA的领域比较小，而且服务器资源有限，所以没有采用C++的方案，而且直接用PHP来完成搜索网站的几个核心步骤：爬虫，html解析。用MYSQL来完成网页的索引和查询。

网页数据库只索引了网页的标题，所以用MYSQL就可以快速的进行查询。

系统的难点主要是爬虫和html的解析，爬虫主要是利用的php可以读取url文件。
至于HTML的解析，主要是用到了php的正则表达式的库。

这种PHP+MYSQL的搜索引擎比较适合小规模的垂直搜索，对某个小领域的搜索，特别适合于对某个新闻话题，就比如美国的救市什么的。主要是他的部属很快，比装一个discuz简单，爬虫的开启什么的都是在网页上进行，后台控制也是在浏览器上进行。

多分辨率的图分割 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,我们可以对测试集中的大多数图得出比较好的结果。