Source Localization for Networks With Partial Timestamps

Description

Source localization can provide valuable insight into many real world problems, like finding the outbreak of an infectious disease, the genesis of malware or computer viruses, and origin of erroneous or classified information. Source localization can be very challenging without knowing when initial and subsequent infections occur. Nodes within a computer network continuously communicate with one another, and keep track of the times they received new information from the network. While timestamps for every node within a network are often unavailable, timestamps for some of the nodes within the network are almost always available. However, current localization techniques ignore any timestamp information, ranking nodes by rumor centrality, infection eccentricity, and other computationally expensive algorithms that consider every possible path of infection.

Researchers at ASU have developed high performance algorithms that leverage timestamp information to minimize the number of potential infection paths. Paths are determined by earliest infection first, for example, a node with a later timestamp could not possibly infect a node with an earlier timestamp, and nodes are ranked based on paths with the briefest time intervals between infections. If timestamps are missing, two end nodes with time stamps can be used to calculate infection time of the nodes in between, which is supported by the quadratic nature of the algorithm’s ranking function. Experimental evaluations with real-world data show that these algorithms significantly improve the ranking accuracy and calculation time needed to locate a source of infection.

Potential Applications

  • Ad Tracking
  • Disease Surveillance
  • Malware & Antivirus Software
  • Network Security
  • Social Media

Benefits and Advantages

  • Accuracy – Utilizing timestamps enhances ranking precision.
  • Efficiency – Computationally cheap algorithm saves processing power and reduces bandwidth consumption.
  • Performance – Faster localization times due to a more effective algorithm.
  • Timestamps – Reduce the number of potential infection paths during ranking.
  • Versatility – Missing timestamps are reconstructed so that all nodes can be ranked within networks where only partial timestamp information is available.

For more information about the inventor(s) and their research, please see

Dr. Lei Ying's directory webpage

Case ID:
M15-001P
Published:
07-01-2015
Last Updated:
12-05-2018

Inventor(s):

Kai Zhu Lei Ying

Patent Information

For More Information, Contact