Finding Quasi-identifiers for K-Anonymity Model by the Set of Cut-vertex

摘要

The rapid development of data publishing andinformation access technology bring a growing number ofproblems in privacy leakage. In order to avoid linking attackshappened between attributes, K-anonymity model wasproposed and become the most widely used in privacypreserving data publishing. Identification of quasi-identifiers(QIs) is one of the primary problems which will directly affectthe effectiveness of K-anonymity method. However, most of theexisting methods ignored this problem or just choose QIsempirically. These will greatly reduce the validity ofK-anonymity method as well as the utility of anonymous data.In this paper, we study the problem of finding QIs for privacypreserving data publishing method based on K-anonymitymodel. Firstly, we analyze the roles of QIs from the view ofindependence of sets, and define it as a collection of attributesthat can separate sensitive attributes from the othernon-sensitive attributes. Then, we propose a constructionmethod for attribute graph based on relationship matrix, whichcan represent potential connectivity of publishing data,published data and external knowledge. Finally, we put forwardan identification algorithm for QIs based on the concept ofcut-vertex, which is aiming to find the necessary and minimumQIs. The proposed algorithm is useful to avoid inconvenienceand inaccuracy caused by artificial partition of QIs, and can beapplied in data publishing situations with multiple sensitiveattributes after some extension. Experiments and analysis showthat the proposed identification algorithm has better partitionability and lower computational complexity. Therefore, it hasgood practical value in the application environment ofpublishing of big data.