发明申请
- 专利标题: ALGORITHMS FOR IDENTITY ANONYMIZATION ON GRAPHS
- 专利标题(中): 身份识别遗传算法的算法
-
申请号: US12134279申请日: 2008-06-06
-
公开(公告)号: US20090303237A1公开(公告)日: 2009-12-10
- 发明人: Kun Liu , Evimaria Terzi
- 申请人: Kun Liu , Evimaria Terzi
- 申请人地址: US NY Armonk
- 专利权人: International Business Machines Corporation
- 当前专利权人: International Business Machines Corporation
- 当前专利权人地址: US NY Armonk
- 主分类号: G06T11/20
- IPC分类号: G06T11/20
摘要:
The proliferation of network data in various application domains has raised privacy concerns for the individuals involved. Recent studies show that simply removing the identities of the nodes before publishing the graph/social network data does not guarantee privacy. The structure of the graph itself, and in is basic form the degree of the nodes, can be revealing the identities of individuals. To address this issue, a specific graph-anonymization framework is proposed. A graph is called k-degree anonymous if for every node v, there exist at least k−1 other nodes in the graph with the same degree as v. This definition of anonymity prevents the re-identification of individuals by adversaries with a priori knowledge of the degree of certain nodes. Given a graph G, the proposed graph-anonymization problem asks for the k-degree anonymous graph that stems from G with the minimum number of graph-modification operations. Simple and efficient algorithms are devised for solving this problem, wherein these algorithms are based on principles related to the realizability of degree sequences.