2 Search Results for "Barrat, Alain"

Document
DOI: 10.4230/LIPIcs.ESA.2025.91
Near-Optimal Differentially Private Graph Algorithms via the Multidimensional AboveThreshold Mechanism

Authors: Laxman Dhulipala, Monika Henzinger, George Z. Li, Quanquan C. Liu, A. R. Sricharan, and Leqi Zhu

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
Many differentially private and classical non-private graph algorithms rely crucially on determining whether some property of each vertex meets a threshold. For example, for the k-core decomposition problem, the classic peeling algorithm iteratively removes a vertex if its induced degree falls below a threshold. The sparse vector technique (SVT) is generally used to transform non-private threshold queries into private ones with only a small additive loss in accuracy. However, a naive application of SVT in the graph setting leads to an amplification of the error by a factor of n due to composition, as SVT is applied to every vertex. In this paper, we resolve this problem by formulating a novel generalized sparse vector technique which we call the Multidimensional AboveThreshold (MAT) Mechanism which generalizes SVT (applied to vectors with one dimension) to vectors with multiple dimensions. When applied to vectors with n dimensions, we solve a number of important graph problems with better bounds than previous work. Specifically, we apply our MAT mechanism to obtain a set of improved bounds for a variety of problems including k-core decomposition, densest subgraph, low out-degree ordering, and vertex coloring. We give a tight local edge differentially private (LEDP) algorithm for k-core decomposition that results in an approximation with O(ε^{-1} log n) additive error and no multiplicative error in O(n) rounds. We also give a new (2+η)-factor multiplicative, O(ε^{-1} log n) additive error algorithm in O(log² n) rounds for any constant η > 0. Both of these results are asymptotically tight against our new lower bound of Ω(log n) for any constant-factor approximation algorithm for k-core decomposition. Our new algorithms for k-core decomposition also directly lead to new algorithms for the related problems of densest subgraph and low out-degree ordering. Finally, we give novel LEDP differentially private defective coloring algorithms that use number of colors given in terms of the arboricity of the graph.
Cite as

Laxman Dhulipala, Monika Henzinger, George Z. Li, Quanquan C. Liu, A. R. Sricharan, and Leqi Zhu. Near-Optimal Differentially Private Graph Algorithms via the Multidimensional AboveThreshold Mechanism. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 91:1-91:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{dhulipala_et_al:LIPIcs.ESA.2025.91,
  author =	{Dhulipala, Laxman and Henzinger, Monika and Li, George Z. and Liu, Quanquan C. and Sricharan, A. R. and Zhu, Leqi},
  title =	{{Near-Optimal Differentially Private Graph Algorithms via the Multidimensional AboveThreshold Mechanism}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{91:1--91:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.91},
  URN =		{urn:nbn:de:0030-drops-245601},
  doi =		{10.4230/LIPIcs.ESA.2025.91},
  annote =	{Keywords: differential privacy, abovethreshold, densest subgraph}
}
Document
DOI: 10.4230/DagSemProc.08391.4
08391 Group Summary – The Berners-Lee Hypothesis: Power laws and Group Structure in Flickr

Authors: Andrea Baldassarri, Alain Barrat, Andrea Capocci, Harry Halpin, Ulrike Lehner, Jose Ramasco, Valentin Robu, and Dario Taraborelli

Published in: Dagstuhl Seminar Proceedings, Volume 8391, Social Web Communities (2008)

Abstract
An intriguing hypothesis, first suggested by Tim Berners-Lee, is that the structure of online groups should conform to a power law distribution. We relate this hypothesis to earlier work around the Dunbar Number, which is a supposed limit to the number of social contacts a user can have in a group. As preliminary results, we show that the number of contacts of a typical Flickr user, the number of groups a user belongs to, and the size of Flickr groups all follow power law distributions. Furthermore, we find some unexpected differences in the internal structure of public and private Flickr groups. For further research, we further operationalize the Berners-Lee hypothesis to suppose that users with a group membership distribution that follows a power law will produce more content for social Web systems.
Cite as

Andrea Baldassarri, Alain Barrat, Andrea Capocci, Harry Halpin, Ulrike Lehner, Jose Ramasco, Valentin Robu, and Dario Taraborelli. 08391 Group Summary – The Berners-Lee Hypothesis: Power laws and Group Structure in Flickr. In Social Web Communities. Dagstuhl Seminar Proceedings, Volume 8391, pp. 1-11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{baldassarri_et_al:DagSemProc.08391.4,
  author =	{Baldassarri, Andrea and Barrat, Alain and Capocci, Andrea and Halpin, Harry and Lehner, Ulrike and Ramasco, Jose and Robu, Valentin and Taraborelli, Dario},
  title =	{{08391 Group Summary – The Berners-Lee Hypothesis: Power laws and Group Structure in Flickr}},
  booktitle =	{Social Web Communities},
  pages =	{1--11},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8391},
  editor =	{Harith Alani and Steffen Staab and Gerd Stumme},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08391.4},
  URN =		{urn:nbn:de:0030-drops-17893},
  doi =		{10.4230/DagSemProc.08391.4},
  annote =	{Keywords: Social group flickr powerlaw}
}
  • Refine by Type
  • 2 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 1 2008

  • Refine by Author
  • 1 Baldassarri, Andrea
  • 1 Barrat, Alain
  • 1 Capocci, Andrea
  • 1 Dhulipala, Laxman
  • 1 Halpin, Harry
  • Show More...

  • Refine by Series/Journal
  • 1 LIPIcs
  • 1 DagSemProc

  • Refine by Classification
  • 1 Security and privacy
  • 1 Theory of computation

  • Refine by Keyword
  • 1 Social group flickr powerlaw
  • 1 abovethreshold
  • 1 densest subgraph
  • 1 differential privacy

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact