Deriving a nested chain of densest subgraphs from a graph
AssigneeHewlett-Packard Development Company, L.P.
InventorsBin Zhang, Meichun Hsu
Life of this patent
Estimating the term…
Abstract
A nested chain of densest subgraphs is derived by a computer from a given graph that has multiple vertices and edges. The two ends of each edge are assigned with respective incident weights, and each vertex is given a vertex weight. A weight balancing process is carried out by the computer to iteratively go through the edges to adjust the incident weights of each edge and the vertex weights of the vertices connected by that edge to reduce a difference between the vertex weights of the two vertices. After the balancing, the vertex weights are put in an ordered sequence according to their values, and a nested chain of densest subgraphs is derived from the ordered sequence.
Claims15
A method of analyzing a graph having multiple vertices and edges, comprising:
- assigning incident weights to first and second ends of each edge in the graph;
- assigning a vertex weight to each vertex in the graph;
- initializing the incident weights of the edges and the vertex weights of the vertices;
- performing a weight-balancing operation on the edges and vertices, including iteratively going through the edges to adjust the incident weights of each edge and the vertex weights of two vertices connected by that edge to reduce a difference between the vertex weights of the two vertices connected by that edge;
- after the balancing operation, outputting the vertex weights in a sequence ordered according to values of the vertex weights;
- and
- deriving a nested chain of densest subgraphs from the ordered sequence based on a change of the vertex weights.
A non-transitory computer readable medium storing computer-executable instructions for analyzing a graph with multiple vertices and edges, the computer-executable instructions upon execution causing a system to perform steps of:
- assigning incident weights to first and second ends of each edge in the graph;
- assigning a vertex weight to each vertex in the graph, the vertex weight of each vertex being a sum of all incident weights of ends of edges incident to that vertex;
- initializing the incident weights of the edges and the vertex weights of the vertices;
- performing a weight-balancing operation on the edges and vertices, including iteratively going through the edges to adjust the incident weights of each edge and the vertex weights of two vertices connected by that edge to reduce a difference between the vertex weights of the two vertices connected by that edge;
- after the balancing operation, outputting the vertex weights in a sequence ordered according to values of the vertex weights;
- and
- identifying a nested chain of densest subgraphs from the ordered sequence based on a change of the vertex weights.
Dependencies are inferred from the claim text.