一种基于度特征替换策略的流式图抽样方法

摘要

本发明属于流式图数据抽样领域，尤其涉及一种度特征替换策略的抽样方法。包括：S1.流式边e＝(u,v)到达，判断是否会产生点替换，如果会发生点替换，则执行S2，否则执行S7；S2.根据抽样子图Gs中点的度特性，确定点替换概率函数f(di)，di∈D，D为子图中点的度分布集合；根据概率函数计算点vi被替换的概率得到子图中点替换概率集合S3.采用遗传算法中的选择算法select(P)，其中P为S2中计算得到的点替换概率集合，选取待替换的点r；S4.根据替换原则，判断S3选择的点r是否符合要求，若符合则转至S5；否则转至S3；S5.从Vs中删除r，从Es中删除与r相关联的边；S6.从Vs中删除独立点；S7.把新增点和边e加入子图Gs中。本发明方法得到的抽样子图与原图的特性相似度高。