交叉抽样在复杂网络中的研究与应用_刘胜久.pdf

第 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)、重庆市高等教育教学改革研究重点项目(202182)、重庆市高等职业教育教学改革研究项目(Z212026)通讯作者:刘胜久，博士，研究方向:复杂网络、自然语言处理和大数据 Email:liushengjiu2008 163comdoi:103969/jissn16721292202301011交叉抽样在复杂网络中的研究与应用刘胜久1，伍小兵1，曹小平2，汪应1，欧明辉1(1重庆工程职业技术学院大数据与物联网学院，重庆 402260)(2重庆科创职业学院人工智能学院，重庆 402160)摘要 针对传统网络抽样主要是对复杂网络的节点及边进行独立抽样，提出对复杂网络的节点或边进行独立的 2 次抽样，再对得到的抽样网络进行分析，从而推算出原始网络的各项参数 在交叉抽样中，分析了点交叉抽样、边交叉抽样及混合抽样中的点混合抽样与边混合抽样 4 种交叉抽样方法，并在经典的 E、WS 及 BA 网络模型上进行了验证 结果表明，通过交叉抽样可较好地推算出原始网络的平均度、平均路径长度、网络直径、传递聚集系数、WS 聚集系数、网络维数等参数，且点混合抽样的效果最优 关键词 复杂网络，网络抽样，交叉抽样，混合抽样，网络参数 中图分类号 TP391 文献标志码 A 文章编号 16721292(2023)01008409esearch and Application of Cross Sampling on Complex 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 analysis 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 parameters 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 length，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 sampling，network parameter传统意义上度量图及复杂网络特性的参数有节点数、边数、度、平均度、直径、平均路径长度、聚类系数等 对于无向图、有向图、混合图，还可通过其图能量1、斜能量2、Hermitian 能量3 及网络能量46 等对其特性进行深层次的分析研究 图的这些参数在各种人工网络78 及真实网络910 中均得到成功应用，如社会学中的六度分割等图及复杂网络的节点及边的数量往往非常庞大，对大规模的图进行分析极为耗时费力，抽样成为推断复杂网络参数的一个可行选择 由于网络是由节点及边构成的，传统抽样方法主要有点抽样和边抽样两种 实际应用中，这两种方法均有一些缺陷与不足 本文提出一种交叉抽样的方法，通过对复杂网络的节点或边分别进行 2 次独立的抽样，再对抽样结果进行分析，以此估算实际网络的各种参数 实验结果表明，所提方法在多个复杂网络模型中表现良好，且混合交叉抽样中的点混合抽样效果最优48刘胜久，等:交叉抽样在复杂网络中的研究与应用1预备知识11图及其分类根据不同的分类标准，图可以分为多个不同的类型11 根据节点及边是否带有权重，图可以分为无权图与带权图 无权图可表述为 G=(V，E)形式的二元组，其中 V 为节点集，E 为边集，VEE 带权图可表述为 G=(V，E，W)，其中 W 为权重 节点或边的权重可以分别是正实数、负实数、纯虚数及复数等 可认为无权图的节点及边的权重非 0 即 1，即无权图是带权图的特例根据图中的边是否有方向，图可分为无向图、有向图及混合图 无向图、有向图、混合图一般情况下可通过邻接矩阵、斜邻接矩阵、Hermitian 矩阵进行表述，这些矩阵均为|V|V|的方阵此外，根据图中是否含有平行边及自环，图可分为简单图与多重图 根据图中一个节点连接的其他节点数目，图可分为零图、空图、环图、规则图、完全图等本文研究所涉及的图是指无向、无权、无自环、无平行边的简单图12复杂网络模型经典的复杂网络模型主要有 E 随机网络模型、WS/NW 小世界网络模型、BA 无标度网络模型Erdos 等提出了 E 随机网络模型12，该网络节点度分布呈泊松分布 但 E 随机网络模型与真实世界中的复杂网络并不契合 Watts 等对 E 随机网络模型的连接策略进行改进，采用断边重连处理节点之间的连接，提出了 WS 小世界网络模型13 Newman 等又采用随机加边处理节点之间的连接，提出了 NW小世界网络模型14 二者得到的度分布呈指数分布 在节点数目极大时，可认为 WS 网络模型与 NW 网络模型是等价的 Barabasi 等继续对 E 随机网络模型的连接策略进行改进，采用增长择优处理节点之间的连接，提出了 BA 无标度网络模型15，较好地解释了真实世界中的网络鲁棒与脆弱并存的特性对经典复杂网络模型的改进是当前研究的一大热点，如对 BA 无标度网络模型的改进16 等 由于邻接矩阵与网络是一一对应的，通过邻接矩阵对复杂网络进行研究也是复杂网络研究的重要内容17 13复杂网络参数度分布是区分 E 随机网络模型、WS/NW 小世界网络模型、BA 无标度网络模型的一个重要方法，三者的度分布不同，参数也不一致 度秩函数18、分维指标19、分形维数20、网络维数21 等是较常用的方法 本文主要应用平均度、平均路径长度、网络直径、聚集系数、网络维数、网络能量对网络参数进行估算对图 G 中的任一节点 vi，与 vi直接相连的节点数目，即与 vi直接相连的边数，称为 vi的度，记为 d(vi)所有节点的度的平均值称为图 G 的平均度，记为 d(v):d(v)=1|V|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 倍的对数值与节点数目对数值的比值: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 构成的抽样网络 Gp进行分析，反推出原始网络的各项参数并分析其特性由于 2 次点抽样是相互独立的，故点交叉抽样的概率为 pv=pv1 pv2 显然，当 pv1或 pv2等于 1 时，点交叉抽样即退化为通常意义上的点抽样一般情况下，在点交叉抽样时对 2 次节点抽样进行等概率抽样，即 pv1=pv2=pv22边交叉抽样边交叉抽样对原始网络中的边进行 2 次随机抽样，再对 2 次抽样得到的边集进行分析，取 2 次抽样得到的不同边集合的交集作为边交叉抽样的结果 步骤如下:(1)以概率 pe1对原始网络 G 中的边进行随机抽样，抽样得到的边集记为 E1;(2)以概率 pe2对原始网络 G 中的边进行随机抽样，抽样得到的边集记为 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)对所得节点交集 V 构成的抽样网络 Gpv进行分析，反推出原始网络的各项参数，即点混合抽样;(5)对所得边交集 E 构成的抽样网络 Gpe进行分析，反推出原始网络的各项参数，即边混合抽样由于 2 次点抽样及边抽样是相互独立的，故点抽样及边抽样的先后顺序不影响混合交叉抽样的结果，混合交叉抽样的概率为 pc=pv pe 显然，当 pv=1 时，混合交叉抽样即退化为通常意义上的边抽样;当 pe=1时，混合交叉抽样即退化为通常意义上的点抽样一般情况下，在混合抽样时对点及边进行等概率抽样，即 pv=pe=pc3实验验证31实验设计本文分别在随机网络、小世界网络及无标度网络上进行交叉抽样实验，随机网络选取 E 随机网络模型，小世界网络模型选取 WS 小世界网络模型，无标度网络模型选取 BA 无标度网络模型 对每种网络模型均选取 3 种不同规模的网络，采用 Pajek64 514 生成不同规模的网络 抽样概率分别设定为 10%、20%、30%、40%、50%为避免随机性的影响，对每次抽样均重复 10 次，取 10 次交叉抽样所得结果的算术平均值作为最终结果 实验硬件环境为 lntel()Core(TM)i54300U CPU 190GHz 250GHz、8G 内存、500G68刘胜久，等:交叉抽样在复杂网络中的研究与应用硬盘，软件环境是 Windows 7 旗舰版 64 位操作系统、jdk180_191、Eclipse 201906(4120)32交叉抽样实验结果321随机网络交叉抽样实验结果表 1E 随机网络参数统计表Table 1Parameter statistics of E random network编号参数E(103，104)E(104，105)E(105，106)1平均度2020202平均路径长度3257 694258 515261 463网络直径5794传递聚集系数0009 878 130000 971 610000 098 185WS 聚集系数0009 787 960000 967 690000 099 596网络维数1433 6771325 2571260 206分别构建 3 个不同规模的 E 随机网络，各项参数如表 1 所示表 1 中，E(m，n)表示向初始的 m 个节点随机添加 n 条边构成的 E 随机网络图1图3 分别是对表1 中的3 个 E 随机网络进行交叉抽样得到的结果322小世界网络交叉抽样实验结果分别构建不同规模的 WS 小世界网络，各项参数如表 2 所示图 1E(103，104)交叉抽样结果Fig.1Cross sampling result of E(103，104)图 2E(104，105)交叉抽样结果Fig.2Cross sampling result of E(104，105)78南京师范大学学报(工程技术版)第 23 卷第 1 期(2023 年)图 3E(105，106)交叉抽样结果Fig.3Cross sampling result of E(105，106)表 2WS 小世界网络参数统计表Table 2Parameter statistics of WS small-world network编号参数WS(103，10，05)WS(104，10，05)WS(105，10，05)1平均度2020202平均路径长度2696 313532 284329 873网络直径4564传递聚集系数0103 776 540089 455 030085 621 835WS 聚集系数0109 375 320093 902 150090 241 156网络维数1433 6771325 2571260 206表 2 中，WS(m，k，p)表示初始的规则图有 m 个节点，每个节点与左右各 k 个节点相连，以概率 p 随机断掉连接并重新连边后得到 WS 小世界网络图 4图 6 分别是对表 2 中的 3 个 WS 小世界网络进行交叉抽样得到的结果图 4WS(103，10，05)交叉抽样结果Fig.4Cross sampling result of WS(103，10，05)88刘胜久，等:交叉抽样在复杂网络中的研究与应用图 5WS(104，10，05)交叉抽样结果Fig.5Cross sampling result of WS(104，10，05)图 6WS(105，10，05)交叉抽样结果Fig.6Cross sampling result of WS(105，10，05)323无标度网络交叉抽样实验结果分别构建不同规模的 BA 无标度网络，各项参数如表 3 所示表 3BA 无标度网络参数统计表Table 3Parameter statistics of BA scale-free network编号参数BA(103，104，10，02)BA(104，105，10，02)BA(105，106，10，02)1平均度1914419897 219921 722平均路径长度2736 863353 713974 603网络直径6784传递聚集系数0068 056 480012 573 680001 961 205WS 聚集系数0049 367 180006 024 660000 689 536网络维数1427 3441324 6981259 86598南京师范大学学报(工程技术版)第 23 卷第 1 期(2023 年)表 3 中，BA(m，n，c，p)表示初始的 E 随机图有 c 个节点，这些节点的初始连接概率为 p，通过添加 m个节点及不超过 n 条边后得到 BA 无标度网络图 7图 9 分别是对表 3 中的 3 个 BA 无标度网络进行交叉抽样得到的结果图 7BA(103，104，10，02)交叉抽样结果Fig.7Cross sampling result of BA(103，104，10，02)图 8BA(104，105，10，02)交叉抽样结果Fig.8Cross sampling result of BA(104，105，10，02)33实验分析通过分析图 1图 9 的结果可以发现，在选定的平均度、平均路径长度、网络直径、传递聚集系数、WS聚集系数、网络维数等 6 个网络参数的交叉抽样中，随着交叉抽样概率的增加，相较于点交叉抽样、边交叉抽样、边混合抽样，点混合抽样在平均度、平均路径长度、传递聚集系数、WS 聚集系数、网络维数等方面都线性趋近原始网络，且平均度及网络维数的线性效果最好，因而完全可以通过分析点混合抽样结果推断出原始网络的各项参数 尽管随着抽样概率的变化，通过点交叉抽样、边交叉抽样、点混合抽样、边混合抽样09刘胜久，等:交叉抽样在复杂网络中的研究与应用图 9BA(105，106，10，02)交叉抽样结果Fig.9Cross sampling result of BA(105，106，10，02)所得结果均存在一定波动，但点混合抽样结果波动更为平缓，在 E 及 WS 网络的抽样中表现得更为突出 在网络直径方面，实验发现，随着交叉抽样概率的逐步增加，交叉抽样网络的参数并未逐步趋近原始网络 实际上，由于网络直径需要对所有路径进行分析，大部分网络抽样方法对推断原始网络的网络直径效果均欠佳4结论本文提出了一种针对复杂网络的交叉抽样方法，通过对复杂网络的节点或边进行独立的 2 次抽样，再对抽样的结果进行分析，从而推断原始网络的各项参数 对 E/WS/BA 网络模型的实验研究发现，通过交叉抽样结果可较好推断出原始网络的各项参数，且点混合抽样效果更好未来的工作包括 3 个方面:交叉抽样对推断原始复杂网络的边介数、点介数的效果如何需继续进一步分析;网络直径的交叉抽样结果欠佳，如何通过交叉抽样推断出原始网络的网络直径需进一步研究;真实世界的复杂网络往往是小世界、无标度、自相似等多种特性的复合体，在真实网络中交叉抽样的效果如何需进行进一步验证 参考文献(eferences)1 GUTMAN I The energy of a graph J Ber Math Statist Sekt Forschungsz Graz，1978，103:122 2 ADIGA C，BALAKISHNAN，SO W The skew energy of a digraphJ Linear Algebra and Its Applications，2010，432:18251835 3 LIU J X，LI X L Hermitian-adjacency matrices and Hermitian energies of mixed graphs J Linear Algebra and Its Applications，2015，466:182207 4 LIU S J，LI T，ZHU J，et al Network energy:a new energy of a graph C/2019 IEEE 14th International Conference onIntelligent Systems and Knowledge Engineering(ISKE2019)Dalian，China:IEEE，2019 5 LIU S J，LI T，ZHANG X B，et al On network energy of oriented graphs C/Proceedings of the 14th International FLINSConference on obotics and Artificial Intelligence/IEEE 15th International Conference on Intelligent Systems and KnowledgeEngineering(FLINS 2020/ISKE 2020)Cologne，Germany:World Scientific，2020 6 刘胜久，李天瑞，谢鹏，等 网络能量在混合图中的研究与应用J 湖南大学学报(自然科学版)，2021，48(6):10511119南京师范大学学报(工程技术版)第 23 卷第 1 期(2023 年)7 倪伟平 最大度是 6 且不含有弦的小圈的可平面图的边染色 J 南京师大学报(自然科学版)，2011，34(3):1924 8 唐保祥，任韩 几类图完美匹配的数目 J 南京师大学报(自然科学版)，2010，33(3):16 9 陈轩泽，霍静，费峰，等 基于 PCA 与 ArcGIS 网络分析的图书馆阅览室管理系统J 南京师范大学学报(工程技术版)，2012，12(2):5763 10 李林，封志明，赵品彰，等 一种基于散射参数测试的人工电源网络校准方法 J 南京师范大学学报(工程技术版)，2011，11(2):48 11 张先迪，李正良 图论及其应用 M 北京:高等教育出版社，2005 12 EDS P，ENYI A On random graphs I J Publicationes Mathematicae，1959(6):290297 13 WATTS D J，STOGATZ S H Collective dynamics ofsmall-world networks J Nature，1998，393(6684):440442 14 NEWMAN M E J，WATTS D J enormalization group analysis of the small-world network model J Physics Letter A，1999，293(4/5/6):341346 15 BAABSI A L，ALBET Emergence of scaling in random networks J Science，1999，286:509512 16 刘胜久，李天瑞，珠杰，等 具有双峰效应特性的复杂网络模型研究 J 复杂系统与复杂性科学，2017，14(1):4651，102 17 刘胜久，李天瑞，洪西进，等 基于矩阵运算的复杂网络构建方法 J 中国科学(信息科学)，2017，46(5):610626 18 朱大智，吴俊，谭跃进，等 度秩函数 个新的复杂网络统计特征 J 复杂系统与复杂性科学，2006，3(4):2834 19 WEI D J，LIU Q，ZHANG H X，et al Box-covering algorithm for fractal dimension of weighted networks J Scientific eports，2013，3:3049 20 LIU J L，YU Z G，ANH VTopological properties and fractal analysis of a recurrence network constructed from fractionalBrownian motions J Physical eview，E Statistical，Nonlinear，and Soft Matter Physics，2014，89(3):032814 21 刘胜久，李天瑞，刘小伟 网络维数:一种度量复杂网络的新方法 J 计算机科学，2019，46(1):5156 22 LUCE D，PEY A D A method of matrix analysis of group structure J Psychometrika，1949，14(2):95116 责任编辑:严海琳(上接第 55 页)39 WANG X，GISHICK，GUPTA A，et al Non-local neural networks C/Proceedings of the IEEE Conference on ComputerVision and Pattern ecognition Salt Lake City，UT，USA，2018 40 HOWAD A G，ZHU M L，CHEN B，et al MobileNets:Efficient convolutional neural networks for mobile vision applications J arXiv Preprint arXiv:170404861，2017 41 GALLUP D，FAHM J M，MODOHAI P，et al eal-time plane-sweeping stereo with multiple sweeping directionsC/2007 IEEE Conference on Computer Vision and Pattern ecognition Minneapolis，Minnesota，USA，2007 42 XU N，PICE B，COHEN S，et al Deep image mattingC/Proceedings of the IEEE Conference on Computer Vision andPattern ecognition Honolulu，HI，USA，2017 43 JENSEN，DAHL A，VOGIATZIS G，et al Large scale multi-view stereopsis evaluationC/Proceedings of the IEEEConference on Computer Vision and Pattern ecognition Columbus，OH，USA，2014 44 TOLA E，STECHA C，FUA P Efficient large-scale multi-view stereo for ultra high-resolution image sets J Machine Visionand Applications，2012，23(5):903920 45 CAMPBELL N D F，VOGIATZIS G，HENNDEZ C，et al Using multiple hypotheses to improve depth-maps for multi-viewstereo C/European Conference on Computer Vision Marseille，France，2008:766779 46 GALLIANI S，LASINGE K，SCHINDLE K Gipuma:Massively parallel multi-view stereo reconstruction J Publikationender Deutschen Gesellschaft fr Photogrammetrie，Fernerkundung und Geoinformation，2016，25:361369 47 FUUKAWA Y，PONCE J Accurate，dense，and robust multiview stereopsis J IEEE Transactions on Pattern Analysis andMachine Intelligence，2009，32(8):13621376 责任编辑:陈庆29