基于文本上下文和网络信息的链接预测方法∗

任奕豪 张 琨 赵 静 冯新淇

（南京理工大学计算机科学与工程学院 南京 210094）

基于文本上下文和网络信息的链接预测方法∗

任奕豪 张 琨 赵 静 冯新淇

（南京理工大学计算机科学与工程学院 南京 210094）

对于链接预测问题，传统的预测模型通常仅考虑网络中节点的链接信息，而社会网络中普遍存在的文本信息可以用于提高链接预测的准确性，利用文本内容来帮助链接预测越发受到重视。结合文本上下文和网络链接，提出了一种基于层次隐狄利克雷分布主题模型的链接预测模型。模型通过层次隐狄利克雷分布模型对文本数据进行训练，从迭代收敛的主题树中提取文本相似特征，然后利用支持向量机模型来训练特征数据以提高链接预测的精度，并得到二元分类器，根据该分类器，可以预测文本与其他文本链接的可能性。实验结果表明，所提出的模型相比于已有的相关模型，提高了预测文本网络中文档之间链接的准确度。

链接预测；层次隐狄利克雷分布；主题树；文本相似特征；支持向量机

1 引言

链接预测，即是在一个网络中，对两个节点间存在但是未被发现的链接进行预测。它是社会网络分析和数据挖掘的一个交叉领域。早期的链接预测问题研究，通常只着眼于网络结构本身，通过挖掘已知节点构成的链接情况来对节点之间的关联性进行预测。但随着网络中信息的不断丰富，节点本身的内容信息越发受到研究者们的关注，通过将内容信息和网络结构信息结合来对链接进行更有效的预测，成为了研究的一大热点。

文本信息是网络中节点内容的一个重要组成部分。在很多情况下，节点都会包含大量文本信息，比如网页上的文本信息、学术论文、社交网站中用户撰写的博客等；而另一方面，这些带文本的节点又会交互，构成一个网络，比如网页对其他页面的超链接、论文的文献引用、社交网站中用户与其他用户的相互关注等。随着Web2.0的发展，互联网中文本的网络规模变得日益庞大，这也为结合文本信息的链接预测提供了大量的应用场景。

2 相关工作

针对网络结构信息来挖掘潜在的网络结构，Murata等［1］基于节点在图上的近邻程度以及网络中已有链接的权值，提出了一种加权距离评估方法，用于网络链接预测；Hofma等［2］提出了一种基于贝叶斯方法的模型来挖掘网络中的聚集情况；Airoldi等［3］假设网络中的每个节点是按一定概率属于多个聚类簇，在此基础上，提出了混合成员随机块模 型（Mixed membership stochastic blockmodels，MMSB）。

另一方面，将节点自身的信息和网络的结构信息结合进行建模，也已经有许多成果。Soumen Chakrabarti等［4］提出了一个结合近邻节点信息来对超文本进行分类的算法；Jiawei Zhang等［5］在社交网络上分别对用户节点锚链接和社交网络进行建模，然后通过概率图随机游走的方式来进行用户社交网络的链接预测；Jonathan Chang等［6］在 LDA（Latent Dirichlet Allocation）文本主题模型［7］的基础上，加入了文本链接的生成概率部分构建了相关主题模型（relational topic model，RTM），通过变分推断推导模型参数，使得该模型可以预测文本之间的链接，或者预测文本可能会出现的单词；Fei Gao等［8］则考察了多个利用不同元数据对社交网络建模的方法，并在此基础上提出了一个混合的社交网络链接预测模型；Jorge Carlos等［9］提出了一种构建在作者关系网络以及主题模型之上的混合模型，用于分析文档作者的社交网络信息；Sheng Gao等［10］结合网络结构、节点自身的所有信息和节点的邻接结构，构造了一个基于矩阵因子分解的模型，并给出了求解模型隐变量的最优化方法；Nicola Barbieri等［11］基于社交网络的用户链接和用户节点的用户画像提出了一个用于链接预测的随机主题模型；Qirong Ho 等［12］则 在 HLDA（Hirerachical Latent Dirichlet Allocation）文本主题模型［13］的模型架构里，以文本主题节点共深路径来作为链接生成的依据，将文本的链接信息融合到了HLDA模型中，从而构造出一个在链接预测和链接歧义消除问题上效果更好的文本层次主题模型Topicblock。

本文的研究将在HLDA文本主题模型的基础上进行，通过在HLDA得到的主题树结构中提取文本的主题分布信息，然后构造每两个文档对的相似特征，最后以文档对是否构成链接作为标签，利用SVM对特征数据进行训练，得到最终分类器用于新文档的链接预测。

3 文本链接预测模型

3.1 模型整体流程

本文对文档的文本数据和文档之间的链接数据进行建模。所有文档的文本构成的集合称之为语料库，构建的链接预测模型的整体过程如下：

