In this paper, we formalize the notion of distributed sensitive social networks (DSSNs), which encompasses networks like enmity networks, financial transaction networks, supply chain networks and sexual relationship networks. Compared to the well studied traditional social networks, DSSNs are often more challenging to study, given the privacy concerns of the individuals on whom the network is knit. In the current work, we envision the use of secure multiparty tools and techniques for performing privacy preserving social network analysis over DSSNs. As a step towards realizing this, we design efficient data-oblivious algorithms for computing the K-shell decomposition and the PageRank centrality measure for a given DSSN. The designed data-oblivious algorithms can be translated into equivalent secure computation protocols. We also list a string of challenges that are needed to be addressed, for employing secure computation protocols as a practical solution for studying DSSNs.
@cite_41: 
@cite_31: Social network analysis (SNA) is now a commonly used tool in criminal investigations, but evidence gathering and analysis is often restricted by data privacy laws. We consider the case where multiple investigators want to collaborate, but do not yet have sufficient evidence that justifies a plaintext data exchange. This paper proposes a solution for privacy-preserving social network analysis where several investigators can collaborate without actually exchanging sensitive private information. An investigator can request data from other sites to augment his view without revealing personally identifiable data. The investigator can compute important metrics by means of a SNA on the subject while keeping the entire social network unknown him.
@cite_47: Consider a multi-layered 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 multi-layered 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 multi-layered graphs: interestingly, the protocol to compute the most sensitive measure (i.e., the multi-layered centrality) is also the most scalable one and can be efficiently run on very large networks.
@cite_39: Motivated by the fast‐growing need to compute centrality indices on large, yet very sparse, networks, new algorithms for betweenness are introduced in this paper. They require O(n + m) space and run in O(nm) and O(nm + n2 log n) time on unweighted and weighted networks, respectively, where m is the number of links. Experimental evidence is provided that this substantially increases the range of networks for which centrality analysis is feasible. The betweenness centrality index is essential in the analysis of social networks, but costly to compute. Currently, the fastest known algorithms require ?(n 3) time and ?(n 2) space, where n is the number of actors in the network.
There exist works that have aimed at designing secure MPC algorithms for a few network measures. These works have generally been motivated by some particular application scenario. To employ SNA for criminal investigation, Kerschbaum and Schaad @cite_31 propose secure multiparty protocols for closeness and betweenness centrality measures. They assume a different definition of betweenness centrality compared to the classical one specified by Brandes @cite_39 ). Furthermore, they employ the adjacency matrix graph representation and hence their protocols are not very efficient for sparse graphs. @cite_41 propose secure multiparty protocols for degree distribution, closeness centrality, Pagerank and K-shell decomposition for the adjacency matrix representation. Employing the ORAM primitive and the edgelist graph representation, the Pagerank and K-shell decomposition protocols designed in the current paper asymptotically outperforms the algorithms in the above work. @cite_47 study the a set of centrality measures over multilayer networks distributedly held by a set of individuals organizations. They propose information theoretic secure MPC protocols for distance based centrality measures.