Reachability Analysis in Privacy-Preserving Perturbed Graphs

Reachability Analysis in Privacy-Preserving Perturbed Graphs,10.1109/WI-IAT.2010.216,Xiaoyun He,Jaideep Vaidya,Basit Shafiq,Nabil R. Adam,Xiaodong Lin

Reachability Analysis in Privacy-Preserving Perturbed Graphs   (Citations: 1)
BibTex | RIS | RefWorks Download
Many real world phenomena can be naturally modeled as graph structures whose nodes representing entities and whose edges representing interactions or relationships between entities. The analysis of the graph data have many practical implications. However, the release of the data often poses considerable privacy risk to the individuals involved. In this paper, we address the edge privacy problem in graphs. In particular, we explore random perturbation for privacy preservation in graph data, and propose an iterative derivation process to analyze node reachability within the graph. We specifically focus on deriving the probability that the shortest path linking two nodes in a directed graph is of a particular length. This allows us to determine the expected length of the shortest path between two nodes, and determine whether they are linked or not. The performance of the proposed method is demonstrated via extensive experiments on both real and synthetic datasets.
Conference: Web Intelligence - WI , pp. 691-694, 2010
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
Sort by: