• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 1
  • Tagged with
  • 2
  • 2
  • 2
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
1

Lost In The Crowd: Are Large Social Graphs Inherently Indistinguishable?

Vadamalai, Subramanian Viswanathan 19 June 2017 (has links)
Real social graphs datasets are fundamental to understanding a variety of phenomena, such as epidemics, crowd management and political uprisings, yet releasing digital recordings of such datasets exposes the participants to privacy violations. A safer approach to making real social network topologies available is to anonymize them by modifying the graph structure enough as to decouple the node identity from its social ties, yet preserving the graph characteristics in aggregate. At scale, this approach comes with a significant challenge in computational complexity. This thesis questions the need to structurally anonymize very large graphs. Intuitively, the larger the graph, the easier for an individual to be “lost in the crowd”. On the other hand, at scale new topological structures may emerge, and those can expose individual nodes in ways that smaller structures do not. To answer this problem, this work introduces a set of metrics for measuring the indistinguishability of nodes in large-scale social networks independent of attack models and shows how different graphs have different levels of inherent indistinguishability of nodes. Moreover, we show that when varying the size of a graph, the inherent node indistinguishability decreases with the size of the graph. In other words, the larger a graph of a graph structure, the higher the indistinguishability of its nodes.
2

Anonymizing subsets of social networks

Gaertner, Jared Glen 23 August 2012 (has links)
In recent years, concerns of privacy have become more prominent for social networks. Anonymizing a graph meaningfully is a challenging problem, as the original graph properties must be preserved as well as possible. We introduce a generalization of the degree anonymization problem posed by Liu and Terzi. In this problem, our goal is to anonymize a given subset of vertices in a graph while adding the fewest possible number of edges. We examine different approaches to solving the problem, one of which finds a degree-constrained subgraph to determine which edges to add within the given subset and another that uses a greedy approach that is not optimal, but is more efficient in space and time. The main contribution of this thesis is an efficient algorithm for this problem by exploring its connection with the degree-constrained subgraph problem. Our experimental results show that our algorithms perform very well on many instances of social network data. / Graduate

Page generated in 0.1108 seconds