符号网络中基于影响控制特性的传播模型

杨宝龙，吴国文

（东华大学计算机科学与技术学院，上海201620）

符号网络中基于影响控制特性的传播模型

杨宝龙，吴国文

（东华大学计算机科学与技术学院，上海201620）

为探究病毒营销中存在的消极影响泛滥问题，提出一种在符号网络中基于影响控制特性的传播模型，并使用NetLogo仿真平台模拟在符号网络中的传播过程。仿真结果表明，改进传播模型负边在影响传播过程中对网络形势具有重要的导向作用，且在负边较少的情况下，具有局部聚类的特性，同时基于影响控制特性的传播模型在负边较少时，具有更强的局部聚类特性。

病毒营销；符号网络；传播模型；影响控制特性；NetLogo仿真

1 概述

病毒营销也叫口碑营销，是用户通过口头推销的方式将产品推荐给身边人，这些人又以相同的方式推荐给其他人，这样产品的推销就如同病毒传播一样在消费者中传递开来。文献［1］将病毒营销引入计算机领域并从数据挖掘的角度对其进行研究，提到一个关键问题是影响在网络中的传播。之后，文献［2］将影响最大化问题转化为离散优化问题，证明了此问题是NP问题，并且提出了一种贪心算法用于初始影响对象的选择。针对影响最大化问题，国内外出现了一大批研究成果［3］。

然而，随着互联网的不断发展，一些人为了个人利益，滥用病毒营销，单纯追求影响的最大化传播，却忽视了影响的性质。由于不去控制影响的性质，一旦出现消极影响，往往是影响越大，损失越大，传统的病毒营销正处于巨大的危机之中。

为了探究病毒营销中存在的消极影响泛滥问题，将病毒营销扩展到符号网络领域。符号网络最基础的理论是1946年由Heider提出的结构平衡理论，从社会和心理角度阐述了人与人之间的符号关系［4］。根据最新的研究发现，很多在线社会网络中也展现出符号关系：包括积极（友好）和消极（敌对）关系。例如，在线评估网站Epinions允许人们对其他评估者给出积极或消极的评估。相似的，在在线讨论网站Slashdot中，用户可以把其他用户标记为朋友或敌人［5］。因为个体间的关系被定义为积极或是消极，这些社会网络能够用符号网络描述。在符号网络中，节点表示个体，积极或消极的边表示一对个体间存在的积极或消极的关系。正如文献［6］的研究，当人们投票时，人们经常反对某些政策，不是因为他们不认同那些政策，而是因为他们不喜欢提出那些政策的党派领导人。因此，积极和消极关系在符号网络中对舆论的传播具有重要的影响。更广泛地说，积极关系推动了相同观点在个体间的传播，而消极关系催生了相反观点的出现与传播。利用符号网络的一些特性能够在一定程度上缓解消极影响泛滥带来的问题，但是对符号网络传播动力学的研究很稀少。

文献［3］利用线性阈值模型（传统单一影响状态传播模型的一种）的“影响力积累”特性，根据结构平衡理论，在符号网络中构建了具有单一影响状态的传播模型，并在真实符号网络中模拟了影响的传播过程；文献［7］通过研究2种对立影响状态（积极、消极）在符号网络中的传播行为，扩展了传统的SIR模型，提出了一种符号网络中的简单的SIR模型，并详细分析了在不同节点分布下的模型特性；文献［8］在符号网络中简单的SIR模型的基础上，模拟了观点在符号网络中的传播过程，发现了“舆论传播关键比率”，由此揭示了积极和消极观点的初始比例对传播范围产生的重要影响，之后通过采集真实数据，利用情绪加权关系方法建立符号网络，验证了之前的发现［9］。

这些研究成果推动了符号网络传播模型的发展，但是依然存在许多问题：

（1）在传统的单一影响状态传播模型中，只有一种影响状态，因此不需要考虑节点影响状态之间相互转变的情况，但是在符号网络中，存在2种对立的关系，并由此催生了2种对立关系的影响状态，它们之间有相互转变的可能，而之前的那些研究只是将单一影响状态的SIR模型简单扩展到符号网络上，并没有考虑这2种对立关系影响状态之间相互转变的情况。

（2）以往的符号网络传播模型大多从节点数量的变化趋势角度分析问题，很少从网络宏观结构角度考虑问题，缺少对符号网络传播模型宏观结构角度的深入分析。

