1在线社交网络中信息传播模型和连接强度的定义
本节首先建立在线社交网络信息传播模型，然后进行连接强度定义，在信息传播模型上验证弱连接对于信息传播范围的影响。在验证弱连接对在线社交网络信息传播的影响时，需要选取一个合适的信息传播模型来模拟信息的传播过程。在研究节点的影响力时，ＫｅｍｐｅＤ等人［５］在论述如何最大化社交网络影响力的文献中采用完全级联模型来模拟信息的传播并且最终利用贪心算法得出一组影响力最大的节点。由于完全级联模型在社交网络研究中的广泛应用和其简单的形式，本文采用完全级联模型来研究弱连接对社交网络信息传播范围的影响。信息传播范围可以归结为影响最大化问题，通常，影响最大化的关键是在网络中发现最有影响力的ｋ个节点。将社区影响最大化问题变为选择最好的ｋ个节点初始激活，目的是在影响最大化过程的最终阶段使得社区覆盖最大。随着时间的推移，某节点的邻居节点中有越来越多的节点变活跃；在某个时间点上，可能使该节点变活跃。当一个节点在时间步ｔ首先变活跃时，认为它具有感染力，它具有影响每个不活跃邻居一次机会。一次成功的激活尝试将使其邻居在下一个时间步ｔ＋１成为活跃节点。如果某节点的多个邻居节点在时间步ｔ变活跃，则这些活跃的邻居节点按任意顺序尝试激活他们的邻居节点，但所有的这些尝试都发生在时间步ｔ。一个活跃节点ｕ对其所有邻居节点尝试激活后，仍保持活跃，但已不具备感染力了。当不存在具备感染力的节点时，这个过程结束。连接强度决定了一条连接的强弱，而连接强度可以通过网络上两个节点的邻居相对重叠来测量［１］。（１）其中，ｃｉｊ是节点ｉ和节点ｊ共同的邻居数，ｋｉ和ｋｊ分别是节点ｉ和节点ｊ的邻居数，ｗｉｊ是两端分别为节点ｉ和节点ｊ的边的连接强度值［２，４］。根据弱连接的理论，如果节点ｉ和节点ｊ之间的连接强度高，那么由于两个节点经常联系并且具有许多相同的属性，两个节点的共同朋友也会多，相应的边的连接强度值就会大。相反地，节点ｉ和节点ｊ之间的连接强度低，则两个节点的共同朋友也少，相应的边的连接强度值就会小。我们把公式（１）定义的ｗｉｊ称之为朋友覆盖率指标，该指标的值在一定程度上反映连接的强度，我们把朋友覆盖率指标值相对较小的连接定义为弱连接。在信息传播模型中，随着信息在社交网络上的传播计算各个边的连接强度值，具体计算流程如下所示：步骤１遍历数据集，建立头节点索引表ｉｎ－ｄｅｘ。因为边的数量通常达到几万甚至几十万，每次顺序寻找头节点的时间开销很大，索引可以帮助我们在只遍历一次数据集的前提下迅速找到头节点所在位置。步骤２随机选择初始信息传播节点并设置传播概率ｐｒｏｂ。在此处为方便对比，我们简单地设传播概率为０．５。步骤３采用广度优先的策略模拟完全级联模型信息传播过程。定义待传播节点队列，并且用ｉｎｆｅｃｔ表标记已经被感染的节点。计算已经被感染节点的所有对应边的连接强度。步骤４传播到信息收敛时计算ｉｎｆｅｃｔ表中被感染的节点数目和对应边的数目。步骤５考虑到信息传播过程中的随机作用，将步骤２～步骤４步过程重复１００００遍，并取其平均值。
2实验与结果分析
本文按照在线社交网络的不同应用方向，选取了ＣＤＢＬＰ网、Ａｒｖｉｘ网、Ｗｉｋｉ投票网络和Ｅｎｒｏｎ电子邮件网作为数据源。ＣＤＢＬＰ网是一个以作者为中心的中文学术作者合作网站，文献原始数据库中包括了中国计算机领域各著名期刊历年的文章作者合作数据，其中作者的合作关系所构建的合作网络可以在一定程度上反映中国计算机领域的学者间合作情况。Ａｒｖｉｘ数据与ＣＤＢＬＰ类似，为国外免费论文共享网站。本文将其数据集抽象为表现各个作者间合作关系的无向网络。Ｗｉｋｉ是一个由世界上众多志愿者合作完成的在线免费百科全书，在众多志愿者中有一小部分是管理者。为了能够使一个普通用户变成管理者，Ｗｉｋｉ使用了一种志愿者间相互投票决定的机制。该数据集已经在众多文献中被用来研究网络拓扑特性，比较有代表性。Ｅｎｒｏｎ电子邮件网数据用来验证弱连接对通过电子邮件收发方式进行信息传播的影响程度。由于对网络特性的相关分析只有在一个连通子图下才具有意义，因此在实验之前需要抽取数据集中的最大连通子图作为实验对象。本文采用ＵＣＩＮＥＴ网络分析集成软件抽取最大子图作为最终研究数据，采用广度优先的搜索方法寻找最大连通子图，从图中的任意一个顶点出发，找出该顶点的等价类，然后再找出该顶点等价类中各元素的等价类，直到顶点等价类为空集，所得结果即为极大连通子图。图１为ＣＤＢＬＰ数据的最大连通子图，有４６２个节点、１９５０条边。图２为Ａｒｖｉｘ数据的最大连通子图，有５２４２个节点、２８９８０条边。图３为Ｗｉｋｉ投票数据的最大连通子图，有７１１５个节点、１０３６８９条边。图４为Ｅｎｒｏｎ电子邮件网络数据的最大连通子图，有３６６９２个节点、３６７６６２条边。实验具体步骤如下：（１）通过朋友覆盖率指标，分别计算社交网络各条边的连接强度。（２）按照连接强度值对边进行排序，当移去强连接时按照强度值从大到小排序，当移去弱连接时按照强度值从小到大排序，从网络中分别移去占总边数１０％、２０％、３０％、４０％、５０％、６０％、７０％、８０％的连接，形成信息阻断网络。（３）在各个信息阻断网络中模拟信息传播，直到收敛。（４）计算收敛后网络中被感染节点的个数。实验结果如表１～表４和图５～图８所示。在表１和表２中，第一列代表所移去边的数量百分比，第二列、第三列分别代表移去强连接和移去弱连接时模拟信息传播后信息可以覆盖的范围。首先分析ＣＤＢＬＰ和Ａｒｖｉｘ的实验数据。从表１中可以发现，当网络完整时，ＣＤＢＬＰ网信息传播的范围为３３４个节点。当移去总边数１０％的边后，移去强连接后信息扩散范围为３２２，然而移去弱连接后信息扩散范围为２８５，扩散范围为前者的８８％。随着移去弱连接数量的增加，弱连接对于信息传播的阻碍作用也更加显著。Ａｒｖｉｘ网实验数据与其类似。从图５和图６中可以直观地看到，在移去弱连接为２０％到３０％时曲线斜率最陡峭，同时移去强连接的曲线依旧按照基本固定的斜率下降。随着移去边条数的增加，对弱连接的判断精度也相应地降低，因此朋友重叠率算法的效果会渐渐趋于好转。当移去连接数为５０％到８０％时，弱连接曲线斜率平缓，原因是此时网络已经被分割成小块，弱连接已经起到了对信息的抑制作用。当移去连接数为５０％到８０％时，强连接曲线斜率平缓并且基本没有变化，原因可能是移去强连接对信息传播的阻碍作用并不明显，其所产生的传播范围减小主要是由于连通性降低所致的。下面分析Ｗｉｋｉ投票网和Ｅｎｒｏｎ电子邮件网的实验数据。从表３和表４中可以发现，移去连接后信息传播的范围基本没有变化。无论是移去强连接还是弱连接，对信息传播的阻碍作用均不明显，信息传播的范围只是随着移去连接数据的增加，图连通性的减弱而缓慢下降。从图７和图８中可以直观地看到，移去弱连接的曲线并没有比移去强连接的曲线整体斜率更加陡峭。两条曲线基本趋势一致，弱连接并没有显示出其对信息传播过程的阻碍作用。通过实验数据分析我们可以发现，去掉弱连接或者强连接并不能有效地对此种网络的信息传播范围产生抑制作用。实验结果表明，去掉弱连接对ＣＤＢＬＰ合作网和Ａｒｖｉｘ网信息阻断的作用非常明显，而对于Ｗｉ－ｋｉ投票网和Ｅｎｒｏｎ电子邮件网，去掉弱连接或者强连接并不能有效地控制网络信息的传播范围。这一实验结果与之前第２节中的矛盾结论相一致。ＯｎｎｅｌａＪＰ等学者采用的网络是移动电话通话记录所形成的网络，这是一个信息网络而非实体关系网络。ＺｈａｏＪｉ－ｃｈａｎｇ等人采用的网络是Ｆａｃｅｂｏｏｋ和ＹｏｕＴｕｂｅ朋友关系网络，这是一个实体朋友关系网络。通过本文的实验结果分析，可以认为社交网络应该分为实体关系网络和信息交换网络两种类型，而弱连接对于信息传播范围的影响与具体的网络类型有关系。通过作图分析以及具体数据分析总结两类网络之间存在着如下几点主要差异：（１）实体关系网络中存在着明显的社区特性，网络由多个联系紧密的社区组成。然而，在信息交换网络中并没有此类特性。（２）信息交换网络中节点的度数差异很大，有很多节点的度数在２００以上，同时又有很多的节点度数仅为１。通过统计分析发现，信息交换网络中度的分布与指数和幂律分别类似。然而，在实体关系网络中，大多数的节点度数相对稳定，通过统计分析发现，实体关系网络中的度的分布基本服从正态分布。参考文献中移动电话通话记录所形成的网络与本文中的Ｗｉｋｉ投票网络和Ｅｎｒｏｎ电子邮件网络同属于信息交换网络，在这一类型的网络中移去弱连接并不能实现对信息传播范围的抑制。而Ｆａｃｅｂｏｏｋ和ＹｏｕＴｕｂｅ等朋友关系网络与本文中的ＣＤＢＬＰ合作网和Ａｒｖｉｘ网同属于基于朋友关系的实体关系网络，在这一类型网络中弱连接对于信息传播起着重要的作用，通过对弱连接的控制可以有效地实现对信息传播范围的控制。
3结束语
弱连接对于不同类型社交网络的信息传播范围影响不同，产生这一区别的原因是因为虽然基于信息交换的社交网络在一定程度上反映了社会关系网络的结构，然而其与实体关系网络的结构还是有所区别，具有不同的网络拓扑特性和信息传播规律，因此控制弱连接并不能有效地控制信息传播范围。
作者：张胜兵 单位：西北工业大学计算机学院
