小世界网络

Facebook社交网络的特征——基于小世界网络

1 概述

1.1 引言

在网络理论 的研究中，复杂网络是由数量巨大的节点 和节点之间错综复杂的关系共同构成的网络 结构。用数学的语言来说，就是一个有着足够复杂的拓扑 结构特征的图 。复杂网络具有简单网络，如晶格网络 、随机图 等结构所不具备的特性，而这些特性往往出现在真实世界的网络结构中。复杂网络的研究是现今科学研究中的一个热点，与现实中各类高复杂性系统，如的互联网 、神经网络 和社会网络 的研究有密切关系。

图1 随机生成的复杂网络

1.2 小世界网络特征

小世界网络，又称为小世界效应，是复杂网络的特性之一。1998年，美国康奈尔大学 理论与应用力学系博士生华兹（Watts）与其导师斯特罗迦茨（Strogatz）合作，在《自然》杂志上发表了题为《“小世界”网络的集体动力学》的论文，标志着小世界网络模型的建立。

小世界网络的判定准则有两个，分别是特征路径长度短，和高集聚系数 。网络的特征路径长度是指在它的图表示中，两个节点的路径长度的平均值（这里路径长度指两节点间最短路径的长度）。许多复杂网络尽管节点数目巨大，但节点之间的特征路径长度则非常小。集聚系数则是用来描述“抱团”现象的，也就是“你朋友之间相互认识的程度”。数学上来说，一个节点的集聚系数等于与它相连的节点中相互连接的点对数与总点对数的比值。高集聚系数实际上保证了较小的特征路径长度。

说白了，小世界网络指的就是虽然这个世界很大，人也很多，但是我要想找到远在千里之外的一个陌生人并不难，我大约只需找到6个中间人就可以了。也就是我们经常听到的六度理论。

2 实验准备

2.1 实验环境

Windows 10 professional 64bit

CPU i7-3.6GHz

内存 8G

Python 3.7.0

PyCharm 2018.3.4 (Professional Edition)

Networkx 复杂网络分析库

Matploatlib 图形绘制库

2.2 Facebook数据库

数据集名称：facebook社交数据集

来源：http://konect.uni-koblenz.de/networks/ego-facebook

基本描述：该社交网络为无向图，无连接权重。节点代表用户，边代表了两个用户之间的关系。共有2888个节点，2981条边。

图2 数据格式（左）和Facebook社交网络图（右）

3 社交网络的验证

3.1 平均度

计算得到平均度为：2.0644

#计算平均度 average_degree=edgeNum*2.0/nodeNum print("平均度："+str(average_degree)) degree_distribute=networkx.degree_histogram(G) x=range(len(degree_distribute)) y=[z/float(sum(degree_distribute))for z in degree_distribute] plt.loglog(x,y) plt.show()

图3 度分布图

从度分布图可以看出，在Facabook社交网络中，大部分节点的度分布在10以内，只有及少量节点的度大于10。说明了现实用户中，每个人所联系的朋友不会太多，在10个朋友左右。

3.2 网络直径

网络直径指的是网络中最长最短路径的长度。

Facebook社交网络中的网络直径为：9。说明了在Facebook社交网络中，路径最长的用户和路径最短的用户相差了9个单位长度。

#计算网络直径 g_dia=networkx.diameter(G) print("网络直径："+str(g_dia))

3.3 图的度匹配性

如果总体上度大的顶点倾向于连接度大的顶点，那么就称网络的度正相关的，或者成网络是同配的；如果总体上度大的顶点倾向于连接度小的顶点，那么就称网络的度负相关的，或者成网络是异配的。

图的度匹配性为：-0.6682。

从图中可以看出，度大的节点更倾向于度小的节点连接，度小的节点更倾向于度大的节点连接，所以Facebook社交网络是异配性的，通过Python编程计算得到的度匹配性值也是负的，再次验证了结果的正确性。

在Facebook社交网络中，人脉广的用户更倾向与人脉低的用户进行联系，这一点与通常的社交网络有所差别。

图4 度匹配图

#计算图的匹配性 g_ass=networkx.degree_assortativity_coefficient(G) print("图的匹配性："+str(g_ass))

3.4 平均路径长度

该网络中的平均路径长度为：3.8674<lnN=8.6932

从平均路径长度这一特征看，Facebook社交网络符合小世界网络的特征。平均路径长度为3.8674代表了在Facebook社交网络中，一个用户可以在4次连接后，找到他（她）想找的任意一个人。

