采用社会网络能力发现的众包服务节点选择算法

彭振龙,桂小林

(1.西安交通大学电子与信息学部,710049,西安; 2.泉州师范学院陈守仁商学院,362000,福建泉州; 3.西安交通大学陕西省计算机网络重点实验室,710049,西安; 4.泉州师范学院云计算物联网电子商务智能福建省高校工程研究中心,362000,福建泉州)

众包系统的质量控制始终是一个严峻挑战[1-2]。一个众包系统一般包括平台、网络、任务的发布者和任务的接受者。众包平台通常通过一定的激励机制,吸引任务接受者参与众包任务[3-5]。由于众包系统的开放性、匿名性,导致可能存在很多的参与者不认真执行任务,而仅仅为了获得奖励,这一现象严重影响了众包系统的效率和可信度[6-8]。控制众包服务质量的基本策略主要有两个:一是事后控制,即对众包服务的结果进行筛查处理;二是事前控制,即对参与者的能力和诚信度进行评估,选择更可靠更合适的参与者。本文从社会关系角度出发,选择更合适、更可靠的参与者,从而提升众包服务质量,属于事前控制策略。

在质量控制方面:Howe提出了golden standard data模式,即在众包任务中随机插入一些具有标准答案的任务,根据参与者对这些任务的应答,判断参与者对其他任务的完成质量[1];Peng等将激励机制与参与者完成众包任务的结果质量相结合,根据众包任务参与者的有效贡献来决定奖励大小,与统一定价方案相比,该方法具有较好的性能[3];Tong等采用了simple majority voting方法,即根据多个参与者对同一个任务的应答,采用简单的多数投票方法确定最终的结果[9]。此外,一种称为historical performance-based methods的方法被广泛使用,该方法根据参与者的历史任务完成情况和评价,对其执行结果赋予一定的权值。但是,以上这些方法没有考虑任务需求与参与者能力之间的匹配,而且存在冷启动问题,即刚开始的时候无法对该参与者进行评价[7,10-11]。另外,Zhang等提出了一个简单有效的称为MacroWiz的框架,并利用MSN进行众包活动,当收到一个众包任务后,MacroWiz可以激励在线MSN用户贡献他们的知识或建议,协助任务请求者选择可靠答案并作出最终决策[12]。Eickhoff等提出了一个反作弊策略,并且得出2条结论:①过滤恶意的参与者可以减少低质量的数据,但是会延长任务的完成时间;②参与者的可靠性无法由其历史任务完成率进行保证[13]。Qin等针对图片的易修改性,提出了一个简单有效的轻量级的图片修改检测方法,用于保证基于手机的图片版权[14]。Shamir等分析了人工分类和标注的一致性,提出了一种基于监督机器学习的众包质量控制方法[15]。

在参与者选择方面,考虑到终端的移动性会导致收集数据的路由发生变化,Zhao等提出了一个无中心化的路由策略,即利用服务节点之间的机会相遇来转发任务、收集数据[16-18]。众包任务一般可分为时间敏感任务和可容忍延时的任务,基于此,Guo等提出了一个适用于多任务的移动用户选择和大范围的众包服务场景的ActiveCrowd的框架,并利用greedy enhanced genetic algorithm为参与者实现总距离或总开销的最优或近似最优[19]。张君涛等将子道路和任务绑定在一起,提出了一种基于矢量任务地图的渐进式的任务分发方法,并提高了任务地图的分辨率[20]。Peng等提出了一种基于泰森多边形的参与者节点选择方法,将传统的基于标准栅格的参与者区域覆盖变成基于任务特征的不规则区域覆盖,提升了参与者的执行效率,降低了平台或任务发布者的总体成本[21]。安健等利用城市中公交载体的轨迹可预测、活动覆盖范围大、乘客节点自主聚集且交互时间有保证等优势,提出了一种基于公交系统的众包任务差异化分发方法[22]。张文东等利用社会关系的多维要素,构造多维语义分级树和空间索引编码,引入交互信息熵等相关概念,提出了一种社会属性亲密度量化方法,对社会关系的不对称性进行分析和比较,从而提高了亲密度量化方法的客观性[23]。

