We consider the problem of detecting an epidemic in a population where individual diagnoses are extremely noisy. We show that only local (possibly only approximate) knowledge of the contact network suffices to accurately detect the epidemic. The motivation for this problem is the plethora of examples (influenza strains in humans, or computer viruses in smartphones, etc.) where reliable diagnoses are scarce, but noisy data plentiful. In flu or phone-viruses, exceedingly few infected people/phones are professionally diagnosed (only a small fraction go to a doctor) but less reliable secondary signatures (e.g., people staying home, or greater-than-typical upload activity) are more readily available.

These secondary data are often plagued by unreliability: many people with the flu do not stay home, and many people that stay home do not have the flu. We identify the regime where knowledge of the contact network enables finding the needle in the haystack: we provide a distributed, efficient and robust algorithm that correctly identifies the existence of a spreading epidemic from highly unreliable local data. We addressed the problem of malware detection from a dynamic perspective as well, and showed that monitoring the dynamics of these “weak signatures” enables us to detect an infection very shortly after the initial infiltration occurred. This may assist in limiting the spread of a contagion to a substantial part of the network.

Additionally, I'll briefly describe other parts of my work. In particular, I'll discuss a dynamic network formation game for heterogeneous networks, and consider its application for the Internet's Autonomous Systems graph.