S³协议模型在学习共同体意见领袖识别中的应用

颜榴红 贾靓

【摘 要】

意见领袖在社交网络成员中具有巨大影响力，识别意见领袖对于任何社交网络，包括在线学习共同体，都有重大意义。目前，意见领袖识别方法大多忽略了对学习共同体中话题和成员的评分数据。原因很可能是学习共同体平台缺乏保障评分结果真实性的技术手段，致使研究者无法获取可靠的评分数据。本文提出了一种满足S3（社交性、扩展性和安全性）计算需求的协议模型，保证评分数据收集过程和结果的真实性和正确性，从而将评分数据纳入意见领袖识别的关键环节——影响力分析。在引入评分因素的基础上，提出了一种新的适用于意见领袖识别的影响力分析方法。

【关键词】 领袖识别；学习共同体；分布式计算；影响力

【中图分类号】 G40-057 【文献标识码】 A 【文章编号】 1009—458x（2015）01—0055—06

一、引言

自20世纪90年代计算机科学繁荣发展以来，作为革命性技术之一的网络技术突飞猛进。今天，网络与普通人的日常生活紧密相关，现实世界的很多社会活动，如商业、教育和娱乐等，都被映射到网络中。对于社会网络中开展的活动，通常会存在能对大多数用户产生舆论和意见导向的一小群用户，这些用户被称为意见领袖[1][2][3]。对于在线学习共同体，意见领袖往往能通过在线学习交流形成的直接与间接社会关系，对其他用户造成波及效应[4]。虽然很多研究着眼于学习共同体中意见领袖的识别，但多使用常见的数据分析手段，如话题或关键字提取等，而忽略了评分数据。原因很可能是缺乏可靠的技术手段保证评分数据，特别是指定时间段内多用户并发评分的真实性。为了全面、精确地反映意见领袖识别过程中的个体关系，本文提出一种满足社交性、扩展性和安全性的协议模型，用于确保评分数据的真实性和正确性，并探索一种应用评分数据的影响力分析方法。

本文针对学习共同体，改进了Giurgiua 等提出的[S3]协议模型[5]，并提出了一种应用该协议模型收集数据的影响力分析方法。 该协议首先将学习共同体按用户参与特性进行分组，对各组用户投票采用先跨组后组内的累加式收集，直至完成所有用户投票收集。该协议已被证明满足[S3]计算要求[6]。本文将[S3]协议收集的评分数据引入意见领袖识别过程中一个主要因子（即影响力）的评估，并将其量化为两部分：一是潜在意见领袖对浏览话题用户的直接影响；二是其对话题回复用户的波及效应。前者主要取决于浏览次数，后者由回复用户的影响力决定，两者在本质上都受评分数据的影响。

二、文献回顾

多数意见领袖识别模型都基于社交网络中个体关系分析。个体种类及其关系取决于研究涉及的范围。已有研究中必要的个体种类和关系分别是用户和用户间关系，通常根据研究涉及范围的大小完成量化。一些识别模型不仅涉及用户和话题，而且深入到内在的用户心理类型和外在现实世界，如SuperedgeRank算法[7]。一些模型仅将用户及其文档模型化为个体，并细致分析了两种个体的各个因素，如用户行为、话题相似性等[8]。还有一些模型仅考虑社交网络中的某一方面，并对此开展深入研究，如用于量化用户关系的距分析[9]。

从模型实现来看，目前的意见领袖识别大致分为三类：依赖图的类型、不依赖图的类型和混合类型。多数是混合类型。一般情况下，依赖图的类型借助社交网络分析（social network analysis，SNA）对用户分类，将其互动映射为图中的节点后进行评估[10][11]。这种类型的缺点是当节点数增加后，算法的复杂性和处理图的代价过高[12]，如SuperedgeRank算法完全依赖图中节点化的superedge实现，定义了四种个体并将个体集合抽象为层，四层中个体间的关系由连接个体的superedge体现。当个体数量增加时，superedge（即节点数量）呈指数级增长。具有较平衡性能的混合型使用图式的数据，但采用不依赖图的算法完成分析，如将用户间关系概念化为图中入度（in-degree）和出度（out-degree），并依此完成距计算。这个过程只涉及了图的概念，并未引入图及其算法。不依赖图的类型直接分析原始数据而不使用图的概念或算法，如使用原始数据直接计算用户影响力和活跃程度[13]。

