Manipulation and management of links and nodes in large graphs

• US 8,810,576 B2
• Filed: 04/13/2010
• Issued: 08/19/2014
• Est. Priority Date: 04/13/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Duplessis, Jean-Pierre, Lovett, Christopher J.
• Primary Examiner(s): Wu, Xiao
• Assistant Examiner(s): Tseng, Charles
• Application Number:
  US12/758,816
• Publication Number:
  US 20110249002A1
• Time in Patent Office: 1,589 Days
• Field of Search: 345/440
• US Class Current: 345/440
• CPC Class Codes: G06F 16/904 Browsing; Visualisation therefor for navigating the web G06F16/954; browsing optimisation for the web G06F16/957
• CPC Class Codes: G06F 3/0481 based on specific properties of the displayed interaction object or a metaphor-based environment, e.g. interaction with desktop elements like windows or icons, or assisted by a cursor's changing behaviour or appearance
• CPC Class Codes: G06F 3/0482 Interaction with lists of selectable items, e.g. menus
• CPC Class Codes: G06F 3/04845 for image manipulation, e.g. dragging, rotation, expansion or change of colour
• CPC Class Codes: G06T 11/206 Drawing of charts or graphs

Abstract

Scalable architecture for managing and rendering a large graph containing a large number of nodes and edges. The user can group arbitrary nodes to encapsulate complexity without losing any of the cross-group edges dependencies. All edges of the nodes contained in the group are rolled up into roll-up links (or “arteries”) where the graphical thickness indicates relatively how many links are bundled. By collapsing groups the entire view gives the user a clearer understanding of the graph. Information related to the groups and links is retained for drill-into to obtain the details inside each group on the same canvas and for user navigation across groups.

Claims

1. A computer-implemented graph visualization system, comprising:

a computer comprising a processing unit coupled to a memory, the memory storing executable instructions comprising;

a graph visually presented via a user interface, the graph presented as an arrangement of nodes and links between the nodes visually represented in a view via a user interface, the links comprising a forward link and a back link;

a scaling component that incrementally scales the view of the graph based on operations on the nodes and the links, the operations include collapse of nodes into groups and links into roll-up links and expansion of the groups and the roll-up links, wherein the scaling component graphically replaces links between a node and a group or between groups with a roll-up link that visually conveys dependency between the node and the group or between the groups with a visually-displayed thickness of the roll-up link indicative relatively of a quantity of dependencies that exist in a given direction and a link count value which indicates the quantity of dependencies that are represented by the roll-up link; and

a navigation tool that facilitates incremental access to collapsed content and update of the graph view of expanded content, when the navigation tool is hovered over a desired link, an information panel is presented that displays source and target node information and an additional action a user can take to obtain an additional option about the desired link.

2. The system of claim 1, wherein the scaling component associates a group of nodes with a group graphic that circumscribes the nodes, a group label, a node count value, and an expansion operator to expand the group of nodes.

3. The system of claim 2, wherein the scaling component enables further collapse of the group of nodes into a box that hides the associated nodes, the box includes the group label, and associated links.

4. The system of claim 2, wherein the scaling component enables nested group of nodes of the group of nodes, the nested group of nodes having a nested group label and associated roll-up link.

5. The system of claim 1, wherein the scaling component presents cross-group links based on selection of a node in a group of the cross-groups.

6. The system of claim 1, wherein the navigation tool facilitates exposure of only collapsed nodes and roll-up links relative to a selected node.

7. The system of claim 1, wherein the navigation tool facilitates creation of an updated visualization based on extraction of nodes and links relative to selection of a link or a node.

8. The system of claim 1, the memory further storing executable instructions comprising:

presenting a navigation history as code that traces a user back through the graph.

9. A computer-implemented graph visualization system, comprising:

a computer comprising a processing unit coupled to a memory, the memory storing executable instructions comprising;

a graph visually presented via a user interface, the graph presented as an arrangement of nodes and links between the nodes visually represented via a user interface, the links comprising a forward link and a back link;

a scaling component that incrementally scales the graph based on operations on the nodes and the links, the operations include collapse of nodes into groups and links into roll-up links and expansion of the groups and the roll-up links, wherein the scaling component graphically replaces links between a node and a group or between groups with a roll-up link that visually conveys dependency between the node and the group or between the groups with a visually-displayed thickness of the roll-up link indicative relatively of a quantity of dependencies that exist in a given direction and a link count value which indicates the quantity of dependencies that are represented by the roll-up link; and

a navigation tool that facilitates incremental access to collapsed content and update of the graph relative to exposed content, when the navigation tool is hovered over a desired link, an information panel is presented that displays source and target node information and an additional action a user can take to obtain an additional option about the desired link.

10. The system of claim 9, wherein the scaling component associates a group of nodes with a group graphic that circumscribes the nodes, a group label, a node count value, and an expansion operator to expand the group of nodes, and enables further collapse of the group of nodes into a box that hides the associated nodes, the box includes the group label, and associated links.

11. The system of claim 9, wherein the scaling component enables nested groups of nodes of the group of nodes, the nested group of nodes having a nested group label and associated roll-up link, the scaling component presents cross-group links of cross-groups and nested groups based on selection of a node in a group of the cross-groups or nested group.

12. The system of claim 9, wherein the navigation tool facilitates exposure of only collapsed nodes and roll-up links relative to a selected node and creation of a new graph based on extraction of nodes and links relative to selection of a link or a node.

13. The system of claim 9, the memory further storing executable instructions comprising:

providing a navigation history so that a user can retrace user steps back through the graph.

14. A computer-implemented graph visualization method executable via a processor, comprising:

presenting a graph as an arrangement of nodes and link dependencies between nodes, the links comprising a forward link and a back link;

collapsing, by the processor, nodes of the graph into groups of nodes;

consolidating, by the processor, link dependencies between the groups into a roll-up link, wherein hovering over the roll-up link causes link information to be presented; and

navigating nodes and links of the groups via a navigation tool to expose graph content, wherein when the navigation tool is hovered over a desired link, an information panel is presented that displays source and target node information and an additional action a user can take to obtain an additional option about the desired link.

15. The method of claim 14, further comprising collapsing a group into a nested group that hides associated nodes.

16. The method of claim 14, further comprising selecting a link via the navigation tool and extracting all nodes and links associated with the selected link.

17. The method of claim 14, further comprising exposing cross-group links associated with a node selected in a group.

18. The method of claim 14, further comprising presenting cross-group links as an overlay to the groups.

19. The method of claim 14, further comprising navigating to an opposite end of a cross-group link via expanded collapsed groups and roll-up links surfaced on a graph pathway to the opposite end.