Span-core Decomposition for Temporal Networks: Algorithms and Applications

Edoardo Galimberti, Martino Ciaperoni, Alain Barrat, Francesco Bonchi, Ciro Cattuto, Francesco Gullo , Span-core Decomposition for Temporal Networks: Algorithms and Applications, ACM Transactions on Knowledge Discovery from Data 15(1):2 (2020)

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). In this article, we tackle this task by introducing a notion of temporal core decomposition where each core is associated with two quantities, its coreness, which quantifies how densely it is connected, and its span, which is a temporal interval: we call such cores span-cores.

For a temporal network defined on a discrete temporal domain T, the total number of time intervals included in T is quadratic in |T|, so that the total number of span-cores is potentially quadratic in |T| as well. Our first main 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 their coreness property and their span. We devise a very efficient algorithm that exploits theoretical findings on the maximality condition to directly extract the maximal ones without computing all span-cores.

Finally, as a third contribution, we introduce the problem of temporal community search, where a set of query vertices is given as input, and the goal is to find a set of densely-connected subgraphs containing the query vertices and covering the whole underlying temporal domain T. We derive a connection between this problem and the problem of finding (maximal) span-cores. Based on this connection, we show how temporal community search can be solved in polynomial-time via dynamic programming, and how the maximal span-cores can be profitably exploited to significantly speed-up the basic algorithm.

We provide an extensive experimentation on several real-world temporal networks of widely different origins and characteristics. Our results confirm the efficiency and scalability of the proposed methods. Moreover, we showcase the practical relevance of our techniques in a number of applications on temporal networks, describing face-to-face contacts between individuals in schools. Our experiments highlight the relevance of the notion of (maximal) span-core in analyzing social dynamics, detecting/correcting anomalies in the data, and graph-embedding-based network classification.


URL: https://dl.acm.org/doi/10.1145/3418226

BIBTEX:

@article{10.1145/3418226,
author = {Galimberti, Edoardo and Ciaperoni, Martino and Barrat, Alain and Bonchi, Francesco and Cattuto, Ciro and Gullo, Francesco},
title = {Span-Core Decomposition for Temporal Networks: Algorithms and Applications},
year = {2020},
issue_date = {January 2021},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {15},
number = {1},
issn = {1556-4681},
url = {https://doi.org/10.1145/3418226},
doi = {10.1145/3418226},
journal = {ACM Trans. Knowl. Discov. Data},
month = dec,
articleno = {2},
numpages = {44},
keywords = {community search, core decomposition, face-to-face interaction networks, maximal cores, Temporal networks}
}

PUBLICATIONS

Building surrogate temporal network data from observed backbones
Effect of manual and digital contact tracing on COVID-19 outbreaks: a study on empirical contact data
Predicting partially observed processes on temporal networks by Dynamics-Aware Node Embeddings (DyANE)
Digital proximity tracing on empirical contact networks for pandemic control
Span-core Decomposition for Temporal Networks: Algorithms and Applications
Relevance of temporal cores for epidemic spread in temporal networks
Measuring social networks in primates: wearable sensors versus direct observations
The effect of age, environment and management on social contact patterns in sheep
High-resolution contact networks of free-ranging domestic dogs Canis familiaris and implications for transmission of infection
Simplicial models of social contagion
Study design and protocol for investigating social network patterns in rural and urban schools and households in a coastal setting in Kenya using wearable proximity sensors
Wearable Proximity Sensors for Monitoring a Mass Casualty Incident Exercise: Feasibility Study
The structured backbone of temporal social ties
Mining (maximal) span-cores from temporal networks
Estimating the outcome of spreading processes on networks with incomplete information: A dimensionality reduction approach
Close encounters between infants and household members measured through wearable proximity sensors
Can co-location be used as a proxy for face-to-face contacts?
Effect of risk perception on epidemic spreading in temporal networks
Estimating the epidemic risk using non-uniformly sampled contact data
Robust modeling of human contact networks across different scales and proximity-sensing techniques
Finding Collaboration Partners in a Scientific Community: The Role of Cognitive Group Awareness, Career Level, and Disciplinary Background
Recalibrating disease parameters for increasing realism in modeling epidemics in closed settings
School closure policies at municipality level for mitigating influenza spread: a model-based evaluation
Contact diaries versus wearable proximity sensors in measuring contact patterns at a conference: method comparison and participants’ attitudes
Impact of spatially constrained sampling of temporal contact networks on the evaluation of the epidemic risk
How to Estimate Epidemic Risk from Incomplete Contact Diaries Data?
Quantifying social contacts in a household setting of rural Kenya using wearable proximity sensors
Epidemic risk from friendship network data: an equivalence with a non-uniform sampling of contact networks
Compensating for population sampling in simulations of epidemic spread on temporal contact networks
Enhancing the evaluation of pathogen transmission risk in a hospital by merging hand-hygiene compliance and contact data: a proof-of-concept study
Contact patterns in a high school: a comparison between data collected using wearable sensors, contact diaries and friendship surveys
Data on face-to-face contacts in an office building suggest a low-cost vaccination strategy based on community linkers
Is Web Content a Good Proxy for Real-Life Interaction? A Case Study Considering Online and Offline Interactions of Computer Scientists
Combining High-Resolution Contact Data with Virological Data to Investigate Influenza Transmission in a Tertiary Care Hospital
Mental health and social networks in early adolescence: A dynamic study of objectively-measured social interaction behaviors
Mitigation of infectious disease at school: targeted class closure vs school closure
How memory generates heterogeneous dynamics in temporal networks
Contact patterns among high school students
Detecting the Community Structure and Activity Patterns of Temporal Networks: A Non-Negative Tensor Factorization Approach
Measuring contact patterns with wearable sensors: methods, data characteristics and applications to data-driven simulations of infectious diseases
Bootstrapping under constraint for the assessment of group behavior in human contact networks
Immunization strategies for epidemic processes in time-varying contact networks
Activity clocks: spreading dynamics on temporal networks of human contact
Gender homophily from spatial behavior in a primary school: a sociometric study
Estimating Potential Infection Transmission Routes in Hospital Wards Using Wearable Proximity Sensors
Empirical temporal networks of face-to-face human interactions
New Insights and Methods for Predicting Face-To-Face Contacts
Time-varying Social Networks in a Graph Database – A Neo4j Use Case
Temporal networks of face-to-face human interactions
An infectious disease model on empirical networks of human contact: bridging the gap between dynamic network data and contact matrices
Fingerprinting temporal networks of close-range human proximity
Digital Epidemiology
Random Walks on Temporal Networks
The making of Sixty-Nine Days Of Close Encounters At The Science Gallery.
High-Resolution Measurements of Face-to-Face Contact Patterns in a Primary School.
Simulation of an SEIR Infectious Disease Model on the Dynamic Contact Network of Conference Attendees.
On the Dynamics of Human Proximity for Data Diffusion in Ad-Hoc Networks.
Close Encounters in a Pediatric Ward: Measuring Face-to-Face Proximity and Mixing Patterns with Wearable Sensors.
What’s in a Crowd? Analysis of Face-to-Face Behavioral Networks.
Wearable Sensor Networks for Measuring Face-to-Face Contact Patterns in Healthcare Settings.
Social Dynamics in Conferences: Analysis of Data from the Live Social Semantics Application.
Providing Enhanced Social Interaction Services for Industry Exhibitors at large Medical Conferences.
Dynamics of Person-to-Person Interactions from Distributed RFID Sensor Networks.
Semantics, Sensors, and the Social Web: The Live Social Semantics Experiments.
The Live Social Semantics Application: a Platform for Integrating Face-to-Face Presence with On-Line Social Networking
Live Social Semantics
High Resolution Dynamical Mapping of Social Interactions With Active RFID.