his.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Data Protection for Online Social Networks and P-Stability for Graphs
University of Skövde, School of Informatics. University of Skövde, The Informatics Research Centre. (Skövde Artificial Intelligence Lab (SAIL))ORCID iD: 0000-0002-0368-8037
University of Konstanz, Konstanz, Germany.
Artificial Intelligence Research Institute(IIIA)–Spanish National Research Council (CSIC), Bellaterra 08193, Catalonia, Spain.
2016 (English)In: IEEE Transactions on Emerging Topics in Computing, ISSN 2168-6750, Vol. 4, no 3, 374-381 p.Article in journal (Refereed) Published
Abstract [en]

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.

Place, publisher, year, edition, pages
IEEE, 2016. Vol. 4, no 3, 374-381 p.
Keyword [en]
Graphs, P-stability, data privacy
National Category
Computer Science
Identifiers
URN: urn:nbn:se:his:diva-13313DOI: 10.1109/TETC.2015.2433923ISI: 000390197500006Scopus ID: 2-s2.0-84986536260OAI: oai:DiVA.org:his-13313DiVA: diva2:1065057
Available from: 2017-01-13 Created: 2017-01-13 Last updated: 2017-05-22Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Torra, Vicenç
By organisation
School of InformaticsThe Informatics Research Centre
In the same journal
IEEE Transactions on Emerging Topics in Computing
Computer Science

Search outside of DiVA

GoogleGoogle Scholar

Altmetric score

Total: 79 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf