Back to results
US 2016/0110365 A1Published application
Systems and methods for locating contagion sources in networks with partial timestamps
OwnerKai Zhu, Lei Yinginventors
Life of this patent
Estimating the term…
Abstract
Systems and methods of identifying a contagion source when partial timestamps of a contagion process are disclosed. A source localization problem is formulated as a ranking problem on graphs, where infected nodes are ranked according to their likelihood of being the source.
Claims20
A method for identifying the source device of data, the method comprising:
- constructing a directed graph comprising a plurality of nodes and at least one directed edge connecting each of the plurality of nodes to at least one other node of the plurality of nodes, wherein each node of the plurality of nodes represents a computing device of a network of a plurality of computing devices in communication over the network;
- determining a subset of the plurality of nodes of the directed graph, the subset comprising computing devices that have received a particular dataset over the network, wherein a first portion of the subset of the plurality of nodes comprises a timestamp indicating when a particular computing device received the particular dataset;
- for each particular node in the subset of the plurality of nodes:
- defining a plurality of spreading tree graphs of the subset of the plurality of nodes of the directed graph, each of the plurality of spreading tree graphs comprising the first portion of the subset of the plurality of nodes and a second subset of the plurality of nodes, the second subset comprising an estimated timestamp estimating when a particular computing device represented in the second subset of the plurality of nodes received the particular dataset;
- calculating a cost estimate for each of the plurality of spreading tree graphs;
- and
- associating at least one calculated cost estimate with the particular node of the subset of the plurality of nodes of the directed graph;
- and
- ranking the nodes of the subset of the plurality of nodes of the directed graph based on the at least one calculated cost estimate associated with each node of the subset of the plurality of nodes of the directed graph.
6 more elements
A system for managing a network, the system comprising:
- at least one processing device;
- and
- a tangible computer-readable medium with one or more executable instructions stored thereon, wherein the at least one processing device executes the one or more instructions to perform the operations of:
- constructing a directed graph comprising a plurality of nodes and at least one directed edge connecting each of the plurality of nodes to at least one other node of the plurality of nodes, wherein each node of the plurality of nodes represents a computing device of a network of a plurality of computing devices in communication over the network;
- determining a subset of the plurality of nodes of the directed graph, the subset comprising computing devices that have received a particular dataset over the network, wherein a first portion of the subset of the plurality of nodes comprises a timestamp indicating when a particular computing device received the particular dataset;
- for each particular node in the subset of the plurality of nodes:
- defining a plurality of spreading tree graphs of the subset of the plurality of nodes of the directed graph, each of the plurality of spreading tree graphs comprising the first portion of the subset of the plurality of nodes and a second subset of the plurality of nodes, the second subset comprising an estimated timestamp estimating when a particular computing device represented in the second subset of the plurality of nodes received the particular dataset;
- calculating a cost estimate for each of the plurality of spreading tree graphs;
- and
- associating at least one calculated cost estimate with the particular node of the subset of the plurality of nodes of the directed graph;
- and
- ranking the nodes of the subset of the plurality of nodes of the directed graph based on the at least one calculated cost estimate associated with each node of the subset of the plurality of nodes of the directed graph.
9 more elements
Dependencies are inferred from the claim text.