SYSTEMS AND METHODS FOR LOCATING CONTAGION SOURCES IN NETWORKS WITH PARTIAL TIMESTAMPS

摘要

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.

主权项

1. 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; andassociating 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.