社交网络中基于强社交图的可信任服务商选择*

时久超，刘冠峰，李直旭，刘 安，郑 凯

苏州大学 计算机科学与技术学院，江苏 苏州 215006

1 引言

近年来，社交网站已经被应用于各种各样的活动。例如Reppler（一个提供社交媒体监控服务的网站）曾经对300名参与公司招聘流程的专业人士进行了调查，结果表明他们中有91%的人使用在线社交网络（online social network，OSN）来筛选潜在员工。再例如，一个购买者可以通过OSN（例如Facebook和Twitter）和其他电商网站（例如ThisNext和eBay）建立的联系，将电商网站上的产品推荐给他/她在OSN的好友。OSN甚至已经被用在了云环境上[1]，目的是形成一个社交云来帮助云服务共享参与者之间的社交关系。在上述活动中，OSN都被用来加强服务提供。然而，当服务消费者需要从不同提供商提供的大量服务中选取一个时，除了功能性和服务质量，信任度也是影响服务消费者做出决定的重要因素之一，此时就需要一个方法来评估出未知服务提供商的信誉情况。

在面向服务的OSN中，每个节点表示一个服务消费者或提供商（例如，在图1中，A提供服务S1和S2并且使用服务S3、S5和S8），每条边对应于真实世界或者在线的交互（例如，图1中的A→B和A→C）。在OSN中，参与者可以根据之间彼此的直接交互情况给对方一个信任值。由于每个参与者通常会与许多其他参与者进行交互，因此，通过串联相邻节点间可信任的边，就可以在两个间接相连的节点间形成多条信任路径。例如，在图1中，A和E通过两条路径A→B→D→E和A→C→E间接相连，参与者可以基于路径中的信任信息来评估彼此的可信度。这个过程叫作信任传播，这条带有信任信息并且连接着起点和终点的路径叫作一条社交信任路径[2-3]。例如，在图1中，作为服务消费者的A可以根据从A到E的这条社交信任路径评估出服务提供商E的可信度。将A称为源参与者，E成为目标参与者。在大型社交网络中，源参与者与目标参与者之间可能存在成千上万条社交信任路径[4]，因此通过计算所有社交信任路径来评估目标参与者的可信度耗时巨大。为了得到目标参与者实际的信任评估结果，源参与者需要参考多个社会信任路径[5]。因此，如何找到那些拥有较高信任值的高质量信任路径成为一个既有挑战又十分重要的问题[4]。

Fig.1 Service-oriented social network图1 面向服务的社交网络图

在相关文献中，Lin等人[6]提出了一种最佳的社交路径查找方法，将源参与者和目标参与者之间的最短路径确定为最优路径。但是这种方法没有考虑参与者之间的信任信息。在其他研究中[3]，将具有最大传播信任值的路径识别为最值得信赖的社会信任路径。但是，这种方法并没有考虑到参与者的社交地位以及社交关系等相关社交信息，而这些信息对信任传播却有着重要的影响[7-8]。另外，源参与者可能会有不同的社交信任路径查找标准，并且应该能够在信任传播的过程中对社交关系设置一些限制，这可以帮助源参与者找到具有最可靠的信任评估结果的社交信任路径。但是，上面提到的方法并不支持这些功能。

本文的目的是解决如何在包含复杂社交关系的社交网络中寻找社交信任路径的问题。本文的主要贡献总结如下：

（1）首先介绍了复杂的社交网络结构并提出了信任质量（quality of trust，QoT）的概念[9]，然后，将基于QoT约束的多条社交信任路径查询问题建模为多约束K最优路径（multiple constrainedKoptimal paths，MCOP-K）选择问题，这个问题被证明为NP-完全问题[4]。

（2）为了解决NP-完全的MCOP-K问题，提出了一个由拥有较强社会联系的参与者构成的名为“强社交图”（strong social graph，SSG）的概念，并提出了一种查询SSGs的方法。

（3）根据建立索引后的SSG，通过运用蒙特卡罗方法和一些优化策略提出了一种时间复杂度是O(MU)的新颖的近似算法SSG-MCBA（strong social graph-Monte Carlo based algorithm），其中M是模拟次数，U是社交网络中的最大出度。

