# Describing group evolution in temporal data using multi-faceted events

Andrea Failla, Rémy Cazabet, Giulio Rossetti, Salvatore Citraro

► To cite this version:

Andrea Failla, Rémy Cazabet, Giulio Rossetti, Salvatore Citraro. Describing group evolution in temporal data using multi-faceted events. Machine Learning, 2024, 113 (10), pp.7591-7615. 10.1007/s10994-024-06600-4. http://dx.doi.org/10.1007/s10994-024-06600-4

HAL Id: hal-04890162

https://hal.science/hal-04890162v1

Submitted on 14 Mar 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>
# Describing group evolution in temporal data using multi-faceted events

Andrea Failla<fnref n="1" />,<fnref n="2" /> · Rémy Cazabet<fnref n="3" /> · Giulio Rossetti<fnref n="2" /> · Salvatore Citraro<fnref n="2" />

Received: 11 March 2024 / Revised: 24 July 2024 / Accepted: 25 July 2024 /

Published online: 1 August 2024

© The Author(s) 2024

## Abstract

Groups—such as clusters of points or communities of nodes—are fundamental when addressing various data mining tasks. In temporal data, the predominant approach for characterizing group evolution has been through the identification of “events”. However, the events usually described in the literature, e.g., shrinks/growths, splits/merges, are often arbitrarily defined, creating a gap between such theoretical/predefined types and real-data group observations. Moving beyond existing taxonomies, we think of events as “archetypes” characterized by a unique combination of quantitative dimensions that we call “facets”. Group dynamics are defined by their position within the facet space, where archetypal events occupy extremities. Thus, rather than enforcing strict event types, our approach can allow for hybrid descriptions of dynamics involving group proximity to multiple archetypes. We apply our framework to evolving groups from several face-to-face interaction datasets, showing it enables richer, more reliable characterization of group dynamics with respect to state-of-the-art methods, especially when the groups are subject to complex relationships. Our approach also offers intuitive solutions to common tasks related to dynamic group analysis, such as choosing an appropriate aggregation scale, quantifying partition stability, and evaluating event quality.

**Keywords** Group evolution · Temporal clustering · Community detection · Clustering evaluation

Editor: Joao Gama.

<figure><img src="image_2.png" /></figure>

Salvatore Citraro
salvatore.citraro@isti.cnr.it

<footnote n="1">¹ Department of Computer Science, University of Pisa, Pisa, Italy</footnote>

<footnote n="2">² Institute of Information Science and Technologies “A. Faedo” (ISTI), National Research Council (CNR), Pisa, Italy</footnote>

<footnote n="3">³ Univ Lyon, UCBL, CNRS, INSA Lyon, LIRIS, UMR5205, 69622 Villeurbanne, France</footnote>
# 1 Introduction

Unsupervised learning, such as clustering and community detection, involves identifying collections of elements that share some form of similarities. Clustering methods identify groups of observations or entities, based on their proximity across multi-dimensional features (MacQueen et al., 1967). Community detection aims to describe the mesoscale dimension of a complex network, grouping nodes that share similar structural behaviour (Fortunato & Hric, 2016). Such groups are often referred to as clusters in data mining-related fields, and communities in complex network analysis. In the remainder of this article, we will use the generic term of “group”. Groups are fundamental when addressing a wide variety of data mining and network science-related questions, such as segmenting customers to improve recommender systems or identifying echo chambers in social media to de-polarize online discussions.

Often, real data are stored as streams or sequences of multi-dimensional points (Zubaroğlu & Atalay, 2021) or links (Rossetti & Cazabet, 2018) such that the formation and evolution of groups can be tracked quantitatively over time. The challenge of identifying evolving groups has emerged as a distinct subfield in many areas; see spatiotemporal data clustering (Ansari et al., 2020; Kisilevich et al., 2010), data stream clustering (Zubaroğlu & Atalay, 2021), and dynamic community detection (Rossetti & Cazabet, 2018).

A key concept specific to dynamic group evolution is the notion of *event* (Bródka et al., 2013; Lughofer, 2012; Palla et al., 2007; Rossetti & Cazabet, 2018). Intuitively, an event is a temporal occurrence involving changes that can be measured and analyzed for a group or a set of groups. A change can be the growth or the shrinking of a group, or the merging of two groups into a larger one. These events have been defined in the literature a priori (Asur et al., 2009; Brodka et al., 2009; Bródka et al., 2013; Greene et al., 2010; Palla et al., 2007), based on what one wishes to extract from the data, and not from the reality of group evolution observed in data. As a consequence, in most datasets we are confronted with a gap between theoretical events such as “merge” or “growth”, and what one actually observes. Most group evolution seems indeed more complex, frequently being a combination of those artificial categories.

In this work, rather than using those strict event definitions, we consider them as “archetypes”, i.e., typical examples of a category conveying its most salient features (Rosch, 1975), while real events can exhibit features from multiple of these archetypes. To tackle this more complex definition, we propose a quantitative definition of event archetypes as a unique combination of three constitutive dimensions called *facets*. Each event is thus defined by a position in this 3-dimensional space, in which usual events occupy an extremity. Following (Bovet et al., 2022), we consider *backward* and *forward* perspectives to study the temporal evolution of a target group.

The rest of the paper is organized as follows. Section 2 sums up the essential literature about temporal clustering across different domains and the need to build taxonomies to describe the life cycles of groups. Section 3 describes our framework for characterizing the temporal evolution of target groups as weighted approximations of archetypal events. Section 4 introduces an experimental setting to test our methodology in real-world data. Finally, Sect. 5 concludes the work by discussing its potentiality and limits.
<figure><img src="image_3.png" /><figcaption>**Fig. 1** Three representations for dynamic groups found in the literature. **a** Does not describe the relation between the groups; **b** Assigns labels (here represented by colors) to each entity/time, yielding a longitudinal group; **c** Describe how groups in a timestep are related to those in the next. Note that none of these representations explicit the events occurring on the network</figcaption></figure>

## 2 Related work

Data stream clustering, temporal clustering, and dynamic community detection are active research topics, and many algorithms have been proposed to identify time-varying groups (Rossetti & Cazabet, 2018; Kisilevich et al., 2010; Ansari et al., 2020; Zubaroğlu & Atalay, 2021). However, most of these works do not address the question of group events. Indeed, dynamic grouping methods often yield their groupings in one of two forms, as illustrated in Fig. 1: (i) The method might only focus on the groups found at each step, for instance ensuring the stability of these groups in time. In that case, we know what are the groups at *t* and at *t* + 1, but there is no information in the relation between groups in *t* and in *t* + 1 (Fig. 1a); or (ii) each group is a set of (entity/time) pairs, i.e., a group exists over multiple timesteps, potentially allowing entities to join and leave the group along time (Fig. 1b). However, none of these representations explicit what the events undergone by evolving groups are. In this work, we will consider starting from a sequence of temporally ordered observations, i.e., snapshots, and sets of partitions on these snapshots, obtained from an existing method—or possibly, from a ground truth—as illustrated in Fig. 1a. The task consists in characterizing the nature of the relation between groups at time *t* and at time *t* + 1, in the form of events.

