弱连接对不同类型在线社交网络信息传播范围的影响研究*

2015-03-31张胜兵

计算机工程与科学 2015年1期

关键词：子图社交强度

张胜兵

(西北工业大学计算机学院，陕西西安 710072)

弱连接对不同类型在线社交网络信息传播范围的影响研究*

张胜兵

(西北工业大学计算机学院，陕西西安 710072)

按照连接强度的不同，在线社交网络节点间的连接可以分为强连接和弱连接，可以通过网络上两个节点的邻居相对重叠来测量连接强度。实验表明，弱连接对于信息传播范围的影响与具体的网络类型有关系，在基于信息交换的在线社交网络中，例如移动电话通信网络、Wiki投票网络，移去弱连接并不会对信息收敛时传播的范围产生明显的影响；而在基于合作关系形成的在线社交网络中，例如Youtube、Facebook、CDBLP合作网，移去弱连接对信息传播的范围有明显的阻碍作用。

社交网络；弱连接；信息传播

1 引言

弱连接(Weak Ties)理论是由美国社会学家Granovetter S M[1]于1974年提出的，弱连接是一种社会关系更为广泛的，然而却是肤浅的社会认知。研究发现：弱连接虽然不如强连接那样坚固，却有着极快的、可能具有低成本和高效能的传播效率。在对于弱连接的研究中，弱连接在信息传播中的影响是广大学者研究的一个重要方面。然而长期以来由于传统人类学和社会学研究中的“测不准原理”，使对弱连接的研究陷入困境，无法得到全部准确的数据。近年来，由于社交网络应用的兴起，大规模的社会行为的真实详细的数据可以通过网络爬虫方便地获取，从而为研究弱连接对信息传播的影响提供了极大的便利。

本文主要研究了弱连接在不同网络结构的社交网络上对信息传播范围的影响。在本文中，首先提出了社交网络信息传播模型，通过朋友覆盖率指标定义了连接强度和弱连接，然后在挑选出的四个网络数据集上进行信息传播实验，分别计算去除强连接与去除弱连接前后的信息传播范围并分析实验结果。

2 弱连接在不同数据集上对信息传播影响不同

弱连接与强连接一样可以应用于各种类型网络的研究中，Onnela J P等学者[4]研究了无线移动网络中弱连接对网络结构和信息传播的影响，文中以一个国家过去18周所有的电话通话记录数据为实验基础，主要研究了在无线通信网络中网络的结构和节点相互作用强度间的关系。文献中的实验得出结论：当从网络中移去强连接时，网络是健壮的，然而当从网络中移去弱连接时，网络陷入崩塌。在对信息传播的影响方面，去掉弱连接可以明显地减慢信息传播的速率，然而强连接和弱连接对于信息传播的范围都没有明显的影响。

Ferrara E等人[3]将弱连接理论应用于Facebook上，研究了基于典型朋友关系的两个大型数据集，发现去掉弱连接可以有效地减小信息传播范围。Zhao Ji-chang等人[6]通过设计一个信息传播模型研究了弱连接在在线社交网络信息传播中的作用。文中提出，一方面弱连接作为沟通各个子社区的桥结构而保证了整个网络结构的完整性；而另外一方面将弱连接作为优先的信息传播通道并不会对信息的扩散产生帮助，原因在于信息通常是通过中间连接传播的。当在网络中移去弱连接与移去强连接对比时，移去弱连接后信息传播的范围骤减，这说明了弱连接在在线社交网络信息传播中有着重要的作用。

以上研究中存在着一个很明显的矛盾之处，Onnela J P等学者指出弱连接对信息收敛时信息传播的范围没有影响，然而Ferrara E等人的研究和Zhao Ji-chang等人的研究结果认为弱连接对于信息收敛时信息传播的范围具有很大的影响。矛盾的原因可能是由于其研究是在不同类型在线社交网络上进行所引起的，接下来本文将通过实验分析产生这一矛盾的原因。

3 在线社交网络中信息传播模型和连接强度的定义

本节首先建立在线社交网络信息传播模型，然后进行连接强度定义，在信息传播模型上验证弱连接对于信息传播范围的影响。

在验证弱连接对在线社交网络信息传播的影响时，需要选取一个合适的信息传播模型来模拟信息的传播过程。在研究节点的影响力时，Kempe D等人[5]在论述如何最大化社交网络影响力的文献中采用完全级联模型来模拟信息的传播并且最终利用贪心算法得出一组影响力最大的节点。由于完全级联模型在社交网络研究中的广泛应用和其简单的形式，本文采用完全级联模型来研究弱连接对社交网络信息传播范围的影响。

信息传播范围可以归结为影响最大化问题，通常，影响最大化的关键是在网络中发现最有影响力的k个节点。将社区影响最大化问题变为选择最好的k个节点初始激活，目的是在影响最大化过程的最终阶段使得社区覆盖最大。随着时间的推移，某节点的邻居节点中有越来越多的节点变活跃；在某个时间点上，可能使该节点变活跃。当一个节点在时间步t首先变活跃时，认为它具有感染力，它具有影响每个不活跃邻居一次机会。一次成功的激活尝试将使其邻居在下一个时间步t+1成为活跃节点。如果某节点的多个邻居节点在时间步t变活跃，则这些活跃的邻居节点按任意顺序尝试激活他们的邻居节点，但所有的这些尝试都发生在时间步t。一个活跃节点u对其所有邻居节点尝试激活后，仍保持活跃，但已不具备感染力了。当不存在具备感染力的节点时，这个过程结束。

连接强度决定了一条连接的强弱，而连接强度可以通过网络上两个节点的邻居相对重叠来测量[1]。我们选取一条边两端节点的邻居覆盖率作为评价连接强度的指标。具体公式如下：

(1)

其中，cij是节点i和节点j共同的邻居数，ki和kj分别是节点i和节点j的邻居数，wij是两端分别为节点i和节点j的边的连接强度值[2,4]。

根据弱连接的理论，如果节点i和节点j之间的连接强度高，那么由于两个节点经常联系并且具有许多相同的属性，两个节点的共同朋友也会多，相应的边的连接强度值就会大。相反地，节点i和节点j之间的连接强度低，则两个节点的共同朋友也少，相应的边的连接强度值就会小。我们把公式(1)定义的wij称之为朋友覆盖率指标，该指标的值在一定程度上反映连接的强度，我们把朋友覆盖率指标值相对较小的连接定义为弱连接。

在信息传播模型中，随着信息在社交网络上的传播计算各个边的连接强度值，具体计算流程如下所示：

步骤1 遍历数据集，建立头节点索引表index。因为边的数量通常达到几万甚至几十万，每次顺序寻找头节点的时间开销很大，索引可以帮助我们在只遍历一次数据集的前提下迅速找到头节点所在位置。

步骤2 随机选择初始信息传播节点并设置传播概率prob。在此处为方便对比，我们简单地设传播概率为0.5。

步骤3 采用广度优先的策略模拟完全级联模型信息传播过程。定义待传播节点队列，并且用infect表标记已经被感染的节点。计算已经被感染节点的所有对应边的连接强度。

步骤4 传播到信息收敛时计算infect表中被感染的节点数目和对应边的数目。

步骤5 考虑到信息传播过程中的随机作用，将步骤2～步骤4步过程重复10 000遍，并取其平均值。

4 实验与结果分析

本文按照在线社交网络的不同应用方向，选取了CDBLP网、Arvix网、Wiki投票网络和Enron电子邮件网作为数据源。CDBLP网是一个以作者为中心的中文学术作者合作网站，文献原始数据库中包括了中国计算机领域各著名期刊历年的文章作者合作数据，其中作者的合作关系所构建的合作网络可以在一定程度上反映中国计算机领域的学者间合作情况。Arvix数据与CDBLP类似，为国外免费论文共享网站。本文将其数据集抽象为表现各个作者间合作关系的无向网络。Wiki是一个由世界上众多志愿者合作完成的在线免费百科全书，在众多志愿者中有一小部分是管理者。为了能够使一个普通用户变成管理者，Wiki使用了一种志愿者间相互投票决定的机制。该数据集已经在众多文献中被用来研究网络拓扑特性，比较有代表性。Enron电子邮件网数据用来验证弱连接对通过电子邮件收发方式进行信息传播的影响程度。

由于对网络特性的相关分析只有在一个连通子图下才具有意义，因此在实验之前需要抽取数据集中的最大连通子图作为实验对象。本文采用UCINET网络分析集成软件抽取最大子图作为最终研究数据，采用广度优先的搜索方法寻找最大连通子图，从图中的任意一个顶点出发，找出该顶点的等价类，然后再找出该顶点等价类中各元素的等价类，直到顶点等价类为空集，所得结果即为极大连通子图。图1为 CDBLP数据的最大连通子图，有462个节点、1 950条边。图2为Arvix数据的最大连通子图，有5 242个节点、28 980条边。图3为Wiki投票数据的最大连通子图，有7 115个节点、103 689条边。图4为Enron电子邮件网络数据的最大连通子图，有36 692个节点、367 662条边。

