[0011] 针对现有的最短路径搜索方法和隐私保护中加权用户关系图的特点，本方法提供了一种针对网络图的最短路径搜索及匿名化隐私保护方法，快速求解源点到目标结点的最短路径，根据最短路径和需要保护的结点对，对所有结点分类，并依据不同情况，增加干扰结点和干扰边，从而达到对最短路径的匿名化保护。
[0012] 为了实现上述目的，本发明采用的技术方案为：基于匿名的网络最短路径隐私保护方法，包括以下步骤：
[0013] 步骤1、将现实世界中的复杂网络建模为加权无向图G＝(V,E)形式，采用邻接矩阵表示，并采用边权值矩阵W表示加权无向图G的边权值，找出边权值矩阵W中的最小值Wmin，并根据最小值Wmin的大小更新边权值矩阵；
[0014] 步骤2、根据边权值创建虚拟边集和虚拟结点集，将虚拟边集和虚拟结点集加入到原有的加权无向图G中，建立距离矩阵D，表示任意两个结点之间的最短距离，并对距离矩阵D进行初始化；
[0015] 步骤3、对于每一个结点，创建队列Q，对每个结点进行遍历，采用动态规划的思想，对每个结点和目标源点进行更新最短距离；
[0016] 步骤4、计算加权无向图G中每个结点的覆盖计数，并根据覆盖计数的数值，对结点进行分类；
[0017] 步骤5、若存在全覆盖结点，则直接增加干扰结点和干扰边；若不存在全覆盖结点，判断有无特殊情况，然后根据半覆盖结点增加干扰结点和干扰边。
[0018] 所述步骤1中，根据边权值矩阵W中的最小值Wmin更新边权值矩阵W时，若Wmin≤0则，对边权值矩阵中的每一个元素根据公式Wij＝Wij+abs(Wmin)+1更新，其中abs(Wmin)表示Wmin的绝对值。
[0019] 所述步骤2中，虚拟边集和虚拟结点集是根据边权值矩阵W创建的，对于每一条边，创建Wij条边权值为1的虚拟边和Wij-1个虚拟结点，其中虚拟边和虚拟结点依次连接并且与结点i和结点j相连，每个虚拟结点的度为2，然后，删除边，并且将虚拟边和虚拟结点加入到边集E和结点集V中。
[0020] 所述步骤2中，距离矩阵D记录结点集V中每一个结点到其他结点的最短距离，距离矩阵D中Dij表示结点i和结点j之间的最短距离，初始化距离矩阵D中每一个元素的值为∞。
[0021] 所述步骤3中，对于结点集V中的每一个结点v需要进行以下操作：
[0022] 1)选择一个结点vi，将Dii设为0，创建一个结点队列Q，将结点vi加入到队列Q；
[0023] 2)采用公式Dij＝min(Dik)+1计算队首结点的所有邻接结点与结点i的最短距离，其中结点j属于队首结点的所有邻接结点，结点k属于结点j的所有邻接结点；将队首结点的邻接结点中没有加入过队列Q的结点加入队列Q，并且将队列Q的队首结点出队；
[0024] 3)重复操作2)，直至队列Q空时为止。
[0025] 6、根据权利要求5所述的基于匿名的网络最短路径隐私保护方法，其特征在于：所述步骤3对于结点集V中的每一个结点v，重复1)-3)操作更新距离矩阵D，删除虚拟边集和虚拟结点集。
[0026] 所述步骤4中，定义需要保护的结点对(vs,vt)之间的最短路径序列为Pst，其中vs和vt分别表示需要保护的起始结点和最终结点，所有需要保护的结点对构成集合H。
[0027] 所述步骤4中，对于图G中的任意一个结点vi，若需保护结点对集合H中有n对结点对的最短路径序列经过它，则称n为该结点的覆盖计数，记为ci＝n,0≤ci≤|H|，其中|H|为结点对集合H中的结点对数，若ci＝|H|，则该结点为全覆盖结点；若ci＝0，则该结点为半覆盖结点；若0
[0028] 所述步骤4中，最短路径序列不包含结点对的起始结点vs和最终结点vt。
[0029] 所述步骤5中，若图G中存在全覆盖结点，则直接根据全覆盖结点增加干扰结点和干扰边，干扰结点与全覆盖结点存在相同的邻接结点，并且与各邻接结点的边权值相同；若图G中不存在全覆盖结点，则先判断有无需要保护的结点对的最短路径序列只包含起始结点和最终结点，若有，则将该最短路径中唯一的边删去，增加两个干扰结点和四条干扰边，边权值根据原有边权值进行随机值修改，然后选取覆盖计数值最大的半覆盖结点，增加干扰结点和干扰边，干扰结点与半覆盖结点存在相同的邻接结点，并且与各邻接结点的边权值相同，删除结点对集合H中所有最短路径序列含有该半覆盖结点的结点对，计算剩余结点对中覆盖计数最大的半覆盖结点，重复上述操作，直至结点对集合H变成空集为止。
[0030] 本发明的技术特点及效果：
[0031] (1)本发明根据原有的边集，找出距离矩阵中最小值，并根据其值得大小更新距离矩阵，引入虚拟边集和虚拟结点集的办法重新组织加权无向图G，使得算法能够根据图G快速搜索出最短距离并且对于负权图也能够很好适应；
[0032] (2)本发明在最短距离的搜索中使用动态规划思想，能够求出任意两个结点权值相加最小的路径，达到搜索到最短路径的效果；
[0033] (3)本发明引入覆盖结点计数的概念，对加权无向图G中所有结点进行归类，根据不同类别的结点，添加干扰结点和干扰边，使得需要保护的结点对之间存在多条最短路径，从而达到了对复杂网络隐私保护的目的。