The earliest attempts to define events on groups can be found in Kalnis et al. (2005) and Hopcroft et al. (2004), with the objective to identify CONTINUATION events, i.e., to define that group $c_1$ at time $t_1$ should be considered as the same group as $c_2$ at time $t_2$, a process also known as *matching* groups. Kalnis et al. (2005) proposed to match groups if (i) they are adjacent, and (ii) their Jaccard coefficient is above a threshold $\tau$. Given $c_t$ and $c_{t+1}$, namely two groups observed over temporally adjacent snapshots, if $|c_t \cap c_{t+1}|/|c_t \cup c_{t+1}| \ge \tau$, the two groups are the same. $\tau$ is a parameter considering the “integrity” of a group, and it indicates the minimum overlap threshold required for two groups to be considered the same. Similarly, to identify a CONTINUATION event in dynamic networks, Hopcroft et al.
(2004) defined a match function as follows: $match(c_t, c_{t+1}) = Min(\frac{|c_t \cap c_{t+1}|}{|c_t|}, \frac{|c_t \cap c_{t+1}|}{|c_{t+1}|})$; then, if $match(c_t, c_{t+1}) \ge \tau$, the two groups are matched. However, without particular constraints on the value of $\tau$, there is no guarantee that a group is matched to a single group in the following step. The process thus naturally creates an *event graph* (Rossetti & Cazabet, 2018), as illustrated in Fig. 1c. Greene et al. (2010) were the first to formalize this event graph and to propose to use it to define typical events. A group having an out-degree of two or more is labeled as undergoing a *SPLIT* event. An in-degree of two or more is a *MERGE*. In/Out degrees of zero respectively lead to *BIRTH* and *DEATH* events. Finally, the authors mention that *CONTRACTION*, *EXPANSION*, and *CONTINUATION* all correspond to the same graph setting, but can be distinguished by adding size thresholds. It is worth noting though that despite its elegance and apparent simplicity, this approach creates complex situations: a group ($t_1, c_1$) can be matched to two groups ($t_2, c_2$), ($t_2, c_3$), but one of these groups might itself have an in-degree of more than one, thus being a merge of ($t_1, c_1$) and ($t_1, c_4$). These situations are not discussed in the article of Greene et al. (2010).

This merge-split ambiguity can be solved by adding some additional constraints, such as in Asur et al. (2009), in which an event is categorized as a MERGE if the following three conditions hold: (i) $\frac{|(c_t^i \cup c_{t+1}^i) \cap c_{t+1}|}{Max(|(c_t^i \cup c_{t+1}^i)|, |c_{t+1}|)} > \tau$, (ii) $|c_t^i \cap c_{t+1}| > \frac{|c_t^i|}{2}$, and (iii) $|c_t^j \cap c_{t+1}| > \frac{|c_t^j|}{2}$ where $c_t^i$ and $c_t^j$ are two distinct groups within the same partition at time t. Sun et al. (2015) also use two correlation matrices —built using $\frac{|c_t^i \cap c_{t+1}|}{|c_t^i|}$ and $\frac{|c_t^i \cap c_{t+1}|}{|c_{t+1}|}$.

Bródka et al. (2013) aimed to define as many events as possible by proposing a methodology for detecting group evolution, namely the Group Evolution Discovery (GED) framework. They introduce a measure to quantify the *inclusion* of one group into another based on both group sizes and a centrality measure called Social Position (SP) (Brodka et al., 2009), namely a function calculating how much a node is important in a group based on the importance of its neighbors. The group events are defined on the basis of a decision tree that assigns an event type to a pair of groups given some thresholds on sizes and inclusion values. Similarly to GED, Gliwa et al. (2012) introduced an algorithm for Stable Group Changes Identification (SGCI), where complex events such as merge, split, and split+merge (a split of the original group and the joining of many groups into successor groups) are associated to groups that have been found stable in neighboring time steps. The stability depends on a match function defined as $Max(\frac{|c_t^i \cap c_{t+1}|}{|c_t^i|}, \frac{|c_t^i \cap c_{t+1}|}{|c_{t+1}|})$.

To complete the overview of the analysis of complex event types in data mining- and network science-related tasks, it is worth mentioning works moving beyond merely identifying group events, but also employing them to predict the future evolution of a system. Typically, this subject has been modeled as a machine learning task, commonly in the form of a classification problem, where a set of features is extracted from the events and used to predict an event type (Saganowski, 2015). The events defined for building the training sets can be obtained from the methods previously described. In Saganowski (2015), events are described through the previously mentioned GED (Bródka et al., 2013) and SGCI (Gliwa et al., 2012) algorithms. Group features used for prediction are size, density, and the sum/average/min/max of aggregated group members' features, such as node degree and other centralities measures. Other works exploit forecasting methods for time series, predicting how the features extracted from the events will change in the following time period $t$han, and Öğüdücü, (2015). The latest directions of research are starting to focus on the behavior
<figure><img src="image_4.png" /><figcaption>**Fig. 2** A realistic group evolution scenario (a), with corresponding event graph using different matching functions: b Jaccard coefficient, high threshold (Kalnis et al., 2005), c Jaccard coefficient, low threshold (Kalnis et al., 2005), d intersection over minimum size, as defined in Hopcroft et al. (2004)</figcaption></figure>

and prediction of individual entities. For instance, Tsoukanara et al. (2021) proposed to predict, using node embedding methods, beyond event types, whether a specific node stays in the same group, moves to another group, or drops out of the dataset.

## 2.1 Limits of existing methods

Existing event detection methods suffer from some limitations, which might explain their limited use in practice.

The first limit is the sensibility to the fixed threshold $\tau$. Choosing a large threshold will cause many groups to die and be born at each step, while a low one will create complex events involving multiple groups from $t$ and from $t + 1$ together, as illustrated in Fig. 2. Choosing this parameter thus strongly affects the results. Although some authors have proposed to use a dynamic threshold (Mall et al., 2015), the problem of their arbitrary values and binary categorization remains present.

Another limit is the discrepancy between having a list of well-defined events—Continuation, Birth, Death, Merge, Split, Expansion, Contraction—and the more complex reality of real situations, as illustrated in Fig. 2a. We can observe that from the point of view of $(t1, c2)$, the event can be interpreted as either a split or a continuation, with a minor number of entities leaving the group. From the point of view of $(t2, c1)$, we can again interpret what is happening as a merge or as a continuation, depending on the threshold fixing what quantity of entities is considered a negligible fraction. An even more ambiguous case is the relation between $(t1, c2)$ and $(t2, c2)$ since a minority fraction of entities leaves the first, but they represent a large fraction of the newly formed one. We can formalize the difficulties encountered by those previous methods by their definition of an event, which involves a set
<table><caption>**Table 1** Notation used in the paper</caption><thead><tr><th>U</th><th>Universe set</th></tr></thead><tbody><tr><td>U<sub>t</sub></td><td>Elements observed at time t</td></tr><tr><td>S</td><td>Temporally-ordered set of partitions</td></tr><tr><td>S<sub>t</sub></td><td>Partition at time t</td></tr><tr><td>X</td><td>target set</td></tr><tr><td>R</td><td>Sets the target evolves into/from (set of related groups)</td></tr><tr><td>R</td><td>A child/parent set of the target (related group)</td></tr><tr><td>U</td><td>Unicity facet</td></tr><tr><td>I</td><td>Identity facet</td></tr><tr><td>O</td><td>Outflow facet</td></tr><tr><td>T</td><td>Event typicality index</td></tr></tbody></table>

of groups from two adjacent timesteps, without a notion of direction. Instead, we argue that a split, for instance, only makes sense when following the direction of time, while a merge is characterized by considering the opposite direction. Thus, in the case of Fig. 2c, we must extract a split from the point of view of (t1,c2), in the direction of time, and a merge from the point of view of (t2,c1), in the reverse direction.

Finally, a last limit of those approaches comes from their disregarding of the distinction between entities moving between groups, and those joining or leaving the system altogether. As an example, a death event might actually correspond to multiple situations: (i) all the entities composing the group might have left the studied system, (ii) entities might have split up and joined other groups. Conversely, a newborn group might be formed from entities joining the system, or from individual entities coming from multiple sources. Intuitively, these situations are different, but existing events do not distinguish them. This limit had already been discussed in Pereira et al. (2021), that introduced a taxonomy including for instance sub-categories for death events, namely death-vanish and death-absorb.

# 3 Methods