（3）面对病毒营销出现的消极影响泛滥现象，很少有人能从符号网络传播模型角度给予解释。

针对以上问题，本文提出一种在符号网络中基于影响控制特性传播模型，并使用NetLogo仿真平台模拟影响符号网络的传播过程。

2 相关概念

结构平衡理论是符号网络领域最基础的理论，最早于1946年由Heider提出。结构平衡理论围绕三角形的平衡性分析开始，在符号网络中，考虑符号性之后的三角形关系具有如图1所示的4种模式。

图1 符号网络中三角形的关系组合

图1 （a）、图1（b）对应的2种三角形是结构平衡的；图1（c）、图1（d）对应的2种三角形是结构不平衡的。

上述三角形的结构平衡性判定是从社会和心理角度出发，可以简单概括为以下4个直观认识：（1）朋友的朋友是我的朋友；（2）朋友的敌人是我的敌人；（3）敌人的朋友是我的敌人；（4）敌人的敌人是我的朋友。其中第（1）个直观认识解释了图1（a）的三角形平衡性问题，其余3个直观认识解释了图1（b）中的三角形的结构平衡性问题。而图1（c）中的三角形不满足前3个直观认识，图1（d）中的三角形不满足第4个直观认识，因此，这2种三角形均被认识是结构不平衡的，存在向前2种三角形转化的倾向。

文献［4］证明，一个符号网络是平衡网络的充分必要条件是：网络的节点集合能够被分割为2个子集，每个子集内的所有边均是正边，子集间的边均为负边。因此，尽管结构平衡理论的定义是基于三角形的微观结构，但该理论同样能够判定网络全局的结构平衡性。

文献［4］放宽了Heider结构平衡理论的约束条件，提出了“弱结构平衡理论”。该理论中放弃了Heider结构平衡理论中第4个直观认识“敌人的敌人是我的朋友”，将3条边的符号均为负号的三角形视为结构平衡的，网络中节点可以分成K个子集，使得子集内部节点间的边全为正边，连接不同子集节点的边全为负边。

近几年对真实网络的实证分析证实了Heider结构平衡理论和扩展后的弱结构平衡理论。但是，绝大部分的真实符号网络甚至不能严格满足弱结构平衡的条件。因此，结构平衡理论在符号网络中仅具有统计意义上的正确性［4］。

3 基于影响控制特性的传播模型

3.1 符号网络建模

用一个带有符号的、无向的图G=｛V，E，A｝表示符号网络，其中，V是节点集合；E⊆V×V是边的集合，并且A∈RN×N是一个说明符号关系的矩阵。

（1）如果aij=+1，节点νi与νj之间的关系是友好关系；

（2）如果aij=-1，节点νi与νj之间的关系是敌对关系；

（3）如果aij=0，节点νi和νj之间没有关系。

3.2 节点状态描述

假设针对某个特定的话题，有3种态度：积极（+），消极（-），中立（0）。

在标准的SIR模型中，有3种节点状态：易感（S），感染（I），免疫（R）。

因此，在离散观点传播过程的环境下，把个体划分为5种状态［7］：

（1）S0：代表持中立态度的个体，能够被感染为I+或I-；

（2）I+：持积极态度的个体，不稳定状态，会传染给S0个体；

（3）I-：持消极态度的个体，不稳定状态，会传染给S0个体；

（4）R+：持积极态度的个体，稳定状态，不再传播影响；

（5）R-：持消极态度的个体，稳定状态，不再传播影响。

3.3 状态转变方式

3.3.1 意见一致性

在许多已经存在的社会影响研究中，友好关系以积极的方式传播影响，人们更倾向于信任并接受他的朋友们持有的观点［10］。这种情况符合结构平衡理论中的“朋友的朋友是我的朋友”、“朋友的敌人是我的敌人”这2个直观认识。

根据文献［6］的研究，当人们投票时，人们经常反对某些政策，不是因为他们不认同那些政策，而是因为他们不喜欢提出那些政策的党派领导人。这种情况符合结构平衡理论中的“敌人的朋友是我的敌人”、“敌人的敌人是我的朋友”这2个直观认识。

如图2所示，用户A分别和用户B，D是友好关系，和用户C，E是敌对关系。

图2 意见一致性示意图

在文献［8］的研究中，据此做出了2个基于常识的假设：

（1）相同的观点将通过朋友传播；

（2）相反的观点将通过敌人传播。

在任意步骤，每一个带有I+（或I-）的个体νi都会选择他的一个邻居νj进行交互。