虽然有很多研究着眼于意见领袖识别，但引入用户投票结果的很少，主要原因很可能是缺乏可靠的技术手段收集投票结果，致使结果有可能被潜在恶意用户篡改。目前，涉及[S3]要求的协议模型大多没有满足其计算要求，例如Benaloth、Rivest和Yao提出的协议模型仅具备有限的可扩展性[14][15][16]；Aberer等描述了一种改进的安全机制，但要求分布式计算仅在受信任节点之间展开[17]；Angluin等构造的协议模型涉及[S3]的可扩展性，但只具备有限的容错性[18]；Guerraoui介绍的协议模型[19]的可扩展性比Angluin等构造的好，但要求代理节点具有唯一的身份标识，从而降低了隐私性。完全满足社交性、扩展性和安全性的[S3]协议模型应适用于多用户并发投票过程，为收集用户数据提供可靠保障。本文通过[S3]协议模型收集的数据作为评分因子引入意见领袖识别过程中的关键因素——影响力分析，并受到了李艳燕提出的意见领袖识别算法的启发[20]。

三、以评分为基础的用户影响力分析

学习共同体中的用户可被六种性质描述：持久性、集中性、专业性、新颖性、影响力和活跃性[21]，其中的决定性因素，同时也是诸多研究者注意的焦点是影响力。除影响力以外，具有其他高特性的用户很难在学习共同体用户中产生波及效应。

1. 影响力的界定

学习共同体中用户活动及关系主要由文本信息和评分体系体现。典型的文本数据包括发布文档和回复。评分数据包括对文档和用户的直接评分和类似文档浏览次数的间接评分。令[u]表示用户，[p]表示文档，[t]表示使用类似LDA[22]的软件从[p]中提取的、或直接由发布用户标记的话题或关键字，则[Pt，u]表示由[u]发布的、主要与[t]相关的文档集合；[Rp]表示对[p]的回复集合；[Vp，u]表示浏览过由[u]发布的[p]的用户集合；[U]表示所有用户集合；[T]表示某一特定时刻；[Ratingu1，u2∈（-1，1）]表示归一化的[u1]对[u2]的评分；[Ratingu1，u2]的正、零和负值分别表示[u1]对[u2]有正面的印象、没有印象和负面的印象；[S]表示集合[S]的基数。在时刻[T]的[u]的影响力[Influence（u）T]定义如下：

2. [S3]计算的相关定义

为能正确计算[Rating∙]，应开发满足[S3]计算要求的协议。以下定义详细描述了[S3]计算要求。节点[P]是平台中的认证用户，即通过平台对个人身份和单位核实的用户个体。节点与个体一一对应。在平台中节点具有两个基本权利：① 与任一节点通信，且信息无法被其他节点截获；② 标注任一节点。标注是指当某节点的非法行为被察觉时，有所察觉的节点对存在非法行为的节点进行描述。该描述对任一节点可见，但描述与被描述节点之间必须存在过通信。如果描述为真，则被描述节点的平台内信誉下降，描述成为被描述节点可见个人信息的一部分，保存一段时间后描述将被删除；如果描述为假，描述节点的平台内信誉下降，被限制描述一段时间并且被平台标注。这种用户相互监督和系统有限介入的模式的有效性已被各种社交网络所证明，如在线游戏[23]、推荐系统[24]和垃圾电子邮件过滤[25]等。

协议模型[T]的隐私性由协议模型[D]保证。因此，存在满足[S3]计算要求的协议模型，基于此，本文构造了适用于学习共同体的协议模型[LC]。

四、[LC]协议模型

1. [LC]协议模型概述

[LC]的活动图如图1所示，包括3个阶段：阶段1：构建群和生成代理，阶段2：生成本地合集和阶段3：处理代标识的合集。

2. [LC]协议模型的阶段1：构建群和生成代理

