3.6 跨网络链接预测的研究

在线社交网络已取得飞速发展，众多网站，如Facebook（脸书）、Twitter 以及国内的新浪微博、人人网、腾讯网等迅速崛起。其中，Facebook 的用户数已经达到14亿，成为世界人口最多的“国家”，这些用户每月花在 Facebook 上的时间超过 6.4 亿分钟；Twitter 用户数也达到 6.4 亿。微信和微博是国内在线社交网络的两个代表，用户数也分别达到5.4 亿和 2.4 亿；阿里巴巴在双 11 节创下 24 小时912 亿元的成交额（见表 1）。

表 1 几个主要在线社交网站基本统计数据所有这些数据显示，在线社交网络已经成为网络信息空间和人类物理世界连接不可或缺的桥梁。在线社交网络发展的另一特点是百花齐放，这里1列出了近 400 个比较活跃的社交系统，用户分布在不同社交网络中，同时为了满足不同需求在不同社交网络中分别注册不同账号。一个初步统计表明，用户平均加入的社交网络数量是 8。针对美国用户的统计分析2表明，近 2/3 的美国成人使用如Facebook、Twitter、MySpace 或者 LinkedIn 等社交网络来和朋友、家人以及商业伙伴保持联络。从研究的角度，这一方面为研究提供了海量数据；另一方面由于用户数据分布异构在不同的社交网络，这也为研究带来很多新的挑战。其中一个技术挑战是，我们能设计一个方法将不同社交网络自动链接起来吗？该问题即跨网络链接集成（预测） [1] 。

跨网络链接预测事实上带来很多针对传统研究问题的思考。例如信息抽取，这是 Web 挖掘、自然语言处理、模式识别等多个领域的一个核心问题。传统的研究思路一般是首先找到目标页面，然后从其中抽取相关信息，如图 1(a) 所示，如果需要抽取Jeannette Wing 博士的个人信息，可以首先找到她的个人主页，然后从其中抽取职位、联系信息、教育经历等信息。然而在线社交网络的快速发展带来三个改变，第一个改变是这些语义信息更加异构且分布在不同数据源；第二个改变是信息更加结构化，很多信息在某些数据源可能是无结构，但在另一些数据源却已经是结构化的数据；第三个改变则是不同数据源数据的时效性不同。从跨网络链接预测的角度来看，获取信息的主要办法不再是单纯的抽取，而更重要的是如何自动链接不同数据源，并从其中识别哪些语义数据是有效的。例如 Talent 系统通过整合散落在多个网络的用户信息，为雇主提供了更全面的用户画像[2] 。图 1(b) 从网络的角度给出异构网络链接的示例，这表明在跨网络链接预测中，不仅需要考虑数据本身，还需要考虑网络拓扑结构，以及多个网络之间的一致性问题。

跨网络链接和传统单网络中的链接预测不同，链接预测是社交关系挖掘研究领域的一个重要研究课题，多年来受到多个领域的广泛关注。但目前大部分链接预测的研究对象是单一网络，主要预测和推荐单个网络中未知的链接，研究新链接的形成机理，讨论链接预测的方法、模型和应用。以手机通讯网络为例，在单个通讯网络内部可以预测用户和用户之间通信链接的建立；而跨网络链接预测，则可以通过某运营商内部用户的通信关系和部分与其他运营商用户的通信关系，成功地预测其竞争对手80% 以上的用户通信关系[3] 。通过主题模型，实现专利与产品的匹配，以及中英文 Wiki 页面匹配。对比传统方法，两个应用中分别可以提高 19.8% 及7.1% 的实体匹配准确率[4] 。

本文将从问题描述、主要方法和未来展望几个方面简要介绍跨网络链接预测问题的研究。