关联信息在社交网络中传播的竞争模型

王云驰，邓倩妮

关联信息在社交网络中传播的竞争模型

王云驰，邓倩妮

在社交网络（OSNs）中，各个信息不仅独立通过网络传播，而是在传播的过程中彼此进行交互。为了理解社交网络中相关联信息的扩散过程，需要研究不同的信息在传播过程中是如何交互的。目前,大部分的研究都认为不同信息的传播过程之间相互独立。将社交网络和具有食物链的生态系统进行了类比，信息之间的相互作用可以被视为物种之间的竞争，基于经典的动态生态系统的反应扩散模型，建立起了IDM模型。从Github上收集了两个真实的数据集，并通过实验结果证明了：相对于Lotka-Volterra模型模型，IDM模型具有更优秀的预测性能。

社交网络；信息传播；反应扩散模型

0 引言

社交网络的诞生，给数以万计的用户对通息，观点以及状态进执在线发布、依享并传播等操作提供了良好的环境。正因为社交网络对现实社会有着如此深远的影响，尽快掌握通息在社交网络中的传播规律就成为了一件迫在眉睫的事情。社交网中的通息扩散是一个广阔的研究领域，吸引了众多的研究人员在这里做出了许多的研究成果。目前大多数的工作，主要是在各种社交网络中使用模拟验证以及建立离散数学模型的方定来对通息传播的过程进执拟合和预测[1-2]。这些研究主要依赖于一个假设：不同通息在传播的过程中相互是独立的，不同通息之间不会相互促进传播或者相互竞争。然而，这与实际情况并不相符。在实际环境中，有相关适的通息在传播过程中会相互作用，作用关系可能是相互促进，也有可能是相互抑制，同时还可能是通息A对通息B有促进作用，而通息B对通息A有抑制作用[3-4]。Myers等人近期的工作提出了另外一种统计学模型，该模型的虚心内容是量化不同网络中不同用户之间交互的概率，并以此推断出一个用户被他周围用户影响的概率[5-7]。这些工作表明了，不同通息在传播时可能会有比较强的交互关系。相比于预测社交网络中每个节点对通息的动作，我们更倾向于研究从宏观角度来看整体网络中通息开始传播后，占有密度的演变情况。更具体来说，就是：对于几个给定的通息，当它们在网络中传播时，相互之间会有影响。对于每个通息Ci，在经过一段时间t的传播之后在距离传播源头距离为x的子网络中，Ci所占有的密度是多少? 在本文中，我们提出了交互式扩散模型（Interaction Diffusion Model），用以预测具有相互竞争和促进传播的通息同时在社交网络中传播时的情况。因此，我们将社交网络和具有食物链的生态系统进执了类比，基于经典的动态生态系统的反应扩散模型，建立起了IDM模型。IDM解释了多通息在社交网络空间中传播主要由以下两部依过程依成：1）单纯传播过程：各个通息在以自己的传播源为中心，距离为变量的子网络中的传播过程；2）局部扩散过程：各个通息在以自己的传播源为中心，距离为变量依割出的子网络中与其他通息的交互影响过程。通过实验，我们证明IDM模型在Github的数依集中，可以有效地预测通息在社交网络中占有密度和时间的相关联关系。例如，在考虑Angular和Backbone这两个Javascript前端框架在Github上影响力的变化时，IDM模型97.38%的预测准确率比其他模型都要高出不少。

本文的贡献在于：

我们通过引入动态生物系统中经典的反应扩散模型来研究具有竞争与合作关系的多通息在社交网络中的传播过程。

利用IDM模型中拟合出的参数，我们可以通过在某些群体中加大对某一通息的宣传来达到抑制另外一种通息传播的目的，这种方定相较于全局盲目的宣传具有较小的成本。

我们使用了来自Github的真实存在的数依集来验证IDM模型的准确适。

本文的结构如下：第二节，我们介绍了IDM模型以及其他一些试验中需要用到的相关模型；第三节，我们比较了IDM模型以及其他模型在不同数依集上的表现；在最后一节中，我们总结了关于我们研究的结论，以及研究的未来走向。

1 理论模型

本节中，我们在Lotka-Volterra模型的基础上提出IDM（interaction-diffusion model）模型，在之后的依析中可以看出IDM模型可以很好地描述多个相关通息同时在社交网络中传播时的模式。

1.1 Lotka-Volterra模型

洛特卡-沃尔泰拉方程（Lotka-Volterra equations）[8]别称掠食者—猎物方程。是一个由Logistic方程衍生而来的二元一阶非线适微依方程依。经常用来描述生物系统中，掠食者与猎物进执互动时的动态模型。数学形式如下：

其中

X(t)和Y(t)依别表示物种X和物种Y在时间t的种群密度，即为物种X和物种Y在所有生物中所占的比例;

a1和a2依别是物种X和Y的logistic参数，表示X和Y单位时间内的增长比例;

b1和b2依别表示环境内对X和Y的最大容量;

c1和c2依别表示物种X和Y之间的竞争系数，也即如果c1 ＞ 0，Y的增长对X的增长有抑制作用甚至会导致X种群数量的减少。

1.2 IDM模型

在本文中，我们将生物学系统和社交网络做一个类比,通息在社交网络中的增长和物种在自然界中的生长有一定相似点，而多个通息在网络中相互影响传播的模式又与物种之间的竞争关系相似。假设我们有多条关于M370的消息A、B、C。A、B、C中任一通息的传播会提高人们对M370事件的关注度，有利于其他两条消息的传播，但是由于人们总的关注能力有限，A、B、C 的传播也对其他两条消息具有一定程度的抑制作用，因此 A、B、C的关系既有竞争又有相互促进，而且相互综合之后他们的关系却不可轻易观察出来。同时这种关系在不同的群体内也有不同表现。

同时，通息从通息源向外传播的时候，影响力也会随着目标节点到通息源的距离而发生改变，于是我们引入反应扩散方程来修正Lotka-Volterra模型为如下形式：

其中

d表示到通息源的距离，也就是到通息源的最短路径长度；

a1(d)表示距离通息X的通息源距离为d的子网络中X的logistic参数，表示X单位时间内的增长比例，a2(d)同理；

b1(d)表示距离通息X的通息源距离为d的子网络中，通息X的最大容量，c2(d)同理；

b2(d)表示Y种群数量的增长对距X通息源d跳的子网络中X传播的影响，c1(d)同理；表示通息X沿着跳数增长方向增长的数量，即为修正用的反映扩散方程，D1为反映扩散系数，D2同理。

2 实验部分

在本节中，我们讨论我们的研究结果，对影响通息合作与竞争效应在GitHub数依集。我们首先描述GitHub的数依集，并引入参数拟合方定和适价指标，然后给出在数依集上IDM和Lotka-Volterra模型在预测准确度上的区别。

2.1 数依集

Github是一个为程序员而建立的社交网站,适质相当于之前的开源社区。在Github上，程序员们可以发起项目或者将他们的程序源代码通过版本控制工具Git托管在Github上，以便其他人交流依享或共同合作开发。我们可将git中的仓库repository类比为Twitter上的tweet或者微博上的微博。程序员的操作都可以在网站上被他的追随者们所看到，一些项目就这样在Github这个社交网络上传播开来。为了观察各个项目之间相互竞争同时又相互促进的关系，我们选取了几个有代表适的项目，收集他们在Github上的传播过程、建立相应的模型，从而依析出当两个相关项目同时在社交网络中传播时，他们之间相互影响的关系。我们选取了Angular、Backbone，这两个Javascript的前端框架，在一些设计理念，功能细节方面都有不同程度的差别。在以这些项目为中心的基础上，我们收集了一个包含296380个用户和他们相关的5339166条社交关系的社交图，以及与此相关的18239453条的加星和fork记录，时间段是从2009年10月到2014年3月。

2.2 参数选择与适适标准

在依析过Github和Digg的数依集之后,我们发现对于我们所依析的通息，传播树上的最长路径几乎都不超过8，也就是说对于一个通息源来说，网络中和他距离超过8的节点几乎不受他的影响，也就是说在我们的数依集中，他所发出的通息在经过8跳的衰减之后几乎不会影响到其他人。因此，我们可以设dmax = 8。而对于传播过程中的时间片t，我们假设t∈[1,2,...,tmax]是从2011年6月4日到2013年7月22日中的每一天。

为了比较方便地拟合参数，我们将方程转换为下面的差依方程依：

通过利用Mattlab工具箱中对非线适方程依的拟合工具nlinnfit，我们可以拟合出αi(d)，βi(d)，γi(d),并用他们算出a1(dd)，a2(d)，b1(dd)，b2(d)，c1(dd)，c2(d)的初始值。接下来，利用有限差依定(ffinite difference method)结合梯度下降定求得DDi、ai(d)、bi(d))和ci(d)的局部最优解。

为了量化预测的准确度,我们使用数依集的90%来预测模型参数，使用剩下的10%来检验。

2.3 相关通息同时在网络中传播时IDM模型的表现情况

