Paper Info
Title
Computing Betweenness Centrality: An Efficient Privacy-Preserving Approach.
Abstract
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 (mathcal {O}(|V||E|log ^3|E|)) and (mathcal {O}(|V||E|^{1.5}log ^{1.5}|E|)) primitive operations respectively. The asymptotic complexity of Circuit ORAM is found to be the least, with an overhead of only (mathcal {O}(log ^3|E|)) compared to the traditional non-oblivious Brandes algorithm with complexity (mathcal {O}(|V||E|)).
Year
Venue
Field
2018
CANS
Oblivious ram,Data structure,Secure multi-party computation,Vertex (geometry),Computer science,Social network analysis,Centrality,Theoretical computer science,Betweenness centrality,Asymptotic complexity
DocType
Citations 
PageRank 
Conference
0
0.34
References 
Authors
14
2
Name
Order
Citations
PageRank
Varsha Bhat Kukkala132.78
S. R. S. Iyengar237.50