pith. sign in

arxiv: 2409.16163 · v3 · submitted 2024-09-24 · 💻 cs.SI

The anonymization problem in social networks

Rachel G. de Jong , Mark P. J. van der Loo , Frank W. Takes This is my paper

Pith reviewed 2026-05-23 20:52 UTC · model grok-4.3

classification 💻 cs.SI
keywords social network anonymizationk-anonymitygraph modificationedge deletionprivacy preservationheuristic algorithmsnetwork structuredata utility
0
0 comments X

The pith

A method that deletes edges around structurally unique nodes retains 14 times more edges while producing far more k-anonymous nodes than baselines.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper defines three variants of the network anonymization problem that aim to maximize the count of k-anonymous nodes by altering the graph. It introduces four heuristics inside a reusable framework and tests them on synthetic models plus 19 real datasets. Experiments establish that random edge deletion works better than rewiring or addition, that the choice of anonymity measure changes both starting anonymity and the effort required to improve it, and that prioritizing deletions around unique nodes beats purely structural heuristics. The best algorithm keeps substantially more edges and anonymous nodes while improving the anonymity-utility balance.

Core claim

An approach which preferentially deletes edges affecting structurally unique nodes consistently outperforms heuristics based solely on network structure. Overall, our best performing algorithm retains on average 14 times more edges in full anonymization. Moreover, it yields 4.8 times more anonymous nodes than the baseline in the budgeted variant. On top of that, the best performing algorithm achieves a better trade-off between anonymity and data utility.

What carries the argument

The four new heuristic algorithms, especially the one that preferentially deletes edges incident to structurally unique nodes, implemented inside the ANO-NET framework for the full, partial, and budgeted variants of maximizing k-anonymous nodes.

If this is right

  • Random edge deletion outperforms edge rewiring and edge addition as an alteration method.
  • The anonymity measure chosen for the k-anonymity definition strongly affects both the initial level of anonymity and how difficult further anonymization becomes.
  • The best heuristic achieves a better anonymity-utility trade-off than the literature baseline.
  • The ANO-NET framework supplies a reusable implementation for testing new algorithms across the three problem variants.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Measure selection must be driven by the specific background knowledge an attacker is assumed to possess rather than by convenience.
  • The performance gap suggests that future algorithms should explicitly track node uniqueness scores instead of relying only on global statistics such as degree or betweenness.
  • The budgeted variant results indicate that limited modification budgets can still produce large anonymity gains when deletions are concentrated on the right edges.

Load-bearing premise

The three graph models and 19 real-world datasets used in experiments are representative of the structural properties and attacker capabilities encountered in actual social networks where anonymization would be applied.

What would settle it

Running the same four algorithms plus the edge-sampling baseline on a fresh collection of large social-network graphs and finding that the preferential-deletion heuristic no longer retains at least twice as many edges or produces at least twice as many anonymous nodes as the next-best method.

read the original abstract

This paper introduces a unified computational framework for the anonymization problem in social networks, where the objective is to maximize node anonymity through graph alterations. We define three variants of the underlying optimization problem: full, partial and budgeted anonymization. In each variant, the objective is to maximize the number of $k$-anonymous nodes, i.e., nodes for which at least $k-1$ other nodes are equivalent under a particular anonymity measure. We propose four new heuristic network anonymization algorithms and implement these in ANO-NET, a reusable computational framework. Experiments on three common graph models and 19 real-world network datasets yield three empirical findings. First, regarding the method of alteration, experiments on graph models show that random edge deletion is more effective than edge rewiring and addition. Second, we show that the choice of anonymity measure strongly affects both initial network anonymity and the difficulty of anonymization. This highlights the importance of careful measure selection, matching a realistic attacker scenario. Third, comparing the four proposed algorithms and an edge sampling baseline from the literature, we find that an approach which preferentially deletes edges affecting structurally unique nodes, consistently outperforms heuristics based solely on network structure. Overall, our best performing algorithm retains on average 14 times more edges in full anonymization. Moreover, it yields 4.8 times more anonymous nodes than the baseline in the budgeted variant. On top of that, the best performing algorithm achieves a better trade-off between anonymity and data utility. This work provides a foundation for the future development of effective network anonymization algorithms.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

3 major / 1 minor

