att_abstract={{Recent years have witnessed an unprecedented proliferation of social
media. People around the globe author, every day, millions
of blog posts, micro-blog posts, social network status updates, etc.
This rich stream of information can be used to identify, on an ongoing
basis, emerging stories, and events that capture popular attention.
Stories can be identified via groups of tightly-coupled realworld
entities, namely the people, locations, products, etc., that are
involved in the story. The sheer scale, and rapid evolution of the
data involved necessitate highly efficient techniques for identifying
important stories at every point of time.

The main challenge in real-time story identification is the maintenance
of dense subgraphs (corresponding to groups of tightly coupled
entities) under streaming edge weight updates (resulting
from a stream of user-generated content). This is the first work
to study the efficient maintenance of dense subgraphs under such
streaming edge weight updates. For a wide range of definitions
of density, we derive theoretical results regarding the magnitude
of change that a single edge weight update can cause. Based on
these, we propose a novel algorithm, DYNDENS, which outperforms
adaptations of existing techniques to this setting, and yields
meaningful results. Our approach is validated by a thorough experimental
evaluation on large-scale real and synthetic datasets.}},
	att_copyright={{VLDB Foundation}},
	att_copyright_notice={{The definitive version was published in Very Large Databases, 2012. {{, Volume 5}}{{, Issue 6}}{{, 2012-08-15}}
	author={Divesh Srivastava and Albert Angel and Nick Koudas and Nikos Sarkas},
	institution={{VLDB 2012}},
	title={{Dense subgraph maintenance under streaming edge weight epdates for realtime story identification}},