Committee:

Dr. Duen Horng (Polo) Chau, School of Computational Science and Engineering (Advisor) Dr. Shamkant B. Navathe, School of Computer Science (Co-Advisor) Dr. Munmun De Choudhury, School of Interactive Computing Dr. Rahul C. Basole, School of Interactive Computing Dr. Kevin A. Roundy, Symantec Research Labs

Abstract:

Graphs (or networks) are now omnipresent, infusing into many aspects of society. This dissertation contributes unified graph-based algorithms and models to help solve large-scale societal problems affecting millions of individuals' daily lives, from cyber-attacks involving malware to tobacco and alcohol addiction. The main thrusts of our research are:

(1) Propagation-based Graph Mining Algorithms: We develop graph mining algorithms to propagate information between the nodes to infer important details about the unknown nodes. We present three examples: AESOP (patented) unearths malware lurking in people's computers with a 99.61% true positive rate at 0.01% false positive rate; our application of ADAGE on malware detection (patent-pending) enables to detect malware in a streaming setting, and EDOCS (patent-pending) flags comment spammers among 197 thousand users on a social media platform accurately and preemptively.

(2) Graph-induced Behavior Characterization: We derive new insights and knowledge that characterize certain behavior from graphs using statistical and algorithmic techniques. We present two examples: a study on identifying attributes of smoking and drinking abstinence and relapse from an addiction cessation social media community; and an exploratory analysis of how company insiders trade.

Our work has already made impact to society: deployed by Symantec, AESOP is protecting over 120 million people worldwide from malware; EDOCS has been deployed by Yahoo and is guarding multiple online communities from comment spammers.