#计算平均路径长度 g_average_path_len=networkx.average_shortest_path_length(G) print("平均路径长度："+str(g_average_path_len))

3.5 平均聚集系数

在图论 中，集聚系数（也称群聚系数、集群系数）是用来描述一个图 中的顶点之间结集成团的程度的系数。具体来说，是一个点的邻接点之间相互连接的程度。例如生活社交网络中，你的朋友之间相互认识的程度。有证据表明，在各类反映真实世界的网络结构，特别是社交网络结构中，各个结点之间倾向于形成密度相对较高的网群。也就是说，相对于在两个节点之间随机连接而得到的网络，真实世界网络的集聚系数更高。

通过计算，平均聚集系数C为：0.0272，随机网络的平均聚集系数Crand为：0.0003463，C/Crand=78.689，所以C>>Crand，该社交网络的平均聚集系数这一特征也符合小世界网络的特征。在Facebook社交网络中，用户和用户之间的小群体特征鲜明。

图5 聚集系数分布图

#计算平均聚集系数 g_average_clustering_num=networkx.average_clustering(G) print("平均聚集系数："+str(g_average_clustering_num))

3.6 中心度

度中心性是在网络分析中刻画节点中心性的最直接度量指标。一个节点度越大就意味着这个节点的度中心性越高，该节点在网络中就越重要。中心度包括点中心度、紧密中心度、介数中心度、特征向量中心度等。

点中心度是指该节点对邻居节点的平均影响力的大小。

图6 点中心度分布图

紧密中心度是指节点到其他节点的距离，间接度量节点的影响力强度。

图7 紧密中心度分布图

介数中心度是指节点在网络中的重要位置，充分体现节点的关键性。

图8 介数中心度分布图

特征向量中心性的基本思想是，一个节点的中心性是相邻节点中心性的函数。也就是说，与你连接的人越重要，你也就越重要。

图9 特征向量中心度分布图

#计算中心度 x1=[0]*nodeNum x2=[0]*nodeNum x3=[0]*nodeNum x4=[0]*nodeNum y1=[0]*nodeNum y2=[0]*nodeNum y3=[0]*nodeNum y4=[0]*nodeNum # 1点中心度 g_degree_centrality=networkx.degree_centrality(G) print("点中心度："+str(g_degree_centrality)) for z in range(len(g_degree_centrality)): x1[z]=z+1 y1[z]=g_degree_centrality[x1[z]] plt.loglog(x1,y1) plt.show() # 2紧密中心度 g_closeness_centrality=networkx.closeness_centrality(G) print("紧密中心度："+str(g_closeness_centrality)) for z in range(len(g_closeness_centrality)): x2[z]=z+1 y2[z]=g_closeness_centrality[x2[z]] plt.loglog(x2,y2) plt.show() # 3介数中心度 g_betweenness_centrality=networkx.betweenness_centrality(G) print("介数中心度："+str(g_betweenness_centrality)) for z in range(len(g_betweenness_centrality)): x3[z]=z+1 y3[z]=g_betweenness_centrality[x3[z]] plt.loglog(x3,y3) plt.show() # 4特征向量中心度 g_eigenvector_centrality=networkx.eigenvector_centrality_numpy(G) print("特征向量中心度："+str(g_eigenvector_centrality)) for z in range(len(g_eigenvector_centrality)): x4[z]=z+1 y4[z]=g_eigenvector_centrality[x4[z]] plt.loglog(x4,y4) plt.show()

4 总结

本文通过对Facebook社交网络进行计算，以验证该网络是否属于小世界网络。对Facebook社交网络的6个特征，9个参数进行了编程计算，尤其是平均路径长度和平均聚集系数这两个特征。计算得到该社交网络的平均路径长度为3.8674，平均聚集系数为0.0272，这两个特征均符合小世界网络所具有的特征。所以Facebook社交网络属于小世界网络，具有小世界网络所有的特征。

参考文献

[1]葛伟伦,房丙午.小世界网络模型分析和算法模拟[J].通化师范学院学报,2018,39(04):56-60.

[2]张佳鹏,郭瑞军.城市道路网的小世界效应和无标度特性分析[J].青海交通科技,2016(06):21-25+38.

[3]Facebook数据集来源：http://konect.uni-koblenz.de/networks/ego-facebook

[4]复杂网络统计指标参考：http://wap.sciencenet.cn/blog-404069-337511.html?mobile=1