复杂网络理论在传统行业中的应用

周其明，刘小园

（1.中国人民解放军92823部队，三亚 572021；2.罗定职业技术学院，罗定 527200）

复杂网络理论在传统行业中的应用

周其明1，刘小园2

（1.中国人民解放军92823部队，三亚 572021；2.罗定职业技术学院，罗定 527200）

随着近年来复杂网络的发展，越来越多的研究人员开始用它来解决诸如生命科学与工程等其他领域的问题。目前，复杂网络理论逐渐渗透到许多不同的学科，也有许多传统产业正在试图将复杂网络理论应用到实际工作中。介绍复杂网络的基本理论研究，并以人际关系与沟通策略为例，建立在传统产业复杂网络的应用模型，并提供解决这些问题的常用方法。

复杂网络；传统产业；人际关系；沟通策略

0 引言

目前从神经生物学到统计物理学，网络已经遍及几乎所有的科学研究［1］。复杂网络（Complex Network），是指具有自组织、自相似、吸引子、小世界、无标度中部分或全部特点的网络。总之，复杂网络提出了很高的复杂性。其复杂性主要表现在以下几个方面：

（1）结构复杂性：一个巨大数量的节点，且网络结构呈现不同的特点。

（2）网络进化性：节点和连接的不断出现和消失。例如，在世界范围内的网络，任何时间网页或链接都可以打开或关闭，网络结构在不断变化。

（3）连接多样性：不同节点之间的连接权值多样，且可能存在方向性。

（4）动力学的复杂性：节点集可能归功于非线性动力学系统，例如，错综复杂的时间节点状态变化。

（5）节点多样性：在一个复杂的网络节点可以代表任何东西，例如，在人际关系网络，一个节点代表一个单独的实体；在万维网的网络，一个节点代表不同的页面。

（6）多个复杂的融合：更多不可预知的结果间的相互融合。

1 复杂网络理论

复杂网络的主要特点是无标度网络和小世界。

无尺度网络意味着一个小数量的节点共享大量的连接或大量节点的连接。一般来说，它们满足Zipf定律（80/20规则，马太定律）。无尺度网络缺乏代表平均度值，和节点度波动范围相当大。无尺度网络共享一个幂律分布。

小世界网络的概念是在六度分离的概念上开发，主要是指大部分节点彼此不相邻，但大多数节点可到达一个小的步数。尽管网络是大规模的，但任何两个节点之间存在一个相对较短的路径。主要是通过测量路径长度和聚类系数小世界网络的特点：它有一个小的特征路径长度和较大的聚类系数［2］。

目前，复杂网络的研究包括：几何特性的网络，网络的形成机制，网络演化的统计法，对网络模型的特点，网络的结构稳定性和网络演化动力学机制。在自然科学领域，网络研究的基本测量包括：程度和分布，特征路径长度，直径，密度，介数的网络，聚类系数，连接矩阵，互惠和幂律。在这里，一些常见的复杂网络参数将简要介绍［3］。

1.1 度

度是描述一个最基本的网络图，它是一个简单的单节点性能的重要概念，但在图论中，度表示一个节点的边。在有向图，它可以分为入度和出度。顾名思义，在某种程度上意味着边缘点为节点，而出度是指该节点指向其他节点的边数。在某种意义上，一个节点的度数越大，表示该节点有更“重要”的结点权值。

所有的节点度被称为网络的平均度。

1.2 特征路径长度

在网络中，任选两个节点，两个节点之间的最少边数定义为这两个节点之间的路径长度。所有路径长度平均值是网络的特征路径长度。

网络的特征路径长度也被称为平均最短路径，这是网络的全局特征，反映了网络的一般特征。

1.3 密度

密度描述了各点之间关系图中的贴近。一个完整的图形是指所有的节点是相邻的。即使在小型网络，完整性也是极为罕见的。密度用来衡量总分配的概念边缘检测，总密度分布边汇总来衡量图的完整程度。

密度测量图的凝聚力的整体水平。从图论的角度，密度反映了“紧”的图。密度取决于两个参数：网络结构的包容性和图形的整体程度。包容是指在图，即在相关部分节点总数，总结负图中的孤立节点的数目。密度的计算方法是如下：

其中L表示在图中的边的数目，N表示节点的数目。密度在有向图中的表达：

1.4 直径

在网络拓扑结构中，通常两个节点之间有多个路径，以最小的步骤路径作为两个节点之间的最短路径。最短路径的概念是要找到两个固定的节点之间的最短路径。在复杂的网络很难做到，也没有必要对两个节点之间的最短路径做定性分析。一般指对平均距离做定性分析。

