社交网络拓扑结构实证研究
2017-12-02徐焱
徐焱
摘要：采用传统统计方法很难直观了解大规模社交网络的结构特点和演化特征。通过对科学网博客域名下的网页进行搜索，建立一个由244 662个博主和113 062对好友关系构成的复杂网络——科学网博客博主好友关系网络。采用复杂网络理论进行研究，测算网络度分布、平均路径长度和聚类系数，发现该网络具有无尺度属性和小世界属性，存在相对较多的集散节点，导致网络的度分布幂指数小于正常范围。通过逐步删除高连接度节点，观察网络破碎程度，分析了集散节点在维持社交网络链接中的重要性，建议重点关注10%的最高度节点，使网络更加健壮。该研究有助于阐明在线社交网络的自组织结构性质。
关键词关键词：在线社交网络；复杂网络；拓扑结构；集散节点
DOIDOI：10.11907/rjdk.172730
中图分类号：TP319
文献标识码：A文章编号文章编号：16727800（2017）011017604
0引言
随着Web 2.0技术的迅速发展，人们进入了在线社交网络（Online Social Network，OSN）时代。在线社交网络成为一种广泛使用的人际交往方式，为用户带来了新的体验，社交网络研究得到了广泛关注。
社交网站与一般信息网站的不同之处在于其拥有数量庞大的注册用户，而且用户之间存在错综复杂的好友关系，这些好友关系将所有用户连在一起，形成了一个庞大的好友网络。随着新用户的注册，陌生人之间随时都可能形成新的好友关系，这个好友网络在快速演化。研究这个庞大的好友网络，从错综复杂的关系中理出头绪，挖掘和发现新的知识，是研究工作的重点。
在线社交网络涉及经济、政治、娱乐、军事、卫生、科技、体育和生活等领域，为知识共享、信息传递和人类交互提供了便捷的通信平台，带来了巨大的商业机会。在线社交网络中大量信息来源不确定，存在一些不良、虚假或煽动性信息，可能对社会稳定产生很大的负面影响。随着在线社交网络的普及，网络已经成为舆论传播的重要途径。因此，如何通过社会网络监测控制舆论特别是恐怖行为的传播，已经成为一个非常急迫的问题[1]。社交网络包含大量的内容和链接数据，可以用于分析。链接数据本质是社会网络和实体间通信的图形结构。在线社交网络拓扑结构的实证分析，有助于确定网络的重要节点、社区、链路和演化区域，理解各种动态过程。
在线社交网络具有复杂性、大规模、非线性和快速演化等特征，与一般网络有很大区别。因此，与传统信息系统相比，其挖掘目标和研究方法大不相同。
关于复杂网络的研究方兴未艾，1998年Strogatz和Watts[2]在《Nature》杂志上发表文章，提出了小世界（SmallWorld）网络模型概念。1999年Barabasi和Albert[3]在《Science》上发表文章，提出了无尺度（ScaleFree）網络概念，指出许多复杂网络链接度分布具有典型的幂律形式。这两项开创性研究掀起了一股研究复杂网络热潮。
著名科学家钱学森把复杂网络定义为具有自相似、自组织、小世界、无尺度的网络。复杂网络在自然界、工程界、生物界和人类社会界中广泛存在，如蛋白质网络、食物链网络、新陈代谢网络、万维网、Internet、电力网、铁路网、航空网、演员合作网络、朋友关系网、科学家合作网及金融网络等都是复杂网络。
复杂网络的复杂性主要体现在节点数量巨大，而且节点之间的连接关系较为复杂，既不像随机网络那样具有完全不确定的连接关系，也不像规则网络那样具有完全确定的连接关系，而是介于两者之间[4]。复杂网络及其演化研究已经成为多学科交叉的研究方向。
社交网络拥有数量庞大的用户，而且用户之间的连接关系错综复杂，是一种典型的复杂网络。因此，可以用复杂网络理论研究社交网络。
本文重点研究科学网博客，即Science Net Blog[5]。科学网博客是提供交流和共享科学信息的平台，在中国拥有2万多注册用户。通过网络爬虫抓取网站上的公开信息获取数据，并将数据用于研究。研究重点是该网站内的社交网络用户，具体研究用户关系图中最大连接片的属性，而不是整个用户社区，这代表了构建复杂系统模型的新框架。通过计算科学网博客网络的拓扑特性，包括度分布、平均聚类系数和平均路径长度，进行详细分析，证实了科学网博客既是无尺度网络又是小世界网络；此外，还证明了复杂网络中重要节点的数量非常少，这意味着如果控制这些节点，消息的传播将被控制。
1复杂网络拓扑属性
1.1拓扑属性
（1）节点度和度分布。节点的度是网络中一个节点连接到该网络中其它节点的边数，用k表示。网络的度分布是该网络中所有节点的度的概率分布[6]。
（2）路径长度和平均路径长度。路径长度是从一个节点到另一个节点必须遍历的最小边数[7]。平均值长度是任何节点对之间的路径长度平均值。
（3）聚类系数。聚类系数表示在一个网络中同一个顶点的邻居之间有边连接的平均概率。按照Watts和Strogatz的定义，如果一个节点v有k个邻居，其邻点将可能存在的最大边数是2，实际存在的边数用Ei表示，则节点v的聚类系数定义为；所有节点的聚类系数的平均值定义为整个网络的聚类系数C[2]。
1.2随机、无规模和小世界网络
20世纪60年代，鄂尔多斯（Red）和雷尼（Reyni）[8]发表了开创性的论文，之后随机网络被广泛研究。随机网络图通常通过随机添加链接到静态节点集来构造，这意味着每个节点以相等概率p随机连接到图形中。大规模随机图具有高斯度分布，随机网络的主要特征是平均路径长度很短、聚类系数低。相反，规则网络通常具有非常长的平均路径和高聚类系数。
描述真实世界网络的大多数图形显著偏离了简单的随机图模型。Barabasi和Albert[3]发现一些网络具有幂律形式的度分布：即节点具有度k的概率为Prob（k）～k-λ。度数指数λ通常在2～3之间，并且度分布的幂律衰减非常缓慢（“长尾”），这意味着网络缺乏特征尺度，这样的网络称为“无尺度”网络。Barabasi和Albert提出了“BarabasiAlbert模型”，并展示了无尺度网络可以源自一个过程，每个连接到网络的节点优先连接那些度比较高的节点。endprint
Watts和Strogatz[2]发现了一些网络介于规则网络和随机网络之间。规则网络的平均路径长度很长，但是它的聚类系数很高；随机网络平均路径长度小，但是聚类系数很低。而介于这两者之间的网络，具有较小的平均路径和较高的聚类系数，这类网络称为小世界网络。
社交网络指社会个体成员之间通过社会关系结成的网络体系，社交网络由个体和个体间连接关系组成。在社交网络中，节点代表社会环境中的人或其它实体，边代表实体之间的相互作用、合作或相互影响。因此，社交网络可被看作是一种特殊类型的复杂网络，建模为无向图G=（V，E），即每个节点v∈V和无向边缘
2数据采集
本文针对科学网（http：//www.sciencenet.cn）中的科学网博客（http：//www.sciencenet.cn/blog）进行研究。科学网主要为网民提供快捷权威的科学新闻报道、丰富实用的科学信息服务以及交流互动，目标是建成最具影响力的全球华人科学社区。科学网博客采用实名注册，博主多为一线研究人员，有院士、重点实验室主任等知名学者，研究内容涉及生命科学、信息科学等多个领域，可在一定程度上反映不同领域的前沿研究。
随着时间的推进，科学网博客注册用户不断增加，用户间的关系逐渐复杂。本文利用网络爬虫爬取到该博客中共有244 662个博主和113 062对好友关系，采集的数据截至2012年3月。这244 662个博主组成的好友网络中包含大量的孤立节点，即这些节点没有任何好友关系，有一些很小的网络碎片以及一个巨大的连接片。
因为孤立的节点与整个网络中的其它节点没有任何链接，无法传播信息，因此不对网络造成任何影响。同理，较小的网络碎片之间存在的边极少，因此传播消息的范围也很小，对整个网络的影响几乎为零。本文的研究对象就是由这个巨大连接片组成的子网络，包含了20 236个博客用户节点和113 014对好友关系。这个仅有8.27%节点的巨大连接片中的好友关系占到整个网络的99.96%。
下面详细分析这个社交网络的拓扑结构，以及一些统计属性，包括度数分布、平均最短路径长度以及聚类系数，揭示在线社交网络的内部特征。
3网络结构拓扑分析
本节描述了网络的拓扑特性，并与现实观察到的网络进行比较。
3.1度分布
许多复杂网络的度分布都符合幂律分布，包括离线社交网络。对科学网博主好友关系网络中的最大连通子网进行研究，绘制网络的度分布和度分布的对数分布图，如图1所示。
图1博客网度分布与度的对数分布
通过统计发现该网络的度分布符合幂律P（k）～k-γ，其中γ=1.5±0.1，即该网络是无尺度网络。但是，通过表1发现该无尺度网络不同于现实世界中已经发现和验证的无尺度网络。现实世界中无尺度网络的幂指数γ一般在2～3之间[9]，但是本网络的幂律指数非常小，只有大约1.5。下面详细研究这一现象。
经过研究发现，随着γ的增长，网络从异质向同质转变。
现实网络中，γ≤1是不存在的。当1<γ≤2时，网络包含比较多的集散节点，即度较高的节点较多。当2<γ
≤3时，网络中包含大量的度很小的节点和极少的集散节点；当γ>3时，网络中绝大多数节点的度很相近，但是基本不存在集散节点。
当γ>3时，网络中由于基本不存在集散节点，所以网络消息传输率很低，这种网络在现实生活中基本不存在。
当1<γ≤2时，集散节点较多，虽然此时消息传输率很高，但是维持这些集散节点花费的代价太大，所以此种网络在现实生活中也很少。
当2<γ≤3时，网络既能确保消息的传输率又不需要花费太高的代价，所以此种网络在现实生活中最为常见，例如：蛋白质网络、作家合作网、Internet路由网等等。
而本文研究的网络是一个虚拟网络，不受资源限制，即使有较多的集散节点也不需要花费人力物力进行维护，因此本研究网络中γ<2并不奇怪。另外，还推测出该网络的信息传输效率较高，因为它包含了相对较多的集散节点。
3.2平均路径长度和聚类系数
计算网络的平均路径长度，即任意两个节点之间最短路径的平均值。本网络中该值为3.29，这意味着在一个有两万多个节点的网络中，从一个用户到另一个用户平均只需点击4次就可到达。图2显示了最短路径长度分布，很明显，大部分的路径长度在2～4之间。虽然博客网络节点很多，规模很大，且很稀疏，但是它的平均路径很短，这验证了著名的“六度分隔”理论[10]。
图2博客网最短路径长度分布
无向网络中聚类系数
Ci=2Eiki（ki-1）（1）
Ei是节点i的所有邻居之间存在的边数目，ki（ki-1）/2是节点i的邻居间存在边的最大数量，网络的聚类系数C是所有Ci的平均值。本網络中C=0.193，而相同规模的随机网络聚类系数Crand=
综合这两点可以得出，研究网络的聚类系数比随机网络的聚类系数大得多，而比规则网络的平均路径长度小得多。因此，本网络是具有小世界属性的网络。
3.3集散节点重要性
在电力网络中，对重要的断路器、发电单元等进行监控和保护，可以有效防止由级联故障引起的大范围停电，从而避免大的经济损失；在大规模计算机网络中，可以对关键节点的服务器有针对性地进行备份，既能有效节省资源，又可保证网络的鲁棒性；在传染病、病毒传播网络中，可以优先治疗、隔离病源，有效防止病毒的传播和扩散；在发掘复杂网络社区时，可以通过集散节点确定社区中心。社交网络的结构很大程度上依赖于高连接度的节点，而这些高连接度的集散节点与信息传播、蓄意攻击的脆弱性和随机攻击的鲁棒性都有很大关系[11]。下面研究在线社交网络中解散节点对整个网络的影响。
研究方法是逐步移除具有高连接度的节点，然后计算剩下的最大连通片大小，剩下的最大连通片大小就是信息能在网络上传播的最大范围。随着高连接度节点移除，最大的连通网络开始分解成较小的网络碎片。逐步移除Top1%到Top10%的高连接度节点。当移除1%的节点后，最大连通网络是原网络大小的68%；移除5%后，是原网络的40%；移除10%，此时最大连通网络是原网络的10%。另外计算了移除20%的情况，此时，整个网络破碎成几千个很小的网络，而最大的网络只有18个节点。图3显示分解后最大连通网络的大小。
图3移除一定比例节点与最大连通网络规模的关系
本研究网络中只需关注10%的节点，这种情况下，即使受到蓄意攻击，网络也不会瘫痪；即使有人发布恐怖消息，消息传播的范围也不会超过网络规模的10%。如果关注网络中20%的节点，虽然监控效果会更好，但是付出的代价太大。所以，选择监控10%的节点时监控效果最好，而代价又是可以承受的。
4结语
本文对科学网博客采集的数据集进行了在线社交网络实证研究。数据显示社会网络的度分布具有无尺度网络特征——幂律。然而它具有比现实世界网络更小的幂律指数。本文验证了社交网络具有非常短的平均路径长度和较高的聚类系数，符合小世界网络特征。研究了最短路径长度的频率，证明了该网络符合著名的“六度分离”理论。关注整个网络10%的节点时，网络将更加健壮。本研究有助于了解在线社交网络的拓扑特征。今后将研究如何建立网络的图结构和动态演化，探讨影响网络增长的因素等。
参考文献参考文献：
[1]V KREBS. Mapping networks of terrorist cells[J]. Connections，2002，24（3）：4352.
[2]D J WATTS， S H STROGATZ.Collective dynamics of “smallworld” networks[J].Nature，1998（393）：440442.
[3]A L BARABASI， R ALBERT. Emergence of scalling in random networks[J].Science，1999（286）：509512.
[4]王林，戴冠中.复杂网络的Scalefree性、Scalefree现象及其控制[M].北京：科学出版社，2009：511.
[5]科学网[EB/OL].http：//www.sciencenet.cn/blog.
[6]LAN AMARAL， A SCALA， M BARTHELEMY，et al. Stanley[EB/OL]. http：//ishare.iask.sina.com.cn/f/23802485.html，Classes of small.
[7]E BULLMORE， O SPORNS. Complex brain networks： graph theoretical analysis of structural and functional systems[J].Nature Reviews Neuroscience，2009（3）：186198.
[8]P ERDOS， A RENYI. On random graphs[J].Publications Mathematics，1959（6）：290297.
[9]R ALBERT， A L BARAB′ASI.Statistical mechanics of complex network[J].Reviews of Modern Physics，2002（74）：4797.
[10]艾伯特拉斯洛，巴拉巴西.網络链接新科学[M].长沙：湖南科学技术出版社，2007.
[11]P HOLM， B J KIM， C N YOON，et al.Attack vulnerability of complex networks[J]. Physical Review E，2002（65）：254259.
责任编辑（责任编辑：杜能钢）endprint
