Discovering recurring activity in temporal networks

Orestis Kostakis*, Nikolaj Tatti, Aristides Gionis

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

6 Citations (Scopus)

Abstract

Recent advances in data-acquisition technologies have equipped team coaches and sports analysts with the capability of collecting and analyzing detailed data of team activity in the field. It is now possible to monitor a sports event and record information regarding the position of the players in the field, passing the ball, coordinated moves, and so on. In this paper we propose a new method to analyze such team activity data. Our goal is to segment the overall activity stream into a sequence of potentially recurrent modes, which reflect different strategies adopted by a team, and thus, help to analyze and understand team tactics. We model team activity data as a temporal network, that is, a sequence of time-stamped edges that capture interactions between players. We then formulate the problem of identifying a small number of team modes and segmenting the overall timespan so that each segment can be mapped to one of the team modes; hence the set of modes summarizes the overall team activity. We prove that the resulting optimization problem is (Formula presented.)-hard, and we discuss its properties. We then present a number of different algorithms for solving the problem, including an approximation algorithm that is practical only for one mode, as well as heuristic methods based on iterative and greedy approaches. We benchmark the performance of our algorithms on real and synthetic datasets. Of all methods, the iterative algorithm provides the best combination of performance and running time. We demonstrate practical examples of the insights provided by our algorithms when mining real sports-activity data. In addition, we show the applicability of our algorithms on other types of data, such as social networks.

Original languageEnglish
Pages (from-to)1840–1871
Number of pages32
JournalData Mining and Knowledge Discovery
Volume31
Issue number6
DOIs
Publication statusPublished - 2017
MoE publication typeA1 Journal article-refereed

Keywords

  • Basketball
  • Dynamic graphs
  • Football
  • Handball
  • Segmentation
  • Social networks
  • Sports analytics
  • Summarising
  • Temporal networks

Fingerprint Dive into the research topics of 'Discovering recurring activity in temporal networks'. Together they form a unique fingerprint.

Cite this