根据已有研究[27][28]，当[n]个节点被随机分配到[n]个大小为[n]的群时，低信誉节点也将被随机分配到各群。协议模型[LC]的节点分配根据学习共同体进行。如果分布式计算不涉及某些共同体内部的数据，则采用上述方法分配节点；如果涉及，则[n]个节点按共同体进行分配，例如[ni]个节点参与了共同体[i]，那么这[ni]个节点将被分配至[ni]个大小为[ni]的群。由于[LC]协议模型需要特定群参与阶段3，这个特定群根据节点的声誉生成，即无论是否涉及共同体内部数据，在分配节点之前，选出[n]个声誉最高的节点组成特定群，剩下的[n-n]个节点按照上述方法分配（如图2所示）。

分配完成的群组成一个封闭有序的环。对于任意群中的任意节点[P]，[P]可以向其所在群中的任意节点发送信息，也可以向位于环中紧邻[P]所在群的后续[K]个群以及每个群中的[L]个节点发送信息。所有[K×L]个节点称为[P]的代理。这些代理的选择优先考虑与P常联系的正常信誉节点，根据其交互的频率[F]和声誉[R]计算[Rαln （F）]其中[F，R，α>1]，按该值从大到小的顺序选择[K×L]个节点作为代理，并拒绝低信誉节点。[α>1]保证[R]对结果具有较大的影响，[ln （F）]削弱了[F]对结果的影响。

3. [LC]协议模型的阶段2：生成本地合集

合并完成后，验证下式是否成立：

其中，[δV]是[V]中任意两点间距离的最大值，且[k∈N]，判断合并后的输入是否还在[（U，d）]中，即[v1 ⨁ ...⨁ vk∈V]是否成立。根据[⨁]的性质，[V⊆U]成立。如果上式成立，则将合并后的输入被发送至代理所在群的所有节点，否则触发警报。如果有节点收到了源自同一节点的生成输入和逆输入，则两者的合并结果为空。每个节点合并收到的输入形成本地合集。阶段2适用于所有群，阶段3是由声望群发起的。图3描述了阶段2的活动。

4. [LC]协议模型的阶段3：处理代标识的合集

阶段1构造的声望群发起了阶段3。阶段2结束后，所有节点的真实输入保存于本地合集中。阶段3的目的是通过处理代标识的合集，最终使每个节点都拥有只包括所有节点真实输入的本地合集，最终在本地对[n]个真实输入完成[f]的运算。

声望群中没有非法节点，因此可以保证其每个节点合并得到的本地合集都是相同的。每个节点对其合集添加唯一的标识信息，形成标识合集。标识合集被每个节点发送给对应的[K×L]个代理。对于每个收到标识合集的代理，如果是首次收到，则将本地合集与标识合集合并，然后发送给隔壁群中对应的[L]个代理；如果收到两次以上，该代理会检查合集的标识是否与上一次相同，如果相同则在群内广播，然后抛弃合集，否则触发警报。这一过程在图4中称为“处理代标识的合集”。该处理过程反复进行，直到每个节点都收到了其他[n-1]个节点的真实输入为止。

在上述3个阶段中，一旦触发警报，说明合集被参与计算的低信誉节点篡改，计算结果将不能保证正确，警报触发后整个计算会终止，系统会查找参与生成该合集的低信誉节点，并标注这些节点。根据Giurgiu等的理论[30]，协议模型[LC]具有[ ]-可扩展性、[ ]-准确性和隐私性，满足[S3]计算要求。

五、结语

本文提出了一种分析网络学习共同体中用户影响力因素的方法，并构造了名为[LC]的[S3]协议模型。该协议模型收集的可靠的投票数据被用于影响力分析。通过本文提出的结合用户投票数据的影响力分析方法，可以构建一种涵盖用户间关系的精细的意见领袖识别模型。本文从理论上探讨了应用[LC]协议模型评分数据的影响力分析，仍需进一步实证研究验证其有效性。今后的研究还可以将用户持久性、集中性、专业性、新颖性和活跃性模型化，以完善适用于学习共同体的意见领袖识别方法。

[参考文献]

[1][4][8][13][20][22][26] Y. Li， S. Ma， Y. Zhang， R. Huang. Kinshuk， “An improved mix framework for opinion leader identification in online learning communities”， Knowledge-Based Syst.， vol. 43， 2013， pp. 43-51.

[2][7] N. Ma， Y. Liu， “SuperedgeRank algorithm and its application in identifying opinion leader of online public opinion supernetwork”， Expert Syst. with Applicat.， vol. 41， no. 4， 2014， pp. 1357-1368.

