Sequential Clustering for Anonymizing Social Networks

Abstract-The main contributions in this paper are sequential clustering algorithm for anonymizing a social network and a measure that quantifies the information loss in the anonymization process to preserve privacy. The algorithm significantly outperforms the SaNGreeA algorithm due to Campan and Truta which is the leading algorithm for achieving anonymity in networks by means of clustering. SaNGreeA builds the clustering greedily, one cluster at a time by selecting the seed node and then keep adding to it the next node. The main disadvantage of SaNGreeA is it does not contain any mechanism to correct bad clustering decisions which are made earlier and also it includes structural information loss which may be evaluated only when all of the clustering is defined. The sequential clustering algorithm does not suffer from those problems because in each stage of its execution it has a full clustering. It always makes decisions according to the real measure of information loss. Sequential clustering algorithm constantly allows the correction of previous clustering decisions.