Reconstructing randomized social networks

Niko Vuokko, Evimaria Terzi

    Research output: Chapter in Book/Report/Conference proceedingConference contributionScientific

    16 Citations (Scopus)


    In social networks, nodes correspond to entities and edges to links between them. In most of the cases, nodes are also associated with a set of features. Noise, missing values or efforts to preserve privacy in the network may transform the original network G and its feature vectors F. This transformation can be modeled as a randomization method. Here, we address the problem of reconstructing the original network and set of features given their randomized counterparts G′ and F′ and knowledge of the randomization model. We identify the cases in which the original network G and feature vectors F can be reconstructed in polynomial time. Finally, we illustrate the efficacy of our methods using both generated and real datasets.

    Original languageEnglish
    Title of host publicationProceedings of the 10th SIAM International Conference on Data Mining
    Number of pages11
    Publication statusPublished - 1 Dec 2010
    MoE publication typeB3 Non-refereed article in conference proceedings
    EventSIAM International Conference on Data Mining - Columbus, United States
    Duration: 29 Apr 20101 May 2010
    Conference number: 10


    ConferenceSIAM International Conference on Data Mining
    Abbreviated titleSDM
    CountryUnited States


    • Privacy-preserving data mining
    • Social-network analysis

    Fingerprint Dive into the research topics of 'Reconstructing randomized social networks'. Together they form a unique fingerprint.

    Cite this