整个网络，这两个节点之间的最长路径被定义为网络的直径。直径可与NMB和Pajek计算。

1.5 介数

介数通常分为边介数和节点介数。

节点介数定义为最短路径贯穿节点的所有最短路径比。边介数定义为最短路径穿过边缘的最短路径比。

介数反映相应节点或边缘网络中的作用和影响，这是一个重要的全局几何形状，具有很强的现实意义。例如，在人际关系的社会网络中，介数的分布特征反映了不同的人在整个社会中的地位，这对于发现和保护关键人员非常重要。

1.6 聚类集数

假设一个节点有k条边，在连接的节点，这些k边缘之间的最大边数为k（k-1）/2。实际上的边数与最大数的比值定义为聚类系数。所有的聚类系数的平均值被定义为网络的聚类系数。聚类系数是一个本地网络的特点，反映了两人的朋友圈的重合度，又是朋友的朋友之间的节点度。

1.7 连接矩阵

如果网络中有n个节点，这些节点之间的连接可以由一个n×n的0-1矩阵来表示。例如，对于一个有向图的顶点，如果顶点i到顶点j，第i行第j列的值为1，否则其值为0。同样，如果顶点j点到点i，第j行和第i列的值为1。这样的矩阵称为连接矩阵。当有在连接矩阵的几个非零元素，它是一个稀疏矩阵。在矩阵中的数字1是指一种这n个节点之间的连接。

1.8 互惠

在现代的P2P流媒体技术的应用所建立的模型是通用网状拓扑结构，并存在着或多或少的同伴和同行之间的互惠行为。例如，在一个有向图，顶点i可以连接顶点j，并且顶点j可以连接顶点i，那么边ij是互惠的边，顶点i和顶点j是互惠点。

一个简单的方法来获得一个图的互惠的边：bidirected边和图中总的边之比，公式如下：

在这个公式中的分子是图中bidirected的边（不包括自环），而M是图中总的边（不包括自环），即，

然而，这个简单的公式往往不能区分高互惠网络和有很多互惠的连接密度高的随机网络，因此我们引入一个更准确的公式来计算互惠边：

在这个公式中，r是上面定义的互惠边和有向边的比率，其计算方法如下：

其中N是在网络的总的节点数。

1.9 度幂律

在许多真实世界的复杂网络连通度的分布表现出幂函数的形式。K表示节点的度，P（k）表示K的概率密度，幂律分布P（k）～K（-），其中K是大于一个无符号整数，且幂律系数大于1，这是为了确保概率密度的积分收敛从一个无符号整数到无穷大。由于幂律分布无明显的特征长度，网络也被称为无标度网络。幂律分布广泛存在于真实世界的大型系统，如互联网、万维网、航空网络、电网、科研合作网络、生物generegularoty网络和代谢网络等。研究人员发现，幂律系数在许多真实世界的复杂网络是2-3。例如，互联网络幂律系数是在2.2-2.48之间，万维网幂律系数是在2.1-2.45，而代谢网络的幂律系数约为2.2。

网络的度幂律分布的一个重要特征是：P（k），节点度K的出现概率exponintially不趋于0时，K的增加，但相对渐近0，由此可知，“长尾巴”的特征，这个首先是在80/20规则和Zipf定律的提出。

网络的幂律分布表明，有一定数量的度较大的节点，称为中心。虽然枢纽节点只股票图形中的一小部分，但它们发挥了重要的作用。由于轮毂的存在，具有完全不同的性格与均匀分布的随机网络。

随机网络模型假设连接一对节点的概率是相等的，而度分布P（k）是泊松分布。P（k）速度趋于0时，节点K趋于无穷大时是正态分布、指数分布之间的关系。指数分布趋于0时，速度快了，因此我们可以形象的称为泊松分布的速度。在一般情况下，这三种分布都几乎是“窄尾”或“无尾”。以最常见的正态分布为例，假设期望值为0，方差为1，则变量的期望值小于方差之间的边缘的概率是2/3多一点；和它的概率小于两倍的方差为95%；而概率三倍以上的方差仅为0.3%。这表明，在一个狭窄的范围内的预期值的变量数的变化，而尾数几乎是0。因此，只有正态分布与泊松分布一致时，才能反映复杂网络的特征系统的本质特征。

2 复杂网络在传统产业的应用模型

