基于微分进化算法的消息传播网构建

邓柯+闫述

摘 要：某事件发生时，除消息以广播的方式通知相关人员外，还需依赖个体之间的责任关系传播，消除信息孤岛问题。社会网络（Social Network）中的个体之间存在复杂的责任关系，针对该问题，以滑坡事件发生时为例，创建带责任制的消息传播网模型，并采用微分进化算法评估关系属性和来往交流等因素对责任关系的影响权重，同时加入责任弱化（Responsibility Decline，RD）效应模拟消息传播过程。结果表明，关系属性和面对面交流对责任关系的影响较大，紧急消息的传播过程也会受距离的影响。实现了一对多的责任分派机制，多对多的责任分派方式则有待进一步研究。

关键词：消息传播网；责任关系；影响权重；微分进化算法

DOIDOI：10.11907/rjdk.162758

中图分类号：TP301

文献标识码：A 文章编号：1672-7800（2017）007-0005-06

0 引言

滑坡是我国多发的地质灾害。在面向区内全体人员的WSN（Wireless Sensor Network）滑坡监测预警系统[1-2]方面，手机作为配备最普遍的个人通信工具，是监测系统信息传递与接收的理想节点。但在事关生命安全的紧急情况下，必须使撤离警报无遗漏地传达到每一个人，包括老人、病人、婴幼儿等无行为能力的人员。由于人机分离、遗漏等造成的信息孤岛问题是监测系统中需要解决的问题。因此，除以消息广播的方式传播紧急预警信息给具有接收信息能力的移动设备外，为解决信息孤岛的问题还需将消息传播的责任划分到个体，这意味着收到消息的责任个体需要将消息传播给被负责对象。传统的消息传播网以网络社交平台为传输媒介，研究节点、边的特征及信息特征对消息传播的影响，强调消息的扩散性[3]，但滑坡紧急事件发生时的报警消息传达强调及时性和知晓性。滑坡监测系统将区域中的居民依据责任关系构造成一个消息传播网，责任关系主要受关系属性和来往交流等因素的影响，且影响权重不同。针对多属性决策问题有主观赋权法、客观赋权法[4-5]，解决该问题的采纳率达到了85.8%[1]。为实现滑坡报警消息无遗漏地通知，这里引入主要解决实参数优化问题的微分进化算法[6-8]，确立了影响因子的权重，使得模拟消息传播过程中采纳率在居民之间的百米范围内达到97.8%，同时这种方案考虑了滑坡事件的紧急特殊性，加入受传播距离影响的RD效应，使消息在电话传播和走动传递两种方式中自由切换，与实际情况结合更灵活。根据自定义的目标函数解决优化与责任关系相关的权重组合问题，能够实现一对多的责任分派问题。结果显示，关系属性和各种交流方式对责任关系的影响各占一定比重，但关系属性和面对面交流方式影响更大。同时解决该问题的方案可以运用到其它紧急事件发生并需要传播紧急消息的场景，具有应用拓展性。

1 消息传播网模型构建

1.1 问题描述

滑坡监测系统中的消息传播网由具有信息传播能力的正常人和无知晓能力的老人、病人、婴幼儿等责任关系构成，责任关系主要考虑由关系属性和来往交流频数综合决定。若收到紧急消息的居民不能以电话的方式传播消息给未收到紧急消息的居民，則以走动的方式传递消息，走动传递消息会受到距离的影响。依据以上问题构建网络模型如下：

（1）建立消息传播网络。滑坡区的居民依据责任关系构建一个带权有向的消息传播网络G（V，E，W），V是网络中的节点集合，V={v1，v2，v3，…，vN}，W是边的权值集合，W={wij|i≠j，1≤i≤N，1≤j≤N }，wij表示节点vi与节点vj之间的相互权值，代表居民之间的责任关系强度，其中wij≠wji。

（2）加入RD效应。假设电话传播信息失败，则需要个体移动传播信息给被负责对象。这时需要考虑与距离相关的传播时间，存在随时间延迟的RD效应。假设有正常居民A、B、C，其中居民A、B收到紧急信息，居民C没有收到紧急信息且电话联系不上，wAC>wBC，理应由A负责通知C，但A到C的距离远大于B到C 的距离，在紧急事件发生时需要考虑消息传达的及时性，应由距离C较近的B负责传递消息给C，传播时间更短。因此，A的责任因消息传播时间间隔变大而弱化了。

（3）网络中存在普通节点和特殊节点。以居民为节点构成的网络图G（V，E，W），存在老人、病人、婴幼儿等无知晓能力的个体形成的节点，可以视为特殊节点（vs），其余视为普通节点（vg）。

1.2 特征提取