这些方法通过选择更优质的服务节点,在一定程度上提升了众包的服务质量,但是通常需要所有的参与者都事先在平台上注册,而且他们的信息(兴趣、爱好、专长等)是固定不变的,任务发布者或者平台能够获得他们的所有信息。但是,实践中参与者的位置属性、专长都有可能随着时间而变化,即使是众包服务平台,也不可能获知那些在平台上注册用户的全部信息,更不可能获知那些未在平台上注册的潜在参与者的全部信息。

基于此,本文提出了基于社会关系的众包服务节点选择算法,任务发布者不需要获得全部参与者的信息,算法即会根据任务发布者与其朋友的社会关系、聊天信息等,对朋友能力进行动态、精准地分类与刻画,将任务与朋友的能力值进行匹配,从而选择最合适的参与者参与众包任务。当朋友接受任务后,以同样的方式在自己的朋友圈里发布该任务。如此循环迭代,能够更高效、准确地完成众包任务。本文算法充分利用了社会关系中的天然信任关系,构建了众包任务参与者之间的信任链条,并且可以由社会关系中的六度分隔理论保证任务传输的时间效率[24-25]。

1 基于社会网络的能力发现与任务传播

1.1 社会网络

社会网络是由许多节点构成的一种社会关系结构,节点通常是指个人或组织,社会网络代表各种社会关系,这些社会关系可以把从偶然相识的泛泛之交到紧密结合的家庭关系的各种人们或组织串连起来[24]。社会网络内个体成员之间以任何形式进行的联系称为交互。交互能帮助社会网络中的节点之间形成相对稳定的关系体系,进而影响节点的社会行为。

1.2 基本定义

每个节点都有其自身的属性,如兴趣爱好、专业特长等,并且对他的所有朋友都会有能力区分和认识,如认为某个朋友适合干什么、某个朋友对什么感兴趣等。社会网络中的一个节点用p表示,p的朋友数用m表示。众包系统约定的能力类别数用n表示。任务参与者既包括任务发布者,又包括任务接受者。

定义1:能力。能力是完成一个项目或者任务所需要的基本技能或素质,用a表示。

定义2:能力集合。能力集合是完成一个众包任务需要的所有能力的集合。平台能力集合表示为A={a1,a2,…,an},共n种能力。

定义3:能力值。众包任务参与者的能力值是该参与者对应能力集合中各个能力的数值。由于一个节点的能力值在其不同朋友中会有不同认知,因此即使是同一种能力,也可能会有不同的能力值。能力值的初始值Cp是由节点p的朋友根据其各自的认知设定的,没有设定的默认为0。Cp具体表示为

(1)

(2)

定义5:诚信指数。诚信指数是指某个众包参与者的所有朋友对该参与者质量因子的加权平均。p的所有朋友对p总体评价可用诚信指数hp表示,表达式为

(3)

定义6:朋友能力向量。社会网络中的节点对其每个朋友在能力集合中对应的能力大小,构成该节点的一个朋友能力向量。如节点p与朋友pj之间的能力向量ep,pj可表示为

(4)

定义7:朋友能力矩阵。社会网络中的某一节点的所有朋友能力向量,构成了该节点的朋友能力矩阵。节点p的朋友能力矩阵Ep可表示为

(5)

2 社会关系中基于内容的能力发现

2.1 参与者社会关系重构

结合式(1)(3)(5),可以将社会网络中的节点p重新定义为一个三元组

p=〈hp,Cp,Ep〉

(6)

2.2 能力值的计算与更新

在能力值计算上,主要统计节点p与其朋友之间就某个关键词的出现次数。如果某个关键词出现在其朋友圈中,则以更大的权重计算。含加权朋友圈的能力值动态更新算法的伪代码如下。

1:k=1;

2:Do whilek<=n

∥动态更新节点p的ak能力的能力值

5:k=k+1;

6:End Do;

2.3 含加权朋友圈能力的能力矩阵计算与更新

