MURAL - Maynooth University Research Archive Library

    Synthetic generation of spatial graphs

    Torra, Vicenç and Jonsson, Annie and Navarro‐Arribas, Guillermo and Salas, Julián (2018) Synthetic generation of spatial graphs. International Journal of Intelligent Systems, 33. pp. 2364-2378. ISSN 0884-8173

    Download (773kB) | Preview

    Share your research

    Twitter Facebook LinkedIn GooglePlus Email more...

    Add this article to your Mendeley library


    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.

    Item Type: Article
    Additional Information: © 2018 The Authors. This is an open access article under the terms of the Creative Commons Attribution‐NonCommercial‐NoDerivs License, which permits use and distribution in any medium, provided the original work is properly cited, the use is non‐commercial and no modifications or adaptations are made. Cite as: Torra, V, Jonsson, A, Navarro‐Arribas, G, Salas, J. Synthetic generation of spatial graphs. Int J Intell Syst. 2018; 33: 2364‐ 2378.
    Keywords: data privacy; graphs generating algorithms; network modeling; spatial graphs;
    Academic Unit: Faculty of Science and Engineering > Research Institutes > Hamilton Institute
    Item ID: 13282
    Identification Number:
    Depositing User: Vicenç Torra
    Date Deposited: 29 Sep 2020 14:05
    Journal or Publication Title: International Journal of Intelligent Systems
    Publisher: Wiley
    Refereed: Yes
    Use Licence: This item is available under a Creative Commons Attribution Non Commercial Share Alike Licence (CC BY-NC-SA). Details of this licence are available here

    Repository Staff Only(login required)

    View Item Item control page


    Downloads per month over past year

    Origin of downloads