Connection nature between nodes in graph structure
AssigneeMicrosoft Technology Licensing, LLC
InventorsLeo Moreno BETTHAUSER, Maurice DIESENDRUCK, Harsh SHRIVASTAVA
Life of this patent
Estimating the term…
Abstract
The interpretation of a graph data structure represented on a computing system in which the connection between a pair of nodes in the graph may be interpreted by which intermediary entity (node or edge) on a path (e.g., a shortest path) between the node pair is most dominant. That is, if the intermediary entity were not present, a detour path is determined. The greater the difference between the detour path and the original path, the more significant that intermediary entity is. The significance of multiple intermediary entities in the original path may be determined in this way.
Claims20
A computing system comprising:
- one or more processors;
- and
- one or more hardware storage devices that store instructions that are executable by the one or more processors to cause the computing system to:
- determine a first path between a set of nodes, which includes a first terminal node, a second terminal node, and a first intermediary node, wherein the first path includes intermediary edges that operate as links between the nodes in the set;
- determine a detour path between the first terminal node and the second terminal node, wherein the detour path omits the first intermediary node and includes a second intermediary node;
- determine a difference between the first path and the detour path, wherein the difference between the first path and the detour path is based on which edges are included in the detour path and which edges are included in the first path;
- and
- assign a significance score to the first intermediary node based on the determined difference between the first path and the detour path.
A method comprising:
- determining a first path between a set of nodes, which includes a first terminal node, a second terminal node, and a first intermediary node, wherein the first path includes intermediary edges that operate as links between the nodes in the set;
- determining a detour path between the first terminal node and the second terminal node, wherein the detour path omits the first intermediary node and includes a second intermediary node;
- determining a difference between the first path and the detour path, wherein the difference between the first path and the detour path is based on which edges are included in the detour path and which edges are included in the first path;
- and
- assigning a significance score to the first intermediary node based on the determined difference between the first path and the detour path.
A computer system comprising:
- one or more processors;
- and
- one or more hardware storage devices that store instructions that are executable by the one or more processors to cause the computer system to:
- determine a first path between a set of nodes, which includes a first terminal node, a second terminal node, and a first intermediary node, wherein the first path includes intermediary edges that operate as links between the nodes in the set;
- determine a detour path between the first terminal node and the second terminal node, wherein the detour path omits the first intermediary node and includes a second intermediary node, which was not previously included in the first path;
- determine a difference between the first path and the detour path, wherein the difference between the first path and the detour path is based on which edges are included in the detour path and which edges are included in the first path;
- assign a significance score to the first intermediary node based on the determined difference between the first path and the detour path;
- and
- visually emphasize at least one of the first intermediary node or the second intermediary node.
Dependencies are inferred from the claim text.