本文使用的社交网络为无向网络，形式为$ G(V,E) $，$V $、$E $分别是网络中的节点集合、连边集合。定义节点类型映射函数$ f:V \to A $，其中每个节点$ v \in V $都对应特定的类型$ f(v) \in A $；定义链接类型映射函数$ \gamma :E \to R $，其中每条链接$ e \in E $都对应特定的类型$ \gamma (e) \in R $。当$R $和$A $满足$ \left| A \right| \gt 1 $或$ \left| R \right| \gt 1 $时，即边的类型数或者节点的类型数大于1，则该网络定义为异质网络，反之为同质网络。

本文将不区分用户类型的社交网络构建为同质网络，将用户类型区分为男性用户与女性用户的社交网络构建为异质网络。如图1所示，同质网络中的节点代表用户，异质网络中的浅色节点代表女性用户，深色节点代表男性用户。

图  1  同质网络与异质网络

1) 评价指标AUC

AUC作为衡量链路预测算法性能的一种重要指标，可以从整体上衡量算法的精确度^[21]。AUC指标可描述为如下形式：每次从测试集中随机选取一条存在的边，然后随机选取一条不存在的边，比较这两条边的相似度得分。如果存在边的分数大于不存在边的分数，就加1分；如果两条边的分数相等，就加0.5分。这样独立比较$ n $次，如果有$ n' $次存在边的分数值大于不存在边的分数值，有$ n'' $次两条边的分数值是相等的，则AUC值可以定义为：

通常，上述评分算法计算出的AUC值应该至少大于0.5。AUC的值越高，算法的精确度越高，但AUC的值最高不会超过1。

2) 评价指标Precision

Precision作为衡量链路预测算法精确度的指标之一，主要从局部衡量预测的准确性。该指标关注的是预测值排序在前$ L $个预测边中预测准确的比例。根据特征的分数值从大到小排序，如果有$ m $条边是真实存在即预测准确的边，Precision可以定义为：

由该式可知，$ m $越大则Precision值越高，预测越准确。

利用节点间的局域结构相似性是研究链路预测问题的一种重要方法，该方法的前提假设为节点间的相似性越大，它们之间存在链接的可能性就越大。在以往研究中，基于共同邻居相似性指标应用广泛、预测精度较高，但本文研究的异质社交网络数据由于只有不同类型的节点存在连边，故不存在共同邻居节点，因此无法基于共同邻居的相似性指标进行预测。本文主要使用局部路径指标LP与偏好连接相似性指标PA、Katz、CAR和L3作为链路预测的基准方法。LP指标在考虑共同邻居的基础上考虑了三阶路径的因素，更全面考虑了节点的局域结构信息，可以有效提升预测精度；Katz指标在三阶路径的基础上进一步考虑了网络的所有路径；PA指标在网络存在“富者愈富”的连接偏好时性能显著，针对稀疏网络的预测性能也较好^[22]；CAR方法不仅考虑网络中的公共节点以及共同邻居节点，同时引入共同邻居节点之间链接的组合；L3方法基于RA指标进一步提出三阶路径的预测方法，可以有效提升链路预测准确度。

1) 局部路径指标(LP)：

式中，$ \alpha $为可调参数；$ {\boldsymbol{A}} $表示网络的邻接矩阵，$ ({\boldsymbol{A}})_{xy}^n $表示节点$ {v_x} $和$ {v_y} $之间长度为$ n $的路径数。当$ \alpha = 0 $时，LP指标就等价于CN指标。

2) 偏好连接相似性(PA)：

式中，$ {k_n} $表示节点$ {v_n} $的度，在网络中一条新边连接到节点$ {v_n} $的概率正比于该节点的度$ {k_n} $。在不考虑增长的网络中，新链接连接节点$ {v_x} $和$ {v_y} $的概率正比于两节点度$ {k_x}{k_y} $的乘积。

3) 全局路径指标(Katz)：

式中，$ \alpha > 0 $为控制路径权重的可调参数，$ ({\boldsymbol{A}})_{xy}^n $表示节点$ {v_x} $和$ {v_y} $之间长度为$ n $的路径数。当参数$ \alpha $很小时，Katz指标的预测结果接近于局部路径指标。

4) CAR指标：

式中，$ \varGamma (x) $为节点$ x $的邻居节点集合；$ \varGamma (y) $为节点$ y $的邻居节点集合；$ {\rm{CN}}(x,y) $为节点$ x $和节点$ y $的三阶邻居数量；$ z $为节点$ x $和节点$ y $的三阶邻居集合；$ \gamma \left( z \right) $是节点$ z $的局部社区度。

5) L3指标：

