Making diffusion work for you: Classification sans text, finding culprits and filling missing values

Abstract

Can we find people infected with the flu virus even though they did not visit a doctor? Can the temporal features of a trending hashtag or a keyword indicate which topic it belongs to without any textual information? Given a history of interactions between blogs and news websites, can we predict blogs posts/news websites that are not in the sample but talk about the ``the state of the economy'' in 2008? These questions have two things in common: a network (social networks or human contact networks) and a virus (meme, keyword or the flu virus) diffusing over the network. We can think of interactions like memes, hashtags, influenza infections, computer viruses etc., as viruses spreading in a network. This treatment allows for the usage of epidemiologically inspired models to study or model these interactions. Understanding the complex propagation dynamics involved in information diffusion with the help of these models uncovers various non-trivial and interesting results.

In this thesis we propose (a) A fast and efficient algorithm NetFill, which can be used to find quantitatively and qualitatively correct infected nodes, not in the sample and finding the culprits and (b) A method, SansText that can be used to find out which topic a keyword/hashtag belongs to just by looking at the popularity graph of the keyword without textual analysis. The results derived in this thesis can be used in various areas like epidemiology, news and protest detection, viral marketing and it can also be used to reduce sampling errors in graphs.