Figure 1 Maximal connected subgraph of CDBLP

Figure 2 Maximal connected subgraph of Arvix

Figure 3 Maximal connected subgraph of Wiki

Figure 4 Maximal connected subgraph of Enron

实验具体步骤如下：

(1) 通过朋友覆盖率指标，分别计算社交网络各条边的连接强度。

(2) 按照连接强度值对边进行排序，当移去强连接时按照强度值从大到小排序，当移去弱连接时按照强度值从小到大排序，从网络中分别移去占总边数10%、20%、30%、40%、50%、60%、70%、80%的连接，形成信息阻断网络。

(3) 在各个信息阻断网络中模拟信息传播，直到收敛。

(4) 计算收敛后网络中被感染节点的个数。

实验结果如表1～表4和图5～图8所示。

Table 1 Comparison of the influence of weak ties in CDBLP on information spreading

Table 2 Comparison of the influence of weak ties in Arvix on information spreading

Table 3 Comparison of the influence of weak ties in Wiki on information spreading

Table 4 Comparison of the influence of weak ties in Enron on information spreading

Figure 5 Comparison of the influence of weak ties in CDBLP on information spreading

Figure 6 Comparison of the influence of weak ties in Arvix on information spreading

Figure 7 Comparison of the influence of weak ties in Wiki on information spreading

Figure 8 Comparison of the influence of weak ties in Enron on information spreading

在表1和表2中，第一列代表所移去边的数量百分比，第二列、第三列分别代表移去强连接和移去弱连接时模拟信息传播后信息可以覆盖的范围。

首先分析CDBLP和Arvix的实验数据。从表1中可以发现，当网络完整时，CDBLP网信息传播的范围为334个节点。当移去总边数10%的边后，移去强连接后信息扩散范围为322，然而移去弱连接后信息扩散范围为285，扩散范围为前者的88%。随着移去弱连接数量的增加，弱连接对于信息传播的阻碍作用也更加显著。Arvix网实验数据与其类似。从图5和图6中可以直观地看到，在移去弱连接为20%到30%时曲线斜率最陡峭，同时移去强连接的曲线依旧按照基本固定的斜率下降。随着移去边条数的增加，对弱连接的判断精度也相应地降低，因此朋友重叠率算法的效果会渐渐趋于好转。当移去连接数为50%到80%时，弱连接曲线斜率平缓，原因是此时网络已经被分割成小块，弱连接已经起到了对信息的抑制作用。当移去连接数为50%到80%时，强连接曲线斜率平缓并且基本没有变化，原因可能是移去强连接对信息传播的阻碍作用并不明显，其所产生的传播范围减小主要是由于连通性降低所致的。

下面分析Wiki投票网和Enron电子邮件网的实验数据。从表3和表4中可以发现，移去连接后信息传播的范围基本没有变化。无论是移去强连接还是弱连接，对信息传播的阻碍作用均不明显，信息传播的范围只是随着移去连接数据的增加，图连通性的减弱而缓慢下降。从图7和图8中可以直观地看到，移去弱连接的曲线并没有比移去强连接的曲线整体斜率更加陡峭。两条曲线基本趋势一致，弱连接并没有显示出其对信息传播过程的阻碍作用。通过实验数据分析我们可以发现，去掉弱连接或者强连接并不能有效地对此种网络的信息传播范围产生抑制作用。

实验结果表明，去掉弱连接对CDBLP合作网和Arvix网信息阻断的作用非常明显，而对于Wiki投票网和Enron电子邮件网，去掉弱连接或者强连接并不能有效地控制网络信息的传播范围。

这一实验结果与之前第2节中的矛盾结论相一致。Onnela J P等学者采用的网络是移动电话通话记录所形成的网络，这是一个信息网络而非实体关系网络。Zhao Ji-chang等人采用的网络是Facebook和YouTube朋友关系网络，这是一个实体朋友关系网络。通过本文的实验结果分析，可以认为社交网络应该分为实体关系网络和信息交换网络两种类型，而弱连接对于信息传播范围的影响与具体的网络类型有关系。通过作图分析以及具体数据分析总结两类网络之间存在着如下几点主要差异：

