基于Motif的图采样算法.pdfVIP

南京大学学报（自然科学）

第60卷第4期Vol.60,No.4

JOURNAIUNIVERSITY

2024年7月CNATURASCIENCEJuly,2024

DOI:10.13232/j.cnki.jnju.2024.04.003

基于Motif的图采样算法

欣*，邹杰军，方星

石俊豪，王宇，蒋

（西南石油大学计算机与软件学院，成都，610500）

摘要：图采样通过对图数据进行约简操作，获得比原图的规模更小的图结构，进而服务于图谱分析、图可视化等下游任

务.现有的图采样算法侧重于保留图中显著的结构特征而忽略了节点属性，导致采样图在许多下游任务如频繁模式挖掘

等，难以取得预期效果，为此，提出基于Motif的节点有偏采样算法（Motif-BasedNodeBiasedSampling，MNBS），利用频

繁Motif结构重新定义图中节点的重要性，随后进行有偏节点采样，实现融合节点属性与结构特征的采样.为了快速识别

频繁Motif模式，设计了具有“提前终止”特性的Motif模式快速发现算法（FastMotif-PatternDiscovery，FMPD），能高效

且准确地发现Motif模式以支持图采样，实验表明，MNBS采样算法在多项指标上优于其他基线算法，其对数归一化累

积组相关性指标平均降低0.54,使用包含“提前终止”特性策略的FMPD算法的时间消耗和内存消耗比基线算法分别降

低56.1%和29.8%.

关键词：图采样，图数据挖掘，网络分析，Motif结构

中图分类号：TP301文献标志码：A

Motif-basedgraphsamplingalgorithm

ShiJunhao,WangXin,ZouJiejun,FangYu,JiangXing

(SchoolofComputerScienceandSoftwareEngineering,SouthwestPetroleumUniversity,Chengdu,610500,China)

Abstract:Graphsamplingobtainsgraphstructuresofsmallersizecomparedtotheoriginalgraphbyperforming

approximationoperationsongraphdata,andthusservesdownstreamtaskssuchasgraphanalysisandgraphvisualisation.

Existinggraphsamplingalgorithmsfocusonpreservingsalientstructuralfeaturesinthegraphandignorenodeattributes,

leadingtodifficultiesinachievingtheexpectedresultsofsampledgraphsinmanydownstreamtasks,suchasfrequentpattern

mining.Forthisreason,thispaperproposesMotif-BasedNodeBiasedSampling(MNBS),analgorithmthatredefinesthe

importanceofno