Sharing confidential graph data using multi-level graph summarization with varying data utility and privacy protection

摘要

A first graph comprises multiple nodes and edges. At least one successive summary graph is created, using the original graph as a predecessor. To create a second graph from a first, nodes of the first graph are grouped into a plurality of subsets, and each subset becomes a super-node. For each super-node, the edges of each corresponding node are replaced with one or more super-edges. Each super-edge represents a relationship between a pair of super-nodes. The nodes of the successor graph comprise the super-nodes and the edges of the successor graph comprise the super-edges. The steps are tracked for restoring each omitted edge of each predecessor graph. Based on a determined quantified value for the restoration of each omitted edge of each predecessor graph, customized summary graphs can be created for and presented to specific parties. Determined values can be, for example, monetary or based on trust levels.