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
Graphic sequences, distances and k-degree anonymity
IIIA-CSIC, Consejo Superior de Investigaciones Científicas, Institut d’Investigació en Intelligència Artificial, Campus Universitat Autònoma de Barcelona, Spain.
University of Skövde, School of Informatics. University of Skövde, The Informatics Research Centre. IIIA-CSIC, Consejo Superior de Investigaciones Científicas, Institut d’Investigació en Intelligència Artificial, Campus Universitat Autònoma de Barcelona, Spain. (Skövde Artificial Intelligence Lab (SAIL))ORCID iD: 0000-0002-0368-8037
2015 (English)In: Discrete Applied Mathematics, ISSN 0166-218X, E-ISSN 1872-6771, Vol. 188, no 1, 25-31 p.Article in journal (Refereed) Published
Abstract [en]

In this paper we study conditions to approximate a given graph by a regular one. We obtain optimal conditions for a few metrics such as the edge rotation distance for graphs, the rectilinear and the Euclidean distance over degree sequences. Then, we require the approximation to have at least kk copies of each value in the degree sequence, this is a property proceeding from data privacy that is called kk-degree anonymity.

We give a sufficient condition in order for a degree sequence to be graphic that depends only on its length and its maximum and minimum degrees. Using this condition we give an optimal solution of kk-degree anonymity for the Euclidean distance when the sum of the degrees in the anonymized degree sequence is even. We present algorithms that may be used for obtaining all the mentioned anonymizations.

Place, publisher, year, edition, pages
Elsevier, 2015. Vol. 188, no 1, 25-31 p.
National Category
Computer Systems
Research subject
Technology
Identifiers
URN: urn:nbn:se:his:diva-10938DOI: 10.1016/j.dam.2015.03.005ISI: 000355767900003Scopus ID: 2-s2.0-84933279022OAI: oai:DiVA.org:his-10938DiVA: diva2:811982
Funder
EU, FP7, Seventh Framework Programme, 262608
Available from: 2015-05-13 Created: 2015-05-13 Last updated: 2016-03-03Bibliographically 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
Discrete Applied Mathematics
Computer Systems

Search outside of DiVA

GoogleGoogle Scholar

Altmetric score

Total: 144 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