This section describes our framework for characterizing event types and group evolution in temporal data. In Table 1 we sum up the notation used in this section.

We decompose the method description into three sections: (i) A description of the backward/forward event perspectives, (ii) The definition of event description scores called *Event facet scores*, (iii) The definition of event names and archetypes from combinations of facet scores.

## 3.1 Backward and forward events

Our method starts from the postulate that events are defined either as *forward* or *backward* (Bovet et al., 2022). The former corresponds to events seen from the perspective of a group at *t*, relative to groups at *t* + 1. Conversely, the latter corresponds to the point of view of groups from *t* + 1 relative to those at *t*. This distinction is already present in the event-graph formalism: a merge event is defined as having an in-degree $k^{in} > 1$, while a
split corresponds to an out-degree $k^{out} > 1$ (see Fig. 1c). As discussed in Sect. 3.5, events as they are defined in the literature (e.g., Cazabet et al., 2018; Palla et al., 2007; Rossetti & Cazabet, 2018) are archetypes composed of a combination of backward and forward events. For instance, if a group has $k^{out} = 1$ (i.e., forward perspective), we must consider $k^{in}$ (i.e., backward perspective) of the target group to know what this particular event is (continuation or merge, in the event graph formalism).

### 3.1.1 Definition

Let $U = \cup_{t \in T} U_t$ be the universe set where each $U_t \subseteq U$ for $t \in T$ identifies the subset of elements of $U$ observed at time $t$. Let $S = \{S_0, S_1, \dots, S_{|T|}\}$ be a temporally ordered set of elements where each $S_t = [S_t^0, S_t^1, \dots, S_t^m]$ identifies a partition of $U_t$. Given a **target** set $X \in S_t$, let $\mathcal{R} = \{R^0, \dots, R^i\}$ be a reference subset of either $S_{t-1}$ or $S_{t+1}$ such that $X \cap \mathcal{R} \neq \emptyset, \forall \mathcal{R} \in \mathcal{R}$. We will refer to this subset as either set of related groups or, to simplify, **related** set (i.e., related to $X$).

Following (Bovet et al., 2022), the evolution of $X$ can be quantified by adopting either of two perspectives. Under the *backward perspective*, we look at the sets in $t-1$ that contribute to $X$'s formation; thus, imposing $\mathcal{R} \subseteq S_{t-1}$, we say that $X$ evolves from $\mathcal{R}$. Conversely, under the *forward perspective*, we look at the sets in $t+1$ that contain current $X$ members; thus, imposing $\mathcal{R} \subseteq S_{t+1}$, we say that $X$ evolves into $\mathcal{R}$.

## 3.2 Event facet scores

In the literature, events are defined as mutually exclusive categories. In the event-graph representation, the in-degree of a group allows one to distinguish between a merge ($k^{in} \ge 2$), a birth ($k^{in} = 0$), and a continuation ($k^{in} = 1$). Instead, our approach first describes quantitatively the nature of an event using scores called *event facets*.

### 3.2.1 Unicity facet

The first facet is called the Unicity Facet. In the forward perspective, it measures if the entities tend to stay together in a single group, or are disseminated in multiple destination ones, with no dominant one. Conversely, in the backward perspective, it measures if all the entities come from a single source or multiple ones. The unicity facet can be understood as a continuous transition between $\frac{k^{in}}{k^{out}} = 1$ and $\frac{k^{in}}{k^{out}} \ge 2$ in the event graph formalism. Figure 3a illustrates this facet in the backward perspective. For a target set $X$, composed of subsets $\mathcal{R}$, each subset corresponding to a different related set, the Unicity of $X$ is defined as the difference between the fraction (relative size) of the elements in the two largest subsets in $\mathcal{R}$.

**Definition 1 (Unicity Facet)** Let $X$ be the target set, and $\mathcal{R} = [R_1, \dots, R_{|\mathcal{R}|}]$ be the related set, ordered in decreasing order of intersection size with $X$, i.e., $\forall_{i>j}$, $|R_i \cap X| \ge |R_j \cap X|$.

The Unicity Facet is defined as:

$$ U = \begin{cases} \frac{|R_1 \cap X| - |R_2 \cap X|}{|\cup_{R \in \mathcal{R}} R|} & \text{if } |\mathcal{R}| \ge 2 \\ 1 & \text{otherwise} \end{cases} \tag{1} $$
<figure><img src="image_5.png" /><figcaption>Fig. 3 Representation of the continuous nature of facets $\mathcal{U}$ and $\mathcal{I}$</figcaption></figure>

This score guarantees that a large value corresponds to (e.g., in the backward perspective) having one dominating source, and reciprocally, that having a dominating source leads to a high score. Conversely, having a low score corresponds to having no dominating unique source, and having no dominating source leads to a low score.

Note that several diversity indices exist in the literature, such as Gini’s, Herfindahl’s, and normalized Shannon diversity indices, that yield similar results on the example of Fig. 3. However, they do not correspond to our needs, since they do not measure the concentration of values in the dominant source, but rather the concentration in a small fraction of all the sources. This means that these indices can yield low values even in the case of clear merges, or in the case of a large number of different sources. Dominance scores such as the Berger-Parker index, suffer from other limits. The shortcomings of all those scores for Unicity are detailed in Appendix 1.

When no set contributes to $X$, i.e., all elements $x \in X$ are observed for the first time, it can be thought of as if all elements came from a single set existing before our observation period. We thus assign $\mathcal{U} = 1$ in that case. Note that apart from this specific situation, elements observed for the first (resp. last) time play no role in Unicity. Indeed, their presence is taken into account by another facet.

### 3.2.2 Identity facet

An aspect of events that is not directly tackled by existing literature is the question of the preservation of groups’ identity. The term is taken as a parallel with social groups, such as for instance a political party. The group itself can be considered to have an identity, and if too many individuals leave the group, that identity might be lost. The Identity facet measures how much of the identity is transferred by/to the target group. Taking as
an example the backward perspective, let us consider a group $g$, which receives all of its nodes from a group $g_{from}$. The Identity facet measures if the elements of $g$ represent a large fraction of the nodes of $g_{from}$, or only a small fraction of them. The facet thus ranges from 0 to 1, 1 if all the nodes of $g_{from}$ joined $g$— thus, the nodes are considered to come with the identity of their group of origin— and tends towards 0 as the nodes joining $g$ represent a smaller fraction of $g_{from}$. Figure 3b illustrates this facet in the backward perspective.

**Definition 2 (Identity Facet)**

