1、第 23 卷第 1 期2023 年 3 月南京师范大学学报(工程技术版)JOUNAL OF NANJING NOMAL UNIVESITY(ENGINEEING AND TECHNOLOGY EDITION)Vol.23 No.1Mar，2023收稿日期:20220915基金项目:重庆市高校创新研究群体项目(CXQT21032)、重庆市自然科学基金项目(cstc2021jcyjmsxmX0532)、重庆市教育委员会科学技术研究计划项目(KJQN202103404、KJQN202005403、KJQN202003409、KJQN202103401、KJZDM202203401)、重庆市高等教育教
2、学改革研究重点项目(202182)、重庆市高等职业教育教学改革研究项目(Z212026)通讯作者:刘胜久，博士，研究方向:复杂网络、自然语言处理和大数据 Email:liushengjiu2008 163comdoi:103969/jissn16721292202301011交叉抽样在复杂网络中的研究与应用刘胜久1，伍小兵1，曹小平2，汪应1，欧明辉1(1重庆工程职业技术学院大数据与物联网学院，重庆 402260)(2重庆科创职业学院人工智能学院，重庆 402160)摘要 针对传统网络抽样主要是对复杂网络的节点及边进行独立抽样，提出对复杂网络的节点或边进行独立的 2 次抽样，再对得到的抽样网络
3、进行分析，从而推算出原始网络的各项参数 在交叉抽样中，分析了点交叉抽样、边交叉抽样及混合抽样中的点混合抽样与边混合抽样 4 种交叉抽样方法，并在经典的 E、WS 及 BA 网络模型上进行了验证 结果表明，通过交叉抽样可较好地推算出原始网络的平均度、平均路径长度、网络直径、传递聚集系数、WS 聚集系数、网络维数等参数，且点混合抽样的效果最优 关键词 复杂网络，网络抽样，交叉抽样，混合抽样，网络参数 中图分类号 TP391 文献标志码 A 文章编号 16721292(2023)01008409esearch and Application of Cross Sampling on Complex
4、NetworkLiu Shengjiu1，Wu Xiaobing1，Cao Xiaoping2，Wang Ying1，Ou Minghui1(1Big Data and Internet of Things School，Chongqing Vocational Institute of Engineering，Chongqing 402260，China)(2School of Artifical Intelligence，Chongqing Creation Vocational College，Chongqing 402160，China)Abstract:Among the analy
5、sis and research of complex network，in view of the traditional network sampling being mainlyon sample the nodes and edges of complex network independently，this paper firstly proposes cross sampling by samplethe nodes or edges of the complex network twice independently，and then calculate the paramete
6、rs of the original networkby sampling network On cross sampling，four cross sampling methods including point cross sampling，edge crosssampling，point mixed sampling and edge mixed sampling are analyzed and verified on E，WS and BA network modelsThe results show that the average degree，average path leng
7、th，network diameter，transitivity clustering coefficient，WSclustering coefficient，and network dimension of the original network can be calculated by cross sampling，while that thepoint mixed sampling is the best cross sampling methodKey words:complex network，network sampling，cross sampling，mixed sampl
8、ing，network parameter传统意义上度量图及复杂网络特性的参数有节点数、边数、度、平均度、直径、平均路径长度、聚类系数等 对于无向图、有向图、混合图，还可通过其图能量1、斜能量2、Hermitian 能量3 及网络能量46 等对其特性进行深层次的分析研究 图的这些参数在各种人工网络78 及真实网络910 中均得到成功应用，如社会学中的六度分割等图及复杂网络的节点及边的数量往往非常庞大，对大规模的图进行分析极为耗时费力，抽样成为推断复杂网络参数的一个可行选择 由于网络是由节点及边构成的，传统抽样方法主要有点抽样和边抽样两种 实际应用中，这两种方法均有一些缺陷与不足 本文提出一种交
9、叉抽样的方法，通过对复杂网络的节点或边分别进行 2 次独立的抽样，再对抽样结果进行分析，以此估算实际网络的各种参数 实验结果表明，所提方法在多个复杂网络模型中表现良好，且混合交叉抽样中的点混合抽样效果最优48刘胜久，等:交叉抽样在复杂网络中的研究与应用1预备知识11图及其分类根据不同的分类标准，图可以分为多个不同的类型11 根据节点及边是否带有权重，图可以分为无权图与带权图 无权图可表述为 G=(V，E)形式的二元组，其中 V 为节点集，E 为边集，VEE 带权图可表述为 G=(V，E，W)，其中 W 为权重 节点或边的权重可以分别是正实数、负实数、纯虚数及复数等 可认为无权图的节点及边的权重
10、非 0 即 1，即无权图是带权图的特例根据图中的边是否有方向，图可分为无向图、有向图及混合图 无向图、有向图、混合图一般情况下可通过邻接矩阵、斜邻接矩阵、Hermitian 矩阵进行表述，这些矩阵均为|V|V|的方阵此外，根据图中是否含有平行边及自环，图可分为简单图与多重图 根据图中一个节点连接的其他节点数目，图可分为零图、空图、环图、规则图、完全图等本文研究所涉及的图是指无向、无权、无自环、无平行边的简单图12复杂网络模型经典的复杂网络模型主要有 E 随机网络模型、WS/NW 小世界网络模型、BA 无标度网络模型Erdos 等提出了 E 随机网络模型12，该网络节点度分布呈泊松分布 但 E
11、随机网络模型与真实世界中的复杂网络并不契合 Watts 等对 E 随机网络模型的连接策略进行改进，采用断边重连处理节点之间的连接，提出了 WS 小世界网络模型13 Newman 等又采用随机加边处理节点之间的连接，提出了 NW小世界网络模型14 二者得到的度分布呈指数分布 在节点数目极大时，可认为 WS 网络模型与 NW 网络模型是等价的 Barabasi 等继续对 E 随机网络模型的连接策略进行改进，采用增长择优处理节点之间的连接，提出了 BA 无标度网络模型15，较好地解释了真实世界中的网络鲁棒与脆弱并存的特性对经典复杂网络模型的改进是当前研究的一大热点，如对 BA 无标度网络模型的改进1
12、6 等 由于邻接矩阵与网络是一一对应的，通过邻接矩阵对复杂网络进行研究也是复杂网络研究的重要内容17 13复杂网络参数度分布是区分 E 随机网络模型、WS/NW 小世界网络模型、BA 无标度网络模型的一个重要方法，三者的度分布不同，参数也不一致 度秩函数18、分维指标19、分形维数20、网络维数21 等是较常用的方法 本文主要应用平均度、平均路径长度、网络直径、聚集系数、网络维数、网络能量对网络参数进行估算对图 G 中的任一节点 vi，与 vi直接相连的节点数目，即与 vi直接相连的边数，称为 vi的度，记为 d(vi)所有节点的度的平均值称为图 G 的平均度，记为 d(v):d(v)=1|V
13、|viVd(vi)(1)对图 G 中的任一节点对 vi及 vj，vi到 vj之间所要经过的边数称为 vi到 vj的路径长度，记为 dij 所有节点对之间的路径长度的平均值称为图 G 的平均路径长度，记为 L:L=1 dijviV，vjV，ijdij(2)图 G 的网络直径 D 定义为所有节点对之间的路径长度的最大值:D=maxviV，vjV，ijdij(3)聚集系数有局部聚集系数及全局聚集系数之分，统计一般只分析全局聚集系数22，记为 CC:CC=3 G3 G+2 G，(4)式中，G 表示图 G 中闭三点组;G表示图 G 中开三点组图 G 的网络维数 ND 定义为图 G 边数目 2 倍的对数值
14、与节点数目对数值的比值:ND=lg2|E|lg|V|(5)58南京师范大学学报(工程技术版)第 23 卷第 1 期(2023 年)2交叉抽样21点交叉抽样点交叉抽样对原始网络中的节点进行 2 次随机抽样，再对 2 次抽样得到的节点集进行分析，取 2 次抽样得到的不同节点集合的交集作为点交叉抽样的结果 步骤如下:(1)以概率 pv1对原始网络 G 中的节点进行随机抽样，抽样得到的节点集记为 V1;(2)以概率 pv2对原始网络 G 中的节点进行随机抽样，抽样得到的节点集记为 V2;(3)对得到的节点集 V1及 V2进行分析，将节点交集 V=V1V2作为点交叉抽样的结果;(4)对所得节点交集 V
15、构成的抽样网络 Gp进行分析，反推出原始网络的各项参数并分析其特性由于 2 次点抽样是相互独立的，故点交叉抽样的概率为 pv=pv1 pv2 显然，当 pv1或 pv2等于 1 时，点交叉抽样即退化为通常意义上的点抽样一般情况下，在点交叉抽样时对 2 次节点抽样进行等概率抽样，即 pv1=pv2=pv22边交叉抽样边交叉抽样对原始网络中的边进行 2 次随机抽样，再对 2 次抽样得到的边集进行分析，取 2 次抽样得到的不同边集合的交集作为边交叉抽样的结果 步骤如下:(1)以概率 pe1对原始网络 G 中的边进行随机抽样，抽样得到的边集记为 E1;(2)以概率 pe2对原始网络 G 中的边进行随机
16、抽样，抽样得到的边集记为 E2;(3)对得到的边集 E1及 E2进行分析，将边交集 E=E1E2作为边交叉抽样的结果;(4)对所得边交集 E 构成的抽样网络 Gp进行分析，反推出原始网络的各项参数并分析其特性由于 2 次边抽样是相互独立的，故边交叉抽样的概率为 pe=pe1 pe2 显然，当 pe1或 pe2等于 1 时，边交叉抽样即退化为通常意义上的边抽样一般情况下，在边交叉抽样时对 2 次边抽样进行等概率抽样，即 pe1=pe2=pe23混合交叉抽样混合交叉抽样分别通过对原始网络中的节点及边进行随机抽样，再对 2 次抽样所得节点集及边集进行分析，取 2 次抽样所得节点集及边集合的交集作为混合交叉抽样的结果 根据混合交叉抽样的结果，混合交叉抽样可进一步分为点混合抽样与边混合抽样 步骤如下:(1)以概率 pv对原始网络 G 中的节点进行随机抽样，抽样得到的节点集记为 Vp;(2)以概率 pe对原始网络 G 中的边进行随机抽样，抽样得到的边集记为 Ep;(3)对所得节点集 Vp及边集 Ep进行分析，将节点交集 V=Vp VEp及边交集 E=EVpVpVpEp作为混合交叉抽样的结果;(4)