P-Stability: Graph generation, randomization and k-degree anonymity

With the motivation of social network privacy and the aim of anonymizing the graph structure of a social network, several methods have been studied. One of the most basic is that of k-degree anonymization. It consists of making the least edge modifications to a given graph, in order that for every degree value of a vertex in the modified graph there are at least k repetitions of it in the degree sequence. This implies that no vertex can be uniquely identified by its degree, hence, the modified graph is k-degree anonymous.


Another technique for graph anonymization is the random modification of its edges. When there is the additional constraint of not modifying the degrees of the vertices in the randomization, random switchings of the edges may be used.


The property of P-stability for a degree sequence can be used for both purposes, for edge randomization and degree anonymization. I will discuss a recent result that improves previous conditions for P-stability and show that such conditions also guarantee that the given degree sequences are graphic.

Date: Mar 11, 2016 at 16:15 h
Venue: Beauchef 851, Torre Norte, Piso 7, Sala de Seminarios John Von Neumann.
Speaker: Julián Salas Piñón
Affiliation: U. Rovira i Virgili, Tarragona, Spain
Coordinator: Prof. Marcos Kiwi

Posted on Mar 1, 2016 in Discrete Mathematics, Seminars