按照意见一致性原理，设定：λs：友好关系中传播相同观点的概率；λo：敌对关系中传播相反观点的概率。

交互方式如下所示［7］：（1）若个体为S0，那么以一定概率接受感染，突变为I+（I-）；

（2）若个体为R+（R-），则不接受任何感染，保持状态直至终止。

3.3.2 影响控制特性

在社会交互中，面对某种有争议的话题，人们会产生积极和消极2种对立的态度，当个体受到身边人的积极或是消极影响时，有可能转变自己原有的态度。如：对于是否应该节制饮酒的问题上，一个人可能是一个支持节制饮酒的人，或者是一个支持放纵饮酒的人。一个支持节制饮酒的人会对他的朋友产生节制饮酒的积极影响，但是如果他的许多朋友都是支持放纵饮酒的人，他可能会变为一个支持放纵饮酒的人，并且对他身边的人产生放纵饮酒的消极影响［11-12］。

大量调查结果显示：对个人的消极/冒险行为最有效的预测方法就是观察那个人是否有朋友从事那项活动；调查显示［13］在青少年青春期品质的变化中有50%来自身边人的影响。一个人有越多的朋友对他施加积极影响，他对身边人施加积极影响的可能性就越高。来自他的消极朋友的消极影响将会被他的积极朋友的努力所压倒。

因此，根据影响控制特性，做一个假设：如果一个个体一半以上的朋友对他有积极影响，那么这个个体对身边人产生积极影响的概率就高。

根据意见一致性的2个假设，将影响控制特性扩展到具有朋友/敌人关系的符号网络中：

（1）如果一个个体一半以上的朋友对他有积极（消极）影响，那么这个个体对身边人产生积极（消极）影响的概率就高。

（2）如果一个个体一半以上的敌人对他有消极（积极）影响，那么这个个体对身边人产生积极（消极）影响的概率就高。

在任意步骤，每一个带有I+（或I-）状态的个体νi都会根据他所有邻居的感染状态调整自身的感染状态。

根据影响控制特性的相关发现，设定：βn：带有I+状态的个体受到所有邻居影响，突变为I-状态的概率；βP：带有I-状态的个体受到所有邻居影响，突变为I+状态的概率。

转变方式如下所示：

把图G=｛V，E，A｝划分为2个子图，友好关系图：GP=｛V，EP｝；敌对关系图：Gn=｛V，En｝。如图3所示，图3（a）代表图G，图3（b）代表图GP，图3（c）代表图Gn。实线表示友好关系，虚线表示敌对关系；白色的节点ν1，ν4，ν5代表持I+状态的个体，灰色的节点ν2，ν3代表持I-状态的个体。

图3 符号网络分割图

按照意见一致性，对于一个个体，如果他的一半以上的朋友持有一种态度，以λs概率接收这种态度；如果他的一半以上的敌人选择了一种态度，以λo概率接收相反的态度。

设一个节点为νi，它有N个带有I+（I-）态度的邻居，其中NP个朋友，Nn个敌人，N=NP+Nn；假设带有I+态度的邻居具有+1的权值，带有I-态度的邻居具有-1的权值，∑Ii就是所有邻居态度的权值叠加的代数和。

则态度转变概率βi：

若βi＞0：

归一化处理：

若βi＜0：

归一化处理：

3.4 数学模型描述

模型的一些参数定义如下：

s0（t）：在t时刻持有S0状态的个体的密度；i+（t）：在t时刻持有I+状态的个体的密度；i-（t）：在t时刻持有I-状态的个体的密度；r+（t）：在t时刻持有R+状态的个体的密度；r-（t）：在t时刻持有R-状态的个体的密度；i-+（t）：在t时刻由I-状态转变为I+状态的个体的密度；

i+-（t）：在t时刻由I+状态转变为I-状态的个体的密度；

μ：带有I+（I-）状态个体突变为R+（R-）状态的概率；

φ：符号网络中友好关系所占比例；

＜K＞：符号网络的平均连通率；

假设在符号网络中所有的个体都和大概相同数目的朋友或敌人进行交互。在文献［8］创建的微分方程基础上，可以得到如下的微分方程组：

其中，引入影响控制特性后，得到：

4 仿真实验结果与分析

本文实验在NetLogo仿真平台上进行。网络规模为N=300，＜K＞=6。根据文献［8］中得到的启示，为了使影响传播出去，需要较大的λs，λo和较小的μ，在此令λs=0.15，λo=0.15，μ=0.02。

4.1 友好/敌对关系比例对演化趋势的影响

在图4中，图4（a）、图4（b）、图4（c）、图4（d）分别代表φ=1.0，0.7，0.3，0.0时的网络状态演化趋势。

图4 不同φ下的演化数据

对比发现，当φ=1.0时，网络中完全是友好关系，消极状态的节点没有出现；当φ=0.7时，网络中出现少量敌对关系，消极状态的节点开始出现，但规模很小；当φ=0.3时，网络中出现大量敌对关系，消极状态的节点大量出现，并逐渐赶超积极状态的节点比例；当φ=0.0时，网络中完全是敌对关系，消极状态的节点大量出现，超过了积极状态节点的比例，但积极状态的节点仍然大量存在，并没有消亡。

据此可知，在病毒营销的初始阶段，大量营销者针对自己的朋友和家人这些友好关系群体展开营销，获得了非常好的效果；当小部分敌对关系的个体卷入营销时，营销在局部区域受到破坏；当更多敌对关系出现时，营销的整体战略被打乱，陷入积极影响节点和消极影响节点相互牵制的局面。

4.2 友好/敌对关系比例对网络结构特性的影响

为了更清楚地展现负边在影响传播过程中对网络形势的重要的导向作用，在NetLogo仿真平台分别获取了φ=1.0，0.9，0.8，0.5，0.3，0.0时的演化仿真图，分别对应图5中的图5（a）、图5（b）、图5（c）、图5（d）、图5（e）、图5（f）。

图5 不同φ下的演化仿真结果

图中黑色球体代表处于消极状态的个体，白色球体代表处于积极状态的个体；黑色连线代表敌对关系，白色连线代表友好关系。对比发现，在φ值较大时，即友好关系占据控制地位时，持有积极态度的个体和持有消极态度的个体都按照各自的友好关系网络聚集在一起；随着φ值的减小，即随着敌对关系逐渐占据控制地位，这种友好关系网络遭到破坏，持有积极态度的个体和持有消极态度的个体渐渐失去了这种聚集性。

据此可知，友好关系会使影响在局部聚类，而敌对关系会打乱这种聚类关系，敌对关系所占比例越大，影响的局部聚类特性就越弱。

4.3 与改进前模型的特性对比

由于传播到最后只剩下S0，R+，R-3种状态的节点，为了方便观察，令免疫概率μ取很小的值，这样就可以忽略S0所占比例。因为R+与R-负相关，所以只需观察R+所占的比例就可以评测网络状态。如图6所示，图6（a）为改进前的传播模型，图6（b）为改进后的传播模型。图中的a，b，c，d、e，f，g分别代表φ值为1.0，0.9，0.85，0.8，0.5，0.2，0.0情况下的R+状态节点所占比例曲线。

图6 改进前后传播模型特性对比

通过大量实验对比发现，改进后的模型在负边比例较小时具有更强的局部聚类特性。这是因为在引入影响控制特性后，局部的占据控制地位的影响状态在影响控制特性的作用下得到加强，促使占少数的持有对立观点的人改变既有立场，使网络结构更趋稳定。

4.4 模型在真实符号网络中的验证

为了验证模型在真实符号网络中的可行性，选取了社会网络领域公开的用于测试的数据集：Slashdot网站的朋友敌人关系网络数据集，节点代表网站的会员，会员之间的边代表两者是朋友或是敌人关系。由于数据集异常庞大，挑选了4组具有代表性的数据来对比说明，如表1所示。

表1 Slashdot数据集

如图7所示，a，b，c，d 4条曲线分别代表a，b，c，d 4组数据的R+状态节点所占比例的演化趋势，随着φ的逐渐减小，R+所占比例逐渐减小。

图7 4组Slashdot数据的R+比例演化对比

在图8中，图8（a）～图8（d）分别为a，b，c，d 4组数据的演化仿真图，随着φ的逐渐减小，R+所占比例逐渐减小，并且影响的局部聚类特性逐渐减小。

图8 4组Slashdot数据的演化仿真对比

5 结束语

