基于网络拓扑特征的图网络生成方法及系统.pdf

(19)中华人民共和国国家知识产权局(12)发明专利申请(10)申请公布号CN113921095A(43)申请公布日2022.01.11(21)申请号202111128068.4(22)申请日2021.09.26(71)申请人浙江工业大学地址310014浙江省杭州市拱墅区潮王路18号(72)发明人宣琦汪泽钰单雅璐王金焕(74)专利代理机构杭州天正专利事务所有限公司33201代理人王兵(51)Int.Cl.G16C20/70(2019.01)G16C20/50(2019.01)G06F16/901(2019.01)G06K9/62(2022.01)权利要求书3页说明书8页附图5页(54)发明名称基于网络拓扑特征的图网络生成方法及系统(57)摘要基于网络拓扑特征的图网络生成方法及系统，包括：S1：读取数据集，获取原网络图特征；S2：根据预先设定的目标选择网络生成规则以进行网络生成操作，本方法包含三种网络生成规则，分别对应平均介数中心性、平均接近中心性和叶子节点百分比，网络生成前后原网络和新网络的特征可以达到近似或保持一致的效果；S3：输出生成网络；实现本发明的基于网络拓扑特征的图网络生成系统，包括：网络读取模块、网络生成模块、网络输出模块；本发明针对不同的网络拓扑特征进行网络生成，有助于对网络特定特征的分析；本方法包含针对三种不同的网络拓扑特征的网络生成规则，可扩展性较好，且对数据增强和图分类的应用有着较好的增益。CN113921095ACN113921095A权利要求书1/3页1.基于网络拓扑特征的图网络生成方法及系统，其特征在于：包括以下步骤：S1：读取数据集，获取原网络图特征；S2：根据网络分析任务针对的拓扑特征，从规则库中选择对应的网络生成规则以进行网络生成操作，所述的规则库包含三种图网络生成规则，分别对应平均介数中心性、平均接近中心性和叶子节点百分比，网络生成前后原网络和新网络的特征可以达到近似或保持一致的效果；S3：输出生成网络。2.如权利要求1所述的基于网络拓扑特征的图网络生成方法及系统，其特征在于：所述步骤S1包括：读取数据集，数据集包含多个原始网络G＝(V，E)，其中V表示网络中节点的集合，E表示网络中连边的集合；网络中共有n个节点，m条连边，并计算原始网络的平均介数中心性、平均接近中心性、叶子节点百分比；平均介数中心性由网络中各个节点的介数中心性平均而得，网络图g的平均介数中心性BCg的计算公式为：其中BCi为节点i的介数中心性如公式(2)所示，其中pst表示从节点s到节点t的最短路径的数量，其中表示从节点s到节点t的经过节点i的最短路径的数量；平均接近中心性由网络中各个节点的接近中心性平均而得，网络图g的平均接近中心性CCg的计算公式为：其中CCi为节点i的接近中心性如公式(4)所示，其中dij表示从节点i到节点j的距离；叶子节点为只有一个邻居的节点，网络图g的叶子节点百分比Pg的计算公式为：其中fg为网络图g中叶子节点的数量。3.如权利要求1所述的基于网络拓扑特征的图网络生成方法及系统，其特征在于：步骤S2所述的从规则库中选择网络生成规则的具体方式如下：根据预先设定的目标，选择对应的生成规则以进行网络生成；当对图网络的介数中心性进行分析、或针对介数中心性进行特征提取时，则可以将目标设定为介数中心性，选择基于平均介数中心性的图网络生成规则；当对图网络的接近中心性进行分析、或针对接近中心性进行特征提取时，则可以将目标设定为接近中心性，选择基于平均接近中心性的图网络生成规则；当对图网络的叶子节点进行分析、或针对叶子节点进行特征提取时，则可以将目标设定为叶子节点，选择基于叶子节点百分比的图网络生成规则。4.如权利要求1所述的基于网络拓扑特征的图网络生成方法及系统，其特征在于：步骤S2所述的基于平均介数中心性的网络生成规则如下：基于平均介数中心性的网络生成规则2CN113921095A权利要求书2/3页包含输入参数有原始图连边更改比例alpha和迭代次数iters；遍历筛选原始网络图的连边集合E，从中随机选择一条不包含叶子节点的连边e＝(v1，v2)；选择比较节点v1，v2的介数中心性，选择连边中介数中心性更大的节点作为改动节点且设为vc将另一个节点设为vd，并删除这条连边；判断删除连边后网络图的连通性，若网络图不连通则撤销本次操作，并累计第一类失败(连通性尝试失败)次数；获取其余节点的介数中心性列表MBC，遍历MBC选择其中与节点vd的介数中心性相近的节点作为重连节点vr，并设定eadd＝(vc，vr)为候选重连连边；判断候选重连连边的有效性，若连边已存在网络图中，则撤销本次数据生成操作，并累计第二类失败(重边失败)尝试次数，反之则添加重连连边；以上仅是针对网络图中一条连边的改动，在数据生成过程中会发生数次这样的操