期刊名称：IEEE Transactions on Emerging Topics in Computing
印刷版ISSN：2168-6750
出版年度：2016
卷号：4
期号：3
页码：374-381
DOI：10.1109/TETC.2015.2433923
出版社：IEEE Publishing
摘要：Graphs can be used as a model for online social networks. In this framework, vertices represent individuals and edges relationships between individuals. In recent years, different approaches have been considered to offer data privacy to online social networks and for developing graph protection. Perturbative approaches are formally defined in terms of perturbation and modification of graphs. In this paper, we discuss the concept of P -stability on graphs and its relation to data privacy. The concept of P -stability is rooted in the number of graphs given a fixed degree sequence. In this paper, we show that for any graph there exists a class of P -stable graphs. This result implies that there is a fully polynomial randomized approximation for graph masking for the graphs in the class. In order to further refine the classification of a given graph, we introduce the concept of natural class of a graph. It is based on a class of scale-free networks.
Loading...
