3.8 主要方法概述
跨网络链接预测方法——跨网络匹配
从更广义的角度来说，跨网络链接预测不仅可以用于上述的发现并集成同一用户在不同社交网络的不同账号[5] ，还能用于异构数据源间的实体匹配 [4]以及跨网络合作关系推荐[6]等。这里主要的挑战是跨网络之间的链接往往非常稀疏；同时由于两个网络可能高度异构，使网络间节点共性少、关联度低。
用户名匹配：最简单的方法是直接使用用户名进行匹配，或者计算不同网络之间用户名的相似度。Zafarani 等[7-8]最早提出使用用户名前缀、后缀进行不同网络用户账号匹配的问题。他们定义了一系列复杂特征，例如个人兴趣、命名模式用于描述用户账号的选择习惯。最后跨网络之间的匹配通过用户账号名字的相似度得到。Liu 等在文献 [9-10] 中进一步提出了基于机器学习的跨网络用户链接预测方法。一般来说这类研究问题都存在标注数据欠缺的问题，所以很难直接使用传统的有监督机器学习方法。Liu 等非常巧妙地利用了人名的唯一性，即将特殊的用户名（用户名唯一性度量函数）之间的映射认为是弱监督信息，训练两个网络不同特性的相关度；此外，他们还将用户属性、用户生成的文档，以及用户在不同网络中的活动集成到一个学习框架中，用于提高链接预测的精度。
融合网络拓扑结构的匹配：另一种思路则是进一步考虑网络中的拓扑结构。Kong 等[5]提出anchorlink 预测的概念，他们利用结构化的特征帮助跨网络之间的 1:1 映射。Cui 等[11] 则是直接集成了用户属性相似度和网络结构相似度，通过两者的结合来提高网络用户链接预测的精度。Tan 等[12]的方法也是集成用户属性和网络结构，但不同的是他们的方法没有直接对两者进行相加，而是将问题形式地定义在流型学习框架中，将两个网络中的用户分别映射于一个公共的低维空间，在低维空间上再计算用户的相似度，从而实现链接预测。
全局一致性的跨网络匹配：然而上述方法都没有考虑跨网络链接预测的全局性，即网络个数越来越多，网络结构越来越复杂，如果只是单纯考虑局部匹配或者网络之间的拓扑结构匹配，必然忽略跨多网络链接的全局特性。清华大学 Zhang 等[1]提出 COSNET 模型，同时考虑了多个网络的局部和全局一致性。该模型巧妙地将网络链接预测问题描述为马尔科夫场中的能量最小化问题，通过能量方程进行全局最优化，将局部和全局一致性进行了统一描述，实现了统一的优化模型，同时考虑用户配对相似度、网络关系以及多网络匹配的一致性。该方法被成功应用于学术网络挖掘系统 AMiner，用于自动集成研究者的 Linkedin 及 Videolectures 账户信息。图 2 给出 COSNET 模型实现跨网络链接预测的基本流程。主要包括四个阶段，(a) 首先给定 2个或者多个输入网络；(b) 模型自动生成一个候选映射图，基本思路是把所有可能的链接（即用户和用户之间的匹配）定义为候选映射图中的一个点，候选映射图中的边表示两个链接之间的关联关系（即可以利用拓扑结构互相影响链接预测的结果）；(c) 由于 (b) 中生成的候选映射图可能非常大，尤其是在输入网络比较大的情况下，因此对候选映射图进行剪枝，剪枝的基本方法是利用领域知识或者一些基本的统计特性；(d) 最后基于得到剪枝后的候选映射图生成对应的马尔科夫场模型并建立相应的能量方程。对能量方程进行求解则可以学习链接预测方程，实现跨网络链接预测。具体求解细节参考文献 [9]。
我 们 将 该 模 型 用 于 AMiner 系 统 自 动 实现 AMiner 系 统 和 LinkedIn、 谷 歌 学 术 以 及VideoLectures 之间的链接预测。AMiner 系统是一个基于作者以及作者之间合作关系网络的开放学术搜索系统，LinkedIn 是全球最大职业网络，谷歌学术是全球最大的学术数据网络，VideoLectures 是一个学术视频网络。实现这几个网络之间的链接，可以更好地整合学术资源，提供更加精准的学术搜索和学术推荐服务。目前 AMiner 系统已经自动实现 237 842 个 AMiner 作者和 LinkedIn 职业人之间的链接（准确率：F 1 值 86%），以及 8 932 个AMiner 作者和 VideoLectures 讲者之间的链接（准确率：F 1 值 79%）。图 3 给出了一个基于链接结果的数据集成结果。
基于话题的网络匹配：其他的网络匹配方法还包括基于话题的网络匹配方法，例如：为解决实体匹配问题，Yang 等[4]提出一个概率图模型。模型的核心思想是，将隐话题提取和实体匹配集成在一个统一的框架中。区别于传统的单一数据源实体匹配，该问题存在异构数据源的实体描述用词差异性大、实体关联度低等挑战。为了处理实体描述差异性大的问题，该方法使用跨域采样的学习算法，不仅能对实体进行匹配，还能通过跨领域话题对匹配结果进行解释。作者通过两个真实应用对模型进行验证：专利 - 产品匹配，以及中英文 Wiki 页面匹配。实验表明，对比传统方法，该模型在两个应用中分别可以提高 19.8% 及 7.1% 的实体匹配准确率。
图 3 AMiner 系统中的跨网络链接结果。以数据挖掘专家 Jiawei Han 教授为例，系统实现 Jiawei Han教授在谷歌学术、LinkedIn、专利和 VideoLecture上不同账号的自动链接和数据集成
跨网络链接预测方法——未知网络链接预测
另一个跨网络链接预测方法是给定两个网络，但仅已知其中一个网络内部的链接和两个网络之间的关联链接，预测另一个网络内部的未知链接。这个问题有很多相关的应用，除了前面提到的移动通信网络的例子，通信公司可以通过本公司用户的通信关系和本公司用户与竞争对手公司用户的链接关系，预测出竞争对手公司内部的用户链接关系，从而在商业竞争中获取商机。另一个例子则是疾病 -基因网络：通常基因之间的相互链接关系的试验代价是比较大的，而相比之下，疾病间的链接关系以及疾病与基因之间的部分链接关系较容易获得。因此这里的问题是如何利用疾病之间的链接，以及疾病与基因之间的链接，预测基因之间的链接关系。图 4 给出了基于疾病 - 基因网络的未知网络链接预测示例。这个问题的关键挑战是在极端情况下，我们可能对另一个未知网络的信息一无所知；另一个挑战则是不同网络之间的用户的关系类型存在异构的特性。
为解决对偶网络的链接预测问题，Dong 等提出一个两阶段的耦合网络链接预测框架 CoulpedLP [3] ，其中第一阶段构建隐式目标网络，第二阶段通过概率因子图模型利用耦合网络中的元路径关系对目标网络结构进行预测。最后能得到 70% 左右的预测精度（基于AUROC指标的评测）。技术细节参见文献 [3]。
