1.一种面向社交网络数据的差分隐私处理发布方法,其特征在于以下步骤:
步骤1)获取某一待发布的原始社交网络图G,每条关系都转换为邻接矩阵中(0,1)的元素形式存储,将其映射在距形二维平面矩阵Ao区域内,对待发布的社交网络图初始的节点标签进行标记χ,用数组n[k]记录初始对应的标签;
步骤2)引入快速社区检测算法对网络图G进行密度聚集的标签识别,让连接相互紧密的节点自成为社区,社区之间的连接较为稀疏,不同标签顺序会使得网络图的邻接矩阵密度聚集情况不同,此过程分配的隐私预算为ε1,识别后图节点标签为χ′,再用数组N[k]记录对应处理后的图节点标签χ′;
步骤3)对标签好的网络邻接矩阵进行密度区域的探索与识别,设计差分隐私方法对数据独立的划分区域进行噪声扰动,此过程分配的隐私预算为ε2=ε-ε1,ε是总隐私预算,并采用标准二分树的结构BT对邻接矩阵进行密度存储;
步骤4)对BT树中每个结点(对应一个边加噪矩阵)进行加噪后的边最优分配,重建带噪的矩阵A′与初始待发布的社交网络图的邻接矩阵Ao要实现最小化差异;
步骤5)结果发布,将经过处理后带有差分隐私噪声的设计网络发布图G′进行发布。
2.根据权利要求1所述的方法,其特征在于,所述步骤2)中引入快速社区检测算法FN结合差分隐私对原始待发布的社交网络进行密度聚集的标签识别,所述的社区检测详细步骤包括:
2.1)计算网络图G=(V,E)对应的邻接矩阵以及该网络的模块度Q,初始化每个节点为单一社区标号1~n,n=|V|;
2.2)快速社区检测算法将选择两个社区成对合并为新的社区,且每次合并都必须使得Q值能得以最大增加,或最小减少,同时记录社区加入顺序,这一合并过程将寻求最大Q值的最优划分,且每次的合并完成后需更新被选择的两个社区行列的矩阵元素eij;
2.3)初始化社区聚集矩阵clusters[3,n],对于社区集合SC中任意不同社区SCi和SCj的组合,即SCi≠SCj时计算ΔQ=2(eij-aiaj);
2.4)如果 找出ΔQ变化最大的社区SCi和SCj中所有对应的
节点并将其节点序号成对写入社区合并过程矩阵Z[n-1,3];
2.5)社区合并后形成的新社区标号变化范围为[|V|+1,2|V|-1],重复步骤2.3)至clusters(社区标号)最终相同,即clusters矩阵所有节点对应的第三行相同,此时得到最终的社区合并过程矩阵Z[n-1,3];
2.6)对矩阵Z[n-1,3]进行前两列遍历(Z矩阵的前两列表征了社区检测过程中的社区标号合并的过程),发现社区检测聚集时合并的先后顺序,从第一行开始循环每一行的前两列,当社区标号Z[i,j]<=|V|时,即为初始时的社区节点标签,需重新排序并对标签重命名,用数组N[k]记录对应处理后的图节点标签χ′。
3.根据权利要求1所述的方法,其特征在于,所述步骤2)中模块度 即一个
社交网络被分解成m个社区,则对应一个m×m维的对称矩阵e,矩阵元素eij表示社区网络中社区i中的节点与社区j中的节点相连边在所有边中所占的比例,eii为社区i中节点内部所有连接边在所有边中所占的比例; 用来表示与社区i中的节点相连的边在所有边中所占的比例。
4.根据权利要求2所述的方法,其特征在于,所述步骤2.2)需迭代执行t=|V|-1次,每一次合并需对当前节点的社区归属计算ΔQ对应的函数q(ΔQ,SC)的变化,即引入指数差分隐私计算 的变化情况,使得Q值能得以最大增加,或最小减少。
5.根据权利要求2所述的方法,其特征在于,其中,步骤2.3)中Clusters为3×n矩阵,网络的社区划分:第1行是节点标号,第2行是社区标号的变换,第3行是社区标号,划分结束时第3行标号相同表示所有节点在同一社区,此时检测结束;在标签检测过程中,节点每一步迭代都会被安排至新的社区标号中,记录了节点归属社区的变换过程。
6.根据权利要求2所述的方法,其特征在于,步骤2.5)中的矩阵Z是一个(n-1)*3的矩阵,第i行表示第i次节点合并,第1列和第2列表示合并的社区标号,第3列是合并后的模块度;其中社区标号初始化为节点标签,从1到最大至n=|V|,当每一步的节点合并后形成的新社区标号范围为[|V|+1,2|V|-1],因为|V|个节点的合并需要|V|-1次。
7.根据权利要求1所述的方法,其特征在于,所述步骤3)中对标签好的网络邻接矩阵进行密度区域的探索与识别包括以下步骤:
3.1) 即二分树结构初始化,根据步骤2中Q值最大时确定的社区个数来计算BT的树高h;
3.2)当i<h时执行:其中i=0时,将上三角邻接矩阵A视为BT树的初始非叶节点进行3个区域划分;
3.3)对于每个非叶节点U∈lev(i,BT)执行:计算隐私预算 和 划分3个子区域否则执行结束;
3.4)对于每一步中形成的3个子区域集R执行:计算R中计数Laplace噪声值用结点V代表任一子区域并将其插入二分树BT;如果结点V满足终止条件,
区域密度大于等于给定的数值,则使结点V成为BT的叶区域;
3.5)i++后跳转至步骤3.2)重复执行直至结束;最终返回噪声社区二分树BT。
8.根据权利要求1所述的方法,其特征在于,所述步骤3)中隐私预算ε2有两部分组成ε2=εc+εp,εc用于对区域计数加噪,εp用于挑选社区划分点,
9.根据权利要求7所述的方法,其特征在于,步骤3.2)中第i次执行非叶区域,以U表示,该区域划分及其形成的二分树BT的联系用U∈lev(i,BT)表示; 表示应用隐私预算 对区域U进行区域划分形成3个子区域。
10.根据权利要求7所述的方法,其特征在于,步骤3.3)中划分区域R中的功用函数设计为 其中ζ表示为区域R中选择划分点p后的子区域集,一个划分点Δl Δr
对应形成左上R 区域,右下R 区域,中间矩形稀疏 区域,该函数找出的划分点将使得中间矩形区域密度den最小。
11.根据权利要求1所述的方法,其特征在于,所述步骤4)中对边加噪矩阵进行加噪后的边最优分配详细步骤包括:
4.1)自上而下遍历构建的噪声二分树BT,遍历到非叶结点区域为矩形稀疏区域 根据区域矩阵 中总数加噪值 及真实值c的大小情况,在原有c个1的位置的直接相邻区域进行概率设计分配;
4.2)若遍历到二分树的密集叶区域,二分树叶区域用上三角邻接矩阵 表示,因为分布密集所以随机安排 个1至叶区域上三角R′ij中的[m(m-1)]/2个位置处置1;
4.3)由各区域矩阵R′ij拼接之后形成完整的上三角邻接矩阵A′,并返回该A′。
12.根据权利要求9所述的方法,其特征在于,步骤4.2)中用上三角邻接矩阵 表示二分树叶节点区域,每一步的划分及处理都对应着当前待处理的上三角矩阵,矩阵中对应位置元素由区域上三角R′ij中的 个位置组成,m为该矩阵的行数即列数。