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_30: We investigate the problem of solving traditional combinatorial graph problems using secure multi-party computation techniques, focusing on the shortest path and the maximum flow problems. To the best of our knowledge, this is the first time these problems have been addressed in a general multi-party computation setting. Our study highlights several complexity gaps and suggests the exploration of various trade-offs, while also offering protocols that are efficient enough to solve real-world problems.
@cite_18: 
@cite_9: This work treats the problem of designing data-oblivious algorithms for classical and widely used graph problems. A data-oblivious algorithm is defined as having the same sequence of operations regardless of the input data and data-independent memory accesses. Such algorithms are suitable for secure processing in outsourced and similar environments, which serves as the main motivation for this work. We provide data-oblivious algorithms for breadth-first search, single-source single-destination shortest path, minimum spanning tree, and maximum flow, the asymptotic complexities of which are optimal, or close to optimal, for dense graphs.
@cite_54: The recent explosion of online networked data and the discovery of universal topological characteristics in real world networks has led to the emergence of a new domain of research, namely, social networks. However, much research in this domain remains unexplored due to the inaccessibility of data of sensitive networks, which include hate networks, trust networks and sexual relationship networks. This paper proposes a secure multiparty protocol which allows a set of parties to compute the underlying network on them. The proposed protocol is information theoretically secure, and its security is further enhanced by a list of security tests, which includes k-anonymity test, check for self loops and weighted edges. Although some solutions have been proposed for this problem earlier, the practicality of each one of those is questionable.
@cite_43: Connections in distributed systems, such as social networks, online communities or peer-to-peer networks, form complex graphs. These graphs are of interest to scientists in fields as varied as marketing, epidemiology and psychology. However, knowledge of the graph is typically distributed among a large number of subjects, each of whom knows only a small piece of the graph. Efforts to assemble these pieces often fail because of privacy concerns: subjects refuse to share their local knowledge of the graph. To assuage these privacy concerns, we propose reconstructing the whole graph privately, i.e., in a way that hides the correspondence between the nodes and edges in the graph and the real-life entities and relationships that they represent. We first model the privacy threats posed by the private reconstruction of a distributed graph. Our model takes into account the possibility that malicious nodes may report incorrect information about the graph in order to facilitate later attempts to de-anonymize the reconstructed graph. We then propose protocols to privately assemble the pieces of a graph in ways that mitigate these threats. These protocols severely restrict the ability of adversaries to compromise the privacy of honest subjects.
@cite_2: We study the problem of privacy-preservation in social networks. We consider the distributed setting in which the network data is split between several data holders. The goal is to arrive at an anonymized view of the unified network without revealing to any of the data holders information about links between nodes that are controlled by other data holders. To that end, we start with the centralized setting and offer two variants of an anonymization algorithm which is based on sequential clustering (Sq). Our algorithms significantly outperform the SaNGreeA algorithm due to Campan and Truta which is the leading algorithm for achieving anonymity in networks by means of clustering. We then devise secure distributed versions of our algorithms. To the best of our knowledge, this is the first study of privacy preservation in distributed social networks. We conclude by outlining future research proposals in that direction.
@cite_20: We investigate how to solve several classical network flow problems using secure multi-party computation. We consider the shortest path problem, the Minimum Mean Cycle problem and the Minimum Cost Flow problem. To the best of our knowledge, this is the first time the two last problems have been addressed in a general multi-party computation setting. Furthermore, our study highlights the complexity gaps between traditional and secure implementations of the solutions, to later test its implementation. It also explores various trade-offs between performance and security. Additionally it provides protocols that can be used as building blocks to solve complex problems. Applications of our work can be found in: communication networks, routing data from rival company hubs; benchmarking, comparing several IT appliances configurations of rival companies; distribution problems, retailer supplier selection in multi-level supply chains that want to share routes without disclosing sensible information; amongst others.
Classical graph algorithms in the context of MPC were first studied by Brickell and Shmatikov in 2006 @cite_18 . The authors proposed secure two party protocols for computing single source and all pair shortest paths problem. Since then, many graph algorithms have been explored in the MPC setting, including BFS, DFS, Dijkstra, minimum spanning tree and classical flow algorithms @cite_30 @cite_20 @cite_9 . Securely constructing an anonymized version of a network distributedly held by a set of parties has been previously studied for various security models @cite_43 @cite_54 @cite_2 .