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,我们可以对测试集中的大多数图得出比较好的结果。
2008-10-03
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的发图片功能在我们看来多么方便，但另人难以置信的是，居然很多人不会用，天哪！！
所以在中国做网站，首页就要考虑网站的易用性，是否好用，很多网站的设计过于复杂。
网站的易用性很大程度上决定网站是否成功，而技术人员永远没有资格来评价一个网站的易用性，在街头随便找一个大妈，都比我们有资格来讨论网站的易用性，我们的作用就是虚心听他们说什么，而不是鄙视他们水平怎么这么烂。
2007-10-22
cindoo收录网站的原则
很多人注意到cindoo并不索引所有的网站，这是因为，我们注意到当今的网络上，最不缺的就是信息。而且cindoo不准备像google那样，做一
个找到所有网站的引擎，而是把一些比较有用的信息组合起来供大家观看。
这个就像很多门户网站的新闻专题一样，比如在cindoo可以搜nba，姚明什么的，里面有关于他们的很多内容。大家完全可以把我们的姚明空间看作一个
姚明的专题。和门户网站相比，我们来源很广，而且有很多不同类型的信息(新闻，博客，视频，BBS)
所以cindoo和google baidu是不一样的，他们之间的功能没有重合的地方，cindoo注重新的信息，google baidu比较注重
静态的信息。google baidu比较适合于想找到某个问题的人。而cindoo适合于那些对某个领域关心的人。比如你对nba关心，你就可以搜索
nba,各个球队,在里面你们肯定可以找到很多你们感兴趣的信息。
在cindoo中，我们只收录那些比较可靠的信息来源，这种可靠性来自大家的口碑，如果很多人觉得他好，才会被收录。
所以在cindoo中，是不会有垃圾网站的
个找到所有网站的引擎，而是把一些比较有用的信息组合起来供大家观看。
这个就像很多门户网站的新闻专题一样，比如在cindoo可以搜nba，姚明什么的，里面有关于他们的很多内容。大家完全可以把我们的姚明空间看作一个
姚明的专题。和门户网站相比，我们来源很广，而且有很多不同类型的信息(新闻，博客，视频，BBS)
所以cindoo和google baidu是不一样的，他们之间的功能没有重合的地方，cindoo注重新的信息，google baidu比较注重
静态的信息。google baidu比较适合于想找到某个问题的人。而cindoo适合于那些对某个领域关心的人。比如你对nba关心，你就可以搜索
nba,各个球队,在里面你们肯定可以找到很多你们感兴趣的信息。
在cindoo中，我们只收录那些比较可靠的信息来源，这种可靠性来自大家的口碑，如果很多人觉得他好，才会被收录。
所以在cindoo中，是不会有垃圾网站的
2007-10-19
订阅：
博文 (Atom)
