向量 Vector 的空间

在web graph中，什么样的网页是popular的，也许有人说，PageRank高的是popular的。不过PageRank还是有很多缺点的。我们研究发现，popular网页有两个特征： 1. popular的网页和大多数网页的距离都很近 2. popular的网页和其他的网...

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

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

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

最近准备就前一段时间对复杂网络的研究做一个总结，先写一个目录吧。 1. 网络属性的度量 network properties 2.网络中的随机游走 random walk 3. 网络中的排名 rank and centrality 4.网络的划分 network partitio...

web graph一天比一天的大，传统的网络分析算法越来越不适应分析大规模的webgraph。90年代后期提出的multilevel方法是处理large scale network的一个比较实用的方法，它通过Graph Matching进行Graph Coarseing，来将图简...

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

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

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

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

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

自从PageRank算法产生以来，它已经被用到越来越多的地方。一般来说，有Graph的地方就有PageRank。 PageRank是一个基于图的排名算法，这一算法很像选举政治，一切实体的地位由投票决定。 有了图的rank算法，现在的主要问题就是如何把我们需要rank的东西转化为G...