2014 EventDetectioninActivityNetwork

• (Rozenshtein et al., 2014) ⇒ Polina Rozenshtein, Aris Anagnostopoulos, Aristides Gionis, and Nikolaj Tatti. (2014). “Event Detection in Activity Networks.” In: Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2014) Journal. ISBN:978-1-4503-2956-9 doi:10.1145/2623330.2623674

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%222014%22+Event+Detection+in+Activity+Networks
• http://dl.acm.org/citation.cfm?id=2623330.2623674&preflayout=flat#citedby

Quotes

Author Keywords

• Data mining; event detection; maximum cut; prize-collecting steiner tree; submodular function maximization

Abstract

With the fast growth of smart devices and social networks, a lot of computing systems collect data that record different types of activities. An important computational challenge is to analyze these data, extract patterns, and understand activity trends. We consider the problem of mining activity networks to identify interesting events, such as a big concert or a demonstration in a city, or a trending keyword in a user community in a social network.

We define an event to be a subset of nodes in the network that are close to each other and have high activity levels. We formalize the problem of event detection using two graph-theoretic formulations. The first one captures the compactness of an event using the sum of distances among all pairs of the event nodes. We show that this formulation can be mapped to the maxcut problem, and thus, it can be solved by applying standard semidefinite programming techniques. The second formulation captures compactness using a minimum-distance tree. This formulation leads to the prize-collecting Steiner-tree problem, which we solve by adapting existing approximation algorithms. For the two problems we introduce, we also propose efficient and effective greedy approaches and we prove performance guarantees for one of them. We experiment with the proposed algorithms on real datasets from a public bicycling system and a geolocation-enabled social network dataset collected from twitter. The results show that our methods are able to detect meaningful events.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2014 EventDetectioninActivityNetwork	Nikolaj Tatti Aristides Gionis Aris Anagnostopoulos Polina Rozenshtein			Event Detection in Activity Networks				10.1145/2623330.2623674		2014