$$ \mathcal{I} = \left\{ \begin{array}{ll} \frac{1}{|\bigcup_{R \in \mathcal{R}} R|} \sum_{R \in \mathcal{R}} |R \cap X| \frac{|R \cap X|}{|R|} & \text{if } |\mathcal{R}| > 0 \\ 0 & \text{otherwise} \end{array} \right. \qquad (2) $$

As an illustrative example, assume that a single set of 10 elements, $R$, provides elements to $X$ with two alternative scenarios: (a) it provides a single element, and (b) it provides 9 out of 10 elements. In the former scenario, the contribution $\mathcal{I}$ will approach 0; in the latter, it will approach 1 (reaching those extreme values only when none or all elements of $R$ are present in $X$).

Note that $\mathcal{I} = 0$ if there is no related set: in that case, the group identity is completely lost (forward) or completely new (backward).

### 3.2.3 Outflow facet

The outflow facet measures the fraction of the group elements that (i) just joined the system in the backward perspective, or (ii) left the system, in the forward perspective. The Outflow facet can be understood as a continuous transition between $\frac{k^{in}}{k^{out}} = 0$ and $\frac{k^{in}}{k^{out}} = 1$ in the event graph formalism, i.e., a birth (resp., death) and a continuation. The facet thus ranges from 0—all elements of the group were already present (resp., remain) in the system—to 1—all elements of the group are new (resp., are not present in the next timestep).

**Definition 3 (Outflow Facet)**

$$ \mathcal{O} = \frac{|X - \bigcup_{R \in \mathcal{R}} R|}{|X|} \qquad (3) $$

## 3.3 Event weights and archetypal events

The facets introduced above describe intuitive quantities that can be used to characterize a group with respect to its evolutionary history, either past or future. Going further, the evolutionary processes that outline a group’s life cycle can be seen as a series of archetypal events that the cluster undergoes. Here, we introduce the possibility of quantifying how much a group and its immediate predecessors/successors approximate some archetypal transformations, by combining facet scores into Event weights. Figure 4 illustrates the relation between two of these facets and event archetypes, some of them common in the literature (Merge, Continuation), some others being new (Reorganization, Offspring), but emerging naturally from our definitions.
<figure><img src="image_6.png" /><figcaption>**Fig. 4** Archetype events according to values of facets *U* and *I*, for *O* = 0. In the middle, an example of an event not clearly affiliated with an archetype according to these facets</figcaption></figure>

We acknowledge that real-world evolutionary events are rarely found in their “pure” or “archetypal” form, often manifesting as complex and hybrid processes, often mired in messiness. As such, it is relevant to characterize these processes as composite, measuring the extent to which they approximate (one or more) “pure” events.

Under the backward perspective, we can do so with the following *event weights*.

**Definition 4** (Backward Event Weights) Let $X$ be the target set and $\mathcal{R}$ be the set of related groups such that $X$ evolves from $\mathcal{R}$. Backward event weights quantify the extent to which $X$'s evolution from $\mathcal{R}$ approximates one of the following transformations:

$$ \text{BIRTH} = \mathcal{U} \cdot (1 - \mathcal{I}) \cdot \mathcal{O} $$

$$ \text{ACCUMULATION} = (1 - \mathcal{U}) \cdot (1 - \mathcal{I}) \cdot \mathcal{O} $$

$$ \text{CONTINUATION} = \mathcal{U} \cdot \mathcal{I} \cdot (1 - \mathcal{O}) $$

$$ \text{MERGE} = (1 - \mathcal{U}) \cdot \mathcal{I} \cdot (1 - \mathcal{O}) $$

$$ \text{OFFSPRING} = \mathcal{U} \cdot (1 - \mathcal{I}) \cdot (1 - \mathcal{O}) $$

$$ \text{REORGANIZATION} = (1 - \mathcal{U}) \cdot (1 - \mathcal{I}) \cdot (1 - \mathcal{O}) $$

$$ \text{GROWTH} = \mathcal{U} \cdot \mathcal{I} \cdot \mathcal{O} $$

$$ \text{EXPANSION} = (1 - \mathcal{U}) \cdot \mathcal{I} \cdot \mathcal{O} $$

BIRTH events are characterized by a high number of joining elements that compose a set $X$, thus, a pure, archetypal BIRTH is found when the outflow $\mathcal{O}$ is maximized. Theoretically, looking at the past to identify a birth is irrelevant since the appearance of new elements is unrelated to the incoming flow. In real-world events, however, some fluctuating elements in $\mathcal{R}$ can also join such newborn sets. The Unicity facet $\mathcal{U}$ of the few elements joining a newborn set lets us further distinguish between a pure BIRTH and an ACCUMULATION, i.e., a birth from subsets – minimizing $\mathcal{U}$.

When the Identity facet is maximized in the absence of new elements, we characterize a CONTINUATION, if Unicity $\mathcal{U}$ is maximized, or a MERGE, if $\mathcal{U}$ is minimized. CONTINUATION
events identify elements from a single set that are found together (i.e., in the same set) in the next timestamp. MERGE events identify the case where two or more sets of similar size join to form a single set in the next timestamp.

When the Identity facet is low, and in the absence of new elements, we can witness an OFFSPRING or a REORGANIZATION, depending on the Unicity. A pure, archetypal OFFSPRING is observed when $U$ is maximized, meaning that a small portion of a single origin set is found in the target set. A REORGANIZATION occurs when $U$ is minimized, meaning the target set comprises small portions of several contributing sets.

When the backward Unicity is maximized in the presence of many new nodes ($\mathcal{O}$ large), we can witness a GROWTH. A pure, archetypal GROWTH is a single set that expands over the next timestamp, thus it is found by maximizing all three facets: Unicity (Single source), Identity (all the source), Outflow (numerous new nodes). If $U$ is minimized, we call the archetype an EXPANSION, i.e., similar to a GROWTH but from several contributing subsets. It should be noted that when $\mathcal{O} = 1$, then by definition $U = 1$ and $\mathcal{I} = 0$, i.e., we are in a BIRTH situation. This means that archetypes ACCUMULATION, GROWTH, and EXPANSION can never reach a value of 1, but can only get close to this maximal value when a majority of nodes are new, but some come from existing groups.

Similarly to Definition 4, other events can be described by adopting the forward perspective.

**Definition 5 (Forward Event Weights)** Let $X$ be the target set and $\mathcal{R}$ be the set of related groups such that $X$ evolves into $\mathcal{R}$. Forward event weights quantify the extent to which $X$'s evolution into $\mathcal{R}$ approximates one of the following transformations:

$$ \text{DEATH} = U \cdot (1 - \mathcal{I}) \cdot \mathcal{O} $$

$$ \text{DISPERSION} = (1 - U) \cdot (1 - \mathcal{I}) \cdot \mathcal{O} $$

$$ \text{CONTINUATION} = U \cdot \mathcal{I} \cdot (1 - \mathcal{O}) $$

$$ \text{SPLIT} = (1 - U) \cdot \mathcal{I} \cdot (1 - \mathcal{O}) $$

$$ \text{ANCESTOR} = U \cdot (1 - \mathcal{I}) \cdot (1 - \mathcal{O}) $$

$$ \text{DISASSEMBLE} = (1 - U) \cdot (1 - \mathcal{I}) \cdot (1 - \mathcal{O}) $$

$$ \text{SHRINK} = U \cdot \mathcal{I} \cdot \mathcal{O} $$

$$ \text{REDUCTION} = (1 - U) \cdot \mathcal{I} \cdot \mathcal{O} $$

The main difference with respect to the events in Definition 4 relates to the meaning of $\mathcal{O}$. From the backward perspective, we compare the target set with the partition in the previous timestamp, so the elements quantified by the Outflow facet are “new”, i.e., they are not present in the previous timestamp. Contrarily, from the forward perspective, we compare the target set with the partition in the next timestamp, so the elements quantified by the Outflow Facet are “dead”, i.e., they are not present in the next timestamp. Thus the equation for DEATH is the same as for BIRTH. A similar situation is found with ACCUMULATION and DISPERSION, MERGE and SPLIT, OFFSPRING and ANCESTOR, REORGANIZATION and DISASSEMBLE, GROWTH and SHRINK, EXPANSION and REDUCTION. The CONTINUATION event, instead, is undirected, meaning that it is measured in the same way regardless of the temporal direction.
## 3.4 Event typicality

Finally, one might be interested in studying events that are closer to their archetype with respect to others, for instance, to separate them from more complex events. To distinguish between less and more pure transformations, we introduce the Event Typicality Index, defined as follows:

**Definition 6** Let $E_X$ be the set of Backward or Forward Event Weights computed for set X. The Event Typicality Index $\mathcal{T}$ is computed as the maximum value among the event weights. Formally:

$$ \mathcal{T} = \max(E_X) \qquad (4) $$

Events corresponding perfectly to archetypes thus have $\mathcal{T} = 1$.

## 3.5 Bidirectional events

Events as they are usually defined in the literature, such as Rossetti and Cazabet (2018), are bidirectional in the sense that they are defined without a sense of direction. The exceptions are Birth and Death, which match our definitions, since they involve groups in only one timestep. For the others, we can describe these bidirectional events using our formalism as a combination of forward and backward events, as follows:

* Literature continuation corresponds to a forward CONTINUATION followed by a backward CONTINUATION.

* Literature merge corresponds to forward ANCESTOR events followed by a backward MERGE. Note that if only two groups of equal size are involved, then the forward event will be between an ANCESTOR and a CONTINUATION.

* Literature split corresponds to a forward SPLIT event followed by an OFFSPRING event. As for merge, with only two groups, the backward events will be between an OFFSPRING and a CONTINUATION.

* Literature growth corresponds to a forward CONTINUATION followed by a backward GROWTH (or CONTINUATION if the faction of new nodes is small).

* Literature shrink corresponds to a forward SHRINK (or CONTINUATION if the faction of quitting nodes is small) followed by a CONTINUATION event.

# 4 Experiments

In this section, we apply the proposed framework to analyze the evolution of groups from real-world data.

## 4.1 Datasets

We leverage the datasets from the SocioPatterns project,<fnref n="1" /> more precisely the Hospital (Vanhems et al., 2013), Primary School (Stehlé et al., 2011), and High-School

<footnote n="1">¹ www.sociopatterns.org</footnote>
<figure><img src="image_7.png" /><figcaption>Fig. 5 Typicality distribution of three SocioPatterns datasets using the same daily aggregation window</figcaption></figure>

(Mastrandrea et al., 2015) datasets. All of them correspond to face-to-face interactions collected via RFID sensors over 4, 2, and 7 days, respectively. They are frequently used in the context of dynamic network analysis, as they allow the consideration of multiple aggregation scales, have a reasonable size to be studied in detail, and undergo dynamics over the studied periods.

As a pre-processing, we first aggregate the data into a series of static networks, using a chosen time scale (hour, day, etc.). We then apply a community detection algorithm, namely the Louvain modularity maximization approach (Blondel et al., 2008). Louvain is a non-deterministic algorithm, meaning that it may return different partitions over multiple runs. We perform some sanity checks on running Louvain on these datasets, and detail them in Appendix 2. This process yields sequences of node partitions, i.e., sets of sets, that constitute the input to our framework.

## 4.2 Events stability and typicality

A specificity of the SocioPatterns datasets is that they are provided at a fine temporal scale of 20 s, but are usually studied by choosing an aggregation scale. Although several approaches exist to do so (e.g., from change points detection (Peel & Clauset, 2015; Darst et al., 2016) to data compression (Cazabet, 2021) in dynamic data), we can leverage our framework to select the most appropriate aggregation scale for partition evolution analysis. Intuitively, to be interpretable, the partition in a timestep should be as similar as possible to partitions in previous and following ones. We know that, by definition, the CONTINUATION event captures how much groups stay unchanged from one timestep to the next. We can thus compute a stability score $\eta$ as follows:

$$ \eta = \frac{1}{|E|} \sum_{e \in E} \text{CONTINUATION}(e) $$

with $E$ the set of all events and CONTINUATION($e$) the event weight for event type CONTINUATION. Moreover, $\eta \in [0, 1]$, a higher score corresponding to more stable groups. In Table 2, we observe that different SocioPatterns datasets are stable at different time-scales. For instance, the Primary School dataset is the most stable of all when using a daily aggregation window. When we check the details of those stable groups, we observe that they match the primary school classes well. The daily aggregation window is not particularly stable for the two other datasets. On the contrary, it is at the smallest aggregation
<table><caption>**Table 2** Stability scores for different durations, PS: Primary School, HS: High School</caption><thead><tr><th>Duration</th><th>η PS</th><th>η Hospital</th><th>η HS</th></tr></thead><tbody><tr><td>1 m</td><td>0.3592</td><td>0.5513</td><td>0.5407</td></tr><tr><td>15 m</td><td>0.3813</td><td>0.2770</td><td>0.4167</td></tr><tr><td>30 m</td><td>0.4042</td><td>0.1999</td><td>0.3276</td></tr><tr><td>1 h</td><td>0.4555</td><td>0.1579</td><td>0.2147</td></tr><tr><td>2 h</td><td>0.3674</td><td>0.1380</td><td>0.1410</td></tr><tr><td>6 h</td><td>0.4533</td><td>0.0929</td><td>0.0818</td></tr><tr><td>12 h</td><td>0.3250</td><td>0.1246</td><td>0.0471</td></tr><tr><td>24 h</td><td>0.7764</td><td>0.1444</td><td>0.1133</td></tr></tbody></table>

We remark that PS is highly stable at the daily aggregation, while the 2 others are more stable at the minute scale

window, at the minute level, that groups are the most stable. When looking at the details, we observe that there are many small groups at this scale, which persist unchanged for some time steps, probably corresponding to interactions in small groups. Thanks to this result, we will use some of the most stable aggregation scales in the following.

In Sect. 3.4, we defined the typicality of an event as the maximal event score for that event in a particular direction. We can leverage this information to describe system-wide the distribution of event types and typicality in a network. In Fig. 5, we plot this distribution for the three datasets at the daily aggregation level. The results are coherent with what we observed for the stability, with the primary school dataset composed mostly of CONTINUATION and MERGE, while the other datasets, mostly unstable, exhibit poorly defined events, at the exception of a few BIRTH and OFFSPRING.

## 4.3 Comparison with state of the art

Comparing the quality of events detected using our approach with those found by previous methods is difficult, due to (i) the absence of external ground truth, and (ii) the difference in nature between events found by previous methods and those produced by our approach. Therefore, we illustrate the interest of our formalism in case studies.

### 4.3.1 Hospital dataset, daily snapshots

In the following, we compare our framework with the event graph formalism by Greene et al. (2010), and the framework by Asur et al. (2009), on the Hospital Dataset, using a daily aggregation window. Daily aggregation seems intuitively reasonable on SocioPatterns datasets, and has commonly been used in the literature. We have seen from Table 2 that it leads to rather unstable partitions for the Hospital dataset. Figure 6a represents the flow for the four days. We observe that the relations between groups are complex, and that assigning archetypes to events does not seem obvious.

Figure 6b represents the event graph obtained from Greene et al. (2010) at the $\mu = 0.1$ threshold, observed to work best by the authors. We observe that in most cases, the events recognized are rather logical: 0_2 and 2_0 being MERGE events, 0_1 and 1_3 being SPLIT events, etc. Only 2 events are CONTINUATION, and 2 others are GROWTH. However, in several other cases, the events obtained are more disputable. Is there no relation between 1_0
<figure><img src="image_8.png" /><figcaption>**Fig. 6** Hospital dataset, daily windows. Groups are labeled as *t_id*, where *t* is the timestamp and *id* is the arbitrary group id. Event legend: =>: CONTINUATION, +: GROWTH</figcaption></figure>

and `2_2`? Is `1_3` really a growth from `0_3`? Why `0_2` is not a split? These limits are consequences of the research of archetypes only, without taking into account the multiple facets of events. Another limit is that most events are intertwined split-and-merge, i.e., outgoing branches of SPLITS form in-going branches of MERGES. The interpretation of such events thus becomes difficult: it seems abusive to say that, for instance, `3_0` is a merge of `2_0` and `2_1`, while both these groups are subject to SPLIT, and only minor fragments of them join into `3_0`.

Using the framework from Asur et al. (2009) leads to an even more unsatisfactory result, since it yields only six recognized events: two MERGES, two SPLITS, and two BIRTHS. Indeed, this framework is very conservative in its definition of events, and most flows are too complex to be recognized as such.

Using our framework, we obtain a richer description of events. We first can consider the typicality of events to identify the closest to archetypes. For instance, the 3 highest forward-CONTINUATION are `0_0`, `1_1`, `2_4`, corresponding to the same group of people continuing in the same group, although not in perfect CONTINUATION. Similarly, the three highest SPLIT scores are `1_3`, `2_1`, `2_0`. We observe that these descriptions are compatible with the description obtained from Greene et al. (2010). However, our framework offers more details. For instance, the forward CONTINUATION of `0_0` also has, in decreasing magnitude, ANCESTOR, SPLIT and DISASSEMBLE facets. Indeed, some of its components join other groups,
while its components represent only 9 out of 15 elements in 1_1, making it far from an archetypal CONTINUATION.

In another example, we focus on an event that seems unconvincing according to Greene et al. (2010), 1_3 seen as a growth from 0_3. We provide the complete facets of 1_3-backward:

* BIRTH: 0.02

* ACCUMULATION: 0.03

* GROWTH: 0.01

* EXPANSION: 0.02

* CONTINUATION: 0.14

* MERGE: 0.25

* OFFSPRING: 0.19

* REORGANIZATION: 0.34

We observe that the dominant facet is REORGANIZATION, since it is composed of multiple minor parts of previous groups. It also has some elements of MERGE, OFFSPRING, and CONTINUATION, which is due to the complexity of receiving a large fraction of its components from the bulk of a single group, while the rest are minor fragments from various other groups.

From this example, we see that when the groups are subject to complex relationships, state-of-the-art approaches yield potentially misleading results, while the richer description of our framework allows a better characterization of group evolution.

### 4.3.2 Primary school, hourly snapshots

We then focus on the Primary School dataset, at the hourly aggregation timescale. We have seen from Table 2 that it is the most stable aggregation step, if we ignore the 1-minute aggregation steps that yield very small groups, and the PS 1-day aggregation window, which contains nearly only perfect CONTINUATION events as seen in Fig. 5.

We first focus on the details of the flow during the first 4 h and plot the details in Fig. 7. We observe that events seem indeed much easier to characterize than in the previous case.

Many events are recognized as pure CONTINUATION by all three frameworks, such as (0_2→1_3), (0_10→1_9), (1_3→2_1), etc. All frameworks also agree on BIRTH events for →1_1, →1_2), while a few other events are recognized without ambiguity as MERGE by all frameworks, such as (1_2, 1_1)→2_0 or (1_5, 1_0)→2_3).

