GRAPH PRUNING IN HIPERGRAPH

摘要

One embodiment of the present invention provides a system for graph pruning. During operation, the system identifies a connected component in a graph comprising one or more vertices. A respective vertex of the graph represent an element in a data set, an edge between two vertices represents a type and strength of relationship between the vertices. The system identifies a connected component to be smaller than a minimum graph traversal threshold associated with a query for the graph. This minimum graph traversal threshold indicates a minimum number of traversal steps needed for the query. The system then generates a second graph by pruning the connected component from the graph. This second graph is processed to extract information of interest from the data set.

主权项

1. A computer-executable method for pruning a graph, comprising:
identifying, by a computer, a connected component in a graph comprising one or more vertices, wherein a respective vertex represent an element in a data set, and wherein an edge between two vertices represents a type and strength of relationship between the vertices; identifying a connected component to be smaller than a minimum graph traversal threshold associated with a query for the graph, wherein the minimum graph traversal threshold indicates a minimum number of traversal steps needed for the query; and generating a second graph by pruning the connected component from the graph, wherein the second graph is processed to extract information of interest from the data set.