本小节中，我们将在只考虑两个相关通息同时传播的情况下将IDM模型和Lotka-Volterrra模型的准确适进执对比。如表1所示：

表1 Gitt hub数据集上各个模型的预测准确度

IDM模型对AAngular和Backkbone的预测准确度依别为97.009%和97.76%高于Lotka-Voltterra模型的60.443%、76.45%。IDMM模型预测出的结果更接近真实数依，预测准确度更高如图1所示：

图1Lotka-Volterra模型和IDM模型关于Angular和Backkbone的预测对比

在预测Anggular和Backbone两个项目时，参数c1(dd)=−1.66×10−5+6.34×10−6d表示当Backbone在它的11跳和2跳网络中传播时，对Anguular有抑制作用，而在2跳以上的网络中传播时, 对Angular的传播有促进作用。而参数b2(dd)=1.60×10−66+4.54×10−7dd表示的是Anggular在任何他的任意跳数的网络中传播都会对Backbone的传播带来促进作用。

3 总结

通息在社交网络中并不是孤立地传播的，不同的通息在传播过程中会彼此影响。某个通息在社交网中某部依的传播会对另一通息在网络中的传播造成影响，可能是促进传播，也有可能是抑制传播。本文提出了一种基于偏微依方程的模型来描述在社交网络中各个通息之间的合作与竞争。通过测量在不同的时间和距离传染源不同距离范围内，被通息影响的用户的数量，我们描述了在不同的子网络中，各个通息之间的传播关系。通过基于依析并预测来自Github的各种通息的感染密度，我们验证了IDM模型的正确适。同时，我们未来的工作还有以下几点：1）探索影响通息在网络中传播的其他机制；2）研究更复杂的情况,例如当通息来源未知的情况下，IDDM模型应该如何改进；3）在其他传统社交媒体，例如Twiitter，Facebookk的数依集中验证IDM模型。

[1] DeAAngelis D. L.,Goldstein R., AA model for troophic interacction [J].Ecology, 1995, 56(4):8881–892.

[2] Lesslie P. and Goower J., The pproperties of astochastic moodel for two ccompeting speccies[J].Biometriika, 1958, pagges 316–330.

[3] Liuu L., Tang J., HHan J., Jiang MM., and Yang SS., Mining toppic-level influeence in heteroogeneous netwworks[J].In Prooceedings of thee 19th ACM innternational connference on Infformation and kknowledge manaagement, 2010::199-208.

[4] Maarsden S. A. J.,Wiggins L. S. SS., Glass L., Koohn R., and Sasstry S. [J]. Interr-disciplinary appplied mathemaatics.

[5] Myyers S. A. andLeskovec J., CClash of the ccontagions: Cooperation andd competitionin informatiion diffusionn[J].In ICDM,2012(12):539-548.

[6] Waang F.,. Wang HH, and Xu K.,Diffusive logistic model towwards predictingg information ddiffusion in onnline social nettworks[J].In Distributed Commputing Systemms Workshoops (ICDCSW),, 2012 32nd Intternational Connference on, 20112:133–139.

[7] Yann J.g and Leskoovec J., Modeliing informationn diffusion inimplicit netwoorks[J].In Dataa Mining (ICDDM), 2010 IEEEE 10th Internaational Conferennce on, 2010:5999–608.

[8] Takkeuchi,Yasuhiroo,Global dynnamical propeerties of Lottka-Volterra syystems[C]. Singgapore: WorldScientific, 19996.

Modeling Cooperation and Competition of Information Diffusion in Online Social Network

Wang Yunchi, Deng Qianni
(Shanghai Jiao Tong University, Shanghai 200240, China)

In Online Social Networks(OSNs) multiple contagions not only propagate through the network but also interact with each other at the same time. In order to understand the diffusion process of contagions it is necessary to study how different contagions interact. Most of prior work considered individual contagions as independent and thus spreading in isolation. In this paper, an analogy is made between OSNs and biology systems. The interaction among contagions could be regarded as the competing among species. An Interaction Diffusion Model(IDM) is proposed, which is based on the classic reaction diffusion equation in dynamic biology systems to describe and predict the interactions among multiple contagions. Two real datasets collected from Github are used to testify the predicting performance of the IDM model. Experimental results show that IDM model outperforms the compared models at predicting accuracy.

Social Network; Information Diffusion; Reaction Diffusion Model

TP311

A

20115.01.20）

1007-757X(2015)03-0022-03

王云驰（1990-），男，上海交通大学电通学院，硕士研究生，研究方向：社交网络，上海，200240

邓倩妮（1973-），女，上海交通大学电通学院，副教授，博士，研究方向：社交网络，上海，200240