本文提出一种在符号网络中基于影响控制特性的传播模型，并使用NetLogo仿真平台模拟了影响在符号网络中的传播过程。仿真结果表明，在由正边和负边这2种对立关系组成的符号网络中传播影响时，负边所占比例对网络形势具有重要的导向作用，并且在负边所占比例较小时，网络中带有不同影响状态的节点出现了局部聚类的特性，当引入影响控制特性后，这种局部聚类特性进一步加强。下一步的工作主要有：利用爬虫收集网络数据，构建现实符号网络，模拟现实符号网络中的传播模式，完善传播模型；研究符号网络下影响最大化问题，得到topk节点的挖掘算法。

［1］ Richardson M，Domingos P.Mining Know ledge-sharing Sites for Viral Marketing［C］//Proceedings of the 8th ACM SIGKDD International Conference on Know ledge Discovery and Data Mining.New York，USA：ACM Press，2002：61-70.

［2］ Kem pe D，K leinberg J，Tardosé.Maximizing the Spread of Influence Through a Social Network［C］// Proceedings of the 9 th ACM SIGKDD International Conference on Know ledge Discovery and Data Mining. New York，USA：ACM Press，2003：137-146.

［3］ 田家堂，王轶彤，冯小军.一种新型的社会网络影响最大化算法［J］.计算机学报，2011，34（10）：1956-1965.

［4］ 程苏琦，沈华伟，张国清，等.符号网络研究综述［J］.软件学报，2014，25（1）：1-15.

［5］ Leskovec J，Huttenlocher D，Kleinberg J.Signed Networks in Social Media［C］//Proceedings of SIGCHI Conference on Human Factors in Computing System s. New York，USA：ACM Press，2010：1361-1370.

［6］ Jager W，Amblard F.Multiple Attitude Dynamics in Large Populations［C］//Proceedings of Agent Conference on Generative Social Processes，Models，and Mechanism s.Chicago，USA：［s.n.］，2005：215-221.

［7］ Fan P，Wang H，Li Pei，et al.Analysis of Opinion Spreading in Homogeneous Networks with Signed Relationships［J］.Journal of Statistical Mechanics：Theory and Experiment，2012，2012（8）.

［8］ LiWei，Fan P，Li Pei，et al.An Opinion Spreading Model in Signed Networks［J］.Modern Physics Letters B，2013，27（1）.

［9］ LiWei，Li Pei，Wang H.An Extend SIR Opinion dynamic Model Base on Em pirical Signed Network Mining［J］.Applied Mechanics and Materials，2014，513（1）：2744-2747.

［10］ Li Yanhua.Characterizing Diverse Link Patterns in Complex Networks：Theory and Applications［D］. Minneapolis，USA：University of Minnesota，2013.

［11］ Wang F，Camacho E，Xu K.Positive Influence Dominating Set in Online Social Networks［C］// Proceedings of the 4th International Conference on Combinatorial Optimization and Applications.Berlin，Germ any：Springer，2009：313-321.

［12］ W ang F，Du H，Cam acho E，et al.On Positive Influence Dominating Sets in Social Networks［J］.Theoretical Computer Science，2011，412（3）：265-269.

［13］ Jaccard J，B lanton H，Dodge T.Peer Influences on Risk Behavior：An Analysis of the Effects of a Close Friend［J］.Developmental Psychology，2005，41（1）：135-147.

编辑 索书志

Diffusion Model Based on Influence Dominating Characteristic in Singed Network

YANG Baolong，WU Guowen
（School of Computer Science and Technology，Donghua University，Shanghai201620，China）

In order to exp lore the phenomenon that the negative influence always lose control in viral marketing，this paper proposes a diffusion model in signed network，this paper simulates the spreading of influence in signed networks with NetLogo.Simulation results show that the negative relationships can control the situation of the networks，and the less of the negative relationships appear，the more same opinions cluster together，and this paper also show s that the diffusion model based on influence dominating characteristic has a better performance to restrain the clustering features when the negative relationships are less.

viralmarketing；signed network；diffusion model；influence dominating characteristic；NetLogo simulation

10.3969/j.issn.1000-3428.2015.09.032

杨宝龙，吴国文.符号网络中基于影响控制特性的传播模型［J］.计算机工程，2015，41（9）：174-179.

英文引用格式：Yang Baolong，Wu Guowen.Diffusion Model Based on Influence Dominating Characteristic in Singed Network［J］.Computer Engineering，2015，41（9）：174-179.

1000-3428（2015）09-0174-06

A

TP309

杨宝龙（1989-），男，硕士研究生，主研方向：信任模型，传播模型；吴国文（通讯作者），副教授。

2014-08-28

2014-10-06 E-m ail：gww u@dhu.edu.cn