1）利用 VSM（Vector Space Modle）思想［14］，对语料库的文本信息构造词典，并将每个文档转换成文本向量；

2）将步骤1）中处理的文本向量作为HLDA模型的输入数据，进行HLDA模型的训练，直到模型收敛，生成语料的主题树；

3）对于步骤2）中得到的主题树，提取每两个文档之间的相似特征向量；

4）以步骤3）中提取的文档对特征和文档与文档之间的链接作为输入数据，训练SVM模型，得到最终的软间隔线性分类超平面。

上述过程用流程图表示为图1形式。

图1 模型整体流程图

3.2 层次化文本主题模型：HLDA

HLDA是层次化的文本主题模型。它通过Dirichlet过程构建非参数化概率模型，生成一个树形层次结构的主题分布，其模型基于如下假设：1）存在一棵主题树，树上的每个节点都是一个主题；2）主题是关于单词的分布；3）每个文档都隐含着若干个主题，而这些主题来自于主题树，并且在主题树上构成从根节点到某个叶子节点的一条路径。

本文将用HLDA模型对语料库D进行建模。假设语料库包含M个文档，其中第m个文档用dm表示（m=1，2，…，M），并且 dm中有 Nm个单词，语料库D的词典长度为V，HLDA模型假设文本按如下生成过程生成：

1）假设主题树的层数为L，对于一个主题树上的任一个节点h，若其深度为l：

采样该主题节点的单词分布 φh～Dirichlet(β⇀)；

2）对于文档dm：

（1）采样其路径分布rm～nCRP(γ)；

（2）采样其层次分布 θm～Dirichlet(α)；

（3）对于dm中的第n个单词（0＜n＜Nm）：

①对该单词所在的层次进行采样zm，n～Multinomial(θ)；

其中 α、β、γ均为超参数，α、β是Dirichlet分布的参数，分别是长度为L和V的向量；γ是nCRP过程的参数。上述生成过程用贝叶斯网络来描述如图2所示。

图2 HLDA的贝叶斯网络

HLDA模型属于非参数的概率生成式模型，对模型后验分布直接进行推导是非常困难的，通常使用“Collapsed Gibbs”采样方法［15］来近似推导模型的后验分布，其中“Collapsed”是指积分掉模型的部分中间参数，用以简化参数估计。根据该采样方法，HLDA最终所要求的联合概率分布如下：

对上述联合概率分布进行Gibbs采样，可以分为对每个文档路径r⇀的采样和对文档中每个单词

m所在层次 的采样。

1）单词层次采样（z⇀ ）

m，n

其中是 z(m，¬n)是文档dm以外的文档的所有单词所属的主题构成的集合；是文档 d中不m属于单词n的所有单词所属主题构成的集合；是指语料中不属于单词 n 的所有单词构成的集合。层次采样可以看作从两个以Dirichlet分布作为先验的多项式分布中采样的过程。

（1）对于先验部分

其中#(zm，¬n=k)为在文档dm中非 n的单词中主题位于第k层的单词个数，其他类似可得。

（2）对于似然值部分

其中rm为文档dm的路径向量，r¬m为除了文档dm外其他文档路径向量构成的集合；wm为文档dm的单词集合，w¬m为除了文档dm外其他文档的所有单词构成的集合。这两个分布可以分别看作是先验分布和单词似然函数。其中 p(rm]r¬m)可以用nCRP过程进行采样；而 p(wm]z，r，w¬m)则是从以Dirichlet分布作为先验的多项式分布中进行采样。

（1）对于先验部分

对于文档dm，在第l层时，选择某个已有的分支y作为当前文档路径节点的概率与当前经过该节点的文档数量成正比，而选择一个新分支的概率与超参数γ有关，该过程即是从nCRP过程的分布里进行采样。

（2）对于似然部分

通过上述Collapse Gibbs采样的迭代，最终文档数据会收敛，得到一棵主题树，每个文档会对应主题树上从根节点到某个叶子节点的路径，比如第m 个文档的 d对应 r⇀=(h，h，…， h) 。 这mmdm，1dm，2dm，L个路径表示该文档所涉及的主题，统计每个文档在每个主题上的单词数量，可以近似估计出该文档关于主题的分布。

3.3 HLDA文档相似特征抽取与链接预测

在获得每个文档的主题分布之后，利用下面的步骤构造出文档之间的相似特征向量：

1）分别计算出每个文档的层次主题分布：

2）对于每两个文档di和dj：

（2）对于主题树的每一层l：

若 zi，l=zj，l，则 t(i，j)，l=pi，l× pj，l；否则不进行任何操作；

上述方法构造了每组文档对的特征向量，对于最终文本链接的预测，本文采用线性SVM模型［16］，以文档相似特征数据作为输入数据x⇀，以文档之间是否有链接作为标签 y进行训练。在SVM中，构造带惩罚系数C的二次规划问题：

