(Jan 31) Mining Dense Subgraphs in Large Dynamic Graphs

Dense subgraphs are a useful tool to understand the structure of graphs, and they often indicate interesting patterns or anomalies. In this talk, I will discuss several algorithms that I have developed for analyzing and identifying dense subgraphs in real-world graphs, which are large and dynamic (i.e., edges can be added or deleted). Specifically, I will introduce streaming algorithms for estimating the clustering coefficients (i.e., tendencies of nodes to form dense subgraphs) and approximation algorithms for identifying anomalous dense subgraphs in terabyte-scale data. I will also show applications of the algorithms in several domains, including online social networks, e-commerce, and network security.