The DOI matches its Crossref record; 25 of the 25 references it cites were found in a registry or an index.
Accurate Estimation of the Degree Distribution of Private Networks
Abstract
We describe an efficient algorithm for releasing a provably private estimate of the degree distribution of a network. The algorithm satisfies a rigorous property of differential privacy, and is also extremely efficient, running on networks of 100 million nodes in a few seconds. Theoretical analysis shows that the error scales linearly with the number of unique degrees, whereas the error of conventional techniques scales linearly with the number of nodes. We complement the theoretical analysis with a thorough empirical analysis on real and synthetic graphs, showing that the algorithm's variance and bias is low, that the error diminishes as the size of the input graph increases, and that common analyses like fitting a power-law can be carried out very accurately.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Power-Law Distributions in Empirical Data
Clauset, A., Shalizi, C. R., & Newman, M. E. J. (2009) · SIAM Review · doi:10.1137/070710111 · Cited by 8,019
Calibrating Noise to Sensitivity in Private Data Analysis
Dwork, C., McSherry, F., Nissim, K., & Smith, A. (2006) · Lecture Notes in Computer Science · doi:10.1007/11681878_14 · Cited by 7,272
Power-law distributions in empirical data
Clauset, A. J., Shalizi, C. R., & Newman, M. E. J. (2018) · Figshare · doi:10.1184/r1/6586835.v1 · Cited by 6,504
Random graphs with arbitrary degree distributions and their applications
Newman, M. E. J., Strogatz, S. H., & Watts, D. J. (2001) · Physical Review E · doi:10.1103/physreve.64.026118 · Cited by 3,648
Differential Privacy: A Survey of Results
Dwork, C. (2008) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-79228-4_1 · Cited by 3,542 · cited 12×
“Stack J(4) becomes {4, 5} after s̃[4] is considered since s̃[4] < M5.”
BackgroundMethodInfluentialMeasurement and analysis of online social networks
Mislove, A., Marcon, M., Gummadi, K. P., Druschel, P., & Bhattacharjee, B. (2007) · Proceedings of the 7th ACM SIGCOMM conference on Internet measurement · doi:10.1145/1298306.1298311 · Cited by 3,057
Graphs over time: densification laws, shrinking diameters and possible explanations
Leskovec, J., Kleinberg, J., & Faloutsos, C. (2005) · Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining · doi:10.1145/1081870.1081893 · Cited by 2,281
Empirical Analysis of an Evolving Social Network
Kossinets, G., & Watts, D. J. (2006) · Science · doi:10.1126/science.1116869 · Cited by 1,723
De-anonymizing Social Networks
Narayanan, A., & Shmatikov, V. (2009) · 2009 30th IEEE Symposium on Security and Privacy · doi:10.1109/sp.2009.22 · Cited by 1,301
Smooth sensitivity and sampling in private data analysis
Nissim, K., Raskhodnikova, S., & Smith, A. (2007) · Proceedings of the thirty-ninth annual ACM symposium on Theory of computing · doi:10.1145/1250790.1250803 · Cited by 974
Backstrom, L., Dwork, C., & Kleinberg, J. (2007) · Proceedings of the 16th international conference on World Wide Web · doi:10.1145/1242572.1242598 · Cited by 850
Towards identity anonymization on graphs
Liu, K., & Terzi, E. (2008) · Proceedings of the 2008 ACM SIGMOD international conference on Management of data · doi:10.1145/1376616.1376629 · Cited by 773
Preserving Privacy in Social Networks Against Neighborhood Attacks
Zhou, B., & Pei, J. (2008) · 2008 IEEE 24th International Conference on Data Engineering · doi:10.1109/icde.2008.4497459 · Cited by 719
Resisting structural re-identification in anonymized social networks
Hay, M., Miklau, G., Jensen, D., Towsley, D., & Weis, P. (2008) · Proceedings of the VLDB Endowment · doi:10.14778/1453856.1453873 · Cited by 549
Self-citationBoosting the accuracy of differentially private histograms through consistency
Hay, M., Rastogi, V., Miklau, G., & Suciu, D. (2010) · Proceedings of the VLDB Endowment · doi:10.14778/1920841.1920970 · Cited by 528
Self-citationTowards a Theory of Scale-Free Graphs: Definition, Properties, and Implications
Li, L., Alderson, D., Doyle, J. C., & Willinger, W. (2005) · Internet Mathematics · doi:10.1080/15427951.2005.10129111 · Cited by 519
k-automorphism: a general framework for privacy preserving network publication
Zou, L., Chen, L., & Özsu, M. T. (2009) · Proceedings of the VLDB Endowment · doi:10.14778/1687627.1687734 · Cited by 409
Composition attacks and auxiliary information in data privacy
Ganta, S. R., Kasiviswanathan, S. P., & Smith, A. (2008) · Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1401890.1401926 · Cited by 395
Social networks and infectious disease: The Colorado Springs study
Klovdahl, A. S., Potterat, J. J., Woodhouse, D. E., Muth, J. B., Muth, S. Q., & Darrow, W. W. (1994) · Social Science & Medicine · doi:10.1016/0277-9536(94)90302-6 · Cited by 387
Minimality Attack in Privacy Preserving Data Publishing
Wong, R. C.-W., Fu, A. W.-C., Wang, K., & Pei, J. (2006) · Cited by 281
Systematic topology analysis and generation using degree correlations
Mahadevan, P., Krioukov, D., Fall, K., & Vahdat, A. (2006) · Cited by 269
Class-based graph anonymization for social network data
Bhagat, S., Cormode, G., Krishnamurthy, B., & Srivastava, D. (2009) · Proceedings of the VLDB Endowment · doi:10.14778/1687627.1687714 · Cited by 225
Systematic topology analysis and generation using degree correlations
Mahadevan, P., Krioukov, D., Fall, K., & Vahdat, A. (2006) · ACM SIGCOMM Conference (SIGCOMM) · doi:10.1145/1159913.1159930 · Cited by 195
Rastogi, V., Hay, M., Miklau, G., & Suciu, D. M. (2009) · ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS) · doi:10.1145/1559795.1559812 · Cited by 137
Self-citationA Differentially Private Graph Estimator
Mir, D., & Wright, R. N. (2009) · IEEE ... International Conference on Data Mining workshops · doi:10.1109/icdmw.2009.96 · Cited by 55
Cited by
Kifer, D., & Machanavajjhala, A. (2011) · Proceedings of the 2011 ACM SIGMOD International Conference on Management of data · doi:10.1145/1989323.1989345 · Cited by 619
Resisting structural re-identification in anonymized social networks
Hay, M., Miklau, G., Jensen, D., Towsley, D., & Weis, P. (2008) · Proceedings of the VLDB Endowment · doi:10.14778/1453856.1453873 · Cited by 549
Self-citationBoosting the accuracy of differentially private histograms through consistency
Hay, M., Rastogi, V., Miklau, G., & Suciu, D. (2010) · Proceedings of the VLDB Endowment · doi:10.14778/1920841.1920970 · Cited by 528
Self-citationAnalyzing Graphs with Node Differential Privacy
Kasiviswanathan, S. P., Nissim, K., Raskhodnikova, S., & Smith, A. (2013) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-36594-2_26 · Cited by 294
Towards practical differential privacy for SQL queries
Johnson, N., Near, J. P., & Song, D. (2018) · Proceedings of the VLDB Endowment · doi:10.1145/3187009.3177733 · Cited by 257
Metadata
- Authors
- Hay, M., Li, C., Miklau, G., & Jensen, D.
- Venue
- 2009 Ninth IEEE International Conference on Data Mining
- Publisher
- IEEE
- Published
- 2009-12
- Pages
- 169-178
- ISSN
- 1550-4786 (ISSN-L)
- OpenAlex
- W2150611147
- Cited by
- 387
- References
- 25
- FWCI
- 9.40
- Type
- conference paper
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.