[PAST EVENT] Mathematics Colloquium and EXTREEMS-QED Lecture: Thang Dinh (VCU)
March 4, 2016
2pm - 3pm
Abstract: Big graphs have become increasingly popular in many domains such as Social Networks, the Web of Knowledge, and the Internet of Things, to name a few. Graph data are now measured in terabytes, heading towards petabytes, with billions of nodes and edges. For example, Facebook now contains 1.5 billion monthly active users and generate 60 terabytes data every day; the Internet of Things are predicted to contain more than 20.8 billion devices by 2020. Mining and querying such graphs powers many applications in social networks, personal recommendation, fraud and cybersecurity threats detection, and many others. However, mining such humongous graphs is extremely challenging. Not only the graphs do not fit into the memory and storage of a single machine, but also the existing methods provide little guarantees on the quality and the confidence of the solution. In this talk, we will introduce novel frameworks to mine billion-scale graphs with high confidence, near-optimal solutions, and, especially, the ability to interrupt anytime during the execution. The last feature is novel and critical for real-time and time-bounded applications. We illustrate our approaches through two social networks applications in our recent INFOCOM and SIGMOD papers.