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
Synthetic generation of spatial 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 Skövde, School of Bioscience. University of Skövde, The Systems Biology Research Centre. (Ecological Modeling, Ekologisk modellering)ORCID iD: 0000-0002-3965-7371
Universitat Autònoma de Barcelona, Spain / Center for Cybersecurity Research of Catalonia (CYBERCAT), Spain.
Center for Cybersecurity Research of Catalonia (CYBERCAT), Spain / Universitat Oberta de Catalunya (UOC), Barcelona, Spain.
2018 (English)In: International Journal of Intelligent Systems, ISSN 0884-8173, E-ISSN 1098-111X, Vol. 32, no 12, p. 2364-2378Article in journal (Refereed) Published
Abstract [en]

Graphs can be used to model many different types of interaction networks, for example, online social networks or animal transport networks. Several algorithms have thus been introduced to build graphs according to some predefined conditions. In this paper, we present an algorithm that generates spatial graphs with a given degree sequence. In spatial graphs, nodes are located in a space equiped with a metric. Our goal is to define a graph in such a way that the nodes and edges are positioned according to an underlying metric. More particularly, we have constructed a greedy algorithm that generates nodes proportional to an underlying probability distribution from the spatial structure, and then generates edges inversely proportional to the Euclidean distance between nodes. The algorithm first generates a graph that can be a multigraph, and then corrects multiedges. Our motivation is in data privacy for social networks, where a key problem is the ability to build synthetic graphs. These graphs need to satisfy a set of required properties (e.g., the degrees of the nodes) but also be realistic, and thus, nodes (individuals) should be located according to a spatial structure and connections should be added taking into account nearness.

Place, publisher, year, edition, pages
John Wiley & Sons, 2018. Vol. 32, no 12, p. 2364-2378
Keywords [en]
data privacy, graphs generating algorithms, network modeling, spatial graphs
National Category
Computer Sciences
Research subject
Ecological Modelling Group; Skövde Artificial Intelligence Lab (SAIL); INF301 Data Science
Identifiers
URN: urn:nbn:se:his:diva-16290DOI: 10.1002/int.22034ISI: 000448278500004Scopus ID: 2-s2.0-85054373026OAI: oai:DiVA.org:his-16290DiVA, id: diva2:1254993
Available from: 2018-10-11 Created: 2018-10-11 Last updated: 2019-02-14Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records BETA

Torra, VicençJonsson, Annie

Search in DiVA

By author/editor
Torra, VicençJonsson, Annie
By organisation
School of InformaticsThe Informatics Research CentreSchool of BioscienceThe Systems Biology Research Centre
In the same journal
International Journal of Intelligent Systems
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 244 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