最近准备就前一段时间对复杂网络的研究做一个总结，先写一个目录吧。
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-15
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
订阅：
博文 (Atom)
