Epidemic phenomena in networks occur when an infectious disease, computer virus, behavior, piece of information, or innovation is disseminated in a highly decentralized and parallel way along the links of a social or computer network. Epidemic phenomena often have a strong effect on society. Diseases and computer viruses cause the loss of human lives and economic damage. Behavioral patterns, spread by imitation or coercion, can be desirable or undesirable. An innovation or piece of information can lead to improvements in quality of life, or to increased sales revenue for a company. It is thus crucial to study ways of leveraging the limited control one has over epidemics. In the case of harmful epidemics, this includes vaccinations, anti-virus software deployment, and other policy decisions. For the diffusion of innovations, effective "word-of-mouth marketing" strategies (such as identifying influential individuals) must be chosen. For the dissemination of information, efficient network protocols need to be designed.
Given the increasingly detailed data available about social and computer networks, it is becoming feasible to model such epidemic phenomena accurately, and to address algorithmically the problems of minimizing or maximizing the spread of an epidemic in a network. Problems relating to the containment of epidemics lead to novel graph cut optimization problems, while maximization problems relate to graph covering. When multiple influences are competing, the problems take on a game-theoretic component, and in many cases, the models for epidemics are based on Markov Chains and random graphs. The investigator will study algorithms with provable guarantees for the problems of minimizing or maximizing the spread of epidemics.
In my research, I was focusing on two (partly connected) areas: social networks and game-theoretic analysis of interactions between self-interested players. The former is gaining importance as access to social network data is becoming easier and more prevalent; the latter is gradually becoming a de facto methodology for reasoning about systems involving large numbers of actors with different goals. In the domain of social networks, we explored algorithms for identifying influential groups of individuals and for detecting communities of similar individuals. More fundamentally, we analyzed the types of mathematical structures that can explain the observed phenomena of influence and social connections. Such structures can be metrics capturing individuals' similarities, as well as functions determining the influencing behavior of individuals. Our work is centered on solving these computational problems with provable guarantees, that is, ensuring that never mind how strange an input may look, the algorithms find a solution that is provably close to the best possible, and do so efficiently. In the domain of game theory, we worked on several topics. The most prominent of these were an analysis of the impact of partial altruism, and mechanism design problems in the domain of auctions for hiring teams. Game theory as traditionally studied in economics assumes that all participating individuals are purely selfish and rational, meaning they choose optimal actions to benefit solely themselves. In reality, many people act at least partially altruistically, choosing actions that may be slightly suboptimal for them, but not harming other as much. Our goal was to quantify the impact of such partially altruistic behavior when chosen by the entire population. We were able to show that for several domains (traffic routing, vaccinations in a network), partially altruistic behavior can lead to provable societally preferable outcomes. In the context of auction design, we show that for several important combinatorial classes of team assembly tasks, cost-minimizing and truthful (meaning that individuals have no incentives to lie about their cost of participation) auctions can be designed based on reductions to standard graph-theory problems and some interesting linear algebra techniques. In terms of teaching, I created a modern algorithms curriculum at USC, introducing a Ph.D. level algorithms class, as well as three advanced Ph.D. level classes, on Randomized Algorithms, Approximation Algorithms, and Structure and Dynamics of Networked Information. For the latter class, I produced lecture notes which are publicly shared, and have been used by colleagues at other universities for similar classes. At the undergraduate level, I revised the introductory theory sequence, and introduced an advanced class on Algorithmic Problem Solving. In addition to advising three Ph.D. students so far, I also mentored several undergraduate research students, and was awarded two mentoring awards for the effort and success. I also established and am still supervising the USC Programming Contest, held every semester. In addition, I organized a workshop on topics related to algorithmic questions in social networks that brought together researchers from many different disciplines.
