IDEAS home Printed from https://ideas.repec.org/a/eee/apmaco/v412y2022ics0096300321006305.html
   My bibliography  Save this article

Analysis of centrality measures under differential privacy models

Author

Listed:
  • Laeuchli, Jesse
  • Ramírez-Cruz, Yunior
  • Trujillo-Rasua, Rolando

Abstract

This article provides the first analysis of the differentially private computation of three centrality measures, namely eigenvector, Laplacian and closeness centralities, on arbitrary weighted graphs, using the smooth sensitivity approach. We do so by finding lower bounds on the amounts of noise that a randomised algorithm needs to add in order to make the output of each measure differentially private. Our results indicate that these computations are either infeasible, in the sense that there are large families of graphs for which smooth sensitivity is unbounded; or impractical, in the sense that even for the cases where smooth sensitivity is bounded, the required amounts of noise result in unacceptably large utility losses.

Suggested Citation

  • Laeuchli, Jesse & Ramírez-Cruz, Yunior & Trujillo-Rasua, Rolando, 2022. "Analysis of centrality measures under differential privacy models," Applied Mathematics and Computation, Elsevier, vol. 412(C).
    • Handle: RePEc:eee:apmaco:v:412:y:2022:i:c:s0096300321006305
    DOI: 10.1016/j.amc.2021.126546
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0096300321006305
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.amc.2021.126546?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Aaron Clauset & Cristopher Moore & M. E. J. Newman, 2008. "Hierarchical structure and the prediction of missing links in networks," Nature, Nature, vol. 453(7191), pages 98-101, May.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Almaraz Luengo, Elena & Leiva Cerna, Marcos Brian & García Villalba, Luis Javier & Hernandez-Castro, Julio, 2022. "A new approach to analyze the independence of statistical tests of randomness," Applied Mathematics and Computation, Elsevier, vol. 426(C).

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Ding, Ying, 2011. "Community detection: Topological vs. topical," Journal of Informetrics, Elsevier, vol. 5(4), pages 498-514.
    2. Gräbner, Claudius, 2016. "From realism to instrumentalism - and back? Methodological implications of changes in the epistemology of economics," MPRA Paper 71933, University Library of Munich, Germany.
    3. Tamás Nepusz & Tamás Vicsek, 2013. "Hierarchical Self-Organization of Non-Cooperating Individuals," PLOS ONE, Public Library of Science, vol. 8(12), pages 1-9, December.
    4. Nora Connor & Albert Barberán & Aaron Clauset, 2017. "Using null models to infer microbial co-occurrence networks," PLOS ONE, Public Library of Science, vol. 12(5), pages 1-23, May.
    5. Leto Peel & Tiago P. Peixoto & Manlio De Domenico, 2022. "Statistical inference links data and theory in network science," Nature Communications, Nature, vol. 13(1), pages 1-15, December.
    6. Xinyi Liu & Bin Liu & Zhimin Huang & Ting Shi & Yingyi Chen & Jian Zhang, 2012. "SPPS: A Sequence-Based Method for Predicting Probability of Protein-Protein Interaction Partners," PLOS ONE, Public Library of Science, vol. 7(1), pages 1-6, January.
    7. Amulyashree Sridhar & Sharvani GS & AH Manjunatha Reddy & Biplab Bhattacharjee & Kalyan Nagaraj, 2019. "The Eminence of Co-Expressed Ties in Schizophrenia Network Communities," Data, MDPI, vol. 4(4), pages 1-23, November.
    8. Li, Qing & Zhang, Huaige & Hong, Xianpei, 2020. "Knowledge structure of technology licensing based on co-keywords network: A review and future directions," International Review of Economics & Finance, Elsevier, vol. 66(C), pages 154-165.
    9. Wang, Zuxi & Wu, Yao & Li, Qingguang & Jin, Fengdong & Xiong, Wei, 2016. "Link prediction based on hyperbolic mapping with community structure for complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 450(C), pages 609-623.
    10. Lee, Yan-Li & Zhou, Tao, 2021. "Collaborative filtering approach to link prediction," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 578(C).
    11. Thorben Funke & Till Becker, 2019. "Stochastic block models: A comparison of variants and inference methods," PLOS ONE, Public Library of Science, vol. 14(4), pages 1-40, April.
    12. Kan, Kees-Jan & van der Maas, Han L.J. & Levine, Stephen Z., 2019. "Extending psychometric network analysis: Empirical evidence against g in favor of mutualism?," Intelligence, Elsevier, vol. 73(C), pages 52-62.
    13. Yao, Can-Zhong & Lin, Ji-Nan & Zheng, Xu-Zhou & Liu, Xiao-Feng, 2015. "The study of RMB exchange rate complex networks based on fluctuation mode," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 436(C), pages 359-376.
    14. Liu, Zhenfeng & Feng, Jian & Uden, Lorna, 2023. "Technology opportunity analysis using hierarchical semantic networks and dual link prediction," Technovation, Elsevier, vol. 128(C).
    15. Zhichao Ba & Yujie Cao & Jin Mao & Gang Li, 2019. "A hierarchical approach to analyzing knowledge integration between two fields—a case study on medical informatics and computer science," Scientometrics, Springer;Akadémiai Kiadó, vol. 119(3), pages 1455-1486, June.
    16. Li, Wenyao & Cai, Meng & Zhong, Xiaoni & Liu, Yanbing & Lin, Tao & Wang, Wei, 2023. "Coevolution of epidemic and infodemic on higher-order networks," Chaos, Solitons & Fractals, Elsevier, vol. 168(C).
    17. Lü, Linyuan & Zhou, Tao, 2011. "Link prediction in complex networks: A survey," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 390(6), pages 1150-1170.
    18. Guan-Nan Wang & Hui Gao & Lian Chen & Dennis N A Mensah & Yan Fu, 2015. "Predicting Positive and Negative Relationships in Large Social Networks," PLOS ONE, Public Library of Science, vol. 10(6), pages 1-14, June.
    19. Bütün, Ertan & Kaya, Mehmet, 2019. "A pattern based supervised link prediction in directed complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 525(C), pages 1136-1145.
    20. Wen Zhou & Jiayi Gu & Yifan Jia, 2018. "h-Index-based link prediction methods in citation network," Scientometrics, Springer;Akadémiai Kiadó, vol. 117(1), pages 381-390, October.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:apmaco:v:412:y:2022:i:c:s0096300321006305. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: https://www.journals.elsevier.com/applied-mathematics-and-computation .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.