Summary. The paper introduces a unified computational framework for the anonymization problem in social networks, defining three optimization variants (full, partial, and budgeted) whose goal is to maximize the number of k-anonymous nodes under chosen anonymity measures. It proposes four new heuristic algorithms, implements them in the reusable ANO-NET framework, and reports experiments on three graph models plus 19 real-world datasets. The central empirical claims are that random edge deletion outperforms rewiring and addition, that anonymity-measure choice strongly affects difficulty, and that a preferential-deletion heuristic targeting structurally unique nodes outperforms a literature edge-sampling baseline, retaining on average 14 times more edges in the full variant and producing 4.8 times more anonymous nodes in the budgeted variant while improving the anonymity-utility trade-off.

Significance. If the empirical comparisons are shown to be robust, the work supplies a concrete foundation for network anonymization research by quantifying the advantage of targeted over structure-only heuristics and by underscoring the necessity of aligning anonymity measures with realistic attacker models. The release of the ANO-NET framework as a reusable computational platform is a constructive contribution that could facilitate future reproducibility and extension.

major comments (3)
  1. [experimental setup] Experimental setup section: the claim that the three graph models and 19 real-world datasets are representative of structural properties and attacker capabilities encountered in actual social networks is stated without supporting validation or sensitivity analysis for features such as clustering coefficients, community structure, degree assortativity, or temporal dynamics that real de-anonymization attacks exploit. This assumption is load-bearing for the generalizability of the reported 14× edge-retention and 4.8× node-anonymity multipliers.
  2. [results] Results section: no statistical significance tests (e.g., paired t-tests or Wilcoxon tests with correction) are reported for the performance differences between the four proposed algorithms and the edge-sampling baseline, despite the strong claims of consistent outperformance across all datasets and variants.
  3. [methods] Methods section: the exact mathematical definitions of the anonymity measures, the precise construction of equivalence classes, and the algorithmic implementation of k-anonymity counting are not supplied, preventing independent verification of how the reported anonymity gains are computed.
minor comments (1)
  1. [abstract] The abstract refers to 'a literature baseline' without citing the specific prior work or describing its implementation details in the experimental comparison.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the detailed and constructive review. Below we respond point-by-point to the major comments, indicating planned revisions where appropriate.

read point-by-point responses

  1. Referee: Experimental setup section: the claim that the three graph models and 19 real-world datasets are representative of structural properties and attacker capabilities encountered in actual social networks is stated without supporting validation or sensitivity analysis for features such as clustering coefficients, community structure, degree assortativity, or temporal dynamics that real de-anonymization attacks exploit. This assumption is load-bearing for the generalizability of the reported 14× edge-retention and 4.8× node-anonymity multipliers.

    Authors: We agree that explicit validation would strengthen the generalizability argument. The 19 datasets are standard benchmarks spanning multiple domains and scales, and the three generative models are chosen to isolate structural effects. However, we did not report sensitivity analyses on the listed features. In revision we will add a dedicated subsection (or table) reporting clustering coefficients, degree assortativity, and modularity for every dataset, together with a brief discussion of how these properties relate to known de-anonymization attacks. We will also note the static nature of the framework as a limitation regarding temporal dynamics. revision: yes

  2. Referee: Results section: no statistical significance tests (e.g., paired t-tests or Wilcoxon tests with correction) are reported for the performance differences between the four proposed algorithms and the edge-sampling baseline, despite the strong claims of consistent outperformance across all datasets and variants.

    Authors: We accept the criticism. The manuscript relies on average multipliers without formal testing. In the revised results section we will report Wilcoxon signed-rank tests (with Bonferroni correction) comparing the best heuristic against the baseline on every metric and variant, across the 19 datasets. This will provide quantitative support for the consistency claims. revision: yes

  3. Referee: Methods section: the exact mathematical definitions of the anonymity measures, the precise construction of equivalence classes, and the algorithmic implementation of k-anonymity counting are not supplied, preventing independent verification of how the reported anonymity gains are computed.

    Authors: Section 3 introduces the measures and the k-anonymity objective, yet the referee is correct that the precise equivalence-class construction and counting procedure lack the formality needed for independent re-implementation. We will expand the Methods section with formal definitions of each anonymity measure, the exact partitioning into equivalence classes, and pseudocode for the k-anonymity counting routine used to obtain the reported numbers. revision: yes