（4）在Enron email和Epinions这两个真实社交网络数据集上进行了实验。实验结果表明，提出的SSG-MCBA算法在路径查找的准确率和效率方面都极大地优于现存最好的算法D-MCBA（double-Monte Carlo based algorithm）。

2 相关工作

2.1 社交网络分析

20世纪60年代，社会网络研究证实了社交网络中的小世界特征[10]，通过邮件发送的实验证明两个美国人之间建立连接的平均路径长度约为6.6。20世纪70年代，Pool等人[11]分析了小世界特征对人们交互的影响。近年来，在计算机科学学院，Mislove等人[12]通过分析几个流行的在线社交网络（如Facebook和Flickr）来验证在线社交网络的小世界和power law特征。

2.2 社交网络中的信任度

Yao等人[13]提出了一种名为MATRI的信任推理模型，该模型综合考虑了信任偏差，共同引用信任和信任推理中的信任耦合等因素。这些因素可以通过矩阵来建模，其中信任推理建模为最小化观察信任评级集合上的平方误差。此外，Tang等人[14]提出了一种用于预测参与者之间的信任度的动态在线信任模型，该模型考虑了用户的动态喜好，用户对产品的评价以及用户间的相互关系等因素。

2.3 OSNs中社交信任路径的查询

SmallBlue[6]是一个为IBM员工创建的在线社交网络。在该系统中，如果一个源用户想要找到一个目标用户（例如一个C++程序员），他最多考虑他们间的16条路径，并且每条路径的长度都不超过6，其中，最短的那条路径就被认为是最佳路径。然而，这种方法忽略了一个重要因素，那就是社交网络中间节点之间的信任情况，这些信任信息对用户的最终决策产生重要影响。Hang等人[3]在这方面做出了改进，他们在路径查找的过程中进一步考虑了参与者之间的信任度。在他们的模型中，拥有最大传播信任值的路径被选为最佳路径。该方法考虑了用户间的信任信息，但他并没有考虑到用户之间可能存在不同的信任评估标准。Wang等人[15]提出了一种新的社交信任路径查找方法。该方法中，源参与者可以指定阈值。如果该方法计算出的某个推荐点的聚合信任值大于源用户给定的阈值，那么这个推荐点就会被保留在信任网络中；否则，该点就会被删去。删除节点后，剩余的社交信任路径将继续做信任评估。文献[4，9，16-19]综合考虑了具体的社交关系的约束。这些已提出的方法虽然综合考虑了社交网络中的许多属性，并且提高了最终结果的质量，但是当应用到实时的社交信任网络中时，它们的准确性或者效率就会变得很低[9，16-17]。

3 语义社交网络

本章为了更好地映射到真实世界的社交网络，提出了一个包含社会信任、社会关系和社会地位等复杂社会环境的语义社交网络（contextual social network，CSN）结构[9,17]。

3.1 语义社交网络

语义社交网络[9,17]是一个带标记的有向图G=(V,E,LV,LE)，其中：

（1）V是节点的集合。

（2）E是边的集合，(vi,vj)∈E表示从节点vi到节点vj的一条有向边。

（3）LV是定义在点集V上的一个函数，对于每个节点v,LV(v)是节点v的一组标签。节点标签表示特定域中的一些社交角色。

（4）LE是定义在边集E上的函数，对于E中的每条边(vi,vj)，LE(vi,vj)就是(vi,vj)的一组标签，表示某个特定领域的社交关系、社交信任以及偏好等。

3.2 社交影响因素

（2）社交亲密度：根据社会心理学相关理论[8]，一个参与者往往更倾向于信任和他具有更亲密的社会关系的参与者，并且更愿意跟他们进行往来。rAB∈[0,1]表示A和B之间的社交亲密度，rAB=0表示A和B没有任何的社交亲密度，rAB=1表示他们有最亲近的亲密度。

（3）角色影响因子：根据社会心理学相关理论[7]，在某一兴趣领域，专家的建议比普通人更为可信。因此，代表A的角色影响因子，即参与者A在领域i中的影响力。当时，表示A是该领域的专家并且具有最大影响力；当时，表示A对该领域没有影响力。

虽然很难在各个领域都建立起全面的社交亲密度和角色影响因子，但是可以通过利用数据挖掘技术在一些特定的社交网络中进行挖掘和建立[19-21]。

3.3 语义社交网络结构

