Please use this identifier to cite or link to this item:
http://hdl.handle.net/10609/150971
Title: | Improving the characterization of P-stability for applications in network privacy |
Author: | Salas Piñón, Julián Torra, Vicenç ![]() |
Citation: | Salas, J. [Julián], & Torra, V. [Vicenç] (2016). Improving the characterization of P-stability for applications in network privacy. Discrete Applied Mathematics, 206, 109-114. |
Abstract: | Recently, we have found that the concept of P-stability has interesting applications in network privacy. In the context of Online Social Networks it may be used for obtaining a fully polynomial randomized approximation scheme for graph masking and measuring disclosure risk. Also by using the characterization for P-stable sequences from Jerrum, McKayandSinclair (1992) it is possible to obtain optimal approximations for the problem of k-degree anonymity. In this paper, we present results on P-stability considering the additional restriction that the degree sequence must not intersect the edges of an excluded graphX,improvingearlier results on P-stability. As a consequence we extend the P-stable classes of scale-free networks from Torra et al. (2015), obtain an optimal solution for k-anonymity and prove that all the known conditions for P-stability are sufficient for sequences to be graphic. |
Keywords: | P-stability k-anonymity Graphic sequence Degree sequence FPRAS Rapidly mixing Markov chain Fully polynomial-time randomized approximation scheme |
DOI: | https://doi.org/10.1016/j.dam.2016.01.025 |
Document type: | info:eu-repo/semantics/article |
Version: | info:eu-repo/semantics/publishedVersion |
Issue Date: | Feb-2016 |
Appears in Collections: | Articles cientÍfics Articles |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Salas_DiscreteAppMath_Improving.pdf Until 2124-12-31 | 365,67 kB | Adobe PDF | View/Open Request a copy |
Share:
![]( /image/googleScholar.png)
![](/image/microsoftAcademic.png)
Items in repository are protected by copyright, with all rights reserved, unless otherwise indicated.