| 主权项 |
一种优化的社交网络图数据发布隐私保护方法，其特征是包括如下步骤：(1)将社交网络的数据抽象为无向图G(V，E)，其中V是顶点的有限集合、表示社交网络中的个人或团体，E是V上的二元关系、表示社交网络中的关系；(2)计算无向图G(V，E)中每个顶点的度d<sub>i</sub>，其中度d<sub>i</sub>表示与第i个顶点相关的二元关系的个数，其中i＝1，2，……，n，其中n为顶点的个数；(3)对无向图G(V，E)中的所有度d<sub>i</sub>进行排序，获得度序列d<sub>G</sub>，其中d<sub>G</sub>＝(d<sub>1</sub>，d<sub>2</sub>，……，d<sub>n</sub>)，且d<sub>1</sub>≥d<sub>2</sub>≥……≥d<sub>n</sub>；(4)用户根据隐私数据的敏感程度自行设定所需达到匿名度k的值，并对度序列d<sub>G</sub>进行匿名度操作，构建出匿名度序列d<sub>G</sub>’；即(4.1)从度序列d<sub>G</sub>中的d<sub>1</sub>开始，计算度序列d<sub>G</sub>中两两相邻度的差值，即︱d<sub>j</sub>‑d<sub>j+1</sub>︱，并记录首次遇到的最大差值对应的j；(4.2)调整j的值，以确保每个分组至少有k个元素,即将j与k进行比较，若j≥K，则将第j个元素作为分组的结束点，若j＜K，则将第k个元素作为分组的结束点；(4.3)以第j+1位度作为新分组的起点；(4.4)重复步骤(4.1)‑(4.3)，即重复寻找新分组的起点和计算差值的过程，直至将度序列d<sub>G</sub>中的所有新分组的起点都找出，由此将度序列d<sub>G</sub>中的度d<sub>i</sub>划分为多组，此时带有分组信息的度序列d<sub>G</sub>即为构建出的匿名度序列d<sub>G</sub>’；(5)针对匿名度序列d<sub>G</sub>’的每组分组中的度d<sub>i</sub>’，计算其与同分组中第一个度值间的差值x<sub>i</sub>，其中x<sub>i</sub>代表这个顶点要达到匿名所需的边数，并把所有x<sub>i</sub>不为0的点放在集合V<sub>d</sub>中；(6)在集合V<sub>d</sub>中搜索添加匿名所需的边，其条件为在无向图G(V，E)中两个顶点之间不能够有边，每添加一条边，对应的两个顶点的匿名所需的边数x<sub>i</sub>都减少1，当某个顶点的x<sub>i</sub>为0时，表示此顶点满足匿名需求，将该顶点移出集合V<sub>d</sub>；(7)重复步骤(6)添加边的步骤；如果能够使集合V<sub>d</sub>为空，则认为该组匿名度序列d<sub>G</sub>’已经完成匿名无向图G’(V’，E’)的构建，此时输出匿名度序列d<sub>G</sub>’所对应的匿名无向图G’(V’，E’)；如果集合V<sub>d</sub>不为空，则需要对V<sub>d</sub>集合中剩余的未匿名顶点进行步骤(8)的添加新顶点的步骤；(8)计算剩余集合V<sub>d</sub>中所有顶点到达匿名度k所需的最大边数t，并添加t个新顶点，选择集合V<sub>d</sub>’中的第一个顶点，根据前面计算出的这个顶点匿名所需边数x<sub>i</sub>，建立这个点同x<sub>i</sub>个新增加点间的边，这个顶点匿名完成，将该顶点移出集合V<sub>d</sub>；(9)重复步骤(8)添加边的步骤，直至集合V<sub>d</sub>为空，完成构建匿名无向图G’(V’，E’)的工作；此时输出匿名度序列d<sub>G</sub>’所对应的匿名无向图G’(V’，E’)。 |