基于上述定义的社交影响因子，提出了一种复杂语义社交网络的新结构，如图2所示。基于这种新结构，在下一章中，介绍一种新的社交信任路径查询的模型，该模型不仅考虑了社交背景的影响，还考虑了上面提到的社交影响因子的某些约束的规范。

Fig.2 Contextual social network图2 语义社交网络图

4 多条社交信任路径查找

本章提出了一种用于实现端到端并且满足质量信任约束的多条社交信任路径查询的新模型[22]。

定义1（信任质量（QoT））是指沿着一条社交信任路径的信任传播过程中能够保证一定信任度的能力，它采用社交信任(T)、社交亲密度(r)以及社交影响因子 (ρ)。

在本文的模型中，源参与者可以为信任质量属性（即T、r和ρ）设置多个端对端的约束，并以此作为社交信任路径上的信任评估需求标准。例如，在图2中，源参与者A可以为从A到E这条社交信任路径设置端到端的信任质量约束，用QoC表示，例如分别对应着信任质量里面的T、r和ρ约束。

根据社会心理学的相关理论[23]，采用乘法来聚合路径中的T和r值，用平均值来聚合路径中节点的ρ值。使用AS(A,B)来表示A到B这条路径上的聚合社交影响因子。其中，具体的聚合方法在文献[22]有详细讨论。

在本文的模型中，定义了一个效用函数（用F表示）来度量社交信任路径的可信任度，它采用QoT的T、r和ρ作为参数。

其中ωT、ωr和ωρ分别是T、r和ρ的权值，并且满足0＜ωT,ωr,ωρ＜1以及ωT+ωr+ωρ=1。

一条可行的路径是指它可以满足多个端到端的信任质量约束。多条社交信任路径查询的目的就是从多条可行路径中找出最符合用户给定的效用函数的那条路径。

5 强社交图以及基于强社交图的索引

5.1 强社交图

为了提高NP完全信任路径选择方法的准确率和效率，提出了一种强社交图的识别方法。在图论中[24]，一个图被称作强连通图当且仅当图中任意两个节点都互相可达。基于上述强连通的定义，下面给出了强社交图的定义。

定义2（强社交图（SSG））在语义社交网络中，一个子图被称作强社交连通，当且仅当子图中的每个节点在特定领域都有较高的社交影响因子，并且连接节点的每条边都具有亲密的社交关系以及较高的社交信任度。

根据社会心理学的相关理论[23]，人们通过长时间的观察发现，在强社交图中，整体的社交结构，社交环境，包括每条边上的社交信任度和社交关系以及每个节点上的社交影响因子在很长一段时间内都会保持稳定。基于这个特性，就可以以更小的代价对强社交图进行索引。

5.2 可达性索引

为了进一步提高NP完全MCOP-K的效率，提出了一种新的索引结构来对SSG中的可达性和社会关系进行索引。

（1）可达性索引：该索引记录了强社交图中某个节点能够调查到的其他节点所构成的集合，其中每个节点的具体索引值包含了该节点的祖先及后继节点。

例1图3是强社交图在领域j上的一个索引。从图中可以看出，每个节点的索引包括两部分，可达性索引和社交关系索引。以节点E为例，它既有前驱节点又有后继节点。E的可达性索引记录了它的先节点C(Anc.:C)以及它的后继节点H(Des.:H)。类似地，可以为图3中的其他每个节点构建可达性索引。如果强社交图中包含两个节点间的社交信任路径，就可以立刻检索出它们间的可达性，从而极大地节省了运行时间。

（2）社交关系索引：社交关系索引是用来记录数据图中映射路径的最大聚合社交影响因子。

下面是社交关系索引的详细信息：

①如果两个节点间存在的一条路径的聚合T，r和ρ值比这两个节点间其他路径上的相应值都大，就把该路径长度以及相关的社交影响因子值作为索引值；

②否则，将最多为3条路径建立索引，它们分别具有最大的聚合T、r和ρ值。

例2考虑图3中所展示的社交关系的索引。以节点C为例，从C到它的后继节点H存在两条路径，分别是路径p1(C,E,H)和路径p2(C,F,H)，并且AS(p1(C,E,H))比AS(p2(C,F,H))的聚合社交影响因子都大。随后，记录p1的聚合社交影响因子。类似地，可以用这种方法对其他节点构建索引。