信息传播以责任制的要求进行，对于任意用户u（假设该用户没有收到广播消息），存在wuv=max{wui|u≠i，1≤i≤N }，与其责任关系最强的用户v负责传播信息给用户u。wuv受居民u与居民v之间关系属性以及来往交流频数的影响。

（1）关系属性。任何两个有关联的用户之间存在某种关系属性，这些关系可以分为家庭关系、朋友关系、情侣关系、邻里关系等。这里可以用情感系数来表示情感的强弱，4种情感系数表示为Rfamily、Rfriend、Rflover、Rneighbor。这几种系数一般存在以下大小关系：

（2）来往交流频数。居民之间存在走访（视为一种面对面的交流方式）、短信通话、微信、QQ等多种交流方式，交流会影响人与人之间的关系，因此来往交流频数在影响责任关系中占有一定的权重。

走访频数（visits）：统计居民之间一年内的走访频数，用集合Fvisits表示。v_fuv表示居民u与居民v之间的走访频数。

短信通话频数（calls）：统计居民之间一年内的短信通话频数，用集合Fcalls表示。c_fuv表示居民u与居民v之间的短信通话频数。

微信和QQ交流频数（QQs）：统计居民之间在一年内用QQ或者微信通信的总频数，用集合FQQs表示。q_fuv表示居民u与居民v之间的微信QQ交流频数。

以上几种特征所占的影响比重不同，各个特征取值范围不一，需要作进一步的标准化处理。这里采用Min-Max标准化方法，将以上特征集合的取值分别映射到[0，1]区间：

其中，fuv和f′uv分别表示标准化处理前后的特征值。

1.3 模型建立

关系属性和来往交流对责任关系各有一定的影响权重，设定关系属性所占权重为wR，来往交流中走访方式所占权重为wvisits，短信通话所占权重为wcalls，微信QQ交流所占权重为wQQs，用户u与用户v的责任关系强度wuv可以表示如下：

节点之间的影响力或信息传播能力随着时间间隔增大存在指数衰减规律[9]。假设居民u在tu时刻收到紧急信息，在tv时刻居民v才收到居民u传来的紧急信息。居民v在时刻tv收到居民u紧急信息的概率为fp（（v，tv）|（u，tu）），这个概率会随着时间间隔Δt=tv-tu的增大而降低。同时wuv越大代表居民之间的责任关系越强，传播概率p（u，v，c）越大，居民之间紧急消息的初始传播概率p（u，v，c）与wuv成正比关系。C为不大于1的常量，c为传播信息，设定：

RD效应可以视为传播概率随时间衰减。融合时间衰减因素的传播概率模型通常有3种表示方法，如表1所示的3种传播概率模型，分别是指数模型[10-11]、幂率模型和瑞利模型。指数模型和幂率模型中的传播概率随着Δt的增大单调递减，幂率模型中传播概率的演化还具有长尾特征。瑞利模型中传播概率先是随Δt增大而增加，到达峰值后开始缓慢降低，该模型研究传染病传播概率增长和衰退的演化规律[12]。初始传播概率与责任关系强度正相关，随着传播时间增大会产生RD效应，这里选择指数模型来刻画传播概率随Δt的衰减规律。

在指数模型中τ（u，v，c）代表传播延迟，传播延迟受传播主体、传播客体、传播内容等因素的影响。当紧急事件发生时，传播主体需立即将紧急消息传递给传播客体，在居民之间传播延迟无差别（忽略电话通话时延），因此τ（u，v，c）可以视为一个常量Llatency。变换指数模型后，随时间变化的传播概率fp（（v，tv）|（u，tu））表示为：

其中，Suv表示u与v之间的传播距离，人员行动平均速率为v。

在1.1问题描述中，问题（1）和问题（2）是预选的两种消息传播方式，传播主体首选电话传播方式，当电话传播方式失败时再选择人员走动传播方式。设电话传播方式成功的概率为P，采用人员走动传播方式的概率为1-P，若普通节点vg收到紧急消息概率Pr（vg，par（vg）），par（vg）表示传递消息给vg的父节点，有：

问题（3）考虑到消息传播网中老人、病人、婴幼儿等这些无知晓能力的信息孤岛点，针对这类节点选择采用人员走动的方式传递消息，则：

将式（4）、式（5）分别带入式（6）、式（7），得到式（8）、式（9）：

从式（3）、式（8）、式（9）可以看出，在确定父节点收到消息的情况下，节点收到消息的概率与父节点之间的关系属性以及来往交流频度相关，同时受节点之间距离的影响。

2 权重评估

