一种信任优化的中心节点选取策略

熊师洵，范通让

（石家庄铁道大学 信息科学与技术学院，河北 石家庄 050043）

随着对网络性质的物理意义和数学特性的研究，人们逐渐发现，在社会网络环境中，社团结构是构成网络环境的主要单元，即社会网络是由数量不等的“群落”或“社团”组成的。社团内部节点的关联度较强，而社团间节点的关联度较弱。经过多年的研究，人们注意到，各个群落之间在进行信息交互时，其大部分信息流都会经过中心节点，中心节点对于信息的交互，起到了非常重要的作用。所以，在社会网络传播中，中心节点的选择与使用成为了信息交互的关键。

然而，当前研究者们对于中心节点的选择策略更多的体现在网络中的社团范围判定、入度与出度的计算等，而忽略了节点本身的可靠性。不可靠的节点所传播的信息中极有可能出现木马、病毒或是垃圾信息，严重时甚至会导致社区网络的瘫痪。于是人们又提出一种网络传播信任机制，对于每个在网络中产生交互的节点，都赋予一个信任值，通过信任值的相互关系来确定节点是否具有可靠的传播性能。但是当前人们的研究更侧重于对全网任意节点间信任值的计算方法，由于网络节点的数量庞大，分布不均匀，因此在进行网络节点选择时易耗费大量的时间与费用。

针对上述问题，笔者提出了一种基于社区间信任关系的中心节点选择策略。在以往的信任关系研究中，信任关系的计算往往会受到时域衰减和智能记忆的影响。因此，在不考虑时域衰减和智能记忆的前提下，以中心节点的选择为基础，加入信任关系值的计算。通过判断中心节点间的信任值，来判断该节点是否具有可靠的传播特性，进而产生信息流的传播。

1 相关工作

目前，对于复杂网络中的中心节点的选取策略一直是网络世界中非常具有代表性的问题，研究人员对其进行了长达数十年的研究。在最初的的研究中，研究人员通过对人们在社会网络活动中的行为进行对比与分析，比如交互邮件行为［1］和科研论文引用行为［2］等等。并在文献［3，4］引入了社会网络挖掘方法，该方法以Web2.0为基础，并且将社会网络的分析结果应用于各大领域。而近年来，网络规格的急剧增大，对这些领域造成了一定的冲击。中心性等网络性质度量方法由于复杂性太高而不能在大规模网络中有效的应用。并且复杂网络通常都具有无标度特性，而无标度网络中存在少量具有较高度数的活跃节点，比如在文献［5］中引用了网络Cora。在该网络中，度数最高的节点，其总度数可以达到网络总度数的75.6%。因此在复杂网络中，要划分一个符合网络拓扑特性的区域，只需选出其局部度数最高的部分节点即可。该方法可以快速高效的划分出具有满足网络拓扑特性的区域。根据文献［6］，我们认为选取区域若要满足网络拓扑特性，其最大的特点是所选取的中心点的总度数和必须大于等于该网络中所有节点总度数和的50%，这时绝大部分边都会与中心点相连。

节点选取的另一个关键是信任关系值的计算。Ravi Kumar等人最早在文献［7］中提出了一种信任关系的算法，这使得我们在一个网络系统中寻找可以交互的节点时，给予了一种判断节点之间关系的方法。Blaze等人在文献［8］中提出一种新的信任管理机制，适用于大规模分布式环境，在解决该环境下的信任问题时具有非常好的优越性，并以此研究出了相应的信任管理系统Police maker［9］。Sabater J等人在文献［10］提出信任系统REGRET，该系统以声望值为基础，结合了社会网络分析的结果与分等级的结构体等不同类型的声望值，并对其进行综合计算来得出最终的节点信任值。甘早斌等人在文献［11］中提出了多维度的信誉计算方法，认为在电子商务这样的社会网络中，仅靠单一维度的信誉计算已经不满足现阶段的信任关系计算。Phalak Rasik等人在文献［12］提出了一种新的网络信任预测框架机制，以等级制度和经验分享为基础。但由于在该机制下，用户被划分出的信任等级并不总是有效的，并且用户数量的变化使其不能保证每次实验都具有采样性，因此，利用Rigg算法可以有效的计算内容质量及用户可信度。上述文献中提到的信任模型均采用了多维度信誉评估方法，该方法在针对节点欺骗行为方面具有一定的效果，但不适用于合适交易节点的选取，因为该方法使节点的选择具有较大的随意性，易造成效率低下。王刚等人在文献［13］提出了一个基于竞标方法的交易节点的选取策略，较好的弥补了交易节点选择策略的不足。但是在社会网络中大部分网络具有非常明显的无标度特性，单一的对交易节点进行选取会耗费大量的时间。

