Title： Dense Regions: a Different Type of Event in Graph Streams

Speaker：葛廷健 (University of Massachusetts, USA)

Time：10:00am, Tuesday, 23 April, 2019

Venue:：Room 334, 3th Floor, Building #5, Institute of Software, CAS

Abstract:

    A graph stream, as a special data stream, consists of a sequence of edge insertions and deletions over a dynamic graph. Analogous to general data streams, complex events have been studied on graph streams which incorporate both time order and structural relationship over basic edge events. In this talk, I will propose a new type of complex event – the occurrence of a dense region that also lasts for a long time. This turns out to be very useful in applications of various domains including telecommunication hotspot detection, road traffic control, spam network filtering, and dynamic community detection.

　　To efficiently discover dense regions, we propose an algorithmic framework called the Expectation-Maximization with a Utility function (EMU), a novel stochastic approach that nontrivially extends the conventional EM. We validate our EMU approach by showing that it converges to the optimum—by proving that it is a specification of the general Minorization-Maximization (MM) framework with convergence guarantees. We then devise EMU algorithms for the densest lasting subgraph problem. Using real-world graph streams, we experimentally verify the effectiveness and efficiency of our techniques.

Speaker

Biography:

    Tingjian Ge is an associate professor in Computer Science at the University of Massachusetts, Lowell. He received a Ph.D. from Brown University in 2009. Prior to that, he got his Bachelor’s and Master’s degrees in Computer Science from Tsinghua University and UC Davis, respectively, and worked at Informix and IBM for six years. His research areas are in data management and analytics, with a recent focus on applying machine learning, AI, and algorithmic techniques in data management and mining. He is a recipient of the NSF CAREER Award in 2012, and a Teaching Excellence Award at UMass Lowell in 2014.