However, we also find ambiguous cases in this dataset. Let us focus on one example, the event involving groups (0_15, 0_0, 0_1, 1_0): According to Asur et al. (2009), this event has no label. According to Greene et al., it is a merge from 0_0, 0_1 into 1_0, and 0_15 is a death. With our framework, 0_15, 0_0, 0_1 are classified as ANCESTORS ($T=0.8$), while 1_0-backward is MERGE($T=0.45$) and EXPANSION($T=0.45$). Indeed, we see that this new group is composed of one-half of a perfect merge of those
<figure><img src="image_9.png" /><figcaption>Fig. 7 Primary School, 1 h windows, first 4 h</figcaption></figure>

3 predecessors, the other half being new entities. Through this example, we see that using a richer description is also useful even when group evolution is mostly stable.

Beyond focusing on individual events, our framework can be used to describe system-wide dynamics. Figure 8 details the evolution of events for each hour *t*, by computing the contribution of each event type as $\sum_{X \in S} |X|E(X)$, $E(X)$ the score for this event type for target group X and $|X|$ the number of entities in these groups.

From a backward perspective, most groups are born in the first hours (8:00–10:00), when students arrive at their classrooms and have the chance to connect. Conversely, group death in the forward perspective occurs at the end of days, when students leave the school.

Communities are mostly stable during class hours, as exemplified by the large CONTINUATION areas between 9:00–12:00, and 14:00–17:00. However, some MERGE, respectively SPLIT events can also be observed during that period.