求解上述二次规划问题，可以得到软间隔的线性分类面：

对于预测文档的相似特征向量，都可以算出其与分类超平面的距离，基于距离对文档对进行排序，以Top-K的规则取前K个文档对作为有链接的预测。

4 实验设计以及结果分析

4.1 实验数据采集

本文所使用的实验数据集为英文维基百科数据集。维基百科是一个开放的网络文档集合，其中的每个文档存在对其他文档的超链接引用，因此满足实验所需的带引用链接文本的要求。由于原始的维基百科文档数量过于庞大，实验中，随机抽取1000个文档作为实验样本，最多取每个文档摘要的前150个单词作为文本，并对数据进行去停用词处理，最终得到的语料数据如表1所示。

表1 实验数据集

4.2 实验参数设置

在实验过程中，设定主题树的树高L=3（包括根节点）。由于HLDA模型中，超参数对于主题树的影响非常大，因此本文实验将Dirichlet(1)作为超参数的先验分布，通过在该分布上采样自动对模型超参数赋值。具体操作是在每次gibbs采样迭代之前通过在Dirichlet(1)分别采样出三个值，并将这三个值赋给α、β、γ。相比于固定超参数的方式，该方法可以有效减小超参数取值对于模型结果的影响［17］。对于SVM分类，取惩罚系数C=1.0。

4.3 评估指标

本文将以准确率（Precision）、召回率（Recall）以及平均准确率（MAP，Mean Average Precision）作为评估指标。其中准确率和召回率的定义如下：

其中tp为模型正确检索为正类数据的数量；fp是被模型错误检索为正类数据的数量；fn是被模型错误检索为负类的数据数量。对于一个模型而言，准确率和召回率与模型检索的效果正相关（即两个指标数值越高表明模型检索的效果越好），但通常来说提高准确率会降低召回率，反之亦然。

而MAP是一个综合的评估指标，常常被用于评估模型信息检索结果的优劣，并且相比于其他指标呈现现出良好的有效性和稳定性［18］。假设Q是所有需要检索的文档集合，|Q|是检索文档的数量，对于第 j个检索的文档dj∈Q，与其有链接关系的文档集合为｛d1，d2，…，dmj｝，那么对应的MAP定义如下所示。

其中Rjk是排序后的检索结果集合中，与dj相关的第k个文档在集合中所处的的序号，而。MAP可以近似地看作是准确率-召回率曲线图中位于曲线下方区域的面积，该值越高表明检索效果越好。

4.4 实验步骤及结果分析

本实验将预处理后的1000个维基百科文档随机划分成训练集和测试集，用训练集数据进行模型训练，然后拟合测试集数据。实验步骤如下：

1）将训练集的数据放入3.1所描述的模型流程进行训练，得到收敛的HLDA主题树和SVM分类面。

2）将测试集的文本数据放入收敛的HLDA模型进行拟合，再用3.3描述的特征提取过程提取测试集中文档与其他文档的相似特征，最后用步骤1）得到的SVM分类面对测试集中文档的链接进行预测。

3）对步骤2）得到的预测结果计算其准确率、召回率以及MAP值。

由于文献［13］中验证了当迭代次数大约大于150时，模型趋于稳定，因此本实验中，设定训练集数据迭代次数为200次作为收敛条件。本实验分别对比了文献［12］中所介绍的TMSB模型和HLDA模型以及tf-idf算法［19］。最后的各个模型的实验结果的准确率和召回率情况如图3～4所示。

由于数据集中正例数据较为稀疏，因此造成了准确率非常低但召回率相对较高的结果。然而由图3～4可以看出，整体而言，HLDA+SVM模型在准确率和召回率这两个指标上都要优于其他几个对照模型，具体地，HLDA+SVM模型和Topicblock模型在准确率和召回率上要明显优于HLDA模型和tf-idf模型，而同样是考虑了文本数据和链接数据，HLDA+SVM模型在大多数K的取值情况下准确率和召回率指标都要优于Topicblock。

图3 各个模型准确率

图4 各个模型召回率

至于MAP指标，各个模型在不同检索数K的结果对比如图5所示。通过该结果可以看出，相比于仅仅考虑了文本信息的HLDA模型，同时考虑了网络结构信息和文本信息的HLDA+SVM混合模型在链接预测的准确度上提升显著；而相比于同样也考虑了网络结构信息和文本信息的Topicblock模型，本文的HLDA+SVM模型在MAP指标上也较优；而对于tf-idf模型，它仅仅通过文档之间共现单词来简单刻画文档之间相似度，最终的指标结果也远低于其他几个模型。

图5 各个模型在不同K值下的MAP指标

5 结语

