De-anonymization of heterogeneous random graphs in quasilinear time

DOI10.1007/s00453-017-0395-0zbMath1414.05263OpenAlexW2769398099MaRDI QIDQ1755750

Karl Bringmann, Anton Krohmer, Tobias Friedrich

Publication date: 11 January 2019

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-017-0395-0

zbMATH Keywords

social networkslocality-sensitive hashingnetwork privacy

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Social networks; opinion dynamics (91D30) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85)

Uses Software

• PrivateLR

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Connected components in random graphs with given expected degree sequences
• A Random Graph Model for Power Law Graphs
• Random Graphs and Complex Networks
• Typical Distances in Ultrasmall Random Networks
• Approximate Graph Isomorphism
• De-anonymization of Heterogeneous Random Graphs in Quasilinear Time
• Emergence of Scaling in Random Networks
• A random graph model for massive graphs
• The Structure and Function of Complex Networks
• A Brief History of Generative Models for Power Law and Lognormal Distributions
• The Average Distance in a Random Graph with Given Expected Degrees
• Parameterized Clique on Scale-Free Networks
• Affiliation networks
• Every property of hyperfinite graphs is testable
• The average distances in random graphs with given expected degrees
• Differential Privacy
• Concentration of multivariate polynomials and its applications

This page was built for publication: De-anonymization of heterogeneous random graphs in quasilinear time