[3][9] Y. S. Kim， V. L. Tran， “Assessing the ripple effects of online opinion leaders with trust and distrust metrics”， ， Expert Syst. with Applicat.， vol. 40， no. 9， 2013， pp. 3500-3511.

[5][6][21][30] A. Giurgiua， R. Guerraouia， K. Huguenina，A.-M. Kermarrecb， “Computing in social networks”， Inform. And Computation， vol. 234， pp. 3-16， Feb. 2014.

[10] P. A. C. Smith， “Knowledge sharing and strategic capital the importance and identification of opinion leaders”， The Learning Organization， vol. 12， no. 6， 2005， pp. 563-574.

[11] F. Bodendorf， C. Kaiser， “Detecting opinion leaders and trends in online social networks”， In Proc. of the 2nd ACM workshop on social web search and mining， 2009， pp. 65-68.

[12] J. M. Kleinberg， “Authoritative sources in a hyperlinked environment”， J. of the ACM， vol. 46， no. 5， 1999， pp. 604-632.

[14] J.Benaloh， “Secret sharing homomorphisms： keeping shares of a secret”， in Proc. of the 6th Annu. Int. Conf. Advances in Cryptology， London， UK， 1986， pp. 251-260.

[15] R. Rivest， A. Shamir， Y. Tauman， “How to share a secret”， Commun. of ACM， vol. 22， no. 11， pp. 612-613， Nov. 1979.

[16] A. Yao， “Protocols for secure computations”， in Proc. of the 23rd IEEE Annu. Symp. on Found. of Comput. Sci.， Washington， DC， USA， 1982， pp. 160-164.

[17] L.-H. Vu， K. Aberer， S. Buchegger， A. Datta， “Enabling secure secret sharing indistributed online social networks”， in Proc. of the 25th Annu. Comput. Security Applic. Conf.， Honolulu， Hawaii， USA， 2009， pp. 419-428.

[18] D. Angluin， J. Aspnes， Z. Diamadi， M. J. Fischer， R. Peralta， “Computation in networks of passively mobile finite-state sensors”， Distrib. Comput.，vol. 4， no.18， 2006， pp. 235-253.

[19] R. Guerraoui， E. Ruppert， “Names Trump Malice： tiny mobile agents can tolerate Byzantine failures”， in Proc. of the 36th Int. Colloq. on Automata， Languages and Programming， Rhodes， Greece， 2009， pp. 484-495.

[23] P. Kabus， W. W. Terpstra， M. Cilia， A. Buchmann， “Addressing cheating in distributed MMOGs”， in Proc. of the 4th Ann. Workshop on Network and Syst. Support for Games， New York， USA， 2005， pp. 1-6.

[24] N. Tran， B. Min， J. Li， L. Subramanian， Sybil-resilient online content voting， in Proc. of the 6th USENIX Symp. on Networked Syst. Design and Implementation， Boston， USA， 2009， pp. 15-28.

[25] M. Sirivianos， K. Kim， X. Yang， “SocialFilter： introducing social trust to collaborative spam mitigation”， in Proc. of the 30th IEEE Int. Conf. Comput. Commun.， Shanghai， China， 2011， pp. 2300-2308.

[27] Z. Galil， M. Yung， “Partitioned encryption and achieving simultaneity by partitioning”， Inf. Process. Lett.， vol. 26， no. 2， pp. 81-88， 1987.

[28] I. Gupta， K. Birman， P. Linga， A. Demers， R. van Renesse Kelips， “Building an efficient and stable P2P DHT through increased memory and back-ground overhead”， in Proc. of the Second Int. Workshop on Peer-to-Peer Syst.， Berkeley， CA， USA ， 2003， pp. 160-169.

[29] C. Delporte-Gallet， H. Fauconnier， R. Guerraoui， E. Ruppert， “Secretive birds： privacy in population protocols”， in Proc. of the 11th Int. Conf. Principles of Distributed Syst.， Guadeloupe， French West Indies， 2007， pp. 329-342.

收稿日期：2014-08-15

作者简介：颜榴红，常州大学外国语学院（213164）。

贾靓，常州大学信息科学与工程学院（213164）。

责任编辑 日 新

责任校对 日 新