式中，$ {k_u} $为节点$ u $的度；$ {a_{xu}} $代表节点$ x $和节点$u$之间的相互作用。如果节点$ x $和$u$之间存在相互作用，则$ {a_{xu}} = 1 $，否则$ {a_{xu}} = 0 $。

基于同质模体特征的链路预测方法主要是针对不考虑节点类型差异的同质网络，根据网络的拓扑结构，构建不区分节点类型的模体结构特征，将其定义为同质模体。由于本文数据为基于男女性别差异的异质网络数据，不考虑网络中的节点类型时，三节点模体和四节点模体结构只有表1的5种类型。

本文基于同质模体的预测方法共涉及5个模体特征，分别为1个三节点模体和4个四节点模体，代表了网络链接的5种关系模式。所有模体编号、图示和关系模式如表1所示，其中虚线表示待预测连边。

表 1  同质模体对应的关系模式

模体编号	图示	关系模式
T1		一位用户与两位无关系的用户其中的一位有 社交关系，则可能与另一位用户有社交关系。
T2		一位用户与三位无关系的用户中的两位有 社交关系，则可能与另一位用户有社交关系。
T3		两位无关系用户分别与两位有关系的用户 具有关系，则其他两位用户可能有社交关系。
T4		两位有关系的用户，其中一位与另一位用户 有关系，则另一位用户与其他用户也有关系。
T5		两位有社交关系的用户分别与两位无关系的 用户有社交关系，则另两位用户可能有社交关系。

基于异质模特特征的链路预测方法主要针对异质网络，即网络中不只存在一种节点类型。根据异质网络的拓扑结构，构建区分节点类型的模体结构特征，将其定义为异质模体。本文主要基于男女性别进行节点类型区分，将节点分为男性节点与女性节点两种类型。在基于异质模体特征的预测方法中，三节点模体和四节点模体共涉及8种模体特征，分别为2个三节点模体和6个四节点模体，代表了社交网络中的8种关系模式。所有模体编号、图示和关系模式如表2所示，其中虚线表示待预测连边。

表 2  异质模体对应的关系模式

模体编号	图示	关系模式
Y1		一位男性用户与两位无关系的女性用户的其中 的一位具有社交关系，则可能与另一位女性 用户也有社交关系。
Y2		一位女性用户与两位无社交关系的男性用户 其中一位具有社交关系，则可能与另一位男性 也有社交关系。
Y3		一位女性用户与三位无社交关系的男性用户 中的两位有关系，则可能与另一位男性有 社交关系。
Y4		一位男性用户与三位无社交关系的女性用户 中的两位有关系，则可能与另一位女性有 社交关系。
Y5		两位有社交关系的男女用户，其中一位女性 用户与一位男性用户有关系，则另外一位男性 用户可能与其他女性有社交关系。
Y6		两位有社交关系的男女用户，其中男性用户 与另外一位女性用户有社交关系，则另外一位 女性用户可能与其他男性有社交关系。
Y7		两位无社交关系的男女用户分别与两位男女 用户有社交关系，则这两位男女用户可能 有社交关系。
Y8		除某两位男女用户无社交关系外，其余男女用户 之间两两相互有关系，则无社交关系的男女用户 可能有社交关系。

基于异质模体特征的社交网络关系预测主要提取训练集的模体特征，将每种预测边上的模体数量作为特征值，男性节点与女性节点之间是否有连边作为机器学习的分类标签，得到预测结果后使用AUC和Precision指标衡量预测性能。图2为基于异质模体特征的社交网络关系预测的具体过程。

图  2  基于异质模体特征的关系预测

如图2所示，图2a为一个7节点的小型异质网络。本文数据为区分男女性别的异质网络数据，且只有男性节点与女性节点存在连边。图2a中节点$ u $为男性节点，节点$ v $为女性节点，边$ \left( {u,v} \right) $为待预测连边，图2b中以异质模体特征Y1、Y3、Y7、Y8为例说明社交网络关系预测的主要过程，异质模体特征Y1、Y3、Y7、Y8的具体数量即为不同模体的特征值。模体特征Y1的计算方法为寻找节点u的邻居节点，且该邻居节点不是节点$ v $的邻居。模体特征Y7的计算方法为寻找节点$ u $和$ v $各自的邻居节点，且该邻居节点不互为邻居。其他模体特征的计算方法以此类推，通过计算得出模体特征Y1的个数为2，模体特征Y3的个数为1，模体特征Y7的个数为1，模体特征Y8的个数为1。

在进行社交网络用户关系预测时，计算图2c中所涉及的4种模体在图2a小网络中的数量，并将得到的每种模体数量作为机器学习方法的输入，从而得到连边的相似度得分，继而进行网络的链路预测。

本文使用百度贴吧数据与性接触数据，分别构建同质网络与异质网络进行链路预测，网络具体信息如表3所示。