基于这种社交关系索引，可以快速地搜索一个强社交图中是否存在可行的社交信任路径以及节点间是否存在具有最佳效用的最优路径，极大地减少了路径查询时间。

5.3 小结

Fig.3 Index of SSG in domainj图3 强社交图在领域 j中的索引

上述两个索引记录了强社交图中社会信任路径的一些重要信息，基于这些信息，可以快速地判断出两个节点间是否存在可行的社会信任路径，并且找到包含在强社交图中的具有最佳效用的最优路径，从而极大地减少了时间。强社交图的结构和社交关系通常会在很长的一段时间内保持稳定。因此，不需要频繁地更新索引，也就减少了维护索引的开销。另外，关于索引更新的方法在文献[25-26]中有详细的论述。

6 SSG-MCBA

在本章中，基于蒙特卡罗方法[27]，提出了一种新颖的有效并且高效的近似算法SSG-MCBA。

蒙特卡罗方法：蒙特卡罗方法[27]是一种依赖重复随机抽样来计算结果的计算算法，是解决NP完全问题[27-28]的方法之一。一般来讲，蒙特卡罗方法包含4个步骤：（1）定义输入；（2）产生随机输入；（3）对每个输入执行计算；（4）将结果聚合成最终结果。

算法描述：提出了一种新的高效近似算法SSGMCBA。SSG-MCBA采用蒙特卡罗方法分别从vt（目标点）到vs（源点）以及vs到vt进行路径搜索。在每一步的搜索过程中，SSG-MCBA最多选择K个候选点。接下来，详细介绍SSG-MCBA。

在社交信任路径查找中，如果一条路径满足信任质量约束，那就意味着这条路径上的每个信任质量属性（T、r和ρ）都应该大于相应的给定的信任质量约束。因此，提出了一个目标方程（式（2））来判断某条路径上的聚合属性值是否满足给定的信任质量约束。从式（2）中可以看出，如果一条社交信任路径中有一个聚合信任质量属性值不满足相应的信任质量约束，那么δ(p)＞1，否则δ(p)≤ 1。

反向搜索：在从vt到vs的反向搜索过程中，SSGMCBA计算从vt到它的当前向后扩展节点（BEN，例如图4中的节点vd）的社交信任路径的δ值。如果这个向后扩展节点属于强社交图，那么SSG-MCBA就可以通过社交影响因子的索引值计算具有最小δ值的路径。否则，就需要基于下面的策略1，用SSGMCBA选择具有前K小个δ值的邻接点作为候选点（例如图4中的va、vb和vc）。随后，就可以基于式（3）选择其中一个节点作为接下来的向后扩展节点。

Fig.4 BEN and FDN图4 BEN和FDN

策略1（查询最小δ值的K路径）根据式（2），如果一条路径的δ值越小，那么它就越有可能成为一个可行解。因此，当给定一个从vt到vd的已经部分识别的社交信任路径时，就可以为每条从vt到vd的每个邻接点的路径计算一个δ值，并且记录下前K个最小值，每个值所对应的节点（例如图4中的va、vb和vc）都是下一个反向扩展节点的候选节点。根据式（3）所计算出来的概率大小选择候选节点。

正向搜索：如果通过反向搜索得到一个可行解，那么SSC-MCBA对社交网络进行一次从vs到vt的正向搜索。该过程使用上述反向搜索提供的信息来判断是否存在一条比上述返回的可行路径ps更好的路径pt(F(pt)＞F(ps))。在该过程中，对于当前向前扩展节点的每个邻接点，如果当前扩展节点属于强社交图，那么SSG-MCBA就可以根据强社交图中的索引信息计算出一条社交信任路径。否则，SSG-MCBA就会计算从vs到中间节点vm这条路径（用表示）的聚合社交信任属性值。用表示反向搜索得到的一条从vm到vt的路径，结合，就可以得到一条从vs到vt的预测路径（用表示）。接下来，基于下面的策略2，SSC-MCBA选择满足下列条件的K个候选点：（1）vs到vt的这条预测路径上的所有正向扩展节点都是可行解；（2）它们具有前K大的F值。那么根据式（4）计算出来的概率，它们有一个将会成为下一个向前扩展节点。最终，SSG-MCBA计算出从vs到新正向扩展节点的F值，并且根据策略2更新这条路径上的聚合信任质量属性值。