(1) 实体关系网络中存在着明显的社区特性，网络由多个联系紧密的社区组成。然而，在信息交换网络中并没有此类特性。

(2) 信息交换网络中节点的度数差异很大，有很多节点的度数在200以上，同时又有很多的节点度数仅为1。通过统计分析发现，信息交换网络中度的分布与指数和幂律分别类似。然而，在实体关系网络中，大多数的节点度数相对稳定，通过统计分析发现，实体关系网络中的度的分布基本服从正态分布。

中移动电话通话记录所形成的网络与本文中的Wiki投票网络和 Enron电子邮件网络同属于信息交换网络，在这一类型的网络中移去弱连接并不能实现对信息传播范围的抑制。而Facebook和YouTube等朋友关系网络与本文中的CDBLP合作网和Arvix网同属于基于朋友关系的实体关系网络，在这一类型网络中弱连接对于信息传播起着重要的作用，通过对弱连接的控制可以有效地实现对信息传播范围的控制。

5 结束语

弱连接对于不同类型社交网络的信息传播范围影响不同，产生这一区别的原因是因为虽然基于信息交换的社交网络在一定程度上反映了社会关系网络的结构，然而其与实体关系网络的结构还是有所区别，具有不同的网络拓扑特性和信息传播规律，因此控制弱连接并不能有效地控制信息传播范围。

参考文献:

[1] Granovetter M S. The strength of weak ties[M].Chicago:University of Chicago Press, 1983.

[2] Onnela J P, Saramaki J, Hyvonen J, et al. Structure and tie strengths in mobile communication networks[C]∥Proc of PNAS’07, 2007:7332-7336.

[3] Bakshy E, Rosenn I, Marlow C, et al. The role of social networks in information diffusion[C]∥Proc of the 21st International Conference on World Wide Web, 2012:519-528.

[4] Zhao Ji-chang, Wu Jun-jie, Xu Ke. Weak ties:Subtle role of the information diffusion in online social network[J].Physical Review E, 2010:82(1):016105-016112.

[5] Kempe D, Kleinberg J, Tardos E. Maximizing the spread of

influence through a social network[C]∥Proc of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,2003:137-146.

[6] Fu F, Chen X, L iu L, et al. Social dilemmas in an online social network： The structure and evolution of cooperation [J]. Physics Letters A, 2007, 371(1-2)：58-64.

[7] Estrada E, Hatano N. Communicability in complex networks[J]. Physical Review E, 2008, 77(3):036111.

[8] Newman M.Modularity and community structure in networks[J].Proceedings of the National Academy of Sciences, 2006, 103(23):8577-8582.

[9] Pathak N, DeLong C, Banerjee A, et al. Social topics models for community extraction[C]∥Proc of the 2nd SNA-KDD Workshop, 2008:1.

[10] Porter M A, Onnela J P, Mucha P J. Communities in networks[J].Notices of the American Mathematical Society, 2009, 56(9):1082-1097.

[11] Sachan M, Contractor D, Faruquie T A, et al. Probabilistic model for discovering topic based communities in social networks[C]∥Proc of CIKM’11, 2011:2349-2352.

[12] Yang J, Leskovec J. Patterns of temporal variation in online media[C]∥Proc of ACM Conference on Web Search and Data Mining, 2010:177-186.

ZHANG Sheng-bing,born in 1974,PhD,lecturer,his research interests include social network, and P2P network.

Weak ties’ influence on information spreading for different types of online social networks

ZHANG Sheng-bing

(School of Computer Science,Northwestern Polytechnical University,Xi’an 710072,China)

There are strong ties and weak ties in terms of strength between two nodes in online social networks.The strength of ties can be measured by the relative overlap of two neighboring nodes in the network.Our experimental results show that weak ties’ influence on information spreading varies in different online social networks.There is little influence on information diffusion when we remove the weak ties in the information-exchang-oriented online social networks,such as mobile phone communication network and Wiki voting network.The coverage of the information will drop sharply when we remove weak ties in the relationship-oriented online social network,such as YouTube, Facebook and CDBLP cooperation network.

social network;weak ties;information diffusion

1007-130X(2015)01-0042-06

2013-05-03;

2013-08-19基金项目：国家自然科学基金资助项目(61103178)

TP393

10.3969/j.issn.1007-130X.2015.01.007