计算机学院学术论坛报告
Academic Forum on Computer Science and Technology
特邀报告 第98期（总第231期）

主题报告：小世界现象与科学研究的道路
报  告  人：李晓明 教授 [北京大学]
报告时间：10月19日（周五）13:30～14:30
报告地点：上海大学宝山校区(东区)计算机学院大楼1106室
邀  请  人：张武 教授
报告摘要：
        1967年，社会心理学家Stanley Milgram发表了他的小世界实验文章。"六度分隔"之类，不仅成为诸多科学领域共同关注的对象，甚至也成为街谈巷议的内容。显然，Milgram的这项实验研究为人们带来了一种具有比较普遍意义的新知识，扩大了人类生活的词汇。
        在大规模社交网络中，节点度数相对很小，但任何两个节点之间居然存在丰富的短路径，这是一个令人惊奇的现象。人们不断探求其背后的原因。直到1998年，Watts和Strogatz给出了一个社会网络理论模型（Nature），比较好地解释了其中的必然性。
        然而，Milgram实验还蕴含着人们较少提到的第二个惊奇：那些信件居然能沿着短路径到达目的地。Watts-Strogatz模型不能对此给予合理解释。事实上，按照他们的模型，尽管两个节点之间存在丰富的短路径，但在该网络上进行"分散搜索"所导致的路径通常很长。2000年，Kleinberg发表文章（Nature），推广了Watts-Strogatz模型，解释了这第二个惊奇的必然性。
        在Watts-Strogatz-Kleinberg模型中有一个基本的参数q，它是刻画社会网络中弱连接跨距的一个概率性指标，模拟表明q=2是最优的（即最有利于导致短路径的分散搜索）。但那只是模拟的结果，成熟的现实社会网络中是这样吗？
        2005年，利用一个含有用户地理位置信息的在线社交网络（LiveJournal）的数据，Liben-Nowell等发表文章（PNAS），表明OSN上的情形与理论模型中的q=2相当吻合。同样也是2005年，利用惠普实验室人员的email数据和组织机构信息，Adamic和Adar发表文章（Social Networks），表明现实社会网络的确也有这种性质。这些工作所提供的证据表明：我们很可能发现了关于社会网络的一个普适常数。社会网络，微观上随机演变的一种结构，宏观上实现了一个确定的优化参数，亦即人们局部随机的社会活动完成了一种全局优化的计算（社会计算？）
        上述，跨40年，生动地体现了一个重要概念研究与发展的学术历程。

报告人简介:
        李晓明，北京大学教授、校长助理、副教务长，教育部计算机专业教学指导委员会主任，中国计算机学会副理事长， IEEE高级会员。最近几年对计算机科学与社会科学的跨学科研究和教学很感兴趣。曾主持发展了全国高校最大的互联网信息搜索引擎，"天网搜索"，出版了《搜索引擎：原理、技术与系统》（科学出版社，2005，2012）；提出了收集存储并系统研究中国网页历史信息的理念，发起并主持建设了"中国网络信息博物馆"；出版了教材《计算机网络与互联网》（机械工业出版社，2009），《计算机系统平台》（清华大学出版社，2009），译著《万维网的定律》（北京大学出版社，2009）和《网络、群体与市场》（清华大学出版社，2011年）。李晓明现在是《Concurrency and Computation: Practice& Experience》（John Wiley），《Journal of Web Engineering》（Riton），《Networking Science》（Springer）等学术刊物的编委。