In the middle of the school day, students are primarily involved in REORGANIZATION (backward) and DISASSEMBLE (forward) events, i.e., few students detach from large communities and form new groups, themselves composed of students from multiple groups. This can be interpreted as a lunchtime activity, in which students can meet peers from other classes. Indeed, we can validate this hypothesis by looking at the Attribute Entropy Change (cf. Appendix 3 for its definition), using class membership as an attribute. We observe an average ~25% increase after MERGE events, meaning that groups resulting from these events are more varied with respect to the contributing ones in the corresponding previous timestamp.

We can also observe a symmetric phenomenon, with DISPERSION events occurring in the forward direction at the beginning of the lunch break, answered with ACCUMULATION (backward) after the break. These event types are in the same color in the figures because they correspond to the same combination of facets. These events are characterized by important outflows. Indeed, one can observe that many students do not participate in the lunch break at school, which can explain this situation.

In fact, the full picture of a group’s transformations can be obtained by analyzing all of its event weights. For example, in Fig. 9, we show backward and forward event weights for
<figure><img src="image_10.png" /><figcaption>**Fig. 8** Temporal distribution of Backward (top) and Forward (bottom) events in the Primary School dataset with a 1-h resolution. We observe a similar pattern for the two days of analysis, with stable groups —large fractions of *continuation* events—during teaching hours, and more diverse events during lunch time</figcaption></figure>

group 2_7. The backward event weights highlight a MERGE-like event showing some traits of a CONTINUATION (i.e., one larger contributing group), of an OFFSPRING (due to the largest contributing group not coming in full), and of REORGANIZATION (due to the low contribution of the smaller contributing groups). The forward event weights, instead, describe an event showing traits of SPLIT — due to the separation into multiple, mostly equally-sized groups — and CONTINUATION because of the larger group moving to 3_9.
<figure><img src="image_11.png" /><figcaption>**Fig. 9** Backward and Forward event weights extracted from group 2_7 in Primary School, 1-h resolution</figcaption></figure>

# 5 Discussion and conclusion

In this paper, we introduced a framework to describe the temporal dynamics of groups by assessing their similarity to archetypal categories. This produces a flexible frame that removes the need for arbitrary thresholds while accurately representing the transformations at play at the same time. We have shown how this framework can be applied to the longitudinal analysis of temporal data, specifically in studying (i) the evolution of target groups, (ii) the evolution of the whole system in terms of its mesoscale dynamics, and (iii) how temporal granularity may impact observations on group transformations. We observed that, whatever the framework, identifying events with unstable dynamic groups seem doomed to fail, thus emphasizing the importance of smoothed dynamic clustering (Cazabet et al., 2020).

In this work, we focused on non-overlapping groups, as it remains the most common scenario both for clustering and community detection in graphs. The facets proposed could still work to characterize individual events in overlapping scenarios, however overlapping sets also have specificities that are not tackled in the present work. Other group specificities, such as periodically inactive groups (resurgences) or entities present in the system but belonging to no groups, or fuzzy groups, could be the focus on extensions of the present contribution. Another possible extension of our work would be to follow the work of Pereira et al. (2021) to define events adjusted for chance, i.e., if a group mostly continue in another group, but this would be expected in the case of random node assignment due to the group size, then we should normalize the scores obtained by the values expected due simply to chance.

Moreover, by introducing measures to quantify the change in the entities’ labels (see Definition 7 in Appendix 3), we also suggest that the relation between group structures and entities’ metadata could be explored further. For instance, this framework could be applied to the analysis of spatiotemporal clusters in human mobility data to understand whether differences in individual attributes are related to substantial differences in group mobility patterns. Another interesting applicative scenario could be the characterization of groups emerging from online social interactions to evaluate peer pressure effects, i.e., to measure the extent to which groups induce opinion change or, conversely, evaluate how opinion change drives group formation. To do so, however, one should account for time-changing attribute values, an aspect we did not cover in this work. Moving away from simply finding
<table><caption>**Table 3** Scores obtained using diversity indices for a situation in which 80% of elements come from a majority source, and 20% from, respectively, a single source, two sources, and 20 different sources (each contributing equally)</caption><thead><tr><th rowspan="2"></th><th colspan="3">Number of sources beyond the main one</th></tr><tr><th>1</th><th>2</th><th>20</th></tr></thead><tbody><tr><th>Gini's</th><td>0.75</td><td>0.46</td><td>0.3</td></tr><tr><th>Shannon's</th><td>0.72</td><td>0.58</td><td>0.35</td></tr><tr><th>Berger-Parker</th><td>0.8</td><td>0.8</td><td>0.8</td></tr><tr><th>Unicity</th><td>0.6</td><td>0.6</td><td>0.79</td></tr></tbody></table>

