4．0 国际专业著名刊物
ACM Transactions on Information Systems （TOIS）
ACM Transactions on Database Systems (TODS)
ACM COMPUTING SURVEYS
IEEE/ACM TRANSACTIONS ON NETWORKING
IEEE JOURNAL OF SELECTED AREAS IN COMMUNICATIONS
IEEE Transactions on Knowledge & Data Engineering (TKDE)
Journal of Data Mining & Knowledge Discovery (JKDD)
Data and Knowledge Engineering(DKE)
VLDB Journal (VLDBJ)
Information Processing and Management（IP&M）
3．5 国际专业著名刊物
ACM Transaction on Storage
IEEE Transactions on Parallel Distributed Systems (TPDS)
IEEE Transactions on Computer
ELSEVIER JOURNAL OF NETWORK AND COMPUTER APPLICATIONS
Intl Journal of Concurrency and Computation
Intl Journal of Parallel Distributed System
Intl Journal of Computer Networks
Bioinformatics
3.0国际专业著名刊物
ACM TRANSACTIONS ON COMPUTER SYSTEMS
ACM TRANSACTIONS ON SENSOR NETWORKS
ACM COMPUTER COMMUNICATION REVIEW
ACM JOURNAL OF THE ACM
IEEE Transactions on Computer
IEEE NETWORK
IEEE INTERNET COMPUTING
IEEE TRANSACTIONS ON MOBILE COMPUTING
IEEE WIRELESS COMMUNICATIONS
IEEE TRANSACTIONS ON COMPUTERS
ELSEVIER ad hoc networks
ELSEVIER computer networks
ELSEVIER JOURNAL OF NETWORK AND COMPUTER APPLICATIONS
ELSEVIER Journal of Network and Computer Applications
ELSEVIER Pervasive and Mobile Computing
SPRINGER WIRELESS NETWORKS
SPRINGER MOBILE NETWORKS & APPLICATIONS
Journal of Computer Networks
3．0 国际专业品牌刊物
ACM Intl Symposium on Modeling, Analysis and Simulation of Wireless and Mobile Systems (MSWiM)
ACM ACM TRANSATIONS ON INTERNET TECHNOLOGY
IEEE Transactions on vehicular technology
IEEE Transactions on Computer
ELSEVIER computer communications
ELSEVIER AD HOC AND SENSOR NETWORKS
JOHN WILEY&SONS INC NETWORKS
JOHN WILEY&SONS INC WIRELESS COMMUNICATIONS
Data and Knowledge Engineering (DKE)
Information Systems (IS)
WORLD WIDE WEB Journal
Knowledge and Information Systems (KIS)
Information Retrieval
Journal of Web Semantics
SIGMOD Record
Journal of Computer Networks
Journal of Software and Systems
2．0 国际有一定知名度的刊物/国内重要期刊
Intl Journal of Information Technology，
Journal of Information Science，
Journal of Computer Science and Technology,
Journal of Web Engineering
JOURNAL OF COMPUTER SCIENCE AND TECHNOLOGY （JCST）
KICS JOURNAL OF COMMUNICATIONS AND NETWORKS
IEICE TRANSATION ON COMMUNICATIONS
《中国科学》
《科学通报》
2008-12-28
2008-12-22
互联网是宇宙吗？
如果我们把互联网看成一个宇宙，那么网站就是星系，网页就是恒星。
不过这个还是有点问题，门户网站可以看做一个星系，但是google呢？google和很多搜索引擎，网页目录一样，他们有点像一个核，指向了大多数网站。
最近有研究显示，银河系中心有一个黑洞，而这个黑洞的引力是的银河系的其他恒星围绕这个黑洞旋转。这个模型很适合互联网，而这个黑洞对应了互联网的核。很多重要的网站都在这个核里面。
对于任何有核的结构，比如原子，大家会对核的分裂很感兴趣。如果我们随机的删去核中网页的超级链接，那么这个核是分成几个差不多大的核，还是分成一个大的核已经很多很小的核？
实验表明，是分成一个大的核和很多很小的核。所以，对于互联网的核，不可能一刀劈两半，只能一层层的削，每削一刀，一些不重要的网站就从核中分离出去了。
下面是互联网的结构图，包含了20w个网站，而中间那些红点，是诸如google，sina，baidu，yahoo那些网站
不过这个还是有点问题，门户网站可以看做一个星系，但是google呢？google和很多搜索引擎，网页目录一样，他们有点像一个核，指向了大多数网站。
最近有研究显示，银河系中心有一个黑洞，而这个黑洞的引力是的银河系的其他恒星围绕这个黑洞旋转。这个模型很适合互联网，而这个黑洞对应了互联网的核。很多重要的网站都在这个核里面。
对于任何有核的结构，比如原子，大家会对核的分裂很感兴趣。如果我们随机的删去核中网页的超级链接，那么这个核是分成几个差不多大的核，还是分成一个大的核已经很多很小的核？
实验表明，是分成一个大的核和很多很小的核。所以，对于互联网的核，不可能一刀劈两半，只能一层层的削，每削一刀，一些不重要的网站就从核中分离出去了。
下面是互联网的结构图，包含了20w个网站，而中间那些红点，是诸如google，sina，baidu，yahoo那些网站
这个图经过了1周的迭代，现在已经变成了下面这个样子，这个样子看起来很像一个圆盘
我们将PageRank前10000名的网站标成了黄色。
2008-12-02
Web Crawler 爬虫的困惑：下一步走向何处
最简单的表述，爬虫的作用就是从一个起始页面开始，抓取整个互联网。但是，互联网太大了，一个爬虫显然不可能抓取整个互联网。那么最简单的想法是，先抓取比较重要的网页，然后再抓取比较不重要的网页，同时比较频繁的更新重要的网页。
这样问题就出来了，爬虫怎么知道什么网页是重要的？也许有人说，不是有pagerank算法吗？但是，pagerank是在爬下网页后根据网页之间的超级连接计算出来的，现在爬虫什么也没爬，他怎么知道互联网的拓扑结构。
我们可以把互联网定义为一个世界，而爬虫相当于在一个世界中的探索者，在一开始，爬虫对这个世界一无所知，这时他只能在这个世界中盲目的走来走去，但是他每走一步，都会加深对这个世界的认识，我们把这种认识称为爬虫眼中的世界。所以，在爬虫研究中，最重要就是，如何根据爬虫眼中的世界去判断下一步走向哪里？
那么，就出现了几种不同的爬虫：
1) 广度优先搜索爬虫(BFS)
这种爬虫永远盲目的走下去，他不会利用它已经获得的知识，就是不停的爬...
2) 反向链接爬虫(BackLink)
这种爬虫在走下一步之前，先根据已经掌握的知识，判断在候选链接中那个链接可能会有比较大的反向链接数，然后就选择那个链接爬下去...
3)pagerank爬虫
这种爬虫更聪明一点，他在判断下一步走向哪里前，先根据现有的知识，将候选链接中每个链接的pagerank计算出来，然后选择那个链接爬下去...
这3种爬虫是爬虫界的典型代表，也许大家觉得，效果最差的应该是BFS爬虫，因为这种爬虫很懒，不会利用自己已经获得的知识，其实这种认识是错误的。 根据研究发现，在很多情况下，效果最差的可能是BackLink爬虫，why？
这是因为，互联网拓扑结构实在是太复杂了，一点点知识用不好还不如不用。BackLink爬虫经常会陷入到局部极小。举一个例子，一个backlink爬虫某一天爬进了新浪网，在里面爬了一段时间，他忽然发现，这个网站太好了，很多页面都有比较大的backlink，于是这个爬虫就在sina里不停的爬，由于sina实在是很大，于是这个爬虫便乐不思蜀，永远也不从sina里出来了，而在他眼里，sina似乎就是整个世界。
所以，如何利用爬虫眼中的互联网去估计整个互联网还是很困难的，难就难在互联网实在是太大了。很多算法，稍不注意就会像上面的例子那样限入到以偏概全的错误中去。但是，如果老是盲目的爬下去，似乎又对不起已经获得的一些知识，所以，如何运用已知世界去预测未知世界，是爬虫遇到的最大困难.
那也许有人要问，现在的搜索引擎爬虫不是都爬的挺好的吗，没发现有上面的问题啊。这是因为，在一个搜索引擎系统中，利用了团结就是力量的道理。在一个真正的搜索引擎中，不会只有一个爬虫在爬，而是成千上万个爬虫从互联网的不同角落开始爬，而每爬一段时间，他们还会互相交流一下自己对互联网结构的看法。所以即使一个爬虫会不时的陷入局部极小，但其他爬虫能够把它从坑中拉出来。在这种设计下，一帮很弱的兵整合在一起就会形成一个有战斗力的部队。
但是，对单一爬虫的研究还是很重要的，如果每个爬虫都很强大，那么把他们组合起来，将是一个更强的的部队。
下面这个例子可以很好的说明几种爬虫的区别
这是我们正在研究的爬虫，他能够对世界产生一个整体的认识，而不会局限到某一个聚类中
Best First 可以看到这种爬虫是爬完一个聚类爬下一个，很难形成对世界的整体认识
Bread First 这种爬虫比Best好一点，但效果取决于网页的顺序
这样问题就出来了，爬虫怎么知道什么网页是重要的？也许有人说，不是有pagerank算法吗？但是，pagerank是在爬下网页后根据网页之间的超级连接计算出来的，现在爬虫什么也没爬，他怎么知道互联网的拓扑结构。
我们可以把互联网定义为一个世界，而爬虫相当于在一个世界中的探索者，在一开始，爬虫对这个世界一无所知，这时他只能在这个世界中盲目的走来走去，但是他每走一步，都会加深对这个世界的认识，我们把这种认识称为爬虫眼中的世界。所以，在爬虫研究中，最重要就是，如何根据爬虫眼中的世界去判断下一步走向哪里？
那么，就出现了几种不同的爬虫：
1) 广度优先搜索爬虫(BFS)
这种爬虫永远盲目的走下去，他不会利用它已经获得的知识，就是不停的爬...
2) 反向链接爬虫(BackLink)
这种爬虫在走下一步之前，先根据已经掌握的知识，判断在候选链接中那个链接可能会有比较大的反向链接数，然后就选择那个链接爬下去...
3)pagerank爬虫
这种爬虫更聪明一点，他在判断下一步走向哪里前，先根据现有的知识，将候选链接中每个链接的pagerank计算出来，然后选择那个链接爬下去...
这3种爬虫是爬虫界的典型代表，也许大家觉得，效果最差的应该是BFS爬虫，因为这种爬虫很懒，不会利用自己已经获得的知识，其实这种认识是错误的。 根据研究发现，在很多情况下，效果最差的可能是BackLink爬虫，why？
这是因为，互联网拓扑结构实在是太复杂了，一点点知识用不好还不如不用。BackLink爬虫经常会陷入到局部极小。举一个例子，一个backlink爬虫某一天爬进了新浪网，在里面爬了一段时间，他忽然发现，这个网站太好了，很多页面都有比较大的backlink，于是这个爬虫就在sina里不停的爬，由于sina实在是很大，于是这个爬虫便乐不思蜀，永远也不从sina里出来了，而在他眼里，sina似乎就是整个世界。
所以，如何利用爬虫眼中的互联网去估计整个互联网还是很困难的，难就难在互联网实在是太大了。很多算法，稍不注意就会像上面的例子那样限入到以偏概全的错误中去。但是，如果老是盲目的爬下去，似乎又对不起已经获得的一些知识，所以，如何运用已知世界去预测未知世界，是爬虫遇到的最大困难.
那也许有人要问，现在的搜索引擎爬虫不是都爬的挺好的吗，没发现有上面的问题啊。这是因为，在一个搜索引擎系统中，利用了团结就是力量的道理。在一个真正的搜索引擎中，不会只有一个爬虫在爬，而是成千上万个爬虫从互联网的不同角落开始爬，而每爬一段时间，他们还会互相交流一下自己对互联网结构的看法。所以即使一个爬虫会不时的陷入局部极小，但其他爬虫能够把它从坑中拉出来。在这种设计下，一帮很弱的兵整合在一起就会形成一个有战斗力的部队。
但是，对单一爬虫的研究还是很重要的，如果每个爬虫都很强大，那么把他们组合起来，将是一个更强的的部队。
下面这个例子可以很好的说明几种爬虫的区别
这是我们正在研究的爬虫，他能够对世界产生一个整体的认识，而不会局限到某一个聚类中
Best First 可以看到这种爬虫是爬完一个聚类爬下一个，很难形成对世界的整体认识
Bread First 这种爬虫比Best好一点，但效果取决于网页的顺序
2008-11-02
网络中顶点相似度的计算 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
未完待续...
相似度图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
未完待续...
2008-10-22
网络的划分 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
未完待续...
我们给顶点一个标号，如果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
未完待续...
2008-10-20
网络中的排名 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
所谓网络排名其实就是计算各个顶点的重要程度，一个顶点如果和很多顶点拥有联系，无疑是比较重要的，这个思想就产生了最简单排名：根据顶点的度排名，也就是说
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
2008-10-15
网络属性的度量 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. 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
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
2008-10-09
Multilevel Graph Layout
web graph一天比一天的大，传统的网络分析算法越来越不适应分析大规模的webgraph。90年代后期提出的multilevel方法是处理large scale network的一个比较实用的方法，它通过Graph Matching进行Graph Coarseing，来将图简化，然后在简化图上利用传统的方法来解决实际问题，最后将小规模图的结果映射到大规模图上。
MultiLevel Graph Layout 主要是首先对小规模图layout，然后将layout的结果还原到原图上。下面是一些结果。
MultiLevel Graph Layout 主要是首先对小规模图layout，然后将layout的结果还原到原图上。下面是一些结果。
2008-10-04
一个PHP+MYSQL的搜索引擎解决方案
帮同学弄了个网站，NBA搜索网站 http://www.8gnba.com/
因为NBA的领域比较小，而且服务器资源有限，所以没有采用C++的方案，而且直接用PHP来完成搜索网站的几个核心步骤：爬虫，html解析。用MYSQL来完成网页的索引和查询。
网页数据库只索引了网页的标题，所以用MYSQL就可以快速的进行查询。
系统的难点主要是爬虫和html的解析，爬虫主要是利用的php可以读取url文件。
至于HTML的解析，主要是用到了php的正则表达式的库。
这种PHP+MYSQL的搜索引擎比较适合小规模的垂直搜索，对某个小领域的搜索，特别适合于对某个新闻话题，就比如美国的救市什么的。主要是他的部属很快，比装一个discuz简单，爬虫的开启什么的都是在网页上进行，后台控制也是在浏览器上进行。
2008-10-03
多分辨率的图分割 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,我们可以对测试集中的大多数图得出比较好的结果。
目前有这方面的专门工具，比如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,我们可以对测试集中的大多数图得出比较好的结果。
2008-09-26
2008-09-18
图可视化工具 GLDF : Graph Layout tool
GLDF : Graph Layout by Directed Force
最近一直在研究复杂网络的问题，可视化是复杂网络中的一个重要工具，Directed Force的可视化算法可以显示出网络中的一些结构，比如聚类结构。
为此写了一个可视化工具，用的 Qt for windows. 可以移植到Linux下面。可以处理10000个顶点的图的可视化（在普通PC机上测试），支持鼠标的拖动，选择等交互。支持PNG图像文件的导出
运行时间
顶点数 500 1秒
1000 10秒
10000 1-2分钟
20000 5-6分钟
主要算法
1. Force Derected Layout
2.对于大规模图， 使用了网格优化
下载地址 http://i.cindoo.com/GLDF.zip
目前这个工具除了可视化，还支持 MultiLevel graph partition， 并提供了多种随机图的模型
下面是该工具的截图
百度贴吧中的社会网络：
普通的几何图
互联网
其他的一些图结构
最近一直在研究复杂网络的问题，可视化是复杂网络中的一个重要工具，Directed Force的可视化算法可以显示出网络中的一些结构，比如聚类结构。
为此写了一个可视化工具，用的 Qt for windows. 可以移植到Linux下面。可以处理10000个顶点的图的可视化（在普通PC机上测试），支持鼠标的拖动，选择等交互。支持PNG图像文件的导出
运行时间
顶点数 500 1秒
1000 10秒
10000 1-2分钟
20000 5-6分钟
主要算法
1. Force Derected Layout
2.对于大规模图， 使用了网格优化
下载地址 http://i.cindoo.com/GLDF.zip
目前这个工具除了可视化，还支持 MultiLevel graph partition， 并提供了多种随机图的模型
下面是该工具的截图
百度贴吧中的社会网络：
普通的几何图
互联网
其他的一些图结构
2008-08-24
2008-05-08
网站日志系统的设计（二）
假设我们需要统计的网页是a.html 日志的js文件叫 log.js
那么我们只要在a.html的</body>前面加入以下代码
<script src=log.js type="text/javscript"></script>
下面就是考虑log.js文件的设计了。
如果用户在a.html进行了某些行为，被log.js捕捉到了，log.js需要将这一个行为通知一个php文件，php文件复制将这一个行为写入到一个mysql的数据库中。那么log.js通知log.php实现的方法就体现了script方法和ajax方法的区别。
如果a.html log.js和log.php 是在同一个域名下面的，就可以用ajax，但如果不是就只能用下面的方法了。
先看一下sendLog的代码：
function sendLog(act)
{
var s = document.createElement("script");
s.type = "text/javascript";
s.src = "http://xxx.xxx.xxx.xxx/log.php?screen="+scr+"&page="+page+"&act="+act+"&ref="+ref+"&t="+title;
document.getElementsByTagName("head")[0].appendChild(s);
}
那么我们只要在a.html的</body>前面加入以下代码
<script src=log.js type="text/javscript"></script>
下面就是考虑log.js文件的设计了。
如果用户在a.html进行了某些行为，被log.js捕捉到了，log.js需要将这一个行为通知一个php文件，php文件复制将这一个行为写入到一个mysql的数据库中。那么log.js通知log.php实现的方法就体现了script方法和ajax方法的区别。
如果a.html log.js和log.php 是在同一个域名下面的，就可以用ajax，但如果不是就只能用下面的方法了。
先看一下sendLog的代码：
function sendLog(act)
{
var s = document.createElement("script");
s.type = "text/javascript";
s.src = "http://xxx.xxx.xxx.xxx/log.php?screen="+scr+"&page="+page+"&act="+act+"&ref="+ref+"&t="+title;
document.getElementsByTagName("head")[0].appendChild(s);
}
网站日志系统的设计（一）
如果要监测一个网站的流量，日志系统肯定是少不了的，可以用google analytics。但如果自己设计，可以获取更多的信息。
最简单的日志系统，是用服务器脚本，比如php来记录，这其实和apache的记录差不多。但这种方法无法跟踪用户的点击和鼠标。所以这种方法就不介绍了。
用javascript来设计网站的日志系统，可以用两种方法设计，Ajax或者script方法（这个方法没有标准的名字，所以暂时叫script方法）。
Ajax方法主要适用于记录本服务器网站的日志，这主要是因为ajax的跨域是比较困难的，我暂时还没有看到比较好的解决方法。对于一个大的网站，有几台服务器，这个方法就不好了，所以这个方法就不介绍了，估计google analytics也不是用这个方法做的。
script方法设计网站的日志系统，最终可以做出和Google一样的效果，就是只要在被统计网页中加入一个js代码，就可以统计了。这个方法的基本原理是动态的在html文件中加入script标签。
最简单的日志系统，是用服务器脚本，比如php来记录，这其实和apache的记录差不多。但这种方法无法跟踪用户的点击和鼠标。所以这种方法就不介绍了。
用javascript来设计网站的日志系统，可以用两种方法设计，Ajax或者script方法（这个方法没有标准的名字，所以暂时叫script方法）。
Ajax方法主要适用于记录本服务器网站的日志，这主要是因为ajax的跨域是比较困难的，我暂时还没有看到比较好的解决方法。对于一个大的网站，有几台服务器，这个方法就不好了，所以这个方法就不介绍了，估计google analytics也不是用这个方法做的。
script方法设计网站的日志系统，最终可以做出和Google一样的效果，就是只要在被统计网页中加入一个js代码，就可以统计了。这个方法的基本原理是动态的在html文件中加入script标签。
2008-05-02
搜索引擎输入提示的几个技术关键
很多搜索引擎都有输入提示，比如google,迅雷等等。这两天我也实现了一个，如下图。
实现这个功能有以下关键：
1.有一个常见搜索的词典，可以存在mysql中。这样根据用户已经输入的字，可以通过mysql 的like查询获得待选结果。
2.一个php文件把待选结果显示成html的格式
3.利用ajax获得php的返回结果，然后控制待选框的div的innerHTML的事件显示
4.处理好输入框,body,和待选框的onkeydown()事件
以上就是实现输入法提示的重点。如果要做的好，最重要的就是常见搜索词典的大小了，查询词越多，结果越好。
实现这个功能有以下关键：
1.有一个常见搜索的词典，可以存在mysql中。这样根据用户已经输入的字，可以通过mysql 的like查询获得待选结果。
2.一个php文件把待选结果显示成html的格式
3.利用ajax获得php的返回结果，然后控制待选框的div的innerHTML的事件显示
4.处理好输入框,body,和待选框的onkeydown()事件
以上就是实现输入法提示的重点。如果要做的好，最重要的就是常见搜索词典的大小了，查询词越多，结果越好。
2008-04-28
2008-02-29
2008-01-12
从中国互联网用户开网站的可用性设计
做了1年多的互联网，也和网民打了一年多的交道，最大的体会就是，普通网民的能力怎么低估都是没错的，一个技术设计者往往过于高估普通网民的素质了，特别是中国网民。
我觉得，这也是百度在中国比google强的原因。很多号称做技术的人都喜欢google,因为google得很多功能都很酷，但关键是，普通网民有谁会去使用他，百度就不一样，百度做的很傻瓜式，百度贴吧，百度空间，百度知道，尽管很傻瓜式，但是很好用。百度从来不宣传自己的技术能力有多强大，因为在中国的互联网，技术对普通网民的影响太小了。
就比如在论坛发个图片，fckedit的发图片功能在我们看来多么方便，但另人难以置信的是，居然很多人不会用，天哪！！
所以在中国做网站，首页就要考虑网站的易用性，是否好用，很多网站的设计过于复杂。
网站的易用性很大程度上决定网站是否成功，而技术人员永远没有资格来评价一个网站的易用性，在街头随便找一个大妈，都比我们有资格来讨论网站的易用性，我们的作用就是虚心听他们说什么，而不是鄙视他们水平怎么这么烂。
订阅：
博文 (Atom)