策略2（查询前K个最大F值的路径）社交信任路径查询的目的就是找到那些具有最佳效用同时还满足信任质量约束的路径。因此，给定一条从vs到vm(vm≠vt)的社交信任路径，如果pfm是可行的，SSGMCBA就计算出从vs到vm的每个邻接点的路径效用值，并且记录下拥有前K个最大路径效用的邻接点（如图5中的节点vx、vy和vz），这些节点就是下一个正向扩展节点的候选点。由于本文的策略是在每一步的查找过程中选择不超过K个邻接点，因此它可以减少搜索空间，提高执行效率。

Fig.5 FEN and BDN图5 FEN和BDN

SSG-MCBA使用双重蒙特卡罗搜索，因此它的时间复杂度是O(MU)，其中M是模拟的次数，U是社交网络中节点的最大出度。根据power-law特征[12]，在社交网络中只有一小部分的节点拥有较高的出度，因此在SSG-MCBA中，每个节点在K路径选择时，不需要通过大量地修剪邻接点（候选节点）就可以保持一个较小规模的搜索空间，这就使得SSGMCBA会有更高的可能性找到高质量的社交信任路径。另外，如果一个强社交图包含源节点和目标节点，SSG-MCBA就可以根据索引快速搜索到最优的社交信任路径。

7 实验

目前还没有一个包含所有社交关系（如T、r和ρ）[16]的完整的语义社交网络。另一方面，由于本文算法的目标是在在线社交网络中找到多条社交信任路径，为了研究提出的路径查询算法的性能，需要一个包含社交网络结构的数据集[12]。因此选择了现实生活中两个真实的社交网络数据集，分别是Enron email（cs.cmu.edu/enron/，包含87 474个节点和300 511条边）和Epinions数据集（trustlet.org，包含88 180个节点和717 667条边）。这两个数据集已经被证明具有社交网络的相关属性，并且被广泛应用于在线社交网络上的信任度研究中[10,29]。

7.1 实验设置

实验的相关设置：

（1）首先，从两个数据集中随机地选择一对源点和目标点，并抽取出它们所构成的子网络。这两个子网一个包含1 695个节点，12 175条边，另一个包含1 746个节点，13 320条边。

（2）在现实生活中，社交影响因子的值不存在固定的模式。为了不失一般性，使用Matlab中的函数rand()函数随机设置这些影响因子的值。

（3）D-MCBA是目前最优的语义社交网络中信任路径查找算法。因此比较了SSG-MCBA和D-MCBA在可信路径查找中的性能。

（4）考虑到在线社交网络中小世界的特点，将最大搜索跳数设置为6。另外，设置一个相对较低的信任质量约束(QoCT=0.005,QoCr=0.005,QoCρ=0.005)使得两种算法有高的可能性在社交网络中找到一个可行解。否则，如果两种算法都没有解，就无法比较它们的性能。将K值设置为5、10、15、20和25。

两个实验都使用Matlab R2013a运行，运行环境是 Intel Xeon E5645 2.40 GHz CPU，3 GB RAM，Windows 7专业版操作系统，数据库是MySQL 5.6。

7.2 实验结果

SSG-MCBA和D-MCBA的效用性和运行时间取5次独立实验的平均值。结果见图6到图11。

实验1（平均路径效用）为了能够根据查找到的社交信任路径的质量来比较算法的效用性，首先用不同的模拟次数和强社交图数量来检测相应的路径平均效用。

图6和图7是SSG-MCBA和D-MCBA基于Enron email和Epinions数据集中不同数目的强社交图，模拟1 000到5 000次所得出的平均路径效用值。从这两张图中可以看出，SSG-MCBA方法求出的平均路径效用值在所有情况下都要优于D-MCBA。这是因为SSG-MCBA将强社交图中两个节点间具有最大聚合社交因子值的社交信任路径做了索引。这就增加了找到一条拥有较高效用值的路径的可能性。另外，从图中可以看出，在相同的模拟次数下，SSGMCBA得出的路径平均效用值随着强社交图数目的增加而增加，但是D-MCBA却不能做到这点。这是因为如果强社交图中两个节点间具有最大社交影响因子值的那条社交信任路径已经被建立起索引，那么这种强社交图的数量越多，就越有可能找到包含在其中的正向或反向扩展节点。正因为如此，SSGMCBA更有可能找到一条具有较高效用值的路径。据统计，平均情况下，在Enron email数据集下，SSGMCBA产生的路径效用值是0.180 2而D-MCBA是0.159 0，在Epinions数据集下，SSG-MCBA产生的路径效用值是0.181 1，而D-MCBA是0.166 8。提出的SSG-MCBA方法所得出的计算结果要比D-MCBA的计算结果高出11%。

