1.本发明涉及社会网络隐私保护领域，具体涉及一种社交网络中抵抗邻居攻击的用户身份隐私保护方法。
背景技术：2.社交网络中用户填写姓名、职业、电话号码、电子邮件、身份证号码等信息，保存在数据库中，然而，这些数据中除了个人的信息外，还体现了一定的社会关系。这些数据中包含了很多用户的隐私信息，因此，在社交网络数据发布前必须使用匿名技术保护用户隐私。
3.朴素用户隐私保护方法是移除用户的身份、属性等，但backstrom等指出这种朴素隐私保护技术在面对1*-邻居攻击时能够重新识别出用户的身份，不能很好地保护用户的隐私。图结构修改能够有效地保护用户的隐私，其通过在数据发布前的原始图中，添加或删除节点和边的方法改变图的结构，在修改后的图(称为匿名图)中达到用户身份隐私或属性隐私的目的。使用图修改技术对用户隐私保护，首先对节点划分，划分精确度直接影响图信息损失量可能导致图数据可用性降低，必须寻求更精确的划分标准。
技术实现要素：4.有鉴于此，本发明的目的在于提供一种社交网络中抵抗邻居攻击的用户身份隐私保护方法，通过对图结构的修改使得修改后的匿名图达到k-匿名，从而能够有效提保护用户的身份隐私。
5.为实现上述目的，本发明采用如下技术方案：
6.一种社交网络中抵抗邻居攻击的用户身份隐私保护方法，包括以下步骤：
7.步骤1)建立社交网络模型，将其表示为图g＝(v,e)，其中v是图的顶点集，表示社交网络中的用户；e是边集，表示社交网络中的用户之间的关系；
8.根据度量d(v),lc(v)将用户节点初划分成t个簇，其中d(v)表示用户节点v 的度，其含义为社交网络中与该用户具有联系的用户数量；lc(v)表示用户节点v在网络中的局部聚类系数，其含义为节点v的邻居之间联系的紧密程度，在划分结束后，将这些簇按照每个簇的最大节点度降序排列；
9.步骤2)预设一个用户隐私需求阈值k，若某个簇ci中用户数少于阈值k，则计算该簇的平均度与相邻的前后两簇c
i-1
,c
i+1
的平均度的差值，将该簇合并到差值小的簇中，重复该过程直到所有簇的中用户的数量都大于k；
10.步骤3)，在簇合并完成后，针对用户节点个数大于2k的簇，对其进行簇分裂操作使得每一个簇中用户的数量为[k,2k)的某个取值；具体为：
[0011]
s3-1，对于每个簇中的用户节点，按度数降序排序，构建用户节点的1*-邻居图；
[0012]
s3-2，构造用户节点的1*-邻居结构特征矩阵其中分别表示用户的节点v在社交网络中的度分布、内度分布、外度分布及
间隙度分布；
[0013]
s3-3，根据公式计算同一簇中任意两个节点之间的结构相似度，其中分别表示用户节点度分布、内度分布、外度分布及间隙度分布的不相关程度,k1、k2、k3、k4分别表示各个相似度所占比重，且满足k1+k2+k3+k4＝1；
[0014]
s3-4，利用k-means聚类算法将节点划分为t个簇；
[0015]
步骤4)，根据每个簇中用户节点的1*-邻居图计算用户每对节点间的相似度，并据此构造出一个带权二部图，在二部图上计算出图编辑距离，据此找到目标图编辑路径p；
[0016]
步骤5)，根据步骤4)找到的图编辑路径p，修改簇中节点的1*-邻居图，使得他们同构。
[0017]
2.根据权利要求1所述的一种抵抗1*-邻居攻击的用户身份隐私保护方法，其特征在于：所述1*-邻居图为原始图g的一个子图，定义为：
[0018]
g(v)＝(v(v),e(v),d(v))
[0019]
其中v(v)是包括用户节点v本身及其邻居节点的集合，e(v)是v(v)中节点的边即邻居之间的关系，d(v)是节点v的邻居在社交网络中邻居的数量构成的集合即v(v)中所有节点的度构成的集合。
[0020]
进一步的，所述步骤2)具体为：
[0021]
s2-1，对于节点数小于k的簇，将其记为其中上标1表示该簇是第一次划分后得到的结果，其簇内节点的平均度记为计算其前后相邻的两个簇的节点平均度，分别记为
[0022]
s2-2，若满足公式则将添加到中，否则将添加到中；
[0023]
s2-3，重复执行上述步骤，直到所有的簇中的节点数都超过k。
[0024]
进一步的，所述步骤4)具体为：
[0025]
s4-1，如果两个用户节点的l*-邻居图中邻居节点数不相等，则在用户邻居节点数少的图中添加用户节点使得两个图中节点数相等；
[0026]
s4-2，构造用户节点的匹配代价矩阵，并以用户节点的匹配代价作为边权值构造一个带权二部图；
[0027]
s4-3，利用二部图计算用户节点间的图编辑距离以得到匹配的节点以及图编辑路径。
[0028]
进一步的，所述步骤5)具体为：
[0029]
s5-1，构造图g的邻接矩阵记为a＝(a
ij
)n×n，其中当节点vi和vj间存在边时， a
ij
＝1，否则，a
ij
＝0；
[0030]
s5-2，计算a2及a3，及若则令若则令计算计算
[0031]
s5-3，对于社交网络中每个用户节点v，根据s4-3计算得到的匹配节点u，计算出节点v需要修改的度并记为点v需要修改的度并记为将社交网络中每个用户节点需修改的度按照降序排列，得到的度修改序列记为其中， dv表示用户节点v的邻居个数；
[0032]
s5-4，按照dm修改图结构。
[0033]
进一步的，所述s3-2具体为：
[0034]
s3-2-1，计算用户节点v的1*-邻居图g(v)中邻居节点的度分布邻居图g(v)中邻居节点的度分布邻居图g(v)中邻居节点的度分布是用户节点vi的度，表示vi在原始图g中邻居的个数，n(vi)为用户节点v所有邻居的集合；
[0035]
s3-2-2，计算用户节点v的1*-邻居图g(v)中邻居节点的内度分布邻居图g(v)中邻居节点的内度分布邻居图g(v)中邻居节点的内度分布是用户节点的内度，表示用户节点vi在1*-邻居图g(v)中邻居的个数，
[0036]
步骤3-2-3，计算用户节点v的1*-邻居图g(v)中邻居节点的出度分布邻居图g(v)中邻居节点的出度分布邻居图g(v)中邻居节点的出度分布是vi的出度，表示用户节点vi在1*-邻居图g(v)之外邻居的个数，
[0037]
步骤3-2-4，计算用户节点v的1*-邻居图g(v)中邻居节点的间隙度分布其中其中
[0038]
s3-2-5，社交网络中每个用户节点的特征矩阵记为5，社交网络中每个用户节点的特征矩阵记为
[0039]
为用户节点v在社交网络中邻居的个数。
[0040]
进一步的，所述s3-3具体为：
[0041]
s3-3-1，对于同一簇中的用户节点v及u，分别利用js散度计算他们的度分布、内度分布、出度分布、间隙度分布的不相关程度，分别记为：分布、出度分布、间隙度分布的不相关程度，分别记为：所述js散度定义为：
[0042][0043]
其中p＝{p1,p2,
…
,p
t
}，q＝{q1,q2,
…
,q
t
}分别为同一概率空间中的两个概率分布，
[0044]
s3-3-2，计算用户节点v及u的相似度向量2，计算用户节点v及u的相似度向量则用户节点u和v的相似度为k1+k2+k3+ k4＝1。
[0045]
进一步的，所述s4-2具体为：
[0046]
s4-2-1，对于同一簇中的任意一对顶点v和u，g(v)＝(v1,e1)和g(u)＝ (v2,e2)分别是它们的1*-邻居图，对于任意节点vi∈g(v)，计算其与g(u)中所有节点的匹配代价
[0047]
s4-2-2，构造所述代价矩阵
[0048]
s4-2-3，构造带权二部图v1、v2分别为顶点集且两者中节点数量相等，记为x，为边集，为边集，为边权值矩阵，w
ij
＝c
ij
。
[0049]
进一步的，所述s4-3具体为：
[0050]
s4-3-1，选择最大度的节点作为匹配种子节点对；
[0051]
s4-3-2，利用蒙特卡洛方法求二部图b的的最优匹配；
[0052]
s4-3-3，找到最优匹配所对应的图编辑路径p＝{v1→ut1
,v2→ut2
,
…
,v
x
→ꢀutx
}，其中，u
t1
、u
t2
、u
tm
分别为v1、v2、vm的匹配节点。
[0053]
进一步的，所述s5-4具体为：
[0054]
s5-4-1，若表示用户节点vi需增加条边，则分别在在节点的两跳和三跳邻居节点间寻找需要增加边的节点，并连边，若连边数量小于则添加假节点并与vi连边最终使得连边总数等于具体为:
[0055]
s5-4-1-1，在节点vi的两跳节点搜寻需要增加度的节点，预设为鼸i，若则在vi和vj之间增加一条边，
[0056]
s5-4-1-2，若不存在需要增加度的两跳节点，则在三跳节点中搜寻需要增加度的节点，预设为鼸i，若则在vi和vj之间增加一条边，
[0057]
s5-4-1-3，重复上述步骤，直到或者不存在需要增加度的两跳及三跳节点；
[0058]
s5-4-1-4，若终止步骤；
[0059]
s5-4-1-5，若且不存在需要增加度的两跳及三跳节点，则增加相应个数的假节点，并与vi相连；
[0060]
s5-4-2，若表示用户节点vi需删除条边，在其邻居中寻找同样需要删除边的邻居，将它们之间的连边删除，当删除边数等于时停止，若删除边数不足则将节
点相邻边按照边介数中心性从低到高删除，直到删除总边数等于具体为：
[0061]
s5-4-2-1，在节点vi的邻居中依次寻找需要减少度数的节点，并把它们加入到一个候选集合cs中，并按照用户节点的度降序排列；
[0062]
s5-4-2-2，依次从删除cs中节点与vi之间的连边；
[0063]
s5-4-2-3，若终止步骤；
[0064]
s5-4-2-4，若在vi的剩下的相邻边中依次按照边介数中心性从小到大删除相应的边，直到所述边介数中心性为社交网络中所有用户之间的最短路径经过该边的路径数与网络中所有最节点之间短路径数量之比。
[0065]
本发明与现有技术相比具有以下有益效果：
[0066]
本发明在社会网络的图数据遭受1*-邻居攻击时，采用图修改技术实现了用户隐私身份隐私信息的保护；根据图编辑距离对同一簇中的1*-邻居图进行修改，使它们达到概率不可区分；在实现社交网络中用户身份隐私保护的同时，提高图数据的可用性。本发明所提供的一种社会网络中抵抗1*-邻居攻击的用户身份隐私保护方法具有较好的应用和推广作用。
附图说明
[0067]
图1是本发明方法流程图；
[0068]
图2是本发明一实施例中原始karate图及图中标号为1的节点的1*-邻居图示意图；
[0069]
图3是本发明一实施例中二部图示意图。
具体实施方式
[0070]
下面结合附图及实施例对本发明做进一步说明。
[0071]
请参照图1，本发明提供一种社交网络中抵抗1*-邻居攻击的用户身份隐私保护方法，包括以下步骤：
[0072]
步骤1)，对于给定图g＝(v,e),根据度量：d(v)，lc(v)将节点划分成若干个簇，其中d(v),lc(v)分别表示节点v的度及其的局部聚类系数。在划分结束后，将这些簇按照每个簇的最大节点度降序排列；
[0073]
步骤2)，在节点粗划分后，某些簇中节点数少于一个给定的隐私需求k，根据簇的平均度与相邻两簇的平均度的差值，将该簇合并到差值小的簇中，以确保所有组的大小都大于k；
[0074]
步骤2)具体方法为：
[0075]
s2-1，对于节点数小于k的簇，我们将其记为其中上标1表示该簇是第一次划分后得到的结果，其簇内节点的平均度记为计算其前后相邻的两个簇的节点平均度，分别记为
[0076]
s2-2，若满足公式则将添
加到中，否则将添加到中；
[0077]
s2-3，重复执行上述步骤，直到所有的簇中的节点数都超过k。
[0078]
步骤3)，在簇合并完成后，某些簇中节点个数大于2k个，需对其进行簇分裂操作使得每一个簇的大小为[k,2k)；
[0079]
步骤3)具体为：
[0080]
s3-1，对于每个簇中的用户节点，按度数降序排序，构建用户节点的1*-邻居图；
[0081]
s3-2，构造用户节点的1*-邻居结构特征矩阵其中分别表示用户的节点v在社交网络中的度分布、内度分布、外度分布及间隙度分布；s3-2-1，计算用户节点v的1*-邻居图g(v)中邻居节点的度分布邻居图g(v)中邻居节点的度分布是用户节点vi的度，表示vi在原始图g中邻居的个数，n(vi)为用户节点v所有邻居的集合；
[0082]
s3-2-2，计算用户节点v的1*-邻居图g(v)中邻居节点的内度分布邻居图g(v)中邻居节点的内度分布邻居图g(v)中邻居节点的内度分布是用户节点的内度，表示用户节点vi在1*-邻居图g(v)中邻居的个数，
[0083]
步骤3-2-3，计算用户节点v的1*-邻居图g(v)中邻居节点的出度分布邻居图g(v)中邻居节点的出度分布邻居图g(v)中邻居节点的出度分布是vi的出度，表示用户节点vi在1*-邻居图g(v)之外邻居的个数，
[0084]
步骤3-2-4，计算用户节点v的1*-邻居图g(v)中邻居节点的间隙度分布
[0085]
s3-2-5，社交网络中每个用户节点的特征矩阵记为5，社交网络中每个用户节点的特征矩阵记为
[0086]
为用户节点v在社交网络中邻居的个数。
[0087]
s3-3，根据公式计算同一簇中任意两个节点之间的结构相似度，其中分别表示用户节点度分布、内度分布、外度分布及间隙度分布的不相关程度,k1、k2、k3、k4分别表示各个相似度所占比重，且满足k1+k2+k3+k4＝1；
[0088]
s3-3-1，对于同一簇中的用户节点v及u，分别利用js散度计算他们的度分布、内度分布、出度分布、间隙度分布的不相关程度，分别记为：分布、出度分布、间隙度分布的不相关程度，分别记为：所述js散度定
义为：其中p＝ {p1,p2,
…
,p
t
}，q＝{q1,q2,
…
,q
t
}分别为同一概率空间中的两个概率分布，为同一概率空间中的两个概率分布，
[0089]
s3-3-2，计算用户节点v及u的相似度向量2，计算用户节点v及u的相似度向量则用户节点u和v的相似度为k1+k2+k3+ k4＝1。
[0090]
s3-4，利用k-means聚类算法将节点划分为t个簇。
[0091]
步骤4)，根据每个簇中节点的1*-邻居图计算节点间的相似度，构造出一个带权二部图，并在二部图上计算出图编辑距离，并找到图编辑路径p；
[0092]
步骤4具体方法为：
[0093]
s4-1，如果两个用户节点的l*-邻居图中邻居节点数不相等，则在用户邻居节点数少的图中添加用户节点使得两个图中节点数相等；
[0094]
s4-2，构造节点的匹配代价矩阵，并以节点的匹配代价作为边权值构造一个带权二部图；
[0095]
s4-2-1，对于同一簇中的任意一对顶点v和u，g(v)＝(v1,e1)和g(u)＝ (v2,e2)分别是它们的1*-邻居图，对于任意节点vi∈g(v)，计算其与g(u)中所有节点的匹配代价
[0096]
s4-2-2，构造所述代价矩阵
[0097]
s4-2-3，构造带权二部图v1、v2分别为顶点集且两者中节点数量相等，记为x，为边集，为边集，为边权值矩阵，w
ij
＝c
ij
。
[0098]
s4-3，利用二部图计算节点的图编辑距离并得到匹配的节点和图编辑路径。
[0099]
s4-3-1，选择最大度的节点作为匹配种子节点对；
[0100]
s4-3-2，利用蒙特卡洛方法求二部图b的的最优匹配；
[0101]
s4-3-3，找到最优匹配所对应的图编辑路径p＝{v1→ut1
,v2→ut2
,
…
,v
x
→
[0102]utx
}，其中，u
t1
、u
t2
、u
tm
分别为v1、v2、vm的匹配节点。
[0103]
步骤5)，根据步骤4)找到的图编辑路径p，修改簇中节点的1*-邻居图，使得他们同构。
[0104]
步骤5)方法为：
[0105]
s5-1，构造图g的邻接矩阵记为a＝(a
ij
)n×n，其中当节点vi和vj间存在边时， a
ij
＝1，否则，a
ij
＝0；
[0106]
s5-2，计算a2及a3，及若则令若则令计算计算
[0107]
s5-3，对于社交网络中每个用户节点v，根据s4-3计算得到的匹配节点u，计算出节点v需要修改的度并记为点v需要修改的度并记为将社交网络中每个用户节点需修改的度按照降序排列，得到的度修改序列记为其中， dv表示用户节点v的邻居个数；
[0108]
s5-4，按照dm修改图结构。
[0109]
s5-4-1，若表示用户节点vi需增加条边，则分别在在节点的两跳和三跳邻居节点间寻找需要增加边的节点，并连边，若连边数量小于则添加假节点并与vi连边最终使得连边总数等于
[0110]
s5-4-1-1，在节点vi的两跳节点搜寻需要增加度的节点，预设为鼸i，若则在vi和vj之间增加一条边，
[0111]
s5-4-1-2，若不存在需要增加度的两跳节点，则在三跳节点中搜寻需要增加度的节点，预设为鼸i，若则在vi和vj之间增加一条边，
[0112]
s5-4-1-3，重复上述步骤，直到或者不存在需要增加度的两跳及三跳节点；
[0113]
s5-4-1-4，若终止步骤；
[0114]
s5-4-1-5，若且不存在需要增加度的两跳及三跳节点，则增加相应个数的假节点，并与vi相连。
[0115]
s5-4-2，若表示用户节点vi需删除条边，在其邻居中寻找同样需要删除边的邻居，将它们之间的连边删除，当删除边数等于时停止，若删除边数不足则将节点相邻边按照边介数中心性从低到高删除，直到删除总边数等于
[0116]
s5-4-2-1，在节点vi的邻居中依次寻找需要减少度数的节点，并把它们加入到一个候选集合cs中，并按照用户节点的度降序排列；
[0117]
s5-4-2-2，依次从删除cs中节点与vi之间的连边；
[0118]
s5-4-2-3，若终止步骤；
[0119]
s5-4-2-4，若在vi的剩下的相邻边中依次按照边介数中心性从小到大删除相应的边，直到所述边介数中心性为社交网络中所有用户之间的最短路径经过该边的路径数与网络中所有最节点之间短路径数量之比。
[0120]
以上所述仅为本发明的较佳实施例，凡依本发明申请专利范围所做的均等变化与修饰，皆应属本发明的涵盖范围。
技术特征：1.一种社交网络中抵抗邻居攻击的用户身份隐私保护方法，其特征在于，包括以下步骤：步骤1)建立社交网络模型，将其表示为图g＝(v,e)，其中v是图的顶点集，表示社交网络中的用户；e是边集，表示社交网络中的用户之间的关系；根据度量d(v),lc(v)将用户节点初划分成t个簇，其中d(v)表示用户节点v的度，其含义为社交网络中与该用户具有联系的用户数量；lc(v)表示用户节点v在网络中的局部聚类系数，其含义为节点v的邻居之间联系的紧密程度，在划分结束后，将这些簇按照每个簇的最大节点度降序排列；步骤2)预设一个用户隐私需求阈值k，若某个簇c
i
中用户数少于阈值k，则计算该簇的平均度与相邻的前后两簇c
i-1
,c
i+1
的平均度的差值，将该簇合并到差值小的簇中，重复该过程直到所有簇的中用户的数量都大于k；步骤3)，在簇合并完成后，针对用户节点个数大于2k的簇，对其进行簇分裂操作使得每一个簇中用户的数量为[k,2k)的某个取值；具体为：s3-1，对于每个簇中的用户节点，按度数降序排序，构建用户节点的1*-邻居图；s3-2，构造用户节点的1*-邻居结构特征矩阵其中分别表示用户的节点v在社交网络中的度分布、内度分布、外度分布及间隙度分布；s3-3，根据公式计算同一簇中任意两个节点之间的结构相似度，其中分别表示用户节点度分布、内度分布、外度分布及间隙度分布的不相关程度,k1、k2、k3、k4分别表示各个相似度所占比重，且满足k1+k2+k3+k4＝1；s3-4，利用k-means聚类算法将节点划分为t个簇；步骤4)，根据每个簇中用户节点的1*-邻居图计算用户每对节点间的相似度，并据此构造出一个带权二部图，在二部图上计算出图编辑距离，据此找到目标图编辑路径p；步骤5)，根据步骤4)找到的图编辑路径p，修改簇中节点的1*-邻居图，使得他们同构。2.根据权利要求1所述的一种抵抗邻居攻击的用户身份隐私保护方法，其特征在于：所述1*-邻居图为原始图g的一个子图，定义为：g(v)＝(v(v),e(v),d(v))其中v(v)是包括用户节点v本身及其邻居节点的集合，e(v)是v(v)中节点的边即邻居之间的关系，d(v)是节点v的邻居在社交网络中邻居的数量构成的集合即v(v)中所有节点的度构成的集合。3.根据权利要求1所述的一种抵抗邻居攻击的用户身份隐私保护方法，所述步骤2)具体为：s2-1，对于节点数小于k的簇，将其记为其中上标1表示该簇是第一次划分后得到的结果，其簇内节点的平均度记为计算其前后相邻的两个簇的节点平均度，分别记为
s2-2，若满足公式则将添加到中，否则将添加到中；s2-3，重复执行上述步骤，直到所有的簇中的节点数都超过k。4.根据权利要求1所述的一种抵抗邻居攻击的用户身份隐私保护方法，其特征在于：所述步骤4)具体为：s4-1，如果两个用户节点的l*-邻居图中邻居节点数不相等，则在用户邻居节点数少的图中添加用户节点使得两个图中节点数相等；s4-2，构造用户节点的匹配代价矩阵，并以用户节点的匹配代价作为边权值构造一个带权二部图；s4-3，利用二部图计算用户节点间的图编辑距离以得到匹配的节点以及图编辑路径。5.根据权利要求1所述的一种抵抗邻居攻击的用户身份隐私保护方法，其特征在于：所述步骤5)具体为：s5-1，构造图g的邻接矩阵记为a＝(a
ij
)
n
×
n
，其中当节点v
i
和v
j
间存在边时，a
ij
＝1，否则，a
ij
＝0；s5-2，计算a2及a3，及若则令若则令计算计算s5-3，对于社交网络中每个用户节点v，根据s4-3计算得到的匹配节点u，计算出节点v需要修改的度并记为需要修改的度并记为将社交网络中每个用户节点需修改的度按照降序排列，得到的度修改序列记为其中，d
v
表示用户节点v的邻居个数；s5-4，按照d
m
修改图结构。6.根据权利要求1所述的一种抵抗邻居攻击的用户身份隐私保护方法，其特征在于：所述s3-2具体为：s3-2-1，计算用户节点v的1*-邻居图g(v)中邻居节点的度分布邻居图g(v)中邻居节点的度分布邻居图g(v)中邻居节点的度分布邻居图g(v)中邻居节点的度分布是用户节点v
i
的度，表示v
i
在原始图g中邻居的个数，n(v
i
)为用户节点v所有邻居的集合；s3-2-2，计算用户节点v的1*-邻居图g(v)中邻居节点的内度分布邻居图g(v)中邻居节点的内度分布邻居图g(v)中邻居节点的内度分布是用户节点的内度，表示用户节点v
i
在1*-邻居图g(v)中邻居的个数，步骤3-2-3，计算用户节点v的1*-邻居图g(v)中邻居节点的出度分布邻居图g(v)中邻居节点的出度分布邻居图g(v)中邻居节点的出度分布是v
i
的出度，表示用户节点v
i
在1*-邻居图g(v)之外邻居的个数，步骤3-2-4，计算用户节点v的1*-邻居图g(v)中邻居节点的间隙度分布其中
s3-2-5，社交网络中每个用户节点的特征矩阵记为5，社交网络中每个用户节点的特征矩阵记为n
v
为用户节点v在社交网络中邻居的个数。7.根据权利要求1所述的一种抵抗邻居攻击的用户身份隐私保护方法，其特征在于：所述s3-3具体为：s3-3-1，对于同一簇中的用户节点v及u，分别利用js散度计算他们的度分布、内度分布、出度分布、间隙度分布的不相关程度，分别记为：布、出度分布、间隙度分布的不相关程度，分别记为：所述js散度定义为：其中p＝{p1,p2,
…
,p
t
}，q＝{q1,q2,
…
,q
t
}分别为同一概率空间中的两个概率分布，s3-3-2，计算用户节点v及u的相似度向量2，计算用户节点v及u的相似度向量则用户节点u和v的相似度为k1+k2+k3+k4＝1。8.根据权利要求4所述的一种抵抗邻居攻击的用户身份隐私保护方法，其特征在于：所述s4-2具体为：s4-2-1，对于同一簇中的任意一对顶点v和u，g(v)＝(v1,e1)和g(u)＝(v2,e2)分别是它们的1*-邻居图，对于任意节点v
i
∈g(v)，计算其与g(u)中所有节点的匹配代价s4-2-2，构造所述代价矩阵s4-2-3，构造带权二部图v1、v2分别为顶点集且两者中节点数量相等，记为x，为边集，w＝(w
ij
)
m
×
m
为边权值矩阵，w
ij
＝c
ij
。9.根据权利要求4所述的一种抵抗邻居攻击的用户身份隐私保护方法，其特征在于：所述s4-3具体为：s4-3-1，选择最大度的节点作为匹配种子节点对；s4-3-2，利用蒙特卡洛方法求二部图b的的最优匹配；s4-3-3，找到最优匹配所对应的图编辑路径p＝{v1→
u
t1
,v2→
u
t2
,
…
,v
x
→
u
tx
}，其中，
u
t1
、u
t2
、u
tm
分别为v1、v2、v
m
的匹配节点。10.根据权利要求5所述的一种抵抗邻居攻击的用户身份隐私保护方法，其特征在于：所述s5-4具体为：s5-4-1，若表示用户节点v
i
需增加条边，则分别在在节点的两跳和三跳邻居节点间寻找需要增加边的节点，并连边，若连边数量小于则添加假节点并与v
i
连边最终使得连边总数等于具体为:s5-4-1-1，在节点v
i
的两跳节点搜寻需要增加度的节点，预设为u
i
，若则在v
i
和v
j
之间增加一条边，s5-4-1-2，若不存在需要增加度的两跳节点，则在三跳节点中搜寻需要增加度的节点，预设为u
i
，若则在v
i
和v
j
之间增加一条边，s5-4-1-3，重复上述步骤，直到或者不存在需要增加度的两跳及三跳节点；s5-4-1-4，若终止步骤；s5-4-1-5，若且不存在需要增加度的两跳及三跳节点，则增加相应个数的假节点，并与v
i
相连；s5-4-2，若表示用户节点v
i
需删除条边，在其邻居中寻找同样需要删除边的邻居，将它们之间的连边删除，当删除边数等于时停止，若删除边数不足则将节点相邻边按照边介数中心性从低到高删除，直到删除总边数等于具体为：s5-4-2-1，在节点v
i
的邻居中依次寻找需要减少度数的节点，并把它们加入到一个候选集合cs中，并按照用户节点的度降序排列；s5-4-2-2，依次从删除cs中节点与v
i
之间的连边；s5-4-2-3，若终止步骤；s5-4-2-4，若在v
i
的剩下的相邻边中依次按照边介数中心性从小到大删除相应的边，直到所述边介数中心性为社交网络中所有用户之间的最短路径经过该边的路径数与网络中所有最节点之间短路径数量之比。
技术总结本发明涉及一种社交网络中抵抗邻居攻击的用户身份隐私保护方法，在社会网络的图数据遭受1*-邻居攻击时，采用图修改技术实现了用户隐私身份隐私信息的保护；根据图编辑距离对同一簇中的1*-邻居图进行修改，使它们达到概率不可区分；在实现社交网络中用户身份隐私保护的同时，提高图数据的可用性。提高图数据的可用性。提高图数据的可用性。
技术研发人员：许力 章红艳 许佳钰 李啸林 周赵斌
受保护的技术使用者：福建师范大学
技术研发日：2022.07.22
技术公布日：2022/11/1
