Non-linear, multi-resolution visualization of a graph

Patent metadata

Field	Value
Publication number	US-10672155-B2
Application number	US-201615238814-A
Country	US
Kind code	B2
Filing date	Aug 17, 2016
Priority date	Aug 17, 2016
Publication date	Jun 2, 2020
Grant date	Jun 2, 2020

Abstract

Methods, systems, and computer program products for non-linear, multi-resolution visualization of a graph are provided herein. A computer-implemented method includes generating multiple sub-graphs derived from an input knowledge graph, wherein the input knowledge graph comprises multiple nodes and multiple edges, and wherein each of the generated sub-graphs comprises a distinct level of resolution; processing an input comprising at least one area of user interest on the input knowledge graph; generating a multi-resolution version of the input knowledge graph by combining two or more of the generated sub-graphs, wherein the two or more sub-graphs are selected based on the at least one area of user interest; and outputting the multi-resolution version of the input knowledge graph to the user via an interactive mechanism.

First claim

What is claimed is:

1. A computer-implemented method, comprising:
generating multiple sub-graphs derived from an input knowledge graph, wherein the input knowledge graph comprises multiple nodes and multiple edges, and wherein each of the generated sub-graphs comprises a distinct level of resolution, wherein each distinct level of resolution comprises a distinct granularity of at least a portion of the input knowledge graph that prioritizes one or more of the multiple nodes of the input knowledge graph relative to the other nodes of the input knowledge graph;
processing an input corresponding to at least one area of user interest on the input knowledge graph;
generating a multi-resolution version of the input knowledge graph that non-linearly varies a zoom level at different points of the multi-resolution version by (i) combining two or more of the generated sub-graphs and (ii) displaying the combined sub-graphs within at least a portion of the input knowledge graph, wherein the two or more sub-graphs are selected based on the at least one area of user interest, wherein said zoom level varies non-linearly at the different points of the multi-resolution version based on the following equation: K/d 2 , wherein d is the distance from the at least one area of user interest, and wherein K is a constant; and
outputting the multi-resolution version of the input knowledge graph to the user via an interactive mechanism;
wherein the steps are carried out by at least one computing device.

2. The computer-implemented method of claim 1 , comprising:
calculating a level of resolution for all portions of the multi-resolution version of the input knowledge graph in response to an input comprising an updated area of user interest.

3. The computer-implemented method of claim 1 , wherein said generating multiple sub-graphs comprises identifying multiple clusters of two or more of the multiple nodes of the input knowledge graph.

4. The computer-implemented method of claim 3 , wherein said identifying multiple clusters comprises implementing one or more semantics-based clustering techniques.

5. The computer-implemented method of claim 1 , wherein said generating multiple sub-graphs comprises summarizing the input knowledge graph via one or more degree distributions.

6. The computer-implemented method of claim 1 , wherein said generating multiple sub-graphs comprises summarizing the input knowledge graph via one or more clustering coefficients.

7. The computer-implemented method of claim 1 , wherein the at least one area of user interest comprise (i) a source node and (ii) a target node.

8. The computer-implemented method of claim 1 , wherein said combining two or more of the generated sub-graphs comprises:
inserting the selected two or more sub-graphs at corresponding positions of the input knowledge graph; and
removing one or more remaining positions of the input knowledge graph.

9. The computer-implemented method of claim 1 , comprising:
adjusting the size of the one or more nodes of the two or more selected sub-graphs.

10. The computer-implemented method of claim 9 , wherein said adjusting is based on screen resolution of a device from which the at least one area of user interest input is provided.

11. The computer-implemented method of claim 9 , wherein said adjusting is based on screen size of a device from which the at least one area of user interest input is provided.

12. The computer-implemented method of claim 9 , wherein said adjusting is based on the number of nodes present in a path captured in the two or more selected sub-graphs.

13. The computer-implemented method of claim 9 , wherein said adjusting is based on at least one of: (i) a predetermined maximum node size, and (ii) a predetermined minimum node size.

14. A computer program product comprising a non-transitory computer readable storage medium having program instructions embodied therewith, the program instructions executable by a device to cause the device to:
generate multiple sub-graphs derived from an input knowledge graph, wherein the input knowledge graph comprises multiple nodes and multiple edges, and wherein each of the generated sub-graphs comprises a distinct level of resolution, wherein each distinct level of resolution comprises a distinct granularity of at least a portion of the input knowledge graph that prioritizes one or more of the multiple nodes of the input knowledge graph relative to the other nodes of the input knowledge graph;
process an input corresponding to at least one area of user interest on the input knowledge graph;
generate a multi-resolution version of the input knowledge graph that non-linearly varies a zoom level at different points of the multi-resolution version by (i) combining two or more of the generated sub-graphs and (ii) displaying the combined sub-graphs within at least a portion of the input knowledge graph, wherein the two or more sub-graphs are selected based on the at least one area of user interest, wherein said zoom level varies non-linearly at the different points of the multi-resolution version based on the following equation: K/d 2 , wherein d is the distance from the at least one area of user interest, and wherein K is a constant; and
output the multi-resolution version of the input knowledge graph to the user via an interactive mechanism.

15. A system comprising:
a memory; and
at least one processor coupled to the memory and configured for:
generating multiple sub-graphs derived from an input knowledge graph, wherein the input knowledge graph comprises multiple nodes and multiple edges, and wherein each of the generated sub-graphs comprises a distinct level of resolution, wherein each distinct level of resolution comprises a distinct granularity of at least a portion of the input knowledge graph that prioritizes one or more of the multiple nodes of the input knowledge graph relative to the other nodes of the input knowledge graph;
processing an input corresponding to at least one area of user interest on the input knowledge graph;
generating a multi-resolution version of the input knowledge graph that non-linearly varies a zoom level at different points of the multi-resolution version by (i) combining two or more of the generated sub-graphs and (ii) displaying the combined sub-graphs within at least a portion of the input knowledge graph, wherein the two or more sub-graphs are selected based on the at least one area of user interest, wherein said zoom level varies non-linearly at the different points of the multi-resolution version based on the following equation: K/d 2 , wherein d is the distance from the at least one area of user interest, and wherein K is a constant; and
outputting the multi-resolution version of the input knowledge graph to the user via an interactive mechanism.

16. A computer-implemented method, comprising:
generating multiple sub-maps derived from an input map, wherein the input map comprises multiple nodes and multiple edges, and wherein each of the generated sub-maps comprises a distinct level of resolution, wherein each distinct level of resolution comprises a distinct granularity of at least a portion of the input map that prioritizes one or more of the multiple nodes of the input map relative to the other nodes of the input map;
processing an input corresponding to at least one area of user interest on the input map;
generating multi-resolution version of the input map that non-linearly varies a zoom level at different points of the multi-resolution version by (i) combining two or more of the generated sub-maps and (ii) displaying the combined sub-m

Assignees

• IBM

Inventors

• Contractor Danish
• Parashar Varun
• Rajput Nitendra

Classifications

• G06F16/9024

  Graphs; Linked lists (G06F16/9027 takes precedence) · CPC title

• G06F16/35

  Clustering; Classification · CPC title

• G06T11/206 Primary

  Physics · mapped topic

• G06K9/6219

  Physics · mapped topic

• G06T3/4076

  using the original low-resolution images to iteratively correct the high-resolution images · CPC title