权重值是责任划分的重要因素，责任划分主要受关系属性和来往交流的影响，需确定wR、wvisits、wcalls、wQQs的最佳值。找出最佳权重值有两种方法可以选择，一种是典型的确定性最优算法，比喻穷举搜索，可以返回最优解。但这种方法需要搜索整个解空间，时间复杂度太大。为了减少计算量，且4个权重值之和为1，权重的取值范围限制在0.000 001～0.999 997。这些权重值的组合就有999 9973种情况，即需要从9.999 91×1017个权值组合中评估最佳权重组合。穷举算法找出这4个权重值，在时间上代价太高，不利于快速决策。另一种是选择一种元启发式方法搜索最佳权重组合。这种智能技术能够搜索解空间并减少评估次数，且在能接受的合理时间内完成，针对目标函数，元启发式方法往往获得近似最优解。微分进化（Differential Evolution）搜索算法，这种元启发式算法非常适用于寻找最优值问题[13-14]。

微分进化算法是一种以人群为基础的算法，人群中的个体对应于目标问题的一个候选解，每个个体是一个存放实际值的向量[15]。设xi表示人群中一个个体，xi[j]元素存放影响因素的权重值，有：

微分进化算法首先随机产生有N个个体的人群，个体中元素的初始值从区间[0.000 01，0.999 97]中选择。参数组在G次换代中不断变化和重组，获得最优解。算法伪代码如下：

//F代表突变因子，CR代表重组因子popl=N；Evaluate（popl）；g=0；while（g

表2為实验中微分进化算法的参数配置，这些值是在调试和测试之后选定的。针对该问题确定了一个目标函数F（xi），微分进化算法需要实现该函数的最小化。目标函数F（xi）由两部分组成：

（1）本实验需要收集与每个居民有责任关系的人员信息。根据居民u的主观判断将这些人员按与自己的责任强弱降序排列，设这个主观序列为Au={y1，y2，y3，…，yn}。求出式（3）在xi组合条件下有责任关系的人员与u的综合权值wuv（v表示与u有责任关系的其他居民），依据综合权值的大小降序排列，设该理论序列为Bu={z1，z2，z3，…，zn}。求序列Bu相对于序列Au的逆序数Inversion_Count（u，xi）。

（2）求xi中超出允许范围的变量数Invalid_Params（xi）：

F（xi）需要考虑（1）和（2）两部分：

为方便采集实验数据，以长咀村为实验基地，约980人。长咀村分7个小区，为便捷调查人员关系，以太子庙小区作为调查代表，调查中病人、幼儿、老人、外出、正常人的人数各为1、3、19、36、33。收集居民之间的日常情感关系属性和来往交流信息，经标准化后带入模型求解最小F（xi），并获取最优权重组合。

表3、表4为实验在Visual C++ 6.0 Win32环境下运行出的部分结果。在实验中依据式（1）设置不同的日常情感关系属性，本次实验设置了4组不同关系属性值进行了4组模拟，表1中的两张子表分别为4组模拟的候选解，选取最小F（xi）值为最优解，对应的权重组合为最优权重组合。从两张子表可以看出，不同关系属性值的设定会影响最优解。但依据图3候选解的散点分布图来看，整体上日常情感关系和走访频数对责任关系的影响比重较大，其次是短信/电话频数，由于居民不常使用QQ/微信，因此这种交流方式对责任关系的影响很小。同时，观察（a）（b）（c）（d）4张子图发现走访频数即面对面的交流频数对责任关系的影响可见一斑，这可以解释为在同种日常情感关系中，面对面的交流方式会增进人与人之间的感情，产生更强的责任关系。

3 模型验证

依据问题（2）描述中的责任弱化效应，责任分派过程还需加入距离影响因素。式（8）、式（9）体现了节点收到消息的概率随距离呈指数衰减的规律，将按概率大小模拟分派任务，概率高者会有较大的责任去传递消息给被负责对象。

模拟前阶段随机设定一些个体为广播消息接受者，这些节点为种子节点。同时，随机初始化个体之间的距离（在现实生活中该距离可以由定位系统测量）。在第3部分的权重评估中分析了各因素对责任关系的影响比重，从结果中选择F（xi）值最小的权重组合xi=（0.250 365，0.391 904，0.235 851，0.092 311）加入模拟运算。将消息传播网中的点集合V分成4部分，Vg1为种子节点集合，Vg2为未收到消息的正常节点集合，Vs1为收到消息的特殊节点集合，Vs2为未收到消息的特殊节点集合。

以太子庙为紧急事件发生点，初始状态下|Vs1|=0，| Vs2|=23，| Vg1|+| Vg2|=69。决策中的责任分派过程如下：①对任意节点vg1∈Vg1，vg2∈Vg2，vs2∈Vg2，求出所有Pr（vg2，vg1），Pr（vs2，vg1）的值；②从求出的值中找出最大Pr（vg2，vg1）和Pr（vs2，vg1）的值，确定对应的消息传播节点vg1和消息接收节点vg2 、vs2。vg1传递消息给被负责对象；③更新集合，Vg1= Vg1∪{ vg2}，Vg2= Vg2-{ vg2}，Vs1= Vs1∪{ vs2}，Vs2= Vs2-{ vs2}，同时更新距离；④循环重复过程①～③，直到| Vg2|=0，| Vs2|=0，消息传播结束。

