Foffano Daniele, Rossi Luca, Torsello Andrea
Dipartimento di Scienze Ambientali, Informatica e Statistica, Università Ca' Foscari Venezia, Venezia, Italy.
Department of Computer Science and Engineering, Southern University of Science and Technology, Shenzhen, China.
Front Big Data. 2019 May 31;2:7. doi: 10.3389/fdata.2019.00007. eCollection 2019.
Complex networks gathered from our online interactions provide a rich source of information that can be used to try to model and predict our behavior. While this has very tangible benefits that we have all grown accustomed to, there is a concrete privacy risk in sharing potentially sensitive data about ourselves and the people we interact with, especially when this data is publicly available online and unprotected from malicious attacks. -anonymity is a technique aimed at reducing this risk by obfuscating the topological information of a graph that can be used to infer the nodes' identity. In this paper we propose a novel algorithm to enforce -anonymity based on a well-known result in extremal graph theory, the Szemerédi regularity lemma. Given a graph, we start by computing a regular partition of its nodes. The Szemerédi regularity lemma ensures that such a partition exists and that the edges between the sets of nodes behave almost randomly. With this partition, we anonymize the graph by randomizing the edges within each set, obtaining a graph that is structurally similar to the original one yet the nodes within each set are structurally indistinguishable. We test the proposed approach on real-world networks extracted from Facebook. Our experimental results show that the proposed approach is able to anonymize a graph while retaining most of its structural information.
从我们的在线互动中收集的复杂网络提供了丰富的信息源，可用于尝试对我们的行为进行建模和预测。虽然这带来了我们都已习以为常的非常切实的好处，但在分享有关我们自己以及我们与之互动的人的潜在敏感数据时，存在切实的隐私风险，尤其是当这些数据在网上公开可用且未受到恶意攻击的保护时。匿名是一种旨在通过模糊可用于推断节点身份的图的拓扑信息来降低这种风险的技术。在本文中，我们基于极值图论中的一个著名结果——塞梅雷迪正则性引理，提出了一种新的算法来强制实现匿名。给定一个图，我们首先计算其节点的正则划分。塞梅雷迪正则性引理确保这样的划分存在，并且节点集之间的边几乎随机地表现。通过这种划分，我们通过在每个集合内随机化边来对图进行匿名化，得到一个在结构上与原始图相似但每个集合内的节点在结构上无法区分的图。我们在从脸书提取的真实世界网络上测试了所提出的方法。我们的实验结果表明，所提出的方法能够在保留图的大部分结构信息的同时对其进行匿名化。
