复杂网络建网算法研究

复杂网络是研究复杂系统的重要手段之一。如何将已有数据高效地映射成为复杂网络即是复杂网络建网算法研究的主要内容之一。在收集整理了大量的文献资料后，文章详细综述了几种复杂网络的建网算法，并进一步分析了各自算法的优缺点。

在自然界和人类社会中，个体总是或多或少被环境所影响，同时也不停地影响着环境。复杂网络是描述个体间相互关系的模型[1]，由于其灵活普适的特点，已经广泛应用在自然科学、社会和科学工程技术上，并取得了很多突破性的进展。复杂网络已经成为国际学术界一个新兴的研究热点，并且取得了飞速的发展。

随着复杂网络分析方法的不断成熟和完善，如何将现实世界映射成复杂网络也已经成为研究的关键问题。2008 年，Lacasa 等人提出了可视图算法。2009 年，Luque 水平可视图算法。2019 年，田甜等人提出基于频域复杂网络分解的局部特征提取建网新方法[2]。2020 年，李姝等人提出基于随机图的复杂网络建网方法[3]。在复杂网络的研究过程中，寻求一种直观、简便而又有效的建网方法已成为众多学者追求的目标。本文总结了复杂网络涉及的一些基本概念，并综述了复杂网络建网的常见算法并分析了各自的优缺点。

2. 复杂网络的基本概念 二元组(), GV E=，nV=，mE=表示一个无向无权图，其中n 和m 是节点和边的数目，V 表示图中节点集合，E 表示图中边的集合。将复杂系统中按照某种规则抽象出来的个体映射为节点，复杂系统中个体之间的某种关系映射为边，这样复杂系统映射的二元组被称为复杂网络。复杂网络有如下几个基本概念。

2.1. 网络的度和度分布 度和度分布是复杂网络中基本而又重要的概念。节点v 的度是指所有与该节点相连的总边数[4]，在复杂网络中随机选择一个节点该节点的度恰好为k 的概率定义为P(k)，则分布函数P(k)为网络中所有节点的度分布。

ER 随机网络的度分布可以近似用泊松分布来描述， 所以这种网络也被称为均匀网络。

然而， 通过对来自生物、信息和社会等不同领域的真实网络的大量研究表明，实际网络的度分布明显不同于泊松分布，而是服从幂律分布的，即 ( ) ~P kk γ− (1) 这类网络称为无标度网络。

2.2. 网络直径D 和网络的平均路径长度L 网络直径为网络节点之间距离的最大值，即 {}, max|; , 1,2, , i jDDij i jV=≠= (2) 网络的平均路径长度为网络中任意两个节点之间的平均距离，即 (), 21i jijLDN N≥=−∑ (3) 这里的Di,j 为无权网络中连接节点i 和j 所经过的最少边的个数，N 为网络中节点的总个数。网络的