De-anonymization of Heterogeneous Random Graphs in Quasilinear Time
De-anonymization of Heterogeneous Random Graphs in Quasilinear Time
复制标题
拟线性时间内异构随机图的去匿名化
DOI：
10.1007/s00453-017-0395-0
复制
发表时间：
2018
期刊：
影响因子：
1.1
通讯作者：
Krohmer
中科院分区：
文献类型：
--
作者：
Bringmann;Friedrich;Krohmer
有数百个在线社交网络，总共拥有数十亿用户。许多这样的网络公开发布结构性信息，删除所有个人信息。然而，经验研究表明，这提供了一种虚假的隐私感--只要知道一些初始映射，就有可能识别出现在两个这样的匿名网络中的几乎所有用户。我们通过协调由顶点和边的独立子采样产生的两个版本的人工幂定律网络，从理论上分析了这个问题。我们提出了一种新的算法，该算法可以识别最多的顶点，并且不会出现高概率的错误识别。匹配的顶点数被证明是渐近最优的。对于n-顶点图，我们的算法使用种子节点(对于任意小的顶点)，并且运行在准线性时间内。这改进了以往需要种子节点且运行时间为数量级的理论结果。此外，还通过实验研究了该算法在不同网络环境下的适用性。
There are hundreds of online social networks with altogether billions of users. Many such networks publicly release structural information, with all personal information removed. Empirical studies have shown, however, that this provides a false sense of privacy—it is possible to identify almost all users that appear in two such anonymized network as long as a few initial mappings are known. We analyze this problem theoretically by reconciling two versions of an artificial power-law network arising from independent subsampling of vertices and edges. We present a new algorithm that identifies most vertices and makes no wrong identifications with high probability. The number of vertices matched is shown to be asymptotically optimal. For ann-vertex graph, our algorithm usesseed nodes (for an arbitrarily small) and runs in quasilinear time. This improves previous theoretical results which needseed nodes and have runtimes of order. Additionally, the applicability of our algorithm is studied experimentally on different networks.
无标度网络上的参数化团
DOI：
--
发表时间：
2012
期刊：
International Symposium on Algorithms and Computation
影响因子：
--
作者：
T. Friedrich;Anton Krohmer
通讯作者：
Anton Krohmer
我告诉你三遍的是真的：小世界中的引导渗透
DOI：
--
发表时间：
2012
期刊：
Workshop on Internet and Network Economics
影响因子：
--
作者：
H. Amini;N. Fountoulakis
通讯作者：
N. Fountoulakis