2.2节主要对节点p的能力值进行计算和更新,更新后可以生成一个1×n的行向量。在此基础之上,还需要对所有的朋友进行能力计算,最后生成一个朋友能力矩阵,算法伪代码如下。

1:k=1;j=1;

2:Do whilej<=m

3: Do whilek<=n

5:k=k+1;

6: End Do;

7:j=j+1;

8:End Do;

通过式(2)和能力值与能力矩阵的计算与更新,节点p完成了对自己社会关系的重构,可重写式(5)为

p=

(7)

3 仿真实验及结果分析

微信是中国最流行的一款移动即时聊天工具,根据最近腾讯公布的2019年第一季度财报,微信月活跃用户数量已正式突破了11亿,同比增长达6.9%,2018年微信日均发送信息450亿条。微信为用户构建了一个庞大的社会关系。本文系统主要以微信交互数据为基础,为了避免隐私泄漏,本文系统只允许在使用者授权同意的情况下,分析自己的聊天记录和内容,对自己的朋友按主题类别进行能力区分,重构自己的社会关系。本文实验模拟微信交互并进行数据分析。

3.1 数据准备

猪八戒网[26]是中国著名的众包服务网站之一,通过对其网站内容进行分析发现,众包项目可以分成20个类目,分别是:知识产权、品牌设计、IT/软件、营销传播、工商财税、科技服务、电商服务等。不失一般性,选择其中的10个类目进行数据分析。由第1节分析可知,每种类目都代表一种能力或主题。10种能力的编号分别为1～10,代表了平台能力集合为A={1,2,…,10}。对每种能力提炼了部分关键词,如表1所示。

表1 能力分类及部分关键词

3.2 能力发现

设定节点p有100个朋友,编号分别为1～100,本节重点介绍该节点的朋友能力矩阵Ep的生成过程。

设定一次采样周期为1个月,随机从10个主题中选择若干个交互主题,交互主题的概率密度呈泊松分布,与每个朋友的交互次数在5～500之间。

根据表1,分别统计了1次采样周期与5次采样周期下,100个朋友中前10个朋友的能力值(交互次数),分别如表2和表3所示。

表2 1次采样下前10个朋友10种主题的交互次数

表3 5次采样下前10个朋友10种主题的交互次数

表4则显示了5次采样周期下,前10个朋友的朋友圈中出现各类关键词的次数,该值表明了该朋友在不同能力类别的朋友圈能力大小。假设朋友圈能力的权重为2,综合表3和表4,可得到最终的朋友综合能力矩阵,如表5所示。

根据表2中的初始能力,随机选取了编号为5、8、69的朋友进行研究,图1和图2分别显示了在1次采样下和5次采样下,节点p与所有朋友在不同主题(能力)下的交互次数(能力值)。图3为1次采样与5次采样(标准化后)下节点p与所有朋友的总交互次数的对比图。可以看出,两条线的趋势基本保持一致,说明1次采样与5次采样的结果相对稳定。图4为加入加权朋友圈能力后,节点p与朋友的交互次数。从图1、2、4可以看出,总体而言,交互次数具有相对稳定性,说明节点p的能力具有相对稳定性,且与某个朋友在某种能力上的交互次数越多,则该能力值越大,反之亦然。

表4 朋友圈5次采样下前10个朋友10种主题的交互次数

表5 计算朋友圈能力值后前10个朋友的最终综合能力矩阵

图1 部分节点1次采样下不同主题的交互次数

图2 部分节点5次采样下不同主题的交互次数

图3 1次采样与5次采样下不同主题所有朋友的总交互次数

图4 5次采样下加入朋友圈权重后不同主题的交互次数

3.3 候选传播节点选择

当一个任务发布者想发布任务时,需要选择任务的类目或者所需的能力关键词,系统将从他自己的朋友中选择匹配度最高的若干用户做第1次任务分发。表6所示为1次仿真实验中得到的单能力候选节点排序表,以5次采样数据得到的最终综合能力矩阵(表5)为基础,将候选节点编号按照能力值从大到小进行顺序,只显示能力值最高的前10个节点。