因此，我们在前期关于互联网中节点信息流行为关系的研究为基础，引入了节点竞标策略、基于节点交互的信任值计算方法与中心节点选取策略。在综合竞标策略的基础上，直接对中心节点进行信任关系计算并筛选。该方法在规模较大的网络中可以节约大量的时间，并且可以对网络中信息流的安全传输起到一定的作用。

2 受信任的中心节点选择策略

大规模复杂网络的受信任的中心节点选择一直是研究者们研究的问题。人们在对信任关系的研究中提出了许多与之相应的模型，而对于信任中心节点的研究尚未找到较好的对应模型。

2.1 竞标策略

竞标是一种国际上普遍运用的有组织的市场交易行为。竞标分为的招标、投标、开标、评标和中标五个部分，其基本流程为：招标人（买方）发出招标公告或投标邀请书，说明所需要的资源，邀请不特定的投标人（卖方）按照一定的程序进行投标，投标人向招标人提供投标申请书，然后由专家评委组对所有的投标申请书进行评定，最后将评定结果公布，并宣布中标人。

2.2 基于竞标信任的中心节点选择策略

在竞标的基础上，我们模仿竞标的模式，建立了基于竞标信任的中心节点选择策略。其主要思想为：假定某一节点想要与某一社区结构发生信息流交互，先将该社区中的所有节点进行筛选，选择出该社区的中心节点集，然后再由评估节点对该中心节点集中的节点进行评估，以此选择出中心节点集中可信任的中心节点，最后与该中心节点发生信息流交互，流程如图1。

在开始策略研究之前，先引入几个定义和说明：

服务招标节点（invitation of tender）：社会网络中获取所需资源服务的节点，记为IT。

服务评估节点（Service Request）：社会网络中对目标信任值进行评价的节点，记为E。

服务交易节点（Service Provider）：社会网络中提供资源服务并被评估的节点，记为SP。

图1 网络节点的竞标流程

2.3 中心节点选取步骤设计

通过对以上服务节点的引入，根据竞标的步骤和对于竞标信任的设想，将信任优化的中心节点选取步骤设计如下：

（1）生成网络节点，对其进行初始化，设置该网络中的每个网络节点的角色，并设置评估节点与招标节点的参数。

（2）将投标节点按照节点度数的大小进行排序，将排序后的节点依次放入节点队列Q。

（3）将队列Q中的第一个元素提出，并放入中心集合C，此时中心集合C中的节点就是服务交易节点。

（4）计算中心点集合C中的节点的总度数。当总度数大于全图所有节点度数和的50%，或C中的节点数目超过了预设节点总数的10%时，则终止循环；否则继续执行第3步。

（5）取出中心点集合C中的第一个节点，由招标节点和评标节点进行运算，如果该节点的信任值超过了阈值，则被确定为可以产生信息流交互的节点，否则抛弃该节点，重新执行第5步。

方案具体流程如图2所示。

图2 信任优化的中心节点选取流程图

3 信任节点的综合信任计算

选取策略，并对其进行简单的改进。信任关系的重点是综合信任的计算，这里引用了文献［13，14］中的直接信任和推荐信任的计算方法。其中直接信任表示根据评估节点E和服务提供节点SP历史交互情况而确定的信任值，本文用下式来表示：