对于目前常见的带文本网络节点链接预测问题，本文提出了同时考虑文档上下文信息和链接结构信息的混合模型，该模型以HLDA对文档的上下文进行建模，考虑文档主题分布之间的相似度来提取文档相似度特征，再用SVM模型对相似特征数据和链接数据进行训练，最后对未知文档的链接进行预测。该模型主要考虑了节点文档在各个层次上的主题分布情况，对文本之间相似度进行了更细致的特征提取。实验结果也表明，该模型在预测文档之间链接的精确性上相对于已有的模型算法有所提升。

［1］T Murata，S Moriyasu.Link prediction of social networks based on weighted proximity measures［C］//IEEE/WIC/ACM International Conference on Web Intelligence，2007，85-88.

［2］JM Hofman，CH Wiggins.A Bayesian approach to network modularity［J］.Physical Review Letters，2008，100（25）：5740-5747.

［3］EM Airoldi，DM Blei，SE Fienberg，et al.Mixed membership stochastic blockmodels［J］.Journal of Machine Learning Research，2008，9（5）：1981-2014.

［4］Chakrabarti S，Dom BE，Indyk P.Enhanced hypertext categorization using hyperlinks［C］//Proceedings of the 4th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，1998，27（2）：307-318.

［5］Zhang J，Yu PS.Integrated anchor and social link predictions across social networks［C］//International Conference on Artificial Intelligence，2015，58-65.

［6］Chang J，Blei D.Relational topic models for document networks［C］//In International Conference on Arti cial Intelligence and Statistics，2009，81-88.

［7］Blei D，Ng A，Jordan M.Latent dirichlet allocation［J］.Journal of Machine Learning Research，2003，3（1）：993-1022.

［8］Gao F，Musial K，Cooper C，et al.Link prediction methods and their accuracy for different social networks and network metrics［J］.Scientific Programming，2015，13（13）：101-113.

［9］Valverde-Rebaza JC，Lopes ADA.Link prediction in online social networks using group information［C］//International Conference on Computational Science&Its Applications，2014，8584：31-45.

［10］Gao S，Denoyer L，Gallinari P.Temporal link prediction by integrating content and structure information［C］//in Proc.CIKM，2011，1169-1174.

［11］Barbieri N，Bonchi F，Manco G.Who to follow and why：link prediction with explanations［C］.In KDD'14，1266-1275.

［12］Ho Q，Eisenstein J，Xing EP.Document hierarchies from text and links［C］//in Proceedings of the 21st international conference on World Wide Web，2012，739-748.

［13］Blei D，Griffiths T，Jordan M.The nested chinese restaurant process and Bayesian nonparametric inference of topic hierarchies［J］.Journal of the ACM，2010，57（2）：1-30.

［14］Salton G，Wong A，Yang CS.A vector space model for automatic indexing［J］.Communication of ACM，1975，18（11）：273-280.

［15］Cortes C，Vapnik V.Monte carlo statistical methods［M］.New York：Springer，2004.

［16］Cortes，Vapnik V.Support-vector networks［J］.Machine Learning，1995，20（3）：273-297.

［17］Bernardo JM，Smith AFM.Bayesian theory［M］.New York：John Wiley&Sons Ltd，1994.

［18］Manning CD，Raghavan P，H Schütze.Introduction to information retrieval［M］.Cambridge：Cambridge University Press，2008.

［19］Bethard S，Jurafsky D.Who should I cite：learning literature search models from citation behavior［C］//In Proceedings of CIKM，2010，609-618.

Link Prediction Method Based on Context and Network Information

REN YihaoZHANG KunZHAO JingFENG Xinqi
（School of Computer Science and Engineering，Nanjing University of Science and Technology，Nanjing 210094）

In regard to link prediction problem，traditional prediction models usually only consider the link information of the nodes from the network.However，the text widely existing in the social networks can be used to improve the performance of link prediction，and using text for link prediction is getting attention increasingly.Combining text and links，proposes a link prediction model based on hierarchical latent dirichlet allocation topic model.First，the model trains text data by hierarchical latent dirichlet allocation model，then it extracts text similar features from the convergent topic tree，finally the model trains the feature data to obtain a two-class classifier by support vector machine model，this classifier can be used to predict the link between nodes.The experimental results demonstrate that，comparing to pre-existing similar models，the model proposed improves the accuracy of predicting the links among the documents in text network.

link prediction，hierarchical latent dirichlet allocation，topic tree，text similar feature，support vector machine

TP301

10.3969/j.issn.1672-9722.2017.10.021

Class Number TP301

2017年4月20日，

2017年5月27日

任奕豪，男，硕士研究生，研究方向：数据挖掘与自然语言处理。张琨，女，博士研究生，教授，研究方向：信息安全与复杂网络。赵静，女，博士研究生，研究方向：信息安全、复杂网络理论与应用。冯新淇，女，硕士研究生，研究方向：数据挖掘与语义分析。