  Due to their real time nature, microblog streams are a rich source of dynamic
information, for example, about emerging events. Existing techniques for
discovering such events from a microblog stream in real time (such as Twitter
trending topics), have several lacunae when used for discovering emerging
events; extant graph based event detection techniques are not practical in
microblog settings due to their complexity; and conventional techniques, which
have been developed for blogs, web-pages, etc., involving the use of keyword
search, are only useful for finding information about known events. Hence, in
this paper, we present techniques to discover events that are unraveling in
microblog message streams in real time so that such events can be reported as
soon as they occur. We model the problem as discovering dense clusters in
highly dynamic graphs. Despite many recent advances in graph analysis, ours is
the first technique to identify dense clusters in massive and highly dynamic
graphs in real time. Given the characteristics of microblog streams, in order
to find clusters without missing any events, we propose and exploit a novel
graph property which we call short-cycle property. Our algorithms find these
clusters efficiently in spite of rapid changes to the microblog streams.
Further we present a novel ranking function to identify the important events.
Besides proving the correctness of our algorithms we show their practical
utility by evaluating them using real world microblog data. These demonstrate
our technique's ability to discover, with high precision and recall, emerging
events in high intensity data streams in real time. Many recent web
applications create data which can be represented as massive dynamic graphs.
Our technique can be easily extended to discover, in real time, interesting
patterns in such graphs.
