欢迎来到知嘟嘟! 联系电话:13095918853 卖家免费入驻,海量在线求购! 卖家免费入驻,海量在线求购!
知嘟嘟
我要发布
联系电话:13095918853
知嘟嘟经纪人
收藏
专利号: 2019102327595
申请人: 安徽师范大学
专利类型:发明专利
专利状态:已下证
专利领域: 电通信技术
更新日期:2023-08-08
缴费截止日期: 暂无
价格&联系人
年费信息
委托购买

摘要:

权利要求书:

1.基于匿名的网络最短路径隐私保护方法,其特征在于,包括以下步骤:

步骤1、将现实世界中的复杂网络建模为加权无向图G=(V,E)形式,采用邻接矩阵表示,并采用边权值矩阵W表示加权无向图G的边权值,找出边权值矩阵W中的最小值Wmin,并根据最小值Wmin的大小更新边权值矩阵;

步骤2、根据边权值创建虚拟边集和虚拟结点集,将虚拟边集和虚拟结点集加入到原有的加权无向图G中,建立距离矩阵D,表示任意两个结点之间的最短距离,并对距离矩阵D进行初始化;

步骤3、对于每一个结点,创建队列Q,对每个结点进行遍历,采用动态规划的思想,对每个结点和目标源点进行更新最短距离;

步骤4、计算加权无向图G中每个结点的覆盖计数,并根据覆盖计数的数值,对结点进行分类;

步骤5、若存在全覆盖结点,则直接增加干扰结点和干扰边;若不存在全覆盖结点,判断有无特殊情况,然后根据半覆盖结点增加干扰结点和干扰边。

2.根据权利要求1所述的基于匿名的网络最短路径隐私保护方法,其特征在于:所述步骤1中,根据边权值矩阵W中的最小值Wmin更新边权值矩阵W时,若Wmin≤0则,对边权值矩阵中的每一个元素根据公式Wij=Wij+abs(Wmin)+1更新,其中abs(Wmin)表示Wmin的绝对值。

3.根据权利要求1所述的基于匿名的网络最短路径隐私保护方法,其特征在于:所述步骤2中,虚拟边集和虚拟结点集是根据边权值矩阵W创建的,对于每一条边,创建Wij条边权值为1的虚拟边和Wij-1个虚拟结点,其中虚拟边和虚拟结点依次连接并且与结点i和结点j相连,每个虚拟结点的度为2,然后,删除边,并且将虚拟边和虚拟结点加入到边集E和结点集V中。

4.根据权利要求3所述的基于匿名的网络最短路径隐私保护方法,其特征在于:所述步骤2中,距离矩阵D记录结点集V中每一个结点到其他结点的最短距离,距离矩阵D中Dij表示结点i和结点j之间的最短距离,初始化距离矩阵D中每一个元素的值为∞。

5.根据权利要求1所述的基于匿名的网络最短路径隐私保护方法,其特征在于:所述步骤3中,对于结点集V中的每一个结点v需要进行以下操作:

1)选择一个结点vi,将Dii设为0,创建一个结点队列Q,将结点vi加入到队列Q;

2)采用公式Dij=min(Dik)+1计算队首结点的所有邻接结点与结点i的最短距离,其中结点j属于队首结点的所有邻接结点,结点k属于结点j的所有邻接结点;将队首结点的邻接结点中没有加入过队列Q的结点加入队列Q,并且将队列Q的队首结点出队;

3)重复操作2),直至队列Q空时为止。

6.根据权利要求5所述的基于匿名的网络最短路径隐私保护方法,其特征在于:所述步骤3对于结点集V中的每一个结点v,重复1)-3)操作更新距离矩阵D,删除虚拟边集和虚拟结点集。

7.根据权利要求1所述的基于匿名的网络最短路径隐私保护方法,其特征在于:所述步骤4中,定义需要保护的结点对(vs,vt)之间的最短路径序列为Pst,其中vs和vt分别表示需要保护的起始结点和最终结点,所有需要保护的结点对构成集合H。

8.根据权利要求7所述的基于匿名的网络最短路径隐私保护方法,其特征在于:所述步骤4中,对于图G中的任意一个结点vi,若需保护结点对集合H中有n对结点对的最短路径序列经过它,则称n为该结点的覆盖计数,记为ci=n,0≤ci≤|H|,其中|H|为结点对集合H中的结点对数,若ci=|H|,则该结点为全覆盖结点;若ci=0,则该结点为半覆盖结点;若0

9.根据权利要求8所述的基于匿名的网络最短路径隐私保护方法,其特征在于:所述步骤4中,最短路径序列不包含结点对的起始结点vs和最终结点vt。

10.根据权利要求1所述的基于匿名的网络最短路径隐私保护方法,其特征在于:所述步骤5中,若图G中存在全覆盖结点,则直接根据全覆盖结点增加干扰结点和干扰边,干扰结点与全覆盖结点存在相同的邻接结点,并且与各邻接结点的边权值相同;若图G中不存在全覆盖结点,则先判断有无需要保护的结点对的最短路径序列只包含起始结点和最终结点,若有,则将该最短路径中唯一的边删去,增加两个干扰结点和四条干扰边,边权值根据原有边权值进行随机值修改,然后选取覆盖计数值最大的半覆盖结点,增加干扰结点和干扰边,干扰结点与半覆盖结点存在相同的邻接结点,并且与各邻接结点的边权值相同,删除结点对集合H中所有最短路径序列含有该半覆盖结点的结点对,计算剩余结点对中覆盖计数最大的半覆盖结点,重复上述操作,直至结点对集合H变成空集为止。