# US 2020/0394249 A1 · Efficient data propagation in a computer network

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2020/0394249 A1
- Document ID: US20200394249A1
- Status: Published application
- Kind: A1
- Application number: 16/463,934
- Filed: 2016-11-25
- Published: 2020-12-17
- Earliest claimed: 2016-11-25
- Assignees: Siemens Aktiengesellschaft
- Applicants: Siemens Aktiengesellschaft
- Inventors: Regine Meunier; Tobias Emrich; Christian Frey; Matthias Renz; Andreas Zuefle
- Web page: https://patentgrep.com/patent/US20200394249A1

## CPC

- G06F 17/10: Complex mathematical operations {(function generation by table look-up G06F1/03; evaluation of elementary functions by calculation G06F7/544)}
- G06N 7/01: Probabilistic graphical models, e.g. probabilistic networks
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS

## Abstract

Propagating data in a technical network by considering runtime requirements. A component tree data structure is generated for a probabilistic graph representing the technical network and its technical constraints. On the component tree a propagation algorithm is applied, which iteratively determines an optimal edge in the generated component tree, which maximizes an expected information flow to a query node to and/or from each network node by considering the technical network constraints and by executing a Monte-Carlo sampling for estimation of the expected information flow for the cyclic components and by computing the expected information flow of the non-cyclic components analytically and which updates the component tree iteratively with each determined optimal edge and re-estimates the expected information flow in the updated component tree for providing a result with nodes in the technical network for data propagation, so that information flow is maximized by considering technical network constraints.

## Claims

### Claim 1

A method for reliably optimizing data propagation in a technical network with a plurality of nodes and edges by processing technical network constraints for activating the edges in the technical network, wherein the technical network is represented as a probabilistic graph with edges and assigned probability values, the method comprising:
generating a component tree as data structure by partitioning the probabilistic graph into independent components, representing a subset of the probabilistic graph and comprising cyclic and non-cyclic components, wherein an edge in the component tree represents a parent-child relationship between the components:
iteratively determining an optimal edge in the generated component tree, which maximizes an expected information flow to a query node to and/or from each network node by processing the technical network constraints and by:
executing a Monte-Carlo sampling for estimation of the expected information flow for the cyclic components, and
computing the expected information flow of the non-cyclic components analytically;
updating the component tree iteratively with each determined optimal edge and re-estimating the expected information flow in the updated component tree; and
calculating an optimal set of edges and based thereon providing a result with nodes in the technical network for data propagation, so that information flow is maximized by processing technical network constraints.

### Claim 2 (depends on 1)

The method according to claim 1, wherein iteratively determining the optimal edge is executed by applying a heuristic, exploiting features of the component tree.

### Claim 3 (depends on 2)

The method according to claim 2, wherein the heuristic is based on a Greedy algorithm.

### Claim 4 (depends on 1)

The method according to claim 1, wherein iteratively determining the optimal edge is optimized by component memorization:
skipping the step of executing a Monte-Carlo sampling for estimation of the expected information flow of the cyclic components which remained unchanged and by
memorizing and re-using calculated values of the information flow for the unchanged components.

### Claim 5 (depends on 1)

The method according to claim 1, wherein the Monte-Carlo sampling is optimized by pruning the sampling and by sampling confidence intervals, so that probing an edge is stopped whenever another edge has a higher information flow with a certain degree of confidence.

### Claim 6 (depends on 1)

The method according to claim 1, the Monte-Carlo sampling is optimized by application of a delayed sampling, which considers the costs for sampling a candidate edge in relation to its information gain in order to minimize the amount of candidate edges to be sampled.

### Claim 7 (depends on 1)

The method according to claim 1, further comprising:
determining runtime requirements for providing the result,
so that the iterative determination of an optimal edge is executed by selecting an edge selection algorithm so that the determined runtime requirements are met.

### Claim 8 (depends on 1)

The method according to claim 1, wherein the number of edges in the technical network, which can be activated, is limited due to the technical network constraints.

### Claim 9 (depends on 1)

The method according to claim 1, wherein computing expected information flow of the non-cyclic components analytically is based on the following equation:
E

(
(
∑
v
∈
V


(
Q
,
v
,
G
)
)
·
W

(
v
)
)
=
∑
v
∈
V

E

(

(
Q
,
v
,
G
)
)
·
W

(
v
)
,
wherein G=(V, E, W, P) is a probabilistic directed graph, where V is a set of vertices v, E ⊆V×V is a set of edges, W: V→+ is a function that maps each vertex to a positive value representing an information weight of the corresponding vertex and wherein Q∈V is a node.

### Claim 10 (depends on 1)

The method according to claim 1, wherein determining an optimal edge is executed by selecting a locally most promising edge out of a set of candidate edges, for which the expected information flow can be maximized, wherein the estimation of the expected information flow for a candidate edge is executed only on those components of the component tree which are affected, if the candidate edge would be included in the component tree of the technical network.

### Claim 11 (depends on 1)

The method according to claim 1, further comprising:
aggregating independent subgraphs of the probabilistic graph efficiently, while exploiting a sampling solution for components of the graph MaxFlow that contain cycles.

### Claim 12

A control node in a technical network with a plurality of nodes and connections between the nodes, which is represented in a probabilistic graph, wherein an edge in the graph is assigned with a probability value, representing a respective technical network constraint for activating the edges in the technical network, wherein the control node comprises:
an input interface for determining technical network parameters and network constraints;
a processor which is adapted for providing a probabilistic graph for the technical network and for decomposing the probabilistic graph into independent components and for generating a component tree structure as data structure
a memory for storing that data structure;
wherein the processor is further adapted to iteratively determine an optimal edge in the generated component tree, which maximizes an expected information flow to a query node to and/or from each node by processing the determined technical network constraints and by:
executing a Monte-Carlo sampling for estimation of the expected information flow for cyclic components in the component tree, and
computing the expected information flow of the non-cyclic components in the component tree analytically
and wherein the processor is adapted to update the component tree iteratively with each determined optimal edge and to re-estimate the expected information flow in the updated component tree and to calculate an optimal set of edges and based thereon
wherein the control node further comprises an output interface for providing a result with nodes in the technical network for data propagation, so that information flow is maximized by processing technical network constraints.

### Claim 13 (depends on 12)

The control node according to claim 12, wherein the control node further comprises an optimizer which is adapted to determine runtime requirements and to apply optimization algorithms for handling a tradeoff between effectiveness and efficiency of the processor for providing the result.

### Claim 14 (depends on 12)

The control node according to claim 12 directed on the control node, wherein the control node is implemented on a sending node for sending data to a plurality of network nodes.

### Claim 15 (depends on 12)

The control node according to claim 12 directed on the control node, wherein the control node is implemented on a receiving node for receiving data from a plurality of network nodes, comprising sensor nodes.

### Claim 16 (depends on 1)

A computer network system for use in a technical network with a plurality of nodes and connections between the nodes, which is represented in a probabilistic graph, wherein an edge in the graph is assigned with a probability value, representing a respective technical network constraint for activating said edge in the network, comprising:
a control node, which is adapted to control the propagation of data in the technical network according to the method of claim 1.