其中代表节点E和节点SP交易成功的次数表示节点E和节点SP交易不成功的次数。

而推荐信任引用了文献［14］中的推荐信任计算公式，由于不考虑服务内容的相似性，我们对其进行简单的改进，表示为：

其中是针对服务交易节点SP的综合评价，是指评估节点i和服务交易节点SP的服务内容，α是指评估节点对服务交易节点的信任程度，SP表示服务交易节点，i表示评估节点表示服务交易节点与评估节点熟悉程度的权因子。

最终在进行信任值计算时，先由直接信任计算出直接信任值，再计算推荐评估信任值，即可得到最终的信任值。并通过与预设阈值的对比，来确定该节点是否具有产生信息流的资格，最终确定是否产生信息流。关于推荐信任的计算方法，我们可以在以后的课题中对其继续进行研究。

4 结束语

在探索从社会网络中寻找中心节点的策略时，中心节点的可靠性往往被忽略。受信任的传播问题是一个基础性问题，而这个问题应该在网络系统中被合理的解决。本文中，提出了一个基于信任传播的中心节点选择策略，通过计算找出受信任的中心节点，来进行信息流的传播。该方法为信息流的正确传播提升了一定的可靠性。未来在关于中心节点的时衰特性，智能计算等方向还有许多值得深入研究的课题。

［1］Stolfo S J，Hershkop S，Wang K，Nimeskern O，Hu CW.Behavior profiling of email［J］.Proc.of the 1st NSF/NIJ Symp.On Intelligence，Security Informatics.Tucson：Springer－Verlag，2003，13（1）：74－90.

［2］Newman MEJ.The structure of scientific collaboration networks［J］.National Academy of Sciences of the United States of America，2001，98（2）：404－409.

［3］Ishida K.Extracting latent weblog communities：A partitioning algorithm for bipartite graphs［J］.Proc.of the 2nd Annual Workshop on the Weblogging Ecosystem.2005，13（2）：83－90.

［4］Lerman K，Jones L.Social browsing on Flickr［J］.Proc.of the Int’l Conf.on Weblogs and Social Media.2006.

［5］Nieminen J.On centrality in a graph［J］.Scandinavian Journal of Psychology，1974，15（1）：332－336.

［6］唐晋韬，王挺，王戟.适合复杂网络分析的最短路径近似算法［J］.软件学报，2011，22（10）：2279－2290.

［7］Ravi Kumar，R.Guha，Prabhakar Raghavan，Andrew Tomkins.Propagation of Trust and Distrust.Computer Science，2005：43－52

［8］Blaze M，Feigenbaum J，Lacy J.Decentralized trust management［J］.Proceedings of the 17th TEEE Symposium on Security and Privacy.Oakland，CA，USA，1996，164－173.

［9］Blaze M，Feigenbaum J，Keromytis A D.KeyNote.Trust management for public－key infrastructures［J］.Christianson B，Crispo B，William S et al.eds.Cambridge 1998Security Protocols International Workshop.Berlin：Springer－Verglag，1999，59－63.

［10］Sabater J，Sierra C.REGRET.Reputation in gregarious societies［J］.Proceedings of the 15th International Conference on Autonomous Agents.Montreal，Canada，2001，194－195.

［11］甘早斌，丁倩，李开，肖国强.基于声誉的多维度信任计算算法［J］.软件学报，2011，22（10）？：2401－2411.

［12］Kim Young Ae，Phalak Rasik.A trust prediction framework in rating－based experience sharing social networks without a Web of Trust［J］.Information Sciences，2012，191（3）：128－145.

［13］王刚，桂小林.社会网络中交易节点的选取及其信任关系计算方法［J］.计算机学报，2013，36（2）：369－383.

［14］Wang Gang，Gui Xiaolin，Wei Guangfu.A recommendation trust model based on E－commerce transactions content－similarity［J］.Proceedings of the 2010International Conference on Machine Vision and Human－Machine Interface，Kaifeng，China，2010，105－108.