复杂网络是一个高度抽象的复杂系统的边和节点的结构。随着对复杂网络研究的深入，网络的拓扑结构、自然的基本理论、演化和解决方案已经证明，对传统产业提供了新的视野和思路。如果在其他域的元素可以被看作是一个集合的边和节点，形成一个网络的拓扑结构，它可以被抽象为复杂网络模型，并用复杂网络的理论解决。在本节中，我们采取两个场景，人际关系与沟通策略，为例介绍了该模型的抽象和解决问题的过程。

2.1 人际关系模型

人际关系模型可以表达为复杂网络G（V，E），如图1所示，其参数含义如下：

V：代表复杂网络中的节点，每个节点代表一人。

E：代表复杂网络中的边，每条边代表有每两人之间的关系。

W：代表复杂的网络中边的权重，Wij表明节点Vi和Vj之间的关系。如两人之间关系的强度，且在不同的场景有不同的含义。

图1 人际关系的复杂网络模型

利用上述模型，人际关系问题可以抽象为复杂网络问题。我们可以用复杂网络理论解决人际关系的问题，例如，描述某个人的关系，计算出不同关系的强度，预测有些关系的演变等［4］。

2.2 沟通策略模型

基于前面构建的人际关系模式，可以提出交际策略模型［5］。

图2 沟通策略的复杂网络模型

如图2所示，ti是指通信塔的位置。选址通信塔需要复杂网络理论。这些通信塔应确保所有用户可以被覆盖，而且使用最少资源。这里的“最少资源”包括以下两个方面的含义：首先，在保证所有用户被覆盖，建造最少的塔；其次，由于通信质量与距离成负相关，尽可能保证塔和用户之间的总距离最短。这就对应最短路径算法的问题，其中Dijkstra算法和弗洛依德的最短路径算法是最流行的。在这里，我们简要介绍如下：

Dijkstra算法是最典型的最短路径算法，用来计算从一个节点到其他节点的最短路径。其主要特点是以起始节点为中心向外扩展，并从它直至结束节点。Dijkstra算法能获得的最短路径的最优解，但由于它通过大量的节点，它的效率很低。当网络是稀疏图，时间复杂度为O（V2）。

弗洛依德算法主要用于多源最短路径查找和无负权图。它使用一个矩阵记录图，且时间复杂度为O （V3）。弗洛依德的Warshall算法能对任意两节点之间的计算出最短路径，并能正确计算有向图或负权图的最短路径。

3 结语

随着社会的不断发展和复杂网络理论的改进，它已被应用于许多传统产业。本文在介绍复杂网络的基本理论的基础上，提出了可能的应用，如人际关系与沟通策略。事实上，复杂网络理论可以用在更多传统的行业，但在建模阶段是非常重要的。只有正确的模型，实际的问题才能得到正确地抽象和解决［6］。

［1］Strogatz S H，Exploring Complex Networks［J］.Nature，2001，410（6825）：268-276.

［2］Newman M E J.The Structure and Function of Complex Networks［J］.SIAM Review，2003，45（2）：167-256.

［3］Chunhong Z，Cuibo Y，Xinning Z，Ya G.Communication Network Technology［J］，2012.

［4］Heider F.The Psychology of Interpersonal Relations［M］.Psychology Press，2013.

［5］Singhal A，Rogers E M.Entertainment-Education：A Communication Strategy for Social Change［M］.Routledge，2012.

［6］Wang X F，Li X，Chen G R.Complex Network Theory and Application［J］.Tsinghua University licensing Agency，2006.

Application of the Complex Network in Traditional Industry

ZHOU Qi-ming1，LIU Xiao-yuan2
（1.Chinese People's Liberation Army 92823 Forces，Sanya 572021；2.Luoding Polytechnic，Luoding 527200）

With the rise and development of complex network in recent years，more and more researchers have begun to use it to solve problems in other fields，such as life science and engineering.Thus，complex network theory is gradually penetrated into many different disciplines，and also many traditional industries are trying to apply complex network theory into practical problems.Introduces the research history and basic theory of complex network，then takes the research of interpersonal relationship and communication strategy as an example，builds the application model of complex network in tradition industry，and provides the common approaches for these problems.

Complex Network；Traditional Industry；Interpersonal Relationship；Communication Strategy

1007-1423（2016）21-0025-04

10.3969/j.issn.1007-1423.2016.21.005

周其明（1979-），男，本科，工程师，研究方向为计算机网络技术

2016-04-27

2016-05-17

刘小园（1978-），男，硕士，副教授，研究方向为网络数据库系统