交叉抽样在复杂网络中的研究与应用_刘胜久.pdf
《交叉抽样在复杂网络中的研究与应用_刘胜久.pdf》由会员分享,可在线阅读,更多相关《交叉抽样在复杂网络中的研究与应用_刘胜久.pdf(9页珍藏版)》请在咨信网上搜索。
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 次抽样所得节点集及边集合的交集作为混
17、合交叉抽样的结果 根据混合交叉抽样的结果,混合交叉抽样可进一步分为点混合抽样与边混合抽样 步骤如下:(1)以概率 pv对原始网络 G 中的节点进行随机抽样,抽样得到的节点集记为 Vp;(2)以概率 pe对原始网络 G 中的边进行随机抽样,抽样得到的边集记为 Ep;(3)对所得节点集 Vp及边集 Ep进行分析,将节点交集 V=Vp VEp及边交集 E=EVpVpVpEp作为混合交叉抽样的结果;(4)对所得节点交集 V 构成的抽样网络 Gpv进行分析,反推出原始网络的各项参数,即点混合抽样;(5)对所得边交集 E 构成的抽样网络 Gpe进行分析,反推出原始网络的各项参数,即边混合抽样由于 2 次点
18、抽样及边抽样是相互独立的,故点抽样及边抽样的先后顺序不影响混合交叉抽样的结果,混合交叉抽样的概率为 pc=pv pe 显然,当 pv=1 时,混合交叉抽样即退化为通常意义上的边抽样;当 pe=1时,混合交叉抽样即退化为通常意义上的点抽样一般情况下,在混合抽样时对点及边进行等概率抽样,即 pv=pe=pc3实验验证31实验设计本文分别在随机网络、小世界网络及无标度网络上进行交叉抽样实验,随机网络选取 E 随机网络模型,小世界网络模型选取 WS 小世界网络模型,无标度网络模型选取 BA 无标度网络模型 对每种网络模型均选取 3 种不同规模的网络,采用 Pajek64 514 生成不同规模的网络 抽
19、样概率分别设定为 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 ran
20、dom 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 随机网络
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 交叉 抽样 复杂 网络 中的 研究 应用 刘胜久
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。