根据表6中数据,如果节点p想要发布能力编号为2的众包任务,则应该在其好友列表中选择编号为57、28、31、50……的朋友,这是因为这些朋友的能力属性最为匹配。如果众包任务需要多种能力,只需要对不同的能力设计相应的权重,即可找到最合适的朋友。实验中,选择了不同的能力要求,并设置了相应的权重,具体选择的结果如表7所示。

表6 1次实验得到的单能力候选节点排序表(以5次采样数据为基础)

表7 多能力及不同权重下的节点选择结果

3.4 任务分发的时效性分析

众包系统中任务分发的时间效率是很重要的,特别是对于那些延迟敏感的任务。因此,随机选择了4种任务类目:兼职、品牌创意、软件开发、个人生活,即表1中编号为3、4、6、8的4种能力。本文采用了3种仿真实验,即随机分发方法、全分发方法、本文方法。假设节点p有2 000个朋友,并设定任务发布成功的标准是收到50个有效的任务转发或执行结果数据。在本文方法和随机分发方法中,都选择200个朋友进行,全分发则意味着任务发送给所有朋友。在实验中,还假设当任务能力需求落在朋友能力矩阵Ep中各能力主题的前50个朋友内时,意味着该朋友将执行任务,任务完成时间是50个朋友完成任务的平均时间。不同分发策略下的完成任务平均时间如图5所示,可以看出:随机分发方法需要花费最长的时间,这是因为其不能精确地发现最合适的参与者;本文方法比随机分发平均节省了约64.5%的时间。进一步地,本文方法和全分发方法的结果基本相似,表明本文方法可以精准地发现合适的工作者,但是本文方法选择的样本数只有全分发方法的1/10,意味着本文方法给无关朋友带来的信息干扰要比全分发策略少得多。此外,大多数任务分配都伴随着一定的激励机制,更少的样本空间意味着能够节约更多的成本。

第3节仿真实验表明:本文系统能顺利地按主题计算各个朋友的能力值大小,并进行采样与更新,同时可以对朋友的诚信指数进行采集与计算更新,形成能力矩阵;对任意一个在能力集合内的众包任务,都能正确选择出最匹配的朋友,据此找到传播候选节点并进行任务分发或数据回传。

任何一个候选节点都可以重复以上步骤,经过若干次迭代,任务能在朋友圈中快速扩展,且朋友圈中的信任关系能被充分利用,在一定程度上增加了众包参与者的可信度,从而提升了众包的数据质量。

图5 不同分发策略下完成任务的平均时间

4 结束语

众包服务节点的选择应综合考虑其背景知识、社会关系、信誉度等多种属性。本文方法首先需要对参与者进行能力发现,即从参与者日常在社交网络中的交互内容、交互次数、交互频率、朋友圈、加入的群、在群里的活跃度等信息中,对朋友的能力进行提炼,形成能力集合并对能力进行量化分级。通过评估参与者的社会关系和社区归属特性,利用参与者社会关系中隐含的天然信任关系,有针对性地完成任务的分发和后续数据的路由转发。因为人们总是更愿意转发与自己有社会关系的人的信息,所以通过社会关系找到的参与者候选集,比随机选择的参与者具有更高的精准性,仿真实验验证了本文方法的有效性。未来还需要在以下方面开展研究。

一是客户信息的隐私保护。未来需要开发基于智能终端的轻量级的隐私保护方法,确保感知者的通信录、社交信息、轨迹与位置信息等不被泄漏。

二是交互信息的多样化。本文中仅仅考虑了文本数据。实际上,声音、图片、视频、表情等超文本元素在社交网络中使用非常频繁,这些元素在朋友间的表达感情方面越来越重要。这需要通过AI、语音识别、图像理解等技术,融合社交网络中的全媒体信息,以便更精准地刻画朋友信息。

三是交互的时间维度。本文在分析交互内容时,没有考虑交互发生的时间因素,而时间因素往往具有重要意义。例如同样的交互内容,一个星期内发生的可能比6个月前发生的更准确。如果加入交互内容的时间因素,方法会变得更加复杂,此时可以通过折中方法,给不同的采样阶段设置不同的权重。