We observe that Gini's and Shannon's diversity indices switch from a large to a low value depending only on how the remaining 20% are distributed, while Unicity remains large, as expected since a large majority of nodes comes from a unique source

evolutive patterns in the data, this framework and its measures could be exploited to forecast both individual and group activity, e.g. using the proposed measures as input for a classification task.

## Appendix 1: Unicity facet

We have defined the Unicity facet for a target group as the difference between the fraction of elements in the two largest related sets. One could think that similar indices already exist in the literature, known as diversity indices. Indeed, there is a family of such indices (Morales et al., 2021), including Gini's, Herfindahl's, Shannon's (normalized) diversity, and even dominance scores such as the Berger-Parker index (later, BP). The problem with Berger-Parker is that it depends only on the most frequent contributing set, ignoring the others. Thus, it does not distinguish between a case in which there are two sources representing each 50% of the target set (a perfect merge), and a case in which 50% of the target set comes from a single source, and the rest comes from fragmented sources (something very different from a merge, as it has a single relevant source).

Diversity indices such as Gini's and Shannon's do make this distinction. However, their shortcoming is that the value is dominated by the number of different contributing sources. Considering an example in which one single source represents 80% of the target set, then such diversity indices are dominated by how the remaining 20% are distributed (see Table 3).

We thus express more formally the desired properties for the unicity facet $\mathcal{U}$, and which ones are not respected by existing diversity indices.

1. $\mathcal{U} = 1$ if there is a single related set, as expected in a continuation event.

2. $\mathcal{U} = 0$ if there are two or more related sets sharing equally the elements of $X$, as expected in an archetypal merge or split.

3. Independently of $|\mathcal{R}|$, $\lim_{|R_1 \cap X|/|X| \to 1} \mathcal{U} = 1$

4. Independently of $|\mathcal{R}|$, with $|R_1| = |R_2|$, $\lim_{(R_1 \cup R_2) \cap X|/|X| \to 1} \mathcal{U} = 0$

Property 1. is true for Gini/Shannon and BP. It is true for $\mathcal{U}$ by considering that $|R_2| = 0$ if $|\mathcal{R}| = 1$. Property 2 is true for Gini/Shannon but not for BP. Property 3 is true for BP but
<figure><img src="image_12.png" /><figcaption>**Fig. 10** Comparison between Unicity, diversity, and dominance indices. On the top row, cases in which Unicity=0, i.e., there is not one dominating element. One can think of them as merge/split. The bottom row corresponds to situations with a dominant element, either a relative domination (**e**) or an absolute one (**f**, **g**, **h**). Unicity value increases as the domination of the main element is relatively strong. BP has the same scores for (**a**) and (**e**), although the first one is clearly not unique. Scores for Gini and Shannon are high (**d**), having close values with (**h**), although the former clearly looks more like a merge, and the second like having a unique main source</figcaption></figure>

not for Gini/Shannon, because it depends on $|R|$. Property 4 is false both for Gini/Shannon and BP.

In Fig. 10, we illustrate different cases and the advantages of Unicity over existing scores to capture the notion of having a unique, dominating source, or not.

## Appendix 2: Evaluating clustering sensitivity

In this section, we aim to estimate our results' sensitivity to the variability intrinsic in the Louvain algorithm. Indeed, Louvain is non-deterministic, meaning that its output may vary across multiple runs. We analyze all snapshots of both hourly- and daily-aggregated SocioPatterns data, since most of our experiments are performed at these temporal scales. We run the algorithm 100 times for each snapshot of the daily- and hourly-aggregated SocioPatterns datasets. For each snapshot, we compare all pairs of partitions via Adjusted Mutual Information (AMI) and Adjusted Rand Index (ARI) (Vinh et al., 2009; Hubert & Arabie, 1985). Both measures
<figure><img src="image_13.png" /><figcaption>Fig. 11 Evaluation of Louvain stability in terms of a Adjusted Mutual Information and b Adjusted Rand Index. Top: PS; center: HS; bottom: Hospital</figcaption></figure>

are adjustments of clustering similarity measures to account for chance, and are computed as follows:

$$f_{adj}(C_1, C_2) = \frac{f(C_1, C_2) - E(f(C_1, C_2))}{max(f(C_1, C_2)) - E(f(C_1, C_2))}, \quad (5)$$

where $C_1$ and $C_2$ are two data partitions, $f(C_1, C_2)$ is a function comparing clustering similarity, and $E(f(C_1, C_2))$ is the expected value for $f(C_1, C_2)$. For AMI, $f$ computes the Mutual Information, For ARI, the Rand Index is computed instead. Both AMI and ARI indices measure partition similarity and return values close to 1 if the partitions are similar (up to a full permutation), and values close to 0 otherwise. Figure 11 displays average values for each snapshot, along with the corresponding standard deviations (represented as error bars). Both AMI and ARI values outline coherence in Louvain’s outputs for all datasets, at all snapshots, and at both temporal scales. Indeed, values are close to 1 in all scenarios, with minimal variations. This is especially true for the PS dataset. The only
sensible difference we record relates to the Hospital dataset, where the average values reach a minimum of ~ 0.8 and ~ 0.5 in the daily and hourly aggregations respectively. However, in Sect. 4.3.1, where this dataset is analyzed, we focus specifically on the daily aggregation, which shows lower sensitivity to reruns overall.

## Appendix 3: Attribute entropy change

We introduce the possibility of labeling the elements in a set with a categorical attribute A such that $a(e) \in A$ identifies the categorical attribute value of an element e. We assume the attribute value assigned to an element stays the same across time. We use a measure of diversity (Morales et al., 2021), the Shannon entropy diversity index, to quantify changes in group mixing with respect to the attribute value.

**Definition 7 (Attribute Entropy Change)** Let the Attribute Entropy of X's elements be:

$$ \mathcal{H}_{att}(X) = - \sum_{x \in X} \frac{p(a(x)) \log_2 p(a(x))}{\log_2 |\{a(x) \forall x \in X\}|} \quad (6) $$

The attribute entropy change is defined as the difference between the Attribute Entropy of the current set X and the mean of the Attribute Entropies of the related sets. Formally:

$$ \mathcal{M} = \Delta \mathcal{H}_{att} = \mathcal{H}_{att}(X) - \frac{1}{|\mathcal{R}|} \sum_{R \in \mathcal{R}} \mathcal{H}_{att}(R) \quad (7) $$

**Author contributions** All authors designed research, performed research, and wrote the paper. A.F., S.C., and R.C. contributed to the acquisition, analysis, and interpretation of the experiments. A.F., S.C., and R.C. contributed to the software design and to its implementation. S.C., G.R., and R.C. coordinated and supervised all of the research. All authors read and approved the final manuscript.

**Funding** Open access funding provided by Consiglio Nazionale Delle Ricerche (CNR) within the CRUI-CARE Agreement. This project was partly funded by: (i) BITUNAM grant ANR-18-CE23-0004; (ii) SoBigData.it which receives funding from the European Union - NextGenerationEU - National Recovery and Resilience Plan (Piano Nazionale di Ripresa e Resilienza, PNRR) - Project: “SoBigData.it - Strengthening the Italian RI for Social Mining and Big Data Analytics” - Prot. IR0000013 - Avviso n. 3264 del 28/12/2021; (iii) EU NextGenerationEU programme under the funding schemes PNRR-PE-AI FAIR (Future Artificial Intelligence Research).

