基于情境分析的移动社交网络群体任务分配

王小雪，张志勇，史培宁

(河南科技大学 信息工程学院，河南 洛阳 471023)

0 引 言

群体计算[1]旨在整合互联网上大量未知用户(人群)和计算资源(机群)来处理现有计算技术难以完成的复杂任务。在群体计算的研究中，任务分配问题是核心问题之一，该问题研究如何将实时出现的群体任务分配给适宜的用户。现有工作[2]通常基于静态场景，即全部群体任务与用户的信息在任务分配前已经完整获知，较少融合用户多维环境信息[3]，且很少考虑到用户的属性信息与历史记录，但群体任务在实际应用中动态出现，且需实时地对其进行任务分配。上下文感知[4-6]在1994年被提出，并将情景定义为位置，周边的人和对象的集合和这类对象的变化。Carl K.Chang[7]提出了情境分析理论，并基于此理论提出Situ架构，该架构能够通过分析用户历史行为数据获取用户的实时意图，从而为用户提供实时并且个性化的服务。张等[8]在上述理论的基础上建立了SocialSitu理论，提出了一种面向在线社交网络用户的行为模式发现方法，通过分析用户的历史行为数据，预测用户下一时刻意图。因此，在此研究的基础上，通过分析移动社交用户的SocialSitu(t)序列和历史信息提出了面向移动在线社交网络的任务分配架构，进一步提出基于SocialSitu的用户适合度任务分配算法并通过实验验证算法的适用性。

1 任务分配架构

本文所提出的面向在线社交网络的群体计算系统架构的目的在于为社交网络中的用户分配合适的任务，因此需满足3个基本需求：①在社交网络中找到最适合某项任务的移动用户群体；②服务端可以自主设计、发布、评价任务；③提供用户执行任务的接口，因此本文设计了一个层次架构以满足这些要求，群体计算系统架构如图1所示。具体的分层架构设计如下：

(1)社交平台设施层

第一层是社交平台设施层，其中社交媒体平台服务器设计并发布群体计算任务。该层的主要功能是待用户完成任务并回传数据至本层时，平台设施层对用户返回的数据进行处理，处理结果将作为下次该用户分配任务的参考，同时更新群体的信息。

(2)数据处理中间层

第二层是数据处理中间层，数据传输链将社交平台设施层的群体用户数据传递至数据处理中间层，本层分析用户的访问行为(如：登录)与历史信息(如：成功率)，根据基于SocialSitu的用户适合度任务分配算法寻找合适的用户。同时，本层还整理、分析、存储来自群体用户应用层的结果数据。

(3)群体用户应用层

第三层是群体用户应用层，本层包括不同种类的群体应用，并提供群体用户接口。用户加入群体任务后，可以转发任务兴趣相投的好友，待执行任务之后，用户将结果数据返回至数据处理中间层处理。

图1 任务分配架构

2 基于SocialSitu的用户适合度任务分配算法

移动社交用户具有移动性、随机性和复杂性等特征，因此面向移动社交网络用户群体的任务分配不单单要着重考虑用户的可信度和服务能力，而且更要关注用户的访问行为的变化及历史服务信息等因素。考虑到影响任务分配的因素，本文通过分析移动社交用户的历史信息定义了影响任务分配的属性，由这些属性计算得出的用户任务适合度即用户适合某项任务的程度。

2.1 相关定义

定义1 SocialSitu (t)：定义请参见文献[8]。

定义2 成功率Ssucc为移动用户成功完成历史任务的比例，如式(1)所示，其中Nsucc为历史服务成功次数，Ntotal为历史服务总次数

(1)

定义3 平均服务应答时间Sdel为平台分配任务到移动用户接受任务的时间间隔，如式(2)所示，其中d(hj)为历史任务hj的应答时间(hj∈H)，sdel(Ui)为平台分配任务的时间，e(Ui)为用户Ui接受任务的时间，H为用户历史信息

(2)

定义4 满意度Ssat为用户对于系统为其分配的任务的满意程度，如式(3)所示，其中s(hj)为用户对平台分配历史任务hj的满意度(hj∈H)，ρ(式(4))为衰减因子，它是一种随时间变化而动态衰减的量，即所隔时间越久，用户满意度对服务决策的影响越小

(3)

(4)

定义5 用户适合度是评价用户适合执行某项任务的程度。由以上成功率、平均服务应答时间、满意度计算得出，由式(5)所示，适合度越大表示用户越适合此项任务。其中wij表示用户i的第j个属性，αit表示对于任务t，用户Ui的第j个属性duj所占的权重，p为属性的个数

(5)

2.2 分配算法

为实时准确地为移动社交用户分配任务，采用的基于SocialSitu(t)的用户意图序列化算法可根据用户的历史行为的SocialSitu序列实时地预测用户在下一时刻的意图，在了解用户的意图(用户会选择何种任务)的情况下，再计算出移动用户的任务适合度，依据任务适合度大小分配任务。算法流程如图2所示，具体的算法过程如下所示：

(1)获取待完成任务的相关信息。待完成任务列表R={r1,r2,…rn}，遍历i(1≤i≤n)个任务ri的ID，需要完成该项任务的人数K，待完成任务的类别库C，以及任务完成的截止时间T。

(2)在用户列表中获取用户的历史信息，计算出包括用户的完成度Ssucc，平均服务应答时间Sdel，满意度Ssat。

(3)如果用户u当前在线，则跳到步骤(4)，如果用户u为离线用户，则跳到步骤(8)。

(4)对在线用户u的历史SocialSitu(t)信息进行分析处理，并通过用户行为模式发现算法SituBehaviorAnalytics(DS, Min_Support, G)获得用户u的行为序列模式。

(5)将用户u对应特定意图的行为序列模式存储，Compare(Social(0)u,Social(1)u,…,SocialSitu(t-1)u),uBehaviorpattern[intention]函数将用户u当前行为与行为模式序列进行对比，并预测用户u下一刻意图。

(6)如果用户u的意图与待完成任务ri的类别C相关，则将用户u的ID存入待分配任务的用户集合U。

(7)计算用户u对于待完成任务ri的适合度Sui。

(8)计算出所有对于待分配任务ri的用户的适合度，按照适合度从高到低进行排序，选出被分配的用户集合L，将任务ri分配给L中的所有用户。

(9)重复步骤(1)～(7)直到不再有新的未分配的任务。

图2 算法流程

算法1：任务分配算法

Input: 用户集合：U， 用户历史信息：H， 用户的情境信息： SocialSitu(t)， 待完成任务集合：T， 待分配任务用户集合：UT， 所需人数：K

Output: 待分配任务的用户的UserID

TaskAssign(UT, T)

(1)Begin

(2)foreachri∈Randi←1ton

(3)foreachu∈UandSsucc、Sdel、Ssat

(4)ifu is online

(5)u.Behaviorpattern[intentionm]=SituBehaviorAnlytics(DS,Min_Support,G);

(6)foreach intentionm∈Intention

(7)Compare(Social(0)u,Social(1)u,…SocialSitu(t+1)u),uBehaviorpattern[intention]

(8)ifintentionut=intentionm

(9)ifintentionut∈C

(10)u∈UT

(11)endif

(12)endif

(13)foreachu∈UT

(15)endfor

(16)endif

(17)else

(18)foru∈UT

(20)endfor

(21)Rank(Sui);

(22)endfor

(23) Assign(UT, T)

(24)endfor

(25)End

其中SituBehaviorAnlytics(DS, Min_Support, G)函数指分析用户特定意图下的行为模式，DS为用户行为数据集，Min_Support,为最小支持度，G为用户的意图。Compare(Social(0)u,Social(1)u,…,SocialSitu(t-1)u),uBehaviorpattern[intention]函数指将用户当前行为与行为模式进行对比[8]。

3 实验与结果

本文所采用的实验平台是在线社交网络平台CyVOD[9](www.cyvod.net)和CyVOD客户端应用。该平台架构如图3所示。CyVOD平台作为设计、发布、分配任务的服务端，如图4所示。客户端则作为用户申请、执行、反馈、转发任务的应用端，如图5所示。

图3 CyVOD体系架构

图4 服务端任务分配界面

图5 客户端执行任务界面

3.1 实验设计

移动社交网络作为人类传播信息、进行社会交流活动的平台，引发了广泛的应用和关注。当今社交网络平台上的安全隐私问题的凸显，亟需社交网络用户对平台功能、安全防范、隐私保护等功能进行评估[10-12]。根据当前社交网络中普遍存在的安全问题，本文设计了7项社交平台群体评估任务，分别对社交网络平台的安全信任等方面进行评估，评估内容见表1。群体评估的流程如图6所示。

3.2 实验结果

为验证所提算法的正确性，因此与随机分配和基于用户属性两种任务分配算法进行对比。随机任务分配算法即不考虑用户的多维属性与影响因子，只是简单随机地选取用户后分配任务。操作简单但无针对性，因此用户完成度，反馈率均较低。基于用户属性分配算法充分考虑用户的多维属性与影响因子，但是不考虑用户的行为与意图，因此提出的基于SocialSitu算法综合二者优点，取长补短。既充分分析了用户的行为与意图，还综合考量了多维属性与影响因子。

表1 群体评估任务

图6 群体评估流程

3.2.1 正确性分析

表2是通过基于SocialSitu(t)的用户意图序列化算法根据用户的历史行为的SocialSitu序列得出用户的行为模式，并实时地预测出的下一时刻的意图。

表2 基于SocialSitu的用户行为模式与意图

表3是采用随机分配算法所得出的实验数据，表4是采用基于用户属性的任务分配算法所得出的实验数据，表5是采用基于SocialSitu的用户适合度分配算法所得出的实验数据，很显然，随机算法以及基于用户属性分配算法所选取的用户并没有及时反馈信息，从而导致用户完成率低下，用户对平台的所分配任务的满意程度也较低，相对而言，基于SocialSitu的用户适合度分配算法大大提高了用户的完成率与用户满意度。

表3 随机算法任务分配及回收情况

表4 基于用户属性的任务分配及回收情况

表5 基于SocialSitu的用户适合度任务分配及回收情况

3.2.2 有效性分析

为验证所提算法有效性，比较同一任务下用户的适合度，如图7所示，用户ID为9，8，5更适合此项任务。在总体任务数相同的基础上分别比较采用3种算法整体用户的任务平均完成度和满意度，实验结果如图8和图9所示。通过3种分配算法的对比结果可以得出基于SocialSitu的用户适合度分配算法在提高用户任务完成度与用户满意度方面效果显著，用户整体平均完成度较随机和基于属性的分配算法提高平均0.4和0.2左右，平均满意度提高平均0.1和0.2左右，因此可说明基于SocialSitu的用户适合度任务分配算法优势明显。

图7 用户适合度对比情况

图8 3种算法的整体用户完成度比较

图9 3种算法的整体用户满意度比较

4 结束语

在线社交网络的迅速发展，移动设备的普及使得在线社交网络中含有丰富的计算资源，为了充分地利用这些资源，本文提出了一种面向移动社交网络群体的任务分配架构，同时提出了基于SocialSitu的用户适合度任务分配算法，通过分析用户的访问行为、历史信息为用户分配适合的任务，并通过群体评估实验验证了算法的有效性。该算法的分配准确率和用户完成度较高，运算速度还较慢。在后续研究中，考虑利用机器学习中的关联规则解决此问题。