ClusterBased Anonymization of Directed Graphs Social network providers anonymize graphs storing usersu0027 relationships to protect users from being reidentified. Despite the fact that most of the relationships are directed (e.g., follows), few works (e.g., the Paireddegree 1 and KInu0026OutDegree Anonymity 2) have been designed to work with directed graphs. In this paper, we show that given a graph, DGA 1and DSNDGKIODA 2 are not always able to generate its anonymized version. We overcome this limitation by presenting the Clusterbased Directed Graph Anonymization Algorithm(CDGA) and prove that, by choosing the appropriate parameters, CDGA can generate an anonymized graph satisfying both the Paired kdegree 1 and KInu0026OutDegree Anonymity 2. Also, we present the Outand InDegree Information Loss Metric to minimize the number of changes made to anonymize the graph. We conduct extensive experiments on three reallife data sets to evaluate the effectiveness of CDGA and compare the quality of the graphs anonymized by CDGA, DGA, and DSNDGKIODA. The experimental results show that we can generate anonymized graphs, by modifying less than 0.007% of edges in the original graph.

Network Identification and Authentication Research on networks is commonly performed using anonymized network data for various reasons such as protecting data privacy. Under such circumstances, it is difficult to verify the source of network data, which leads to questions such as: Given an anonymized graph, can we identify the network from which it is collected? Or if one claims the graph is sampled from a certain network, can we verify it? The intuitive approach is to check for subgraph isomorphism. However, subgraph isomorphism is NPcomplete; hence, infeasible for most large networks. Inspired by biometrics studies, we address these challenges by formulating two new problems: network identification and network authentication. To tackle these problems, similar to research on human fingerprints, we introduce two versions of a network identity: (1) embeddingbased identity and (2) distributionbased identity. We demonstrate the effectiveness of these network identities on various realworld networks. Using these identities, we propose two approaches for network identification. One method uses supervised learning and can achieve an identification accuracy rate of 94.7%, and the other, which is easier to implement, relies on distances between identities and achieves an accuracy rate of 85.5%. For network authentication, we propose two methods to build a network authentication system. The first is a supervised learner and provides a low false accept rate and the other method allows one to control the false reject rate with a reasonable false accept rate across networks. Our study can help identify or verify the source of network data, validate networkbased research, and be used for networkbased biometrics.