Patent ID: 8590049

Claim:
A method for providing an anonymization of data, comprising: receiving, by a processor, a request for anonymizing, wherein the request comprises a bipartite graph for a plurality of associations between a plurality of nodes of a first type and a plurality of nodes of a second type, wherein each association of the plurality of associations comprises a correlation between one of the plurality of nodes of the first type and one of the plurality of nodes of the first type; placing, by the processor, each node of the first type of the bipartite graph in a safe group, wherein the placing comprises: selecting a node of the first type for placing in a safe group, wherein the safe group is a group that has no other node of the first type that has an association with a particular node of the plurality of nodes of the second type, wherein the node of the first type that is selected has an association with the particular node of the plurality of nodes of the second type; and starting a new group that contains the node that is selected, when attempts have been made to place the node that is selected in each group of a partial grouping, and placing the node in any one of each group of the partial grouping would make any one of each group of the partial grouping in which the node is placed unsafe; incrementing, by the processor, a value of a group size by one and repeating the placing each node of the first type in the safe group, when a maximum group size has not been reached and when there is a group with fewer nodes than the value of the group size; and providing, by the processor, an anonymized graph that encodes the plurality of associations of the bipartite graph, when a safe group for all nodes of the first type of the bipartite graph is found.