Towards transparency and privacy in the online advertising business

Secure centrality computation over multiple networks

G. Asharov, F. Bonchi, D. García Soriano and T. Tassa


26th International World Wide Web Conference (WWW), April 2017, Perth, pp. 957-966


Consider a multilayer graph, where the different layers correspond to different proprietary social networks on the same ground set of users. Suppose that the owners of the different networks (called hosts) are mutually non-trusting parties: how can they compute a centrality score for each of the users using all the layers, but without disclosing information about their private graphs? Under this setting we study a suite of three centrality measures whose algebraic structure allows performing that computation with provable security and efficiency. The first measure counts the nodes reachable from a node within a given radius. The second measure extends the first one by counting the number of paths between any two nodes. The final one is a generalization to the multilayer graph case: not only the number of paths is counted, but also the multiplicity of these paths in the different layers is considered. We devise a suite of multiparty protocols to compute those centrality measures, which are all provably secure in the information-theoretic sense. One typical challenge and limitation of secure multiparty computation protocols is their scalability. We tackle this problem and devise a protocol which is highly scalable and still provably secure. We test our protocols on several real-world multilayer graphs: interestingly, the protocol to compute the most sensitive measure (i.e., the multilayer centrality) is also the most scalable one and can be efficiently run on very large networks.

Research highlights:
  • We initiate investigation in the area of secure and distributed computation of centrality and  social influence measures over multiple, mutually non-trusting, social networks.
  • Our main contribution is a suite of multiparty protocols to compute three different measures of centrality of increasing complexity. Our protocols  are provably secure in the information-theoretic sense.
  • The third of the measures of centrality that we consider is the most sensitive one, as it takes into consideration the multiplicity of paths in the multi-layered graph. For that measure we devise a scalable protocol and empirically show that it can be efficiently run on very large real-world multi-layered graphs.

Read the entire paper here.

Leave a Reply