Ph.D Thesis

Ph.D StudentMeirom Eli
SubjectStructure, Dynamics and Learning on Networks
DepartmentDepartment of Electrical and Computer Engineering
Supervisors PROF. Ariel Orda
PROF. Shie Mannor


This thesis is composed of three main topics. First, we discuss network formation games for the Internet Autonomous Systems graph. We follow by investigating early detection schemes for epidemic spreading on networks, and we conclude with proxy voting.

The Internet is composed of multiple Autonomous Systems, which are contracted by different economic agreements. We represent the resulting network as a graph, where two nodes are connected by a link if traffic is allowed to traverse through them. Recently, there has been a surge of studies exploring networks created by rational player. Nonetheless, most of these studies assume that players are identical, whereas the Internet is composed of many types of ASs. Furthermore the majority of studies on the application of game theory to networks focus solely on static properties. Finally, reliability, or network survivability, is of utmost importance for any functional system, and this requirement was never addressed in the context of a network formation game.

We follow by developing tools for early epidemic detection. Anti-virus software can find the signature of known worm or virus. But how do we intercept malware spread in actionable time-scales, and critically, before we know what is spreading - and thus before we have malware-specific signatures? In the absence of signatures that pinpoint the presence of malware we necessarily resort not to signatures, but indications. A Malware may produce slight deviations in system behavior, for example, a spike in network activity. These indicators are extremely weak, possibly symptomatic of nothing abnormal.

Can we use indications of abnormality that are so weak that on their own they are statistically indistinguishable from noise, to make an accurate diagnosis about the presence of an epidemic? We show that, given a map of nodes that experience suspicious behavior and (only) local network information, we were able to identify a malware outbreak. The error rates of our method are extremely low, even when the noise in the reporting process was high, namely, the “weak signatures” were very weakly related to the malware. We provide a simple, distributed algorithm that runs in time linear in the number of reporting infected nodes. We address the problem of malware detection from a dynamic perspective as well, and show that monitoring the dynamics of these “weak signatures” enables us to detect an infection very shortly after the initial infiltration occurred.

Finally, we discuss proxy voting, which allows voters who are unable or uninterested to vote themselves transfer their voting rights to another person---a proxy. While common in politics and in corporates, only a handful of theoretical models deal with proxy voting, and our understanding of its effects are limited.

The intuition for why proxy voting should increase accuracy is straight-forward: opinions that are more “central” would attract followers and gain weight, whereas the weight of “outliers” that distort the outcome will be demoted. However, this reasoning does not always work in practice. Thus it is important to understand the conditions in which proxy voting is expected to improve accuracy, especially when voters behave strategically.