July 06, 2006
六度分隔与最短路径::[Blog]
【最短路径】
圆明园的北部有一个迷宫，据说古时候每次有庆典在圆明园的时候，皇帝会派一些宫女走迷宫，看谁最先走到迷宫内的亭子，会有不错的奖赏。
迷宫问题对数学家们来讲虽然是小儿科但在计算机课程上却非常重要，因为不同的求解会涉及到递归，广度优先和深度优先等算法。
迷宫毕竟是一个放置在2维空间的有限联系的网络，也就是说，迷宫里的每一个点，最多只和周围的4个点(上下左右)发生关系，而且这些点的位置是固定的。
六度分割通常用来描述一个广阔的社会网路（SN），现在大部分的社会网路服务都提供了搜索功能，即搜索出一个用户到达另外一个用户的最短路径，也就是找出这两个用户之间通过最少的用户的链接。
一般的SN提供的搜索都是4度的，也就是例如A-B-C-D-E 称为4度的分隔。提供5度搜索和6度搜索的几乎寥寥无几，当然一方面是5，6度分隔的用户很少，大部分的用户都应该在4度内，另外一个方面是5，6度分隔的搜索在实际计算上也涉及非常大的运算量。
【SN搜索算法】
如果说寻找两个人之间的最小分隔的路径和寻找最短路径可以类比，那么唯一不同的是SN上每个节点的联系可以非常的广阔，不只是上下左右，而是十个甚至上百个联系。这是是一个多维空间内的最短路径的寻找。假设一个用户平均有n个好友，那么粗略估计一个用户的4度好友大约有n×n×n×n＋n×n×n+n×n+n ~ n^4，无疑是一个非常恐怖的数目。因此采用传统的递归的方法显然是不大现实的。
当然，事情并非这么麻烦，有简洁的方法可以加快找到用户之间的最小分隔：不单是从一个用户搜索，而是从两个用户同时搜索，而看两个用户的2度之内的用户是否有相同：
A-B-C
E-D-C
A和E的处在在两度分隔的用户基本上数目估计都在n的平方。问题变成了比较n^2和n^2之间有没有相同，这个计算的时间等同于2×n^2的排序所需要的时间。
【SN索引】
那么能否继续加快速度？
当然可以，可以提前对用户的好友进行索引，对好友的好友进行索引，这样在未来进行关系的搜索时会大大加快：
A: {A1} {A2} A1为A的好友的集合，A2为A的好友的好友的集合
E: {E1} {E2}
那么
1度分隔为： A 属于｛E1｝，等同于E属于 {A1}
2度分隔为： A 属于｛E2｝，等同于E属于 {A2}，{A1}{E1}有共同项。
3度分隔为： {A1} ｛E2｝有共同项，等同于A属于 {E2}
4度分隔为： {A2} ｛E2｝有共同项
【SN关系的更新】
当然，发现是一个核心问题，另外一个问题就是更新，因为SN的关系不会是一成不变的，在一个活跃的SN社区里，每天用户之间的关系的更新更是可观。这里只考虑关系添加的例子：
A: {A1} {A2}
E: {E1} {E2}
当A 与 E 直接建立了好友关系后，应该说整合系统的关系全都变化了，因为这个新的关系一定会导致一些关系的短路，从而导致很多现有的关系的调整。但是因为我们只存储2度分隔以内的关系，也只关心两度分隔以内的关系，因此当发生了一个新的关系后，2度内关系的变化一定是A和E本身或者他们的一度关系的用户，再远的用户将不受这个关系的影响。
因此首先 所有｛A1｝的元素的二度分隔集合里要加上E，所有｛E1｝的元素的二度分隔集合里要加上A。
然后是二度的修正。分别加上对方的1度。
{A2} = {A2 + E1}
{E2} = {E2 + A1}
最后是一度的修正：A, E 的 一度{A1}{E1}需要加入E,A:
{A1} = {A1 + E}
{E1} = {E1 + A}
整体操作的量大约在2n次操作，比我们通常认为的要小的多 :) 。
Posted at July 6, 2006 01:22 AM by Liang at 01:22 AM | Comments (15) | TrackBack(0) | Booso!| Niu.la收藏!
这里是我在博客网的好友网络，大约40人左右。Trackback
You can ping this entry by using http://www.wespoke.com/cgi-bin/mt/mt-tb.cgi/879
Comments
美国硅谷搜索引擎专家在海外创办的Roboo儒豹手机搜索引擎公司，以创新为特长，获得风险投资(VC)支持。中国-新加坡苏州工业园区分公司急聘50人：CTO，开发副总裁VP，主任(总监)，经理，开发工程师，运维工程师，市场推广，广告销售，运营商合作，SP/CP合作，代理渠道搭建，人事行政内务等
如果你羡慕百度的辉煌和大量百度人都是千万富翁的传奇，请不要再羡慕别人了，来加盟Roboo儒豹手机搜索引擎公司吧！中国有一亿多PC用户，却有四亿多手机用户！无线移动搜索将给四亿多手机用户带来随时随地，随身随手搜索的便利，意义和影响比百度PC上的搜索还要巨大。中国十几亿人口为手机用户群提供了巨大的增长空间，前途不可估量。现在加盟儒豹，都会拥有高额股票，优厚工资，各种福利，全面保险，快速扩张中大量提职高升的机会。想干一番事业的人，快来加盟Roboo儒豹!
Roboo儒豹手机搜索引擎公司注册在海外，架构专家组在美国硅谷，每人均有世界一流搜索引擎公司工作经验。儒豹中国分公司位于美丽如画的人间天堂苏州工业园，办公室掩映在清澈绿荫的湖畔。公司创始人在清华大学无线电系获得学士，硕士，中国科学院自动化所模式识别国家重点实验室工作近三年，美国南加大(USC)获得计算机博士。博士生期间在IEEE和ACM国际一流刊物发表八篇论文，论文以创新引人瞩目而接受 LA TIMES(洛杉矶时报)采访拍照并见报，这在海外博士生中非常少见。博士毕业后在硅谷从事大型搜索引擎，海量数据挖掘等工作。公司其他创始人的从业经验包括中国移动，中国联通，掌上万维，中国航天集团等。儒豹以美国硅谷世界一流搜索专家为架构，以产品创新为特色，营造自由务实的企业文化。2006年7月面向全国寻觅人才50名，不限户口。
1. 首席技术官CTO
熟悉搜索引擎技术，五年以上搜索引擎直接经验。成为公司管理和技术核心团队，获得巨额股票。
2. 工程副总裁(VP of Engineering)
熟悉大型Web平台开发，熟悉搜索引擎平台开发。有项目组织协调能力和经验。熟悉C++或JAVA软件的设计，开发，测试，运维。成为公司管理和核心技术团队，获得高额股票。五年以上软件开发和管理经验，一年以上搜索引擎经验。
3. 技术总监(Director of Engineering)
熟悉大型Web平台，有项目组织协调能力和经验。熟悉C++或JAVA软件的设计，开发，测试，运维。三年以上软件开发和管理经验。一年以上搜索引擎知识和经验。
4. 内容获取：软件开发经理，工程师
熟悉C++或JAVA开发。熟悉HTTP GET，FTP GET，HTML文件。熟悉XML文件格式和处理。了解TCP协议。有分布式文件系统经验者更佳。经理: 三年以上软件开发经验。工程师: 两年以上软件开发经验。
5. 内容分析：软件开发经理，工程师
熟悉C++或JAVA开发。熟系内容分析，信息提取等方法。有Perl或Python等脚本编程经验更好。懂regular expression，parsing等。经理: 三年以上软件开发工作经验。工程师: 两年以上软件开发经验。
6. 索引检索：经理，工程师
熟悉C++或JAVA开发。熟悉文本内容的索引，关键词匹配，搜索结果排序。经理: 三年以上软件开发工作经验。工程师: 两年以上软件开发经验。
7. 中文信息处理：经理，工程师
熟悉中文处理技术和软件，例如中文分词，信息提取，词性标注，新词发现，同义词词典，各种词典构建，相似概念提取，标题生成，摘要生成，分类，聚类，等等。熟悉C++或JAVA开发。经理: 三年以上软件开发工作经验。工程师: 两年以上软件开发经验。
8. 前台软件：经理，工程师
熟悉前台展现和用户交互的开发，熟悉PHP或JSP。熟悉SQL数据库。最好有WML和XHTML知识和经验。注重用户体验。经理: 三年以上经验。工程师: 一年以上经验。
9. 应用开发：经理，工程师
熟悉铃声，彩铃，歌曲，图片，游戏等文件的存储，下载。熟悉C++或JAVA开发。经理: 三年以上软件开发工作经验。工程师: 两年以上软件开发经验。
10. 分布式系统软件：经理，工程师
熟悉Linux服务器，熟悉多台服务器机群软件，如机群管理，控制，负载均衡，监控等。熟悉C++或JAVA。经理: 三年以上工作经验。工程师: 两年以上工作经验。
11. 软件测试：经理，工程师
熟悉软件测试原理，会写SHELL，PERL或PYTHON脚本语言。会C++或JAVA更佳。经理: 三年以上软件测试工作经验。工程师: 一年以上软件测试工作经验。
12. 硬件系统运维：经理，工程师
熟悉Linux服务器的运维。了解大型网站平台中的问题如load balancing, monitoring等事宜。了解服务器的操作系统级问题。熟悉软件安装，更新，维护。熟悉网络设备，架构。经理: 两年以上工作经验。工程师: 一年以上经验。
13. 搜索引擎软件运维：经理，工程师
对搜索引擎的运营有经验，例如亲手做过内容收集，索引检索，前台系统等。不要求编程，若会更好。经理: 两年经验。工程师: 一年经验。
14. 市场拓展: 市场总监，市场经理，市场业务员
负责手机搜索引擎业务推广，内容合作，渠道搭建，运营商/SP/CP合作。要求了解SP行业，了解CP行业。擅长和人打交道。在全国各地或一个地区有一定市场关系的积累，并能拓展新的市场。职位: 市场总监，市场经理，市场业务员。
15. 广告客户发展
熟悉SP行业，了解CP行业。了解搜索引擎更好。擅长和人打交道。在全国各地或一个地区有一定广告客户关系的积累，并发展新的广告客户。职位: 销售总监，销售经理，销售业务员。
16. 人事行政内务: 1名
负责公司的人事招聘等行政事务，内部管理事务。细心，耐心，有条理。热情，对员工有亲和力。熟悉苏州本地情况者优先。
17. 出纳: 1名
负责公司的日常开支，报销。有其方面能力如文章写作更佳。熟悉苏州本地者优先。
18. 写作: 1名
擅长写作，文笔好，文章有见解，善于构思和捕捉生活中的话题。欢迎心理系，社会学系等专业。最好能提供以前的文稿。将负责与记者，公众，媒体的关系等。
除了以上具体列出的，每个部门都有空缺：技术研发部，产品集成部，广告销售部，渠道建设部，内容采编部，宣传稿写作组，服务器运维部，客户服务部，联盟合作部，等等。请指出适和自己的职位，把几句话介绍和完整简历发送到：jobs @ roboo .com
说的的确高屋建瓴，又学习了不少。。。
-------------------------------------------------
googler.hk 转让啦！！！要得抓紧时间哦。
呵呵 顺便打个广告，挣点小钱混口饭吃啦！
这里的googler比较多，希望能找到我心仪的买家。。。
http://www.googler.hk
Posted by: googler at July 25, 2006 05:03 PM from 60.209.153.53朋友您好，第一次来这里做客。
下午的时候因为写作需要，突发冲动，想做个blog专门的搜索引擎。
于是首先上午尝试查找国内是否已经有人在做这个项目了，转来转去，就走到这来了。
看来目前国内只有两家，除了贵公司外还有souyo在做。
以后会继续关注贵公司的成长。
祝搜索引擎越做越好。
hi,兄弟在广州就职一家企业搜索引擎公司，希望结识南方地区的对企业搜索引擎有偏好的朋友， msn:petter_ljm@msn.com,
卢亮的文章很专业顶一个。
Posted by: 牛的时代 at July 31, 2006 12:54 AM from 218.107.2.188欢迎大家来看看我的网站. http://www.epeaksoft.com
Posted by: xing006 at October 16, 2006 07:37 PM from 203.191.19.50在下没怎么接触过搜索引擎方面，且才疏学浅。但仍想提一点拙略的想法：
关于【SN搜索算法】君曰：“问题变成了比较n^2和n^2之间有没有相同，这个计算的时间等同于2×n^2的排序所需要的时间。”
我的问题：你要搜索的结果是A的好友中有没有E，还是A和E的
二层好友都有谁。如果答案是前者那么你的算法好像还没有得到答案 。 你最少还需要作一次n^2*n^2次的比较。因此我认为双向查找好像并不比单向快很多。不过的确可以减少很多提前保存的数据。
呵呵！看你们的时间都很宝贵，如果有需要 “监控”“智能管理系统”的请登陆：http://www.235689.com/jiankong.htm
Posted by: youth at November 24, 2006 02:46 PM from 125.33.123.119Think you need to live near water to need flood insurance? Think again. ... Dont get caught in rising water protect your home with flood insurance. ... http://flood-insurance.marketland.org/map.html
Posted by: flood insurance at December 11, 2006 01:39 PM from 210.22.117.100分析太好了，值得学习啊！[url=http://www.kuangzi.com]kuangzi医疗搜索[/url]
Posted by: kuangzi.com at July 19, 2007 09:13 PM from 221.217.9.246