百度贴吧数据为百度贴吧恋爱吧用户评论数据，在该网络中，节点代表贴吧中的用户，依据性别划分为男性用户和女性用户，连边代表一名用户对另一名用户的发帖进行了评论或回复。本文将百度恋爱吧男女之间的评论关系设定为具有线上社交关系，恋爱吧数据构建的网络，只使用男性节点与女性节点的社交关系构成连边。

性接触网络全称为基于性接触的经验时空网络(empirical spatiotemporal network of sexual contacts^[23])，该网络是一名男性用户与另一名女性用户进行性接触的线上沟通网络数据，节点代表性接触网络中的用户个体，分为男性用户与女性用户，连边代表一名男性用户与一名女性用户进行了线上的联络，即具有特殊社交关系。

在进行链路预测实验时，对于每个实证网络数据，从正样本和负样本中分别随机选取90%的数据作为训练集$ {E_T} $，选取剩余10%的正负样本数据作为测试集$ {E_v} $，满足训练集与测试集正负样本比例1:1。

本文对所有单个模体特征(5个同质模体和8个异质模体)和多个模体特征(所有5个同质模体和所有8个异质模体)进行链路预测，得到评价指标AUC与Precision的值。链路预测的结果如表4和表5所示，单个模体特征的最好预测性能和多模体特征的预测效果加粗标出。

由表4可以发现，使用单个同质模体特征进行链路预测时，模体特征T3的预测准确率和精确度最高。说明在社交网络中，如果两位无关系用户分别与两位其他用户具有社交关系，则其他两位用户有社交关系的可能性较大。本文综合多个同质模体特征进行预测，发现多同质模体特征的预测效果比单个同质模体特征的最好预测效果高4.3%～16.6%，说明综合多种用户关系模式进行链路预测效果更好。

由表5可以发现，使用单个异质模体特征进行链路预测时，模体特征Y7的预测准确率与精确度最高，说明在社交网络中，如果两位有关系的男女分别与两位无关系的男女有关系，则另外两位男女有关系的可能性越大。在Y7与T3的网络拓扑结构一致的情况下，异质模体特征的预测效果优于同质模体特征的预测效果。本文综合多个异质模体特征进行预测，发现多异质模体特征的预测效果比单个异质模体特征的最好预测效果高5.2%～12.8%，说明综合多种男女用户关系模式进行链路预测效果更好。

除了比较链路预测的具体性能，本文还对8种异质模体特征进行了皮尔逊相关性分析，结果如图3所示。模体特征Y1和Y3具有较强相关性，Y2和Y4也具有较强相关性，主要原因是Y3与Y4都是Y1与Y2的拓扑组合。Y7与Y8也具有较强相关性，是因为这两个模体特征只关注待预测连边中两个节点的各自邻居节点之间的结构。Y1、Y2、Y5、Y7、Y8可以视为一个相关性程度较高的集合，它们之间有较强的相关性，是因为它们的拓扑结构都是以Y1的拓扑结构为基础。

图  3  链路预测异质模体特征的相关性分析

为了比较同质模体特征与异质模体特征之间的差异，本文对两种模体结构存在边和不存在边的分布情况进行比较分析。百度贴吧数据中同质模体T1和异质模体Y1存在边和不存在边的分布差别如图4所示。其中实线和虚线分别代表网络中的存在边和不存在边的模体数量分布。研究发现，对于同质模体而言，存在边和不存在边有很大程度的重叠，重叠程度越大越不利于链路预测。对于异质模体，存在边和不存在边的重叠分布小于同质模体，说明相较于同质模体，使用异质模体进行链路预测的性能更好。

图  4  同质模体和异质模体边的分布

本文采用基于同质模体特征方法与异质模体特征方法进行链路预测，在相同的网络拓扑结构下，同质模体和异质模体具有一定的相关性。图5分别为相同的网络拓扑结构下，同质模体与异质模体之间的关联性。其中节点代表用户个体，节点之间的连边代表用户之间的社交关系。深色节点代表用户性别为男性，浅色节点代表用户性别为女性。

图  5  同质模体特征与异质模体特征结构差异

由图5可知，Y1、Y2和T1，Y3、Y4和T2，Y5、Y6和T4分别具有相同的网络拓扑结构，为了探究相同网络拓扑结构下，考虑节点异质信息和不考虑节点异质信息的模体的链路预测效果，进行了基于单个异质模体特征、单个同质模体特征、同一网络拓扑结构下多异质模体特征的链路预测，结果如表6所示。

通过表6可以发现，在两个实证网络数据中，融合多个异质模体特征的AUC和Precision值均高于单个异质模体特征和同质模体特征。结果表明在相同的网络拓扑结构下，融合所有区分节点异质信息的异质模体特征，其链路预测准确性高于单个异质模体特征以及不考虑节点异质信息的同质模体特征。这是由于异质模体考虑了网络中节点的异质信息，更全面准确地刻画了网络结构。

