Computing Betweenness Centrality: An Efficient Privacy-Preserving Approach

Betweenness centrality is a classic network measure used to determine prominent nodes in a network G(V, E), where the edges capture a type of flow through the network (like information, material or money). Betweenness being a global centrality measure requires the entire network information to compute the centrality of even a single vertex. We consider the setting where the global network structure is not present centrally with a single individual. Rather, the data is distributed among many individuals, each having only a partial view of the network. Furthermore, confidentiality constraints prevent the individual parties from disclosing their share of the data, thus inhibiting the aggregation of the entire network for analysis. The current paper proposes a secure multiparty protocol to compute the betweenness centrality measure, in a privacy preserving manner, for the considered setting. Employing various optimizations, including oblivious data structures and oblivious RAM, we present a secure variant of the Brandes algorithm for computing betweenness centrality in unweighted networks. The protocol is designed in the semi-honest adversarial model under the two-party setting. We evaluate the performance of the designed protocol by implementing them in the Obliv-C framework for secure computation. We are the first to provide a benchmark for the implementations using the state of the art ORAM schemes and help identify the best schemes for input data of different sizes. Employing the Circuit ORAM and the Square-Root ORAM schemes, we report the complexity of the proposed protocol as O(vertical bar V vertical bar vertical bar E vertical bar log(3) vertical bar E vertical bar) and O(vertical bar V vertical bar vertical bar E vertical bar(1.5) log(1.5) vertical bar E vertical bar) primitive operations respectively. The asymptotic complexity of Circuit ORAM is found to be the least, with an overhead of only O( log(3) vertical bar E vertical bar) compared to the traditional non-oblivious Brandes algorithm with complexity O(vertical bar V vertical bar vertical bar E vertical bar).