实验2（可行社交信任路径的数量）为了研究算法在多条社交信任路径查找过程中的有效性，统计了SSG-MCBA和D-MCBA查询出的可行社交信任路径的数量。

Fig.6 Average path utility delivered by SSG-MCBAand D-MCBA(Enron email)图6 SSG-MCBA和D-MCBA得到的平均路径效用（Enron email）

Fig.7 Average path utility delivered by SSG-MCBAand D-MCBA(Epinions)图7 SSG-MCBA和D-MCBA得到的平均路径效用（Epinions）

Fig.8 Number of paths delivered by SSG-MCBAand D-MCBA(Enron email)图8 SSG-MCBA和D-MCBA得到的路径条数（Enron email）

Fig.9 Number of paths delivered by SSG-MCBAand D-MCBA(Epinions)图9 SSG-MCBA和D-MCBA得到的路径条数（Epinions）

Fig.10 Average execution time of SSG-MCBAand D-MCBA(Enron email)图10 SSG-MCBA和D-MCBA的平均运行时间（Enron email）

Fig.11 Average execution time of SSG-MCBAand D-MCBA(Epinions)图11 SSG-MCBA和D-MCBA的平均运行时间（Epinions）

图8和图9是SSG-MCBA和D-MCBA基于Enron email和Epinions数据集中不同数目的强社交图，模拟1 000到5 000次所得出的可行社交信任路径的数量。从图中可以看出：（1）在所有情况下，SSGMCBA都能比D-MCBA查询出更多的可行解。（2）在相同的模拟次数下，SSG-MCBA查询出的可行解随着强社交图数量的增加而增加。这是因为当模拟次数相同时，SSG-MCBA利用社交影响因子值的索引，会有更高的可能性找到一条可行解。另外，强社交图的数量越多，社交影响因子的索引也会更多。因此，当强社交图的数量增多时，SSG-MCBA就可能得出更多的可行解。据统计，平均情况下，在Enron email数据集下，SSG-MCBA得出的可行解的数量是1 359.5，而D-MCBA得出的可行解数量是858.2，在Epinions数据集下，SSG-MCBA得出的可行解的数量是1 380.8，而D-MCBA得出的可行解数量是883。SSG-MCBA的结果要比D-MCBA高出57.4%。

实验3（效率性）为了研究算法的效率，检测了在不同模拟次数和不同强社交图数目的情况下两种算法的平均运行时间。

图10和图11是SSG-MCBA和D-MCBA基于Enron email和Epinions数据集中不同数目的强社交图，模拟1 000到5 000次所得出的平均运行时间。从图中可以看出，在所有情况下，SSG-MCBA的执行时间都要少于D-MCBA。另外，当模拟次数相同的情况下，强社交图的数量越多，SSG-MCBA所需的运行时间就越少。这是因为如果某个强社交图包含一个正向扩展节点或反向扩展节点，SSG-MCBA可以直接计算出这些可行路径的最佳效用值，因此极大地减少了运行时间。据统计，平均情况下，在Enron email下SSG-MCBA的运行时间是1.113 s，D-MCBA的运行时间是1.478 s，在Epinions数据集下，SSGMCBA的运行时间是1.195 s，而D-MCBA的运行时间是1.594 s。本文算法可以节省33.5%的运行时间。

8 总结

本文提出了语义社交网结构以及NP完全的多约束社交信任路径查询问题。为了解决这些极具挑战的问题，提出了强社交图这个概念，并且介绍了关于它的索引方法。根据强社交图的索引，提出了一个高效的近似算法SSG-MCBA来解决社交网络中多条社交信任路径查找的问题。在两个真实数据集上的实验结果表明，提出的SSG-MCBA方法无论是在路径查找的质量还是效率方面都要优于目前最好的信任路径查找算法，D-MCBA。