这里模拟了一对多的责任分派问题，即一个人可能会被分派到同时通知两个或更多人的任务，还需要决策出优先任务。责任分派的过程依然在Visual C++ 6.0 Win32环境下模拟运行，在此过程中随机初始化居民之间的距离在100m内，同时记录了正常居民的消息传递路径、距离以及通知人员数量。表5为在不同P值设定下，各人员的最大可能行走距离。

表5中Si表示编号为i的行动人员在消息传递过程中的最大可能行动距离。当P值越小时，即电话接受消息的概率减小，通过走动传播消息概率的增大，由于RD效应，距离产生的影响增大。从表4可以看出，部分人员的责任分派会受到距离的影响，如编号为0、27、71、52、83的人员本身会依据责任关系获得分派任务，但随着距离影响的增大不会传递消息。编号为12、72的人员存在距离优势，在距离影响变大时也会参与消息传递。从现实生活来看，居民手机基本随身携带，电话接收到消息的概率会较大，因此整体来说，系统主要依靠责任关系分派任务，表中也体现出在百米范围内大部分人员的责任划分不会受到距离的很大影响。同时考虑信息传达的及时性，若以100m的行动时间为期限，则这种模型的决策方案的采纳率可以达到97.8%。

4 结语

紧急事件发生时，为确保消息无遗漏地传达到每一个人，需要增加责任分派机制。面对复杂的人际关系，本文主要考虑了日常情感和来往交流频数对人际责任关系的影响，该模型后期还可以加入其它多元变化因素，如传播主体、传播客体、传播内容等。人员消息传播过程是复杂多样的，这里只考虑了一对多的责任分派问题，多对多的责任分派问题还待进一步研究。同时该方案可以运用到其它自然灾害所引起的紧急事件中，有一定的应用拓展性。

参考文献：

[1]卢子龙.无线网络滑坡监测的信息处理與知晓概率的研究[D].镇江：江苏大学，2015.

[2]MANEESHA V RAMESH.Design，development，and deployment of a wireless sensor network for detection of landslides[J].Ad Hoc Networks，2014（2）：18.

[3]周东浩，韩文报，王勇军.基于节点信息特征的社会网络信息传播模型[J].计算机研究与发展，2015，52（1）：156-166.

[4]徐玖平，吳巍.多属性决策的理论与方法[M].北京：清华大学出版社，2006.

[5]张全.复杂多属性决策研究[M].沈阳：东北大学出版社，2008.

[6] STRON R，PRICE K.Differential evolution a simple and efficient heuristic for global optimization over continuous spaces[J].Journal of Global Optimization，1997（11）： 341-359.

[7]SU HAIJUN，YANG YUPU，WANG YUJIA.A review of differential evolution algorithms[J].Department of Automation from Shanghai Jiaotong University，2012.

[7]苏海军，杨煜普，王宇嘉.微分进化算法的研究综述[J].上海：上海交通大学，2012.

[8]J C CORTS，J M COLMENAR，J I HIDALGO.Modeling and predicting the Spanish Bachillerato academic results over the next few years using a random network model[J].Physica A，2016（2）： 36-49.

[9]GOMEZ-RODRIGUEZ M，BALDUZZI D，SCHLKOPF B.Uncovering the temporal dynamics of diffusion networks[C].Proc of the 28th Int Conf on Machine Learning.New York： ACM，2011： 561-568.

[10]GOYAL A，BONCHI F，LAKSHMANAN LVS.Learning influence probabilities in social network[C].Proc of the 3rd ACM Int Conf on Web Search and Data Mining，New York： ACM，2010： 241-250.

[11]GOMEZ-RODRIGUEZ M，LESKOVEC J，KRAUSE A.Inferring networks of diffusion and influence[C].Proc of the 16th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining，New York：ACM，2010：1019-1028.

[12]WALLINGA J，TEUNIS P.Different epidemic curves for severe acute respiratory syndrome reveal similar impact of control measures[J].American Journal of Epidemiology，2004，160（6）：509-516.

[13]K V PRICE.An introduction to differential evolution[Z].New optimization platform，1999：79-108.

[14]R STORN.System design by constraint adaptation and differential evolution[J].IEEE Trans.Evol.Comput，1999，3 （1）：22-34.

[15]K P WONG，Z DONG.Differential evolution，an alternative approach to evolutionary algorithm[C].Proceedings of the 13th International Conference on Intelligent Systems Application to Power Systems，2005（2）：73-83.