Privacy preserving maximum-flow computation in distributed graphs

The maximum-flow problem arises in a wide variety of applications such as financial transactions and logistics collaboration networks, where the data can be modeled as a directed graph. In many such applications, the graph data is actually distributed across several organizations where each owns a portion of the overall graph. Due to privacy concerns, the parties may not wish to disclose their local graphs. However, the computation of maximum-flow over the overall graph brings great benefits to concerned stakeholders. In this paper, we address the privacy preserving maximum-flow computation problem in distributed graphs. We propose a two-stage approach that achieves privacy protection while ensuring the correct maximum flow computation. In the first stage, a novel probabilistic edge expansion process is used to obfuscate the graph structure and prevent node re-identification while preserving the maximum flow, the second stage securely integrates local graphs into a global whole such that any third party can then compute the maximum flow. We provide a thorough correctness and privacy analysis and experimentally evaluate the proposed approach. © 2012 IEEE