Mining (maximal) span-cores from temporal networks

Abstract

When analyzing temporal networks, a fundamental task is the identification of dense structures (i.e., groups of vertices that exhibit a large number of links), together with their temporal span (i.e., the period of time for which the high density holds). We tackle this task by introducing a notion of temporal core decomposition where each core is associated with its span: we call such cores span-cores. As the total number of time intervals is quadratic in the size of the temporal domain $T$ under analysis, the total number of span-cores is quadratic in $|T|$ as well. Our first contribution is an algorithm that, by exploiting containment properties among span-cores, computes all the span-cores efficiently. Then, we focus on the problem of finding only the maximal span-cores, i.e., span-cores that are not dominated by any other span-core by both the coreness property and the span. We devise a very efficient algorithm that exploits theoretical findings on the maximality condition to directly compute the maximal ones without computing all span-cores. Experimentation on several real-world temporal networks confirms the efficiency and scalability of our methods. Applications on temporal networks, gathered by a proximity-sensing infrastructure recording face-to-face interactions in schools, highlight the relevance of the notion of (maximal) span-core in analyzing social dynamics and detecting/correcting anomalies in the data.

References in corpus (9)

• Identification of influential spreaders in complex networks
• High-resolution measurements of face-to-face contact patterns in a primary school
• Contact patterns in a high school: a comparison between data collected using wearable sensors, contact diaries and friendship surveys
• A k-shell decomposition method for weighted networks
• Detecting the community structure and activity patterns of temporal networks: a non-negative tensor factorization approach
• Prediction of Emerging Technologies Based on Analysis of the U.S. Patent Citation Network
• Mitigation of infectious disease at school: targeted class closure vs school closure
• Gender homophily from spatial behavior in a primary school: a sociometric study
• Social Resilience in Online Communities: The Autopsy of Friendster

Cited by in corpus (10)

• Randomized reference models for temporal networks
• Distance-generalized Core Decomposition
• Hyper-cores promote localization and efficient seeding in higher-order processes
• The Temporal Rich Club Phenomenon
• From temporal network data to the dynamics of social relationships
• Relevance of temporal cores for epidemic spread in temporal networks
• Reliable Community Search in Dynamic Networks
• Span-core Decomposition for Temporal Networks: Algorithms and Applications
• Fast computation of distance-generalized cores using sampling
• Cores and Other Dense Structures in Complex Networks