Federated k-Core Decomposition: A Secure Distributed Approach

As one of the most well-studied cohesive subgraph models, the k-core is widely used to find graph nodes that are “central” or “important” in many applications, such as biological networks, social networks, ecological networks, and financial networks. For Decentralized Online Social Networks (DOSNs), where each vertex is a client as a single computing unit, distributed k-core decomposition algorithms have already been proposed. However, current distributed approaches fail to adequately protect privacy and security. In today’s data-driven world, data privacy and security have attracted more and more attention, e.g., DOSNs are proposed to protect privacy by storing user information locally without using a single centralized server. In this work, we are the first to propose the secure version of the distributed k-core decomposition.