Circularity Check

0 steps flagged

No circularity; empirical performance claims are independent of inputs

full rationale

The paper advances an empirical framework for network anonymization, defining optimization variants and proposing four heuristics evaluated via experiments on three graph models plus 19 datasets. Performance multipliers (14x edge retention, 4.8x anonymous nodes) are reported as direct outcomes of these comparisons against a literature baseline. No derivation chain, fitted parameters renamed as predictions, or self-citation load-bearing steps exist; the results do not reduce to the experimental corpus by construction. The stated importance of matching measures to attacker scenarios is an explicit caveat, not a circular premise.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The framework rests on standard definitions of k-anonymity and graph editing operations drawn from prior literature, with no free parameters fitted inside the paper, no new invented entities, and only domain-standard assumptions about what constitutes a realistic anonymity measure.

axioms (1)
  • domain assumption k-anonymity under a chosen structural measure is a suitable objective for quantifying and achieving node anonymity against realistic attackers
    Invoked when defining the objective of maximizing the number of k-anonymous nodes across all three variants.

pith-pipeline@v0.9.0 · 5813 in / 1354 out tokens · 30578 ms · 2026-05-23T20:52:51.128434+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

66 extracted references · 66 canonical work pages

  1. [1]

    Infectious Disease Modelling 5, 12–22 (2020) 21

    Azizi, A., Montalvo, C., Espinoza, B., Kang, Y., Castillo-Chavez, C.: Epidemics on networks: Reducing disease transmission using health emergency declarations and peer communication. Infectious Disease Modelling 5, 12–22 (2020) 21

    work page 2020

  2. [2]

    In: Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp

    Chen, W., Wang, Y., Yang, S.: Efficient influence maximization in social net- works. In: Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 199–208 (2009)

    work page 2009

  3. [3]

    In: Proceedings of the 4th Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD), pp

    Akoglu, L., McGlohon, M., Faloutsos, C.: Oddball: Spotting anomalies in weighted graphs. In: Proceedings of the 4th Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD), pp. 410–421 (2010). Springer

    work page 2010

  4. [4]

    In: Proceedings of the 19th International Conference on World Wide Web, pp

    Leskovec, J., Lang, K.J., Mahoney, M.: Empirical comparison of algorithms for network community detection. In: Proceedings of the 19th International Conference on World Wide Web, pp. 631–640 (2010)

    work page 2010

  5. [5]

    Scientific Reports 9(1), 1–12 (2019)

    Traag, V.A., Waltman, L., Van Eck, N.J.: From louvain to leiden: guaranteeing well-connected communities. Scientific Reports 9(1), 1–12 (2019)

    work page 2019

  6. [6]

    In: Proceedings of the 16th International Conference on World Wide Web, pp

    Backstrom, L., Dwork, C., Kleinberg, J.: Wherefore art thou r3579x? anonymized social networks, hidden patterns, and structural steganography. In: Proceedings of the 16th International Conference on World Wide Web, pp. 181–190 (2007)

    work page 2007

  7. [7]

    ports 11(1), 20104 (2021)

    Romanini, D., Lehmann, S., Kivel¨ a, M.: Privacy and uniqueness of neighborhoods in social networks. ports 11(1), 20104 (2021)

    work page 2021

  8. [8]

    Scientific Reports 14(1), 1156 (2024)

    Jong, R.G., Loo, M.P.J., Takes, F.W.: The effect of distant connections on node anonymity in complex networks. Scientific Reports 14(1), 1156 (2024)

    work page 2024

  9. [9]

    In: Database and Expert Systems Applications, pp

    Lu, X., Song, Y., Bressan, S.: Fast identity anonymization on graphs. In: Database and Expert Systems Applications, pp. 281–295 (2012)

    work page 2012

  10. [10]

    In: Privacy, Security, and Trust in KDD, Berlin, Heidelberg, pp

    Campan, A., Truta, T.M.: Data and structural k-anonymity in social networks. In: Privacy, Security, and Trust in KDD, Berlin, Heidelberg, pp. 33–54 (2009)

    work page 2009

  11. [11]

    In: Proceedings of the VLDB Endowment, vol

    Bhagat, S., Cormode, G., Krishnamurthy, B., Srivastava, D.: Class-based graph anonymization for social network data. In: Proceedings of the VLDB Endowment, vol. 2, pp. 766–777 (2009)

    work page 2009

  12. [12]

    In: Proceedings of the 23rd Annual Network and Distributed System Security Symposium (2016)

    Liu, C., Mittal, P.: Linkmirage: Enabling privacy-preserving analytics on social relationships. In: Proceedings of the 23rd Annual Network and Distributed System Security Symposium (2016)

    work page 2016

  13. [13]

    IEEE Transactions on Network Science and Engineering 8(2), 1283–1292 (2020)

    Minello, G., Rossi, L., Torsello, A.: k-anonymity on graphs using the szemer´ edi regularity lemma. IEEE Transactions on Network Science and Engineering 8(2), 1283–1292 (2020)

    work page 2020

  14. [14]

    In: Proceedings of the 2011 ACM SIGCOMM Conference on Internet Measurement Conference, pp

    Sala, A., Zhao, X., Wilson, C., Zheng, H., Zhao, B.Y.: Sharing graphs using differentially private graph models. In: Proceedings of the 2011 ACM SIGCOMM Conference on Internet Measurement Conference, pp. 81–98 (2011)

    work page 2011

  15. [15]

    Transactions on Data Privacy 6(2), 127 (2013)

    Wang, Y., Wu, X.: Preserving differential privacy in degree-correlation based 22 graph generation. Transactions on Data Privacy 6(2), 127 (2013)

    work page 2013

  16. [16]

    In: Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp

    Xiao, Q., Chen, R., Tan, K.-L.: Differentially private network data release via structural inference. In: Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 911–920 (2014)

    work page 2014

  17. [17]

    Proceedings of the VLDB Endowment 7(8), 637–648 (2014)

    Proserpio, D., Goldberg, S., McSherry, F.: Calibrating data to sensitivity in private data analysis: A platform for differentially-private analysis of weighted datasets. Proceedings of the VLDB Endowment 7(8), 637–648 (2014)

    work page 2014

  18. [18]

    Proceedings of the VLDB Endowment 3(1–2), 1021–1032 (2010)

    Hay, M., Rastogi, V., Miklau, G., Suciu, D.: Boosting the accuracy of differentially private histograms through consistency. Proceedings of the VLDB Endowment 3(1–2), 1021–1032 (2010)

    work page 2010

  19. [19]

    Procedia Computer Science 143, 786–793 (2018)

    Macwan, K.R., Patel, S.J.: Node differential privacy in social graph degree publishing. Procedia Computer Science 143, 786–793 (2018)

    work page 2018

  20. [20]

    IEEE Transactions on Knowledge and Data Engineering 35(1), 108–127 (2021)

    Jiang, H., Pei, J., Yu, D., Yu, J., Gong, B., Cheng, X.: Applications of differential privacy in social network analysis: A survey. IEEE Transactions on Knowledge and Data Engineering 35(1), 108–127 (2021)

    work page 2021

  21. [21]

    In: Proceedings of the ACM SIGMOD International Conference on Management of Data, pp

    Liu, K., Terzi, E.: Towards identity anonymization on graphs. In: Proceedings of the ACM SIGMOD International Conference on Management of Data, pp. 93–106 (2008)

    work page 2008

  22. [22]

    In: Proceedings of the VLDB Endowment, vol

    Hay, M., Miklau, G., Jensen, D., Towsley, D., Weis, P.: Resisting structural re-identification in anonymized social networks. In: Proceedings of the VLDB Endowment, vol. 1, pp. 102–114 (2008)

    work page 2008

  23. [23]

    In: Proceedings of the of the VLDB Endowment, vol

    Zou, L., Chen, L., ¨Ozsu, M.T.: K-automorphism: a general framework for privacy preserving network publication. In: Proceedings of the of the VLDB Endowment, vol. 2, pp. 946–957 (2009)

    work page 2009

  24. [24]

    In: Theory of Cryptography, Berlin, Heidelberg, pp

    Dwork, C., McSherry, F., Nissim, K., Smith, A.: Calibrating noise to sensitivity in private data analysis. In: Theory of Cryptography, Berlin, Heidelberg, pp. 265–284 (2006)

    work page 2006

  25. [25]

    PloS one 14(4), 0215856 (2019)

    Aljably, R., Tian, Y., Al-Rodhaan, M., Al-Dhelaan, A.: Anomaly detection over differential preserved privacy in online social networks. PloS one 14(4), 0215856 (2019)

    work page 2019

  26. [26]

    Jong, R.G., Loo, M.P.J., Takes, F.W.: A systematic comparison of measures for k-anonymity in networks (2024) arXiv:2407.02290

    work page arXiv 2024

  27. [27]

    Social Network Analysis and Mining 10, 1–17 (2020) 23

    Rajabzadeh, S., Shahsafi, P., Khoramnejadi, M.: A graph modification approach for k-anonymity in social networks using the genetic algorithm. Social Network Analysis and Mining 10, 1–17 (2020) 23

    work page 2020

  28. [28]

    IEEE Access 7, 108371–108383 (2019)

    Zhang, X., Liu, J., Li, J., Liu, L.: Large-scale dynamic social network directed graph k-in&out-degree anonymity algorithm for protecting community structure. IEEE Access 7, 108371–108383 (2019)

    work page 2019

  29. [29]

    In: Computational Intelligence in Data Mining, pp

    Mohapatra, D., Patra, M.R.: Graph anonymization using hierarchical clustering. In: Computational Intelligence in Data Mining, pp. 145–154 (2019)

    work page 2019

  30. [30]

    Advances in Electrical & Computer Engineering 17(4), 117–124 (2017)

    Macwan, K.R., Patel, S.J.: k-degree anonymity model for social network data publishing. Advances in Electrical & Computer Engineering 17(4), 117–124 (2017)

    work page 2017

  31. [31]

    In: Proceedings of the 2013 IEEE/ACM Inter- national Conference on Advances in Social Networks Analysis and Mining, pp

    Casas-Roma, J., Herrera-Joancomart´ ı, J., Torra, V.: An algorithm for k-degree anonymity on large networks. In: Proceedings of the 2013 IEEE/ACM Inter- national Conference on Advances in Social Networks Analysis and Mining, pp. 671–675 (2013)

    work page 2013

  32. [32]

    In: Proceedings of the 24th IEEE International Conference on Data Engineering, pp

    Zhou, B., Pei, J.: Preserving privacy in social networks against neighborhood attacks. In: Proceedings of the 24th IEEE International Conference on Data Engineering, pp. 506–515 (2008)

    work page 2008

  33. [33]

    Knowledge and Information Systems 28(1), 47–77 (2011)

    Zhou, B., Pei, J.: The k-anonymity and l-diversity approaches for privacy preservation in social networks against neighborhood attacks. Knowledge and Information Systems 28(1), 47–77 (2011)

    work page 2011

  34. [34]

    In: 2012 Fourth International Conference on Computational Aspects of Social Networks, pp

    Tripathy, B., Mitra, A.: An algorithm to achieve k-anonymity and l-diversity anonymisation in social networks. In: 2012 Fourth International Conference on Computational Aspects of Social Networks, pp. 126–131 (2012)

    work page 2012

  35. [35]

    In: Proceedings of the 21st Springer International Conference on Information Security, pp

    Alavi, A., Gupta, R., Qian, Z.: When the attacker knows a lot: The gaga graph anonymizer. In: Proceedings of the 21st Springer International Conference on Information Security, pp. 211–230 (2019)

    work page 2019

  36. [36]

    Wireless Communications and Mobile Computing (2022)

    Ren, X., Jiang, D., et al.: A personalized-anonymity model of social network for protecting privacy. Wireless Communications and Mobile Computing (2022)

    work page 2022

  37. [37]

    In: Proceedings of the VLDB Endowment, vol

    Yuan, M., Chen, L., Yu, P.S.: Personalized privacy protection in social networks. In: Proceedings of the VLDB Endowment, vol. 4, pp. 141–150 (2010)

    work page 2010

  38. [38]

    Social Network Analysis and Mining 4(1), 223 (2014)

    Hao, Y., Cao, H., Hu, C., Bhattarai, K., Misra, S.: K-anonymity for social net- works containing rich structural and textual information. Social Network Analysis and Mining 4(1), 223 (2014)

    work page 2014

  39. [39]

    Security and Communication Networks8(18), 3864–3882 (2015)

    Liu, C.-G., Liu, I.-H., Yao, W.-S., Li, J.-S.: K-anonymity against neighborhood attacks in weighted social networks. Security and Communication Networks8(18), 3864–3882 (2015)

    work page 2015

  40. [40]

    Journal of the Royal Statistical Society Series A: Statistics in Society 181(3), 663–688 (2018)

    Snoke, J., Raab, G.M., Nowok, B., Dibben, C., Slavkovic, A.: General and specific 24 utility measures for synthetic data. Journal of the Royal Statistical Society Series A: Statistics in Society 181(3), 663–688 (2018)

    work page 2018

  41. [41]

    Social Networks 28(2), 124–136 (2006)

    Borgatti, S.P., Carley, K.M., Krackhardt, D.: On the robustness of centrality measures under conditions of imperfect data. Social Networks 28(2), 124–136 (2006)

    work page 2006

  42. [42]

    IEEE Transactions on Knowledge and Data Engineering 30(10), 1852– 1872 (2018)

    Li, Y., Fan, J., Wang, Y., Tan, K.-L.: Influence maximization on social graphs: A survey. IEEE Transactions on Knowledge and Data Engineering 30(10), 1852– 1872 (2018)

    work page 2018

  43. [43]

    Computer Science Department Faculty Publication Series, 180 (2007)

    Hay, M., Miklau, G., Jensen, D., Weis, P., Srivastava, S.: Anonymizing social networks. Computer Science Department Faculty Publication Series, 180 (2007)

    work page 2007

  44. [44]

    Empirical Software Engineering 29(4), 76 (2024)

    Malik, A., Adams, B., Hassan, A.: Towards graph-anonymization of software analytics data: empirical study on jit defect prediction. Empirical Software Engineering 29(4), 76 (2024)

    work page 2024

  45. [45]

    ports 7(1), 1–10 (2017)

    Garcia-Bernardo, J., Fichtner, J., Takes, F.W., Heemskerk, E.M.: Uncovering offshore financial centers: Conduits and sinks in the global corporate ownership network. ports 7(1), 1–10 (2017)

    work page 2017

  46. [46]

    ACM Journal of Experimental Algorithmics 28 (2023)

    Jong, R.G., Loo, M.P.J., Takes, F.W.: Algorithms for efficiently computing structural anonymity in complex networks. ACM Journal of Experimental Algorithmics 28 (2023)

    work page 2023

  47. [47]

    In: Proceedings of the 4th International Symposium on Information, Computer, and Communications Security, pp

    Thompson, B., Yao, D.: The union-split algorithm and cluster-based anonymiza- tion of social networks. In: Proceedings of the 4th International Symposium on Information, Computer, and Communications Security, pp. 218–227 (2009)

    work page 2009

  48. [48]

    Social Network Analysis and Mining 3(2), 151–166 (2013)

    Chester, S., Kapron, B.M., Srivastava, G., Venkatesh, S.: Complexity of social network anonymization. Social Network Analysis and Mining 3(2), 151–166 (2013)

    work page 2013

  49. [49]

    Nature Reviews Genetics 5(2), 101–113 (2004)

    Barabasi, A.-L., Oltvai, Z.N.: Network biology: understanding the cell’s functional organization. Nature Reviews Genetics 5(2), 101–113 (2004)

    work page 2004

  50. [50]

    Journal of Symbolic Computation 60, 94–112 (2014)

    McKay, B.D., Piperno, A.: Practical graph isomorphism, ii. Journal of Symbolic Computation 60, 94–112 (2014)

    work page 2014

  51. [51]

    Scientific Reports 2(1), 336 (2012)

    Lancichinetti, A., Fortunato, S.: Consensus clustering in complex networks. Scientific Reports 2(1), 336 (2012)

    work page 2012

  52. [52]

    arXiv preprint arXiv:2011.07190 (2020)

    Saxena, A., Iyengar, S.: Centrality measures in complex networks: A survey. arXiv preprint arXiv:2011.07190 (2020)

    work page arXiv 2011

  53. [53]

    In: Proceedings of the 16th International 25 Conference on Advances in Mobile Computing and Multimedia, pp

    Tian, H., Lu, Y., Liu, J., Yu, J.: Betweenness centrality based k-anonymity for privacy preserving in social networks. In: Proceedings of the 16th International 25 Conference on Advances in Mobile Computing and Multimedia, pp. 3–7 (2018)

    work page 2018

  54. [54]

    Social Networks 34(4), 396–409 (2012)

    Wang, D.J., Shi, X., McFarland, D.A., Leskovec, J.: Measurement error in network data: A re-classification. Social Networks 34(4), 396–409 (2012)

    work page 2012

  55. [55]

    nature 406(6794), 378–382 (2000)

    Albert, R., Jeong, H., Barab´ asi, A.-L.: Error and attack tolerance of complex networks. nature 406(6794), 378–382 (2000)

    work page 2000

  56. [56]

    In: Proceedings of the 22nd International Conference on World Wide Web, pp

    Kunegis, J.: Konect: the koblenz network collection. In: Proceedings of the 22nd International Conference on World Wide Web, pp. 1343–1350 (2013)

    work page 2013

  57. [57]

    http://www.sociopatterns.org/ datasets/

    Sociopatterns: Sociopatterns: Datasets (2021). http://www.sociopatterns.org/ datasets/

    work page 2021

  58. [58]

    Replication Package for: Toward Instructions-as-Code: Understanding the Impact of Instruction Files on Agentic Pull Requests

    Sapiezynski, P., Stopczynski, A., Lassen, D.D., Jørgensen, S.L.: The Copenhagen Networks Study interaction data. Figshare. https://doi.org/10.6084/m9.figshare. 7267433.v1 (last accessed May 2022) (2019)

    work page doi:10.6084/m9.figshare 2022

  59. [59]

    In: Proceedings of the 29th AAAI Conference on Artificial Intelligence, pp

    Rossi, R.A., Ahmed, N.K.: The network data repository with interactive graph analytics and visualization. In: Proceedings of the 29th AAAI Conference on Artificial Intelligence, pp. 4292–4293 (2015)

    work page 2015

  60. [60]

    http://snap.stanford.edu/data (last accessed May 2022) (2014)

    Leskovec, J., Krevl, A.: SNAP Datasets: Stanford Large Network Dataset Collection. http://snap.stanford.edu/data (last accessed May 2022) (2014)

    work page 2022

  61. [61]

    Technical report, Los Alamos National Lab (LANL) (2008)

    Hagberg, A., Swart, P., Schult, D.: Exploring network structure, dynamics, and function using networkx. Technical report, Los Alamos National Lab (LANL) (2008)

    work page 2008

  62. [62]

    InterJournal Complex Systems, 1695 (2006)

    Csardi, G., Nepusz, T.: The igraph software package for complex network research. InterJournal Complex Systems, 1695 (2006)

    work page 2006

  63. [63]

    Publication of the Mathematical Institute of the Hungarian Academy of Sciences5(1), 17–60 (1960)

    Erd˝ os, P., R´ enyi, A.: On the evolution of random graphs. Publication of the Mathematical Institute of the Hungarian Academy of Sciences5(1), 17–60 (1960)

    work page 1960

  64. [64]

    Science 286(5439), 509–512 (1999)

    Barab´ asi, A.L., Albert, R.: Emergence of scaling in random networks. Science 286(5439), 509–512 (1999)

    work page 1999

  65. [65]

    Nature 393(6684), 440–442 (1998) 26 Appendix A Recompute gap This appendix accompanies Section 5.2 of the full paper

    Watts, D.J., Strogatz, S.H.: Collective dynamics of ‘small-world’ networks. Nature 393(6684), 440–442 (1998) 26 Appendix A Recompute gap This appendix accompanies Section 5.2 of the full paper. Here, we compare the perfor- mance and runtimes achieved by the anonymization algorithms when using different recompute gaps. Figure A1 shows the results for diffe...

    work page 1998

  66. [66]

    Partial 3

    Full 2. Partial 3. Budgeted Network property Pearson correlation p-value Pearson correlation p-value Pearson correlation p-value Unique start -0.86 0.00 -0.92 0.00 -0.76 0.00 |V | 0.13 0.62 0.29 0.25 0.06 0.81 Average degree -0.19 0.45 -0.13 0.61 -0.15 0.56 Median degree -0.80 0.00 -0.87 0.00 -0.68 0.00 Transitivity -0.52 0.03 -0.48 0.05 -0.59 0.01 Assort...

    work page 2009