Method for filtering a graph
AssigneeCelonis SE
InventorsRobert Seilbeck, Willi Mann, Martin Klenk
Life of this patent
Estimating the term…
Abstract
Provided is a computer-implemented method to extract a subgraph from a graph which is stored with a storage device without prior knowledge of the structure of the graph. The graph represents a network. The subgraph starts from at least one selected node into a selected direction. Each directed edge of the graph is composed of an outgoing edge which is connected to a start node and an incoming edge which is connected to an end node. The subgraph is extracted according to a traversal of the graph starting from the at least one selected node into the selected direction according to a predefined graph traversal protocol.
Claims16
A computer-implemented method for extracting a subgraph of a graph the subgraph starting from at least one selected node into a selected direction,
- wherein the graph represents a network and comprises multiple nodes and multiple directed edges,
- wherein each directed edge connects a start node and an end node, wherein each directed edge is composed of an incoming edge which is connected to the end node and an outgoing edge which is connected to the start node,
- wherein each node represents an entity of the network,
- wherein each directed edge represents a relationship between two entities, the method comprising:
- recording, by one or more computer processors, each start node in a first record of a first data structure stored within a storage device, and each end node in a second record of the first data structure,
- wherein each record comprises at least:
- a combination of a number of first attributes, in which an identifier of a node is stored,
- a combination of a number of second attributes, in which an identifier of an incoming edge is stored,
- a combination of a number of third attributes, in which an identifier of an outgoing edge is stored,
- storing, by one or more computer processors, in the first record, the identifier of the start node in the combination of the number of first attributes, and a unique relationship identifier in the combination of the number of third attributes, wherein the unique relationship identifier represents a step along a path in the network,
- storing, by one or more computer processors, in the second record, the identifier of the end node in the combination of the number of first attributes, and the unique relationship identifier in the combination of the number of second attributes,
- wherein a value of the combination of the number of second attributes of the second record matching the value of the combination of the number of third attributes of the first record defines the directed edge between the start node and the end node,
- wherein the subgraph is extracted, by one or more computer processors, according to a traversal of the graph starting from the at least one selected node into the selected direction according to a predefined graph traversal protocol.
Dependencies are inferred from the claim text.