以往关于链路预测的研究中，研究人员提出的基于网络结构相似性的方法大多只关注其中一种网络结构，即一种模体结构。在应用于社交网络的链路预测算法中，往往也只研究了一种社交用户之间的关系模式，忽略了社交用户之间多种关系模式的组合。因此本文通过特征拼接的方式融合多种同质模体和异质模体结构进行链路预测，旨在结合不同模体特征的优势，分析多模体结构即多关系模式对链路预测准确性的影响，并将多模体结构的预测结果与单模体结构的预测结果进行比较。

在链路预测问题中，将所有同质模体特征与所有异质模体特征进行融合，链路预测的结果如表7所示，发现融合多同质模体和异质模体特征的链路预测准确率高于只使用多异质模体特征的链路预测准确率。说明相较于只使用多异质模体进行链路预测，融合同质模体特征对提升链路预测准确性具有一定的积极作用。本文还将所有同质模体特征、所有异质模体特征、融合所有异质模体和同质模体特征与LP、Katz、PA和CAR和L3进行了对比，结果如表7所示，其中最好的预测效果已加粗标出。

由表7中数据可知，融合多异质模体和同质模体特征的链路预测算法准确率最高，其AUC比LP、PA、Katz方法最多提升了27.1%，精确度最多提高了20.1%，该方法也优于CAR和L3方法的精确度。这是因为相比CAR和L3方法，本文提出的基于多同质模体和多异质模体的链路预测方法考虑了更多网络结构的非局域信息。因此，在社交网络中融合多同质和异质模体特征进行链路预测能够有效提高预测的准确性。

尽管CN、LP等局部相似性指标可使用坚实的理论和实证依据进行解释，如社会学中的同质性原理，即两个相似的节点更大概率产生连边^[16]。但最新研究发现，并不存在某一类局域指标可在所有实证网络中都取得最佳预测性能，有些网络是基于二阶路径的相似性指标表现更好，而另一些是三阶路径指标取得更好性能。本文以特殊的异质社交网络为研究对象，这类网络的突出特点是局域性指标失效而只能依靠刻画结构非局域性的模体结构进行链路预测，因此对于研究其他网络的非局域性指标具有一定的借鉴作用，同时考虑到节点角色的异质性也有利于将此类方法应用于二部分图中^[24]。

由于本文数据为实证网络数据，每位用户可能存在造假的动机和现象。为了验证当节点的男女信息存在噪音情况下算法结果的稳定性，本文以百度贴吧数据为例，进行男女节点性别互换。随机选取实证数据中30%、40%、50%、60%的男女节点进行性别互换，互换后的链路预测结果如图6所示。

由图6可知，虽然对实证数据中的男女性别进行了一定比例的置乱，但实验结果表明依旧是多同质模体与异质模体的链路预测算法准确性最高，其次是多异质模体，均高于同质模体的准确性。该结果与上文的实验结果一致，因此本文算法具有一定的通用性和稳定性。

在融合所有同质模体和异质模体特征的链路预测中，本文还对8种异质模体和5种同质模体进行皮尔逊相关性分析，结果如图7所示。

图  6  男女性别互换的链路预测结果

图  7  链路预测同质模体与异质模体特征的相关性分析

由图7可看出，异质模体Y1和Y3，Y2和Y4具有较强相关性，原因是模体特征Y3与Y4分别是模体特征Y1与Y2拓扑结构的组合。异质模体特征Y7和Y8与同质模体特征T3和T5具有较强相关性，原因是这4种模体的网络拓扑结构较为接近，都是以四节点方形拓扑结构为基础进行模体的构建。同质模体T1、T2和T4相关性也较强，这是由于3种模体结构均为同质模体且拓扑结构都是以T1的拓扑结构为基础。

本文研究性接触网络与百度贴吧恋爱吧两种特殊类型网络，为了更精准地刻画网络结构以及充分利用节点的异质信息，本文提出了基于异质模体的链路预测方法，验证了异质模体数量与链路预测准确率的相关性，构建异质模体特征进行关系预测。在此基础上，提出融合多种同质和异质模体特征进行社交网络链路预测方法。结果表明，基于异质模体的预测方法可以有效提升链路预测准确性，融合多异质和同质模体特征的预测效果更为显著。本研究有助于对社交网络的用户关系进行预测和推荐，在用户行为分析、推荐系统等方面具有广阔的应用前景。后续研究将在异质模体特征的基础上引入朴素贝叶斯算法与角色函数，对异质网络中的信息进行更加充分的利用。

周涛教授对本文研究工作给予了一些指导和帮助，在此表示感谢。