**Data availability** All data used in this paper is available on the SocioPatterns project website (URL: www.sociopatterns.org). No new data was generated.

**Code availability** The code is available in a dedicated GitHub repository at the link: https://github.com/andreafailla/LifeCycles, and integrated in the CDLib library, see documentation at the link: https://cdlib.readthedocs.io/en/latest/reference/events.html.

## Declarations

**Conflict of interest** The authors have no relevant financial or non-financial interests to disclose.

**Open Access** This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long
as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.

## References

Ansari, M. Y., Ahmad, A., Khan, S. S., & Bhushan, G. (2020). Mainuddin: Spatiotemporal clustering— A review. *Artificial Intelligence Review*, 53, 2381–2423.

Asur, S., Parthasarathy, S., & Ucar, D. (2009). An event-based framework for characterizing the evolutionary behavior of interaction graphs. *ACM Transactions on Knowledge Discovery from Data (TKDD)*, 3(4), 1–36.

Blondel, V. D., Guillaume, J.-L., Lambiotte, R., & Lefebvre, E. (2008). Fast unfolding of communities in large networks. *Journal of Statistical Mechanics: Theory and Experiment*, 2008(10), 10008.

Bovet, A., Delvenne, J.-C., & Lambiotte, R. (2022). Flow stability for dynamic community detection. *Science Advances*, 8(19), 3063.

Brodka, P., Musial, K., & Kazienko, P. (2009). A performance of centrality calculation in social networks. In *2009 international conference on computational aspects of social networks* (pp. 24–31). IEEE.

Bródka, P., Saganowski, S., & Kazienko, P. (2013). GED: The method for group evolution discovery in social networks. *Social Network Analysis and Mining*, 3, 1–14.

Cazabet, R. (2021). Data compression to choose a proper dynamic network representation. In *Complex networks & their applications IX: Volume 1, Proceedings of the ninth international conference on complex networks and their applications COMPLEX NETWORKS 2020* (pp. 522–532). Springer.

Cazabet, R., Rossetti, G., & Amblard, F. (2018). In: Alhajj, R., Rokne, J. (Eds.), *Dynamic community detection* (pp. 669–678). Springer. https://doi.org/10.1007/978-1-4939-7131-2_383

Cazabet, R., Boudebza, S., & Rossetti, G. (2020). Evaluating community detection algorithms for progressively evolving graphs. *Journal of Complex Networks*, 8(6), 027.

Darst, R. K., Granell, C., Arenas, A., Gómez, S., Saramäki, J., & Fortunato, S. (2016). Detection of timescales in evolving complex systems. *Scientific Reports*, 6(1), 39713.

Fortunato, S., & Hric, D. (2016). Community detection in networks: A user guide. *Physics Reports*, 659, 1–44.

Gliwa, B., Saganowski, S., Zygmunt, A., Bródka, P., Kazienko, P., & Kozak, J. (2012). Identification of group changes in blogosphere. In *2012 IEEE/ACM international conference on advances in social networks analysis and mining* (pp. 1201–1206). IEEE.

Greene, D., Doyle, D., & Cunningham, P. (2010). Tracking the evolution of communities in dynamic social networks. In *2010 international conference on advances in social networks analysis and mining* (pp. 176–183). IEEE.

Hopcroft, J., Khan, O., Kulis, B., & Selman, B. (2004). Tracking evolving communities in large linked networks. *Proceedings of the National Academy of Sciences*, 101, 5249–5253.

Hubert, L., & Arabie, P. (1985). Comparing partitions. *Journal of classification*, 2, 193–218.

İlhan, N., & Öğüdücü, Ş.G. (2015). Predicting community evolution based on time series modeling. In *Proceedings of the 2015 IEEE/ACM international conference on advances in social networks analysis and mining 2015* (pp. 1509–1516).

Kalnis, P., Mamoulis, N., & Bakiras, S. (2005). On discovering moving clusters in spatio-temporal data. In *Advances in spatial and temporal databases: 9th international symposium, SSTD 2005, Proceedings* 9 (pp. 364–381). Springer.

Kisilevich, S., Mansmann, F., Nanni, M., & Rinzivillo, S. (2010). *Spatio-temporal clustering*. Springer.

Lughofer, E. (2012). A dynamic split-and-merge approach for evolving cluster models. *Evolving Systems*, 3(3), 135–151.

MacQueen, J. (1967). Some methods for classification and analysis of multivariate observations. In *Proceedings of the fifth Berkeley symposium on mathematical statistics and probability* (Vol. 1, pp. 281–297).

Mall, R., Langone, R., & Suykens, J. A. (2015). Netgram: Visualizing communities in evolving networks. *PloS One*, 10(9), 0137502.
Mastrandrea, R., Fournet, J., & Barrat, A. (2015). Contact patterns in a high school: A comparison between data collected using wearable sensors, contact diaries and friendship surveys. *PloS One*, 10(9), 0136497.

Morales, P. R., Lamarche-Perrin, R., Fournier-S’Niehotta, R., Poulain, R., Tabourier, L., & Tarissan, F. (2021). Measuring diversity in heterogeneous information networks. *Theoretical Computer Science*, 859, 80–115.

Palla, G., Barabási, A.-L., & Vicsek, T. (2007). Quantifying social group evolution. *Nature*, 446(7136), 664–667.

Peel, L., & Clauset, A. (2015). Detecting change points in the large-scale structure of evolving networks. In *Proceedings of the AAAI conference on artificial intelligence* (Vol. 29).

Pereira, L. R., Lopes, R. J., & Louca, J. (2021). Community identity in a temporal network: A taxonomy proposal. *Ecological Complexity*, 45, 100904.

Rosch, E. (1975). Cognitive representations of semantic categories. *Journal of Experimental Psychology: General*, 104(3), 192.

Rossetti, G., & Cazabet, R. (2018). Community discovery in dynamic networks: A survey. *ACM Computing Surveys (CSUR)*, 51(2), 1–37.

Saganowski, S. (2015). Predicting community evolution in social networks. In *Proceedings of the 2015 IEEE/ACM international conference on advances in social networks analysis and mining 2015* (pp. 924–925).

Stehlé, J., Voirin, N., Barrat, A., Cattuto, C., Isella, L., Pinton, J.-F., Quaggiotto, M., Broeck, W., Régis, C., & Lina, B. (2011). High-resolution measurements of face-to-face contact patterns in a primary school. *PloS One*, 6(8), 23176.

Sun, Y., Tang, J., Pan, L., & Li, J. (2015). Matrix based community evolution events detection in online social networks. In *2015 IEEE international conference on smart city/SocialCom/SustainCom (SmartCity)* (pp. 465–470). IEEE.

Tsoukanara, E., Koloniari, G., & Pitoura, E. (2021). Should I stay or should I go: Predicting changes in cluster membership. In *Web and big data. APWeb-WAIM 2021 international workshops: KGMA 2021, SemiBDMA 2021, DeepLUDA 2021*, Revised Selected Papers 5 (pp. 3–15). Springer.

Vanhems, P., Barrat, A., Cattuto, C., Pinton, J.-F., Khanafar, N., Régis, C., Kim, B.-A., Comte, B., & Voirin, N. (2013). Estimating potential infection transmission routes in hospital wards using wearable proximity sensors. *PloS One*, 8(9), 73970.

Vinh, N., Epps, J., & Bailey, J. (2009). Information theoretic measures for clusterings comparison: Variants. *Properties, Normalization and Correction for Chance*, 18.

Zubaroğlu, A., & Atalay, V. (2021). Data stream clustering: A review. *Artificial Intelligence Review*, 54(2), 1201–1236.

**Publisher’s Note** Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.