Edoardo Galimberti

Martino Ciaperoni

Alain Barrat

Francesco Bonchi

Ciro Cattuto

Francesco Gullo

Span-core Decomposition for Temporal Networks: Algorithms and Applications

come   L'archive ouverte pluridisciplinaire

Introduction

A temporal network1 is a representation of entities (vertices), their relations (links), and how these relations are established/broken over time. Notice that here we will consider discrete times, i.e., the temporal networks can be represented as a time-ordered series of snapshots (instantaneous graphs). Extracting dense structures (i.e., groups of vertices exhibiting a large number of links with each other), together with their temporal span (i.e., the period of time for which the high density is observed) is a key mining primitive to characterize such temporal networks and extract relevant structures. This type of pattern enables fine-grain analysis of the network dynamics and can be a building block towards more complex tasks and applications, such as finding temporally recurring subgraphs or anomalously dense ones. For instance, they can help in studying contact networks among individuals to quantify the transmission opportunities of respiratory infections in a population and uncover situations where the risk of transmission is higher, with the goal of designing mitigation strategies [START_REF] Valerio Gemmetto | Mitigation of infectious disease at school: targeted class closure vs school closure[END_REF]. Anomalously dense temporal patterns among entities in a co-occurrence graph (e.g., extracted from the Twitter stream) have also been used to identify events and buzzing stories in real time [START_REF] Angel | Dense subgraph maintenance under streaming edge weight updates for real-time story identification[END_REF][START_REF] Bonchi | Identifying buzzing stories via anomalous temporal subgraph discovery[END_REF]. Another example concerns scientific collaboration and citation networks, where these patterns can help understand the dynamics of collaboration in successful professional teams, study the evolution of scientific topics, and detect emerging technologies [START_REF] Érdi | Prediction of emerging technologies based on analysis of the us patent citation network[END_REF].

In this paper we adopt as a measure of density of a pattern the minimum degree holding among the vertices in the subgraph during the pattern's span. The problem of extracting all these patterns is tackled by introducing a notion of temporal core decomposition in which each core is associated with its span, i.e., an interval of contiguous timestamps, for which the coreness property holds. We term such a notion of temporal core span-core.

Moreover, in several application scenarios it is typically required to identify only those dense patterns that contain a given set of query vertices. We therefore introduce the problem of temporal community search, whose goal is to find a set of cohesive temporal subgraphs containing the input query vertices and covering the whole temporal domain.

To the best of our knowledge, the problems of (efficient) span-core computation and temporal community search have never been studied so far.

Challenges and contributions

As the number of possible time intervals is quadratic in the size of the input temporal domain T , the total number of span-cores is, in the worst case, quadratic in T too. The naive method to find all span-cores, which would be to operate a core decomposition for each of these time intervals, would therefore be very time-consuming. This is a major challenge that we tackle by deriving containment properties between span-cores and by exploiting them to devise an algorithm for computing all the span-cores that is significantly more efficient than the naïve exhaustive method.

We then shift our attention to the problem of finding only the maximal spancores, defined as the span-cores that are not dominated by any other span-core by both the coreness property and the span. A straightforward way of approaching this problem is to filter out non-maximal span-cores during the execution of an algorithm for computing the whole span-core decomposition. However, as the maximal ones are usually much less numerous than the overall span-cores, it would be desirable to have a method that effectively exploits the maximality property and extracts maximal span-cores directly, without computing the complete decomposition. The design of an algorithm of this kind is an interesting challenge, as it contrasts with the intrinsic conceptual properties of core decomposition, based on which a core of order k can be efficiently computed from the core of order k -1, of which it is a subset. For this reason, at first glance, the computation of the core of the highest order would seem as hard as computing the overall core decomposition. Instead, in this work we derive a number of theoretical properties about the relationship among span-cores of different temporal intervals and, based on these findings, we show how such a challenging goal may be achieved.

Finally, we focus on the problem of community search in temporal networks. Community search has been extensively studied in static graphs. It requires to find a subgraph containing a given set of query vertices and maximizing a certain density measure [START_REF] Fang | A survey of community search over big graphs[END_REF][START_REF] Huang | Community search over big graphs: Models, algorithms, and opportunities[END_REF]. Here, we propose a formulation of the communitysearch problem in temporal networks as follows: given a set Q of query vertices, and a positive integer h, find a segmentation of the underlying temporal domain in h segments {∆ i } h i=1 and a subgraph S i for every identified segment ∆ i such that each S i contains the query vertices Q and the total density of the subgraphs is maximized. Following the bulk of the literature in community search on static networks, in our definition of temporal community search we adopt the minimum degree as a density measure.

We show that, with some manipulations, temporal community search can be reformulated as an instance of the popular sequence segmentation problem, which asks for partitioning a sequence of numerical values into h segments so as to minimize the sum of the penalties (according to some penalty function) on the identified segments [START_REF] Bellman | On the approximation of curves by line segments using dynamic programming[END_REF]. Therefore, the classical dynamic-programming algorithm for sequence segmentation by Bellman [START_REF] Bellman | On the approximation of curves by line segments using dynamic programming[END_REF] can be easily adapted to solve temporal community search in polynomial time.

A criticality of this approach is that a naïve adaptation of the Bellman's algorithm takes quadratic time in the size of the input temporal domain T . As a major contribution in this regard, we prove that the set of maximal span-cores provide a sound and complete basis to still have an optimal solution to temporal community search, while at the same time leading to a significant speed-up with respect to the naïve method. In fact, let T * ⊆ T be the subset of timestamps that are covered by the span of at least one maximal span-core, together with the timestamps that immediately precede or succeed any of such spans. We show that considering T * (instead of T ) in the (adaptation of the) Bellman's algorithm is sufficient to optimally solve the underlying temporal-communitysearch problem instance. As, typically, |T * | |T |, this finding guarantees a considerable improvement in efficiency (as confirmed by our experiments).

A further challenge in our temporal-community-search problem is a typical one in community-search formulations based on minimum degree, namely, that the output subgraphs are typically large in size. We tackle this challenge by devising a method to reduce the size of the output subgraphs without affecting optimality. The proposed method is inspired by the one devised by Barbieri et al. [START_REF] Barbieri | Efficient and effective community search[END_REF] for the problem of minimum community search (in static graphs).

To summarize, the main contributions of this paper are as follows:

• We introduce the notion of span-core decomposition and maximal spancore in temporal networks, characterizing structure and size of the search space and providing important containment properties (Section 3).

• We devise an algorithm for computing all span-cores that exploits the aforementioned containment properties and is orders of magnitude faster than a naïve method based on traditional core decomposition (Section 4).

• We study the problem of finding only the maximal span-cores. We derive several theoretical findings about the relationship between maximal span-cores and exploit these findings to devise an algorithm that is more efficient than computing all span-cores and discarding the non-maximal ones (Section 5).

• We introduce the problem of temporal community search and show how it can be solved in polynomial time via dynamic programming. We prove an important connection between temporal community search and maximal span-cores, which allows us to devise an algorithm that is considerably more efficient than the naïve dynamic-programming one. We also propose a method to achieve the critical challenge of having too large communities as output (Section 6).

• We provide a comprehensive experimentation on several real-world temporal networks, with millions of vertices, tens of millions of edges, and hundreds of timestamps, which attests efficiency and scalability of our methods (Section 7).

• We present applications on face-to-face interaction networks that illustrate the relevance of the notions of (maximal) span-core and temporal community search in real-life analyses and applications (Section 8).

The next section provides an overview of the related literature, while Section 9 discusses future work and concludes the paper.

An abridged version of this work, covering Sections 4 and 5, together with the corresponding experiments (i.e., parts of Sections 7 and 8), was presented in [START_REF] Galimberti | Mining (maximal) span-cores from temporal networks[END_REF]. Reproducibility. For the sake of reproducibility, all our code and some of the datasets used in this paper are available at github.com/egalimberti/span cores.

2 Background and related work Definition 1 (k-core and core decomposition [START_REF] Matula | Smallest-last ordering and clustering and graph coloring algorithms[END_REF]) The k-core

(or core of order k) of G is a maximal set of vertices C k ⊆ V such that ∀u ∈ C k : d(C k , u) ≥ k. The set of all k-cores V = C 0 ⊇ C 1 ⊇ • • • ⊇ C k * (k * = arg max k C k = ∅) is the core decomposition of G.
Core decomposition can be computed in linear time by iteratively removing the smallest-degree vertex and setting its core number as equal to its degree at the time of removal [START_REF] Batagelj | Fast algorithms for determining (generalized) core groups in social networks[END_REF]. Among the many definitions of dense structures, core decomposition is particularly appealing as, among others, it is fast to compute, and can speed-up/approximate dense-subgraph extraction according to various other definitions. For instance, core decomposition allows for finding cliques more efficiently [START_REF] Eppstein | Listing all maximal cliques in sparse graphs in near-optimal time[END_REF], as a k-clique is contained into a (k-1)-core, which can be significantly smaller than the original graph. Moreover, core decomposition is at the basis of approximation algorithms for the densest-(at-least-k-)subgraph problem [START_REF] Kortsarz | Generating sparse 2-spanners[END_REF][START_REF] Andersen | Finding dense subgraphs with size bounds[END_REF], and betweenness centrality [START_REF] Healy | Characterization of graphs using degree cores[END_REF]. Core decomposition has also been recognized as an important tool to analyze and visualize complex networks [START_REF] Batagelj | Partitioning approach to visualization of large graphs[END_REF][START_REF] Alvarez-Hamelin | Large scale networks fingerprinting and visualization using the k-core decomposition[END_REF] in several domains, e.g., bioinformatics [START_REF] Gary | An automated method for finding molecular complexes in large protein interaction networks[END_REF][START_REF] Wuchty | Peeling the yeast protein network[END_REF], software engineering [START_REF] Zhang | Using the k-core decomposition to analyze the static structure of large-scale software systems[END_REF], and social networks [START_REF] Kitsak | Identifying influential spreaders in complex networks[END_REF][START_REF] Garcia | Social resilience in online communities: The autopsy of friendster[END_REF]. It has been studied under various settings, such as distributed [START_REF] Montresor | Distributed k-core decomposition[END_REF], streaming/maintenance [START_REF] Erdem Sariyüce | Streaming algorithms for k-core decomposition[END_REF][START_REF] Li | Efficient core maintenance in large dynamic graphs[END_REF], and disk-based [START_REF] Cheng | Efficient core decomposition in massive networks[END_REF], and generalized to various types of static graphs, such as uncertain [START_REF] Bonchi | Core decomposition of uncertain graphs[END_REF], directed [START_REF] Giatsidis | Dcores: measuring collaboration of directed graphs based on degeneracy[END_REF], weighted [START_REF] Garas | A k -shell decomposition method for weighted networks[END_REF][START_REF] Eidsaa | s-core network decomposition: A generalization of k-core analysis to weighted networks[END_REF], bipartite graphs [START_REF] Liu | Efficient (a, β)-core computation: an index-based approach[END_REF], or including attributes on the nodes [START_REF] Zhang | When engagement meets similarity: efficient (k, r)-core computation on social networks[END_REF]. For a comprehensive survey about theory, algorithms, and applications of core decomposition we refer to [START_REF] Malliaros | The core decomposition of networks: Theory, algorithms and applications[END_REF].

Two types of extension of the core-decomposition bear some relation to our work. First, core decomposition in multilayer networks has been studied in [START_REF] Galimberti | Core decomposition and densest subgraph in multilayer networks[END_REF]. As a core is allowed in this setting to extend on any subset of layers, the total number of cores is intrinsically exponential in the number of layers. Although temporal networks can be seen as a special case of multilayer networks (where each timestamp is interpreted as a layer), there is a fundamental difference: in a temporal network, the "layers" are ordered and the sequentiality of timestamps represents an important structural constraint. Here, we are interested in cores that span a temporal interval, and not simply any subset of (potentially noncontiguous) timestamps. As a consequence, the search space and the number of cores are no longer exponential as in the multilayer case. Second, Wu et al. [START_REF] Wu | Core decomposition in large temporal graphs[END_REF] have proposed a core decomposition on temporal networks, which however does not take any kind of temporal constraint into account. They define indeed the (k, h)-core as the largest subgraph in which every vertex has at least k neighbors and there are at least h temporal edges between the vertex and its neighbors, without any restriction on when these h edges occur: the sequentiality of connections is not taken into account and non-contiguous timestamps can support the same core. In fact, the (k, h)-core decomposition can be seen as a kind of weighted static core decomposition on the weighted static network resulting from the aggregation of the temporal network. In contrast, our temporal cores have each a clear temporal collocation and continuous spans, so that our definition includes temporality in an explicit way and cannot be reduced to the one of Wu et al.'s. As we will see in Section 8, associating a temporal collocation to each core is important in applications.

Patterns in temporal networks

A number of works on extracting dense patterns from a temporal network focus on the well-established notion of densest subgraph, i.e., a subgraph maximizing the average-degree density. Jethava and Beerenwinkel [START_REF] Jethava | Finding dense subgraphs in relational graphs[END_REF] consider as input a set of graphs sharing the same vertex set, which can thus also be interpreted as a temporal network. On such an input they study the densest common subgraph problem, i.e., the problem of finding a subgraph maximizing the minimum average degree over all graphs (timestamps), and devise a linear-programming formulation and a greedy heuristic algorithm for it. Further (mostly theoretical) advancements to the densest-common-subgraph problem have been provided by Reinthal et al. [START_REF] Reinthal | Finding the densest common subgraph with linear programming[END_REF] and Charikar et al. [START_REF] Charikar | On finding dense common subgraphs[END_REF]. Semertzidis et al. [START_REF] Semertzidis | Finding lasting dense subgraphs[END_REF] instead introduce two more variants of the problem, where the goal is to maximize the average average degree and the minimum minimum degree, respectively. They show that the average-average variant easily reduces to the traditional densestsubgraph problem, and that the minimum-minimum variant can be exactly solved by a simple adaptation of the classic algorithm for core decomposition.

Complementary works focus on variants of the densest-subgraph-discovery problem. Rozenshtein et al. study the problem of discovering dense temporal subgraphs whose edges occur in short time intervals considering the exact timestamp of the occurrences [START_REF] Polina Rozenshtein | Finding dynamic dense subgraphs[END_REF], and the problem of partitioning the timeline of a temporal network into non-overlapping intervals, such that the intervals span subgraphs with maximum total density [START_REF] Polina Rozenshtein | Finding events in temporal networks: Segmentation meets densest-subgraph discovery[END_REF]. Epasto et al. [START_REF] Epasto | Efficient densest subgraph computation in evolving graphs[END_REF] deal with the problem of maintaining the densest subgraph in a dynamic setting.

Attention in the literature has also been devoted to densities other than the average degree. The notion of ∆-clique, as a set of vertices in which each pair is in contact at least every ∆ timestamps, has been proposed in [START_REF] Viard | Computing maximal cliques in link streams[END_REF][START_REF] Himmel | Enumerating maximal cliques in temporal graphs[END_REF]. Bentert et al. [START_REF] Bentert | Listing all maximal k-plexes in temporal graphs[END_REF] introduce the ∆-k-plex, a relaxation of ∆-clique in which each vertex has an edge to all but at most k -1 vertices at least once every ∆ consecutive timestamps. Li et al. [START_REF] Li | Persistent community search in temporal networks[END_REF] study the problem of finding the maximum (θ,∆)-persistent k-core in a temporal network, i.e., the largest subgraph that is a connected k-core in all the subintervals of duration θ of a given temporal interval ∆.

A different, but still slightly related body of literature focuses on other definitions of temporal patterns, such as frequent evolution patterns in temporal attributed graphs [START_REF] Berlingerio | Mining graph evolution rules[END_REF][START_REF] Inokuchi | Mining frequent graph sequence patterns induced by vertices[END_REF][START_REF] Desmier | Cohesive co-evolution patterns in dynamic attributed graphs[END_REF], link-formation rules in temporal networks [START_REF] Bringmann | Learning and predicting the evolution of social networks[END_REF][START_REF] Wing-Ki Leung | Mining interesting link formation rules in social networks[END_REF], frequency-estimation algorithms for counting temporal motifs [START_REF] Kovanen | Temporal motifs in time-dependent networks[END_REF][START_REF] Liu | Sampling methods for counting temporal motifs[END_REF], finding a small vertex set whose removal eliminates all temporal paths connecting two designated terminal vertices [START_REF] Zschoche | The complexity of finding small separators in temporal graphs[END_REF], finding a subgraph that maximizes the sum of edge weights in a network whose topology remains fixed but edge weights evolve over time [START_REF] Bogdanov | Mining heavy subgraphs in time-evolving networks[END_REF][START_REF] Ma | Fast computation of dense temporal subgraphs[END_REF], and the discovery of dynamic relationships and events [START_REF] Das Sarma | Dynamic relationship and event discovery[END_REF], or of correlated activity patterns [START_REF] Gauvin | Detecting the community structure and activity patterns of temporal networks: a non-negative tensor factorization approach[END_REF].

This work differs from all the above ones as our notions of span-core and temporal core decomposition do not correspond (or are straightforwardly reducible) to any of those temporal patterns.

Community search

Given a static graph and a set of query vertices, the community search problem aims at finding a cohesive subgraph containing the query vertices. Community search has attracted a great deal of attention in the last years [START_REF] Fang | A survey of community search over big graphs[END_REF][START_REF] Huang | Community search over big graphs: Models, algorithms, and opportunities[END_REF]. Sozio and Gionis [START_REF] Sozio | The community-search problem and how to plan a successful cocktail party[END_REF] are the first to introduce this problem by employing the minimum degree as a cohesiveness measure. Their formulation can be solved by a simple (linear-time) greedy algorithm, which resembles the traditional 2approximation algorithm for densest subgraph proposed in [START_REF] Charikar | Greedy approximation algorithms for finding dense components in a graph[END_REF]. More recently, Cui et al. [START_REF] Cui | Local search of communities in large graphs[END_REF] devise a local-search approach to improve the efficiency of the method defined in [START_REF] Sozio | The community-search problem and how to plan a successful cocktail party[END_REF], but only for the special case of a single query vertex. The case of multiple query vertices has instead been addressed by Barbieri et al. [START_REF] Barbieri | Efficient and effective community search[END_REF], who exploit core decomposition as a preprocessing step to improve efficiency. They also tackle the problem of minimum community search, i.e., a variant of community search where the size of the output subgraph has to be minimized.

Community search has also been studied under different names and/or settings. Huang et al. [START_REF] Huang | Querying k-truss community in large and dynamic graphs[END_REF] introduce a community-search model based on the k-truss notion. Andersen and Lang [START_REF] Andersen | Communities from seed sets[END_REF] and Kloumann and Kleinberg [START_REF] Kloumann | Community membership identification from small seed sets[END_REF] study seed set expansion in social graphs, in order to find communities with small conductance or that are well-resemblant of the characteristics of the query vertices, respectively. Other works define connectivity subgraphs based on electricity analogues [START_REF] Faloutsos | Fast discovery of connection subgraphs[END_REF], random walks [START_REF] Tong | Center-piece subgraphs: problem definition and fast solutions[END_REF], the minimum-description-length principle [START_REF] Akoglu | Mining connection pathways for marked nodes in large graphs[END_REF], the Wiener index [START_REF] Ruchansky | The minimum wiener connector problem[END_REF] and network efficiency [START_REF] Ruchansky | To be connected, or not to be connected: That is the minimum inefficiency subgraph problem[END_REF]. Recent approaches also introduce the flexibility of having query vertices belonging to different communities [START_REF] Bian | On multi-query local community detection[END_REF][START_REF] Yan | Constrained local graph clustering by colored random walk[END_REF]. Finally, community search has been formalized for attributed graphs [START_REF] Huang | Attribute-driven community search[END_REF][START_REF] Fang | Effective and efficient attributed community search[END_REF] and spatial graphs [START_REF] Fang | Effective community search over large spatial graphs[END_REF] as well.

In this work, we study for the first time community search in temporal graphs. Specifically, we provide a novel definition of the problem by asking for a set of subgraphs containing the given query vertices, along with their corresponding temporal intervals, such that the total minimum-degree density of the identified subgraphs is maximized and the union of the temporal intervals spanned by those subgraphs covers the whole underlying temporal domain. None of the above works deal with such a definition of temporal community search, not even the works by Rozenshtein et al. [START_REF] Polina Rozenshtein | Finding events in temporal networks: Segmentation meets densest-subgraph discovery[END_REF] and Li et al. [START_REF] Li | Persistent community search in temporal networks[END_REF] discussed in the previous subsection. In particular, Rozenshtein et al. [START_REF] Polina Rozenshtein | Finding events in temporal networks: Segmentation meets densest-subgraph discovery[END_REF] and Li et al. [START_REF] Li | Persistent community search in temporal networks[END_REF] both search for cohesive subgraphs, but neither consider query vertices as input, which makes a crucial difference (another difference is that they consider different notions of density).

Temporal core decomposition: problem statement

In this section we provide preliminary definitions and the needed notations, introduce the problem of finding all span-cores and only the maximal ones, and prove containment properties among span-cores that are at the basis of our efficient algorithms.

Span-cores

We are given a temporal graph G = (V, T, τ ), where V is a set of vertices, T = [0, 1, . . . , t max ] ⊆ N is a discrete time domain, and τ :

V × V × T → {0,
[S] = {(u, v) ∈ E ∆ | u ∈ S, v ∈ S} and G ∆ [S] = (S, E ∆ [S]). Finally, the temporal degree of a vertex u within G ∆ [S] is denoted d ∆ (S, u) = |{v ∈ S | (u, v) ∈ E ∆ [S]}|.
Definition 2 ((k, ∆)-core) The (k, ∆)-core of a temporal graph G = (V, T, τ ) is (when it exists) a maximal and non-empty set of vertices

∅ = C k,∆ ⊆ V , such that ∀u ∈ C k,∆ : d ∆ (C k,∆ , u) ≥ k, where ∆ T is a temporal interval and k ∈ N + .
A (k, ∆)-core is thus a set of vertices implicitly defining a cohesive subgraph (where k represents the cohesiveness constraint), together with its temporal span, i.e., the interval ∆ for which the subgraph satisfies the cohesiveness constraint. In the remainder of the paper we refer to this type of temporal pattern as span-core.

The first problem we tackle in this work is to compute the span-core decomposition of a temporal graph G, i.e., all span-cores of G.

Figure 1: Search space: for a temporal span ∆ = [t s , t e ], the (k, ∆)-core is depicted as a node labeled "k, [t s , t e ]". An arrow C 1 → C 2 denotes C 1 ⊇ C 2 (the distinction between solid and dotted arrows is for visualization sake only).

Problem 1 (Span-core decomposition) Given a temporal graph G, find the set of all (k, ∆)-cores of G.

Unlike standard cores of simple graphs, span-cores are not all nested into each other, due to their spans. However, they still exhibit containment properties. Indeed, it can be observed that a (k, ∆)-core is contained into any other (k , ∆ )-core with less restrictive degree and span conditions, i.e., k ≤ k, and ∆ ∆. This property is depicted in Figure 1, and formally stated in the next proposition.

Proposition 1 (Span-core containment) For any two span-cores

C k,∆ , C k ,∆ of a temporal graph G it holds that k ≤ k ∧ ∆ ∆ ⇒ C k,∆ ⊆ C k ,∆ .
The result can be proved by separating the two conditions in the hypothesis, i.e., by separately showing that (i

) k ≤ k ⇒ C k,∆ ⊆ C k ,∆ , and (ii) ∆ ∆ ⇒ C k,∆ ⊆ C k,∆ .
The first point holds as, keeping the span ∆ fixed, the maximal set of vertices C for which

d ∆ (C, u) ≥ k is clearly contained in the maximal set of vertices C for which d ∆ (C , u) ≥ k , if k ≤ k. To prove (ii), it can be noted that ∆ ∆ ⇒ E ∆ ⊆ E ∆ , which implies that ∀u ∈ C k,∆ : d ∆ (C k,∆ , u) ≤ d ∆ (C k,∆ , u).
Therefore, all vertices within C k,∆ satisfy the condition to be part of C k,∆ too.

The following observation directly derives from Proposition 1 and states that finding all the span-cores having a fixed span ∆ corresponds to computing the core decomposition of a simple graph.

Observation 1 For a fixed temporal interval ∆ T , finding all span-cores that have ∆ as their span is equivalent to computing the classic core decomposition [START_REF] Batagelj | Fast algorithms for determining (generalized) core groups in social networks[END_REF] of the simple graph G ∆ = (V, E ∆ ).

Maximal span-cores

As the total number of temporal intervals that are contained into the whole time domain T is |T |(|T |+ 1)/2, the total number of span-cores is potentially

O(|T | 2 × k max ),
where k max is the largest value of k for which a (k, ∆)-core exists. It is thus quadratic in |T |, which may be too large an output for human direct inspection. In this regard, it may be useful to focus only on the most relevant cores, i.e., the maximal ones, as defined next.

Definition 3 (Maximal span-core) A span-core C k,∆ of a temporal graph G is said maximal if there does not exist any other span-core C k ,∆ of G such that k ≤ k and ∆ ∆ .

Hence, a span-core is recognized as maximal if it is not dominated by another span-core both on the order k and the span ∆. Differently from the innermost core (i.e., the core of the highest order) in the classic core decomposition, which is unique, in our temporal setting the number of maximal span-cores is O(|T | 2 ), as, in the worst case, there may be one maximal span-core for every temporal interval. However, as observed in empirical temporal-network data, maximal span-cores are always much less than the overall span-cores: the difference is usually one order of magnitude or more. The second problem we tackle in this work is to compute the maximal span-cores of a temporal graph.

Problem 2 (Maximal Span-core Mining) Given a temporal graph G, find the set of all maximal (k, ∆)-cores of G.

Clearly, one could solve Problem 2 by solving Problem 1 and filtering out all the non-maximal span-cores. However, an interesting yet challenging question is whether one can exploit the maximality condition to develop faster algorithms that can directly extract the maximal ones, without computing all the spancores. We provide a positive answer to this question in Section 5.

Algorithms: computing all span-cores

In this section we devise algorithms for computing a complete span-core decomposition of a temporal graph (Problem 1). A naïve approach. As stated in Observation 1, for a fixed temporal interval ∆ T , mining all span-cores C k,∆ is equivalent to computing the classic core decomposition of the graph G ∆ = (V, E ∆ ). A naïve strategy is thus to run a core-decomposition subroutine [START_REF] Batagelj | Fast algorithms for determining (generalized) core groups in social networks[END_REF] A more efficient algorithm. Looking at Figure 1 one can observe that the naïve algorithm only exploits one dimension of the containment property: it starts from each point on the top level, i.e., from cores of order 1, and goes down vertically with the classic core decomposition. Based on Proposition 1, it is possible to design a more efficient algorithm that exploits also the "horizontal containment" relationships.

Example 1 Consider core C 1,[0,2] in Figure 1: by Proposition 1 it holds that it is a subset of both C 1,[0,1] and C 1, [START_REF] Akoglu | Mining connection pathways for marked nodes in large graphs[END_REF][START_REF] Alvarez-Hamelin | Large scale networks fingerprinting and visualization using the k-core decomposition[END_REF] . Therefore, to compute C 1,[0,2] , instead of starting from the whole V , one can start from C 1,[0,1] ∩ C 1, [START_REF] Akoglu | Mining connection pathways for marked nodes in large graphs[END_REF][START_REF] Alvarez-Hamelin | Large scale networks fingerprinting and visualization using the k-core decomposition[END_REF] . Starting from a much smaller set of vertices can provide a substantial speed-up to the whole computation.

This observation, although simple, produces a speed-up of orders of magnitude as we will empirically show in Section 7. The next straightforward corollary of Proposition 1 states that, not only [START_REF] Akoglu | Mining connection pathways for marked nodes in large graphs[END_REF][START_REF] Alvarez-Hamelin | Large scale networks fingerprinting and visualization using the k-core decomposition[END_REF] , but this is the best one can get, meaning that intersecting these two span-cores is equivalent to intersecting all span-cores structurally containing

C 1,[0,2] ⊆ C 1,[0,1] ∩ C 1,
C 1,[0,2] .
Corollary 1 Given a temporal graph G = (V, T, τ ), and a temporal interval

∆ = [t s , t e ] T , let ∆ + = [min{t s + 1, t e }, t e ] and ∆ -= [t s , max{t e -1, t s }]. It holds that C 1,∆ ⊆ (C 1,∆+ ∩ C 1,∆-) = ∆ ∆ C 1,∆ . Example 2 Consider again C 1,[0,2] in Figure 1: Proposition 1 states that it is a subset of C 1,[0,0] , C 1,[0,1] , C 1,[1,1] , C 1,[1,2] , C 1,[2,2]
. Corollary 1 suggests that there is no need to intersect them all, but only C 1,[0,1] and C 1, [START_REF] Akoglu | Mining connection pathways for marked nodes in large graphs[END_REF][START_REF] Alvarez-Hamelin | Large scale networks fingerprinting and visualization using the k-core decomposition[END_REF] : in fact,

C 1,[0,1] ⊆ C 1,[0,0] ∩ C 1,[1,1] and C 1,[1,2] ⊆ C 1,[1,1] ∩ C 1,[2,2] .
The main idea behind our efficient Span-cores algorithm (whose pseudocode is given as Algorithm 1) is to generate temporal intervals of increasing size (starting from size one) and, for each ∆ of width larger than one, to initiate the core decomposition from (C 1,∆+ ∩ C 1,∆-), i.e., the smallest intersection of cores containing C 1,∆ (Corollary 1). The intervals to be processed are added to queue Q, which is initialized with the intervals of size one (Lines 2-3): these are the only intervals for which no other interval can be used to reduce the set of vertices from which the core decomposition is started, thus they have to be initialized with the whole vertex set V . The algorithm utilizes a map A that, given an interval ∆, returns the set of vertices to be used as a starting set of the core decomposition on ∆. The algorithm processes all intervals stored in Q, until Q has become empty (Lines 4-16). For every temporal interval ∆ extracted from Q, the starting set of vertices is retrieved from A[∆] and the corresponding set of edges is identified (Line 6). Unless this is empty, the classic core-decomposition algorithm [START_REF] Batagelj | Fast algorithms for determining (generalized) core groups in social networks[END_REF]

is invoked over (A[∆], E ∆ [A[∆]]) (Line 8
) and its output (a set of span-cores of span ∆) is added to the ultimate output set C (Line 9).

Algorithm 1: Span-cores

Input:

A temporal graph G = (V, T, τ ). Output: The set C of all span-cores of G. 1 C ← ∅; Q ← ∅; A ← ∅ 2 forall t ∈ T do 3 enqueue [t, t] to Q; A[t, t] ← V 4 while Q = ∅ do 5 dequeue ∆ = [t s , t e ] from Q 6 E ∆ [A[∆]] ← {(u, v) ∈ E ∆ | u ∈ A[∆], v ∈ A[∆]} 7 if |E ∆ [A[∆]]| > 0 then 8 C ∆ ← core-decomposition(A[∆], E ∆ [A[∆]]) 9 C ← C ∪ C ∆ 10 ∆ 1 = [max{t s -1, 0}, t e ]; ∆ 2 = [t s , min{t e + 1, t max }] 11 forall ∆ ∈ {∆ 1 , ∆ 2 } | ∆ = ∆ do 12 if A[∆ ] = null then 13 A[∆ ] ← A[∆ ] ∩ C 1,∆ 14 enqueue ∆ to Q 15 else 16 A[∆ ] ← C 1,∆
Afterwards, the two intervals, denoted ∆ 1 and ∆ 2 , for which C 1,∆ can be used to obtain the smallest intersections of cores containing them (Corollary 1) are computed at Line 10. For ∆ 1 (and analogously ∆ 2 ), we check whether A[∆ 1 ] has already been initialized (Line 12): this would mean that previously the other "father" (i.e., smallest containing core) of C 1,∆1 has been computed, thus we can intersect C 1,∆ with A[∆ 1 ] and enqueue ∆ 1 to be processed (Lines [START_REF] Bian | On multi-query local community detection[END_REF][START_REF] Bogdanov | Mining heavy subgraphs in time-evolving networks[END_REF].

Instead, if A[∆ 1 ]
was not yet initialized, we initialize it with C 1,∆ (Line 16): in this case ∆ 1 is not enqueued because it still lacks one father to be intersected before being ready for core decomposition. This procedural update of Q ensures that both fathers of every interval in Q exist and have been previously computed, thus no a-posteriori verification is needed.

Example 3 Consider again the search space in Figure 1. Algorithm 1 first processes the intervals [0, 0], [START_REF] Akoglu | Mining connection pathways for marked nodes in large graphs[END_REF][START_REF] Akoglu | Mining connection pathways for marked nodes in large graphs[END_REF], [START_REF] Alvarez-Hamelin | Large scale networks fingerprinting and visualization using the k-core decomposition[END_REF][START_REF] Alvarez-Hamelin | Large scale networks fingerprinting and visualization using the k-core decomposition[END_REF], and [START_REF] Andersen | Finding dense subgraphs with size bounds[END_REF][START_REF] Andersen | Finding dense subgraphs with size bounds[END_REF].

Then, it intersects C 1,[0,0] and C 1,[1,1] to initialize C 1,[0,1] , intersects C 1,[1,1] and C 1,[2,2] to initialize C 1,[1,2] ,
and intersects C 1, [START_REF] Alvarez-Hamelin | Large scale networks fingerprinting and visualization using the k-core decomposition[END_REF][START_REF] Alvarez-Hamelin | Large scale networks fingerprinting and visualization using the k-core decomposition[END_REF] and C 1, [START_REF] Andersen | Finding dense subgraphs with size bounds[END_REF][START_REF] Andersen | Finding dense subgraphs with size bounds[END_REF] to initialize C 1, [START_REF] Alvarez-Hamelin | Large scale networks fingerprinting and visualization using the k-core decomposition[END_REF][START_REF] Andersen | Finding dense subgraphs with size bounds[END_REF] . Then, it continues with the intervals of size 3: it intersects C 1,[0,1] and C 1, [START_REF] Akoglu | Mining connection pathways for marked nodes in large graphs[END_REF][START_REF] Alvarez-Hamelin | Large scale networks fingerprinting and visualization using the k-core decomposition[END_REF] to initialize C 1,[0,2] and so on.

The next theorem formally shows soundness and completeness of our Span-cores algorithm.

Theorem 1 Algorithm 1 is sound and complete for Problem 1.

The algorithm generates and processes a subset of temporal intervals X ⊆ {∆ | ∆ T }. For every interval ∆ ⊆ X , it computes all span-cores C ∆ = {C 1,∆ , C 2,∆ , . . . , C k∆,∆ } defined on ∆ by means of the core-decomposition subroutine on the graph (A

[∆], E ∆ [A[∆]]). The set of vertices A[∆] is equivalent to (C 1,∆+ ∩C 1,∆-)
because of Line 13 (Corollary 1) and the fact that ∆ is enqueued (Line 14) only when both fathers have been processed and the intersection done. The correctness of doing the classic core decomposition is guaranteed by Observation 1.

As for completeness, it suffices to show that the intervals ∆ / ∈ X that have not been processed by the algorithm do not yield any span-core. The algorithm generates all temporal intervals size by size, starting from those of size one and then going to larger sizes. This is done by maintaining the queue Q. As said above, an interval ∆ is enqueued as soon as both C 1,∆+ and C 1,∆-have been processed. Thus, an interval ∆ is not in X only if either C 1,∆+ or C 1,∆-does not exist. In this case C 1,∆ and all other C k,∆ do not exist as well. Discussion. Algorithm 1 exploits the "horizontal containment" relationships only at the first level of the search space. For a given ∆, once the restricted starting set of vertices has been defined for k = 1, the traditional core decomposition is started to produce all the span-cores of span ∆. In other words, for k > 1 only the "vertical containment" is exploited. Consider the span-core C 3, [START_REF] Akoglu | Mining connection pathways for marked nodes in large graphs[END_REF][START_REF] Alvarez-Hamelin | Large scale networks fingerprinting and visualization using the k-core decomposition[END_REF] in Figure 1: we know that it is a subset of C 2, [START_REF] Akoglu | Mining connection pathways for marked nodes in large graphs[END_REF][START_REF] Alvarez-Hamelin | Large scale networks fingerprinting and visualization using the k-core decomposition[END_REF] ("vertical" ) and of C 3, [START_REF] Akoglu | Mining connection pathways for marked nodes in large graphs[END_REF][START_REF] Akoglu | Mining connection pathways for marked nodes in large graphs[END_REF] and C 3, [START_REF] Alvarez-Hamelin | Large scale networks fingerprinting and visualization using the k-core decomposition[END_REF][START_REF] Alvarez-Hamelin | Large scale networks fingerprinting and visualization using the k-core decomposition[END_REF] ("horizontal" ). One could consider intersecting all these three span-cores before computing C 3, [START_REF] Akoglu | Mining connection pathways for marked nodes in large graphs[END_REF][START_REF] Alvarez-Hamelin | Large scale networks fingerprinting and visualization using the k-core decomposition[END_REF] . We tested this alternative approach, but concluded that the overhead of computing intersections and data-structure maintenance was outweighing the benefit of starting from a smaller vertex set.

The worst-case time complexity of Algorithm 1 is equal to the naïve approach, however, in practice, it is orders of magnitude faster, as shown in Section 7.

Algorithms: computing maximal span-cores

In this section we focus on Problem 2: computing the maximal span-cores of a temporal graph. A filtering approach. As anticipated above, a straightforward way of solving this problem consists in filtering the span-cores computed during the execution of Algorithm 1, so as to ultimately output only the maximal ones. This can easily be accomplished by equipping Algorithm 1 with a data structure M that stores the span-core of the highest order for every temporal interval ∆ T that has been processed by the algorithm. Moreover, at the storage of a spancore C k,∆ in M, the span-cores previously stored in M for subintervals of the temporal interval ∆ and with the same order k are removed from M. This removal operation, together with the order in which span-cores are processed, ensures that M eventually contains only the maximal span-cores. Efficient maximal-span-core finding. Our next goal is to design a more ef-ficient algorithm that extracts maximal span-cores directly, without computing complete core decompositions, passing over more peripheral ones, and without generating all temporal cores. This is a quite challenging design principle, as it contrasts the intrinsic structural properties of core decomposition, based on which a core of order k is usually computed from the core of order k -1, thus making the computation of the core of the highest order as hard as computing the overall decomposition. Nevertheless, thanks to theoretical properties that relate the maximal span-cores to each other, in the temporal context such a challenge can be achieved. In the following we discuss such properties in detail, by starting from a result that has already been discussed above, but only informally.

Consider the classic core decomposition in a standard (non-temporal) graph G (Definition 1) and let C k * [G] denote the innermost core of G, i.e., the nonempty k-core of G with the largest k.

Lemma 1 Given a temporal graph G = (V, T, τ ), let C M be the set of all maximal span-cores of G, and

C inner = {C k * [G ∆ ] | ∆ T } be the set of innermost cores of all graphs G ∆ . It holds that C M ⊆ C inner . Every C k,∆ ∈ C M is the innermost core of the non-temporal graph G ∆ : else, there would exist another core C k ,∆ = ∅ with k > k, implying that C k,∆ / ∈ C M .
Lemma 1 states that each maximal span-core is an innermost core of a G ∆ , for some temporal interval ∆ T . Hence, there can exist at most one maximal span-core for every ∆ T (while an interval ∆ may not yield any maximal span-core). The key question to design an efficient maximal-span-core-mining algorithm thus becomes how to extract innermost cores of the graphs G ∆ more efficiently than by computing the full core decompositions of all G ∆ . The answer to this question comes from the result stated in the next two lemmas (with Lemma 2 being auxiliary to Lemma 3).

Lemma 2 Given a temporal graph G = (V, T, τ ), and three temporal intervals

∆ = [t s , t e ] T , ∆ = [t s -1, t e ] T , and ∆ = [t s , t e +1] T . The innermost core C k * [G ∆ ] is a maximal span-core of G if and only if k * > max{k , k }
where k and k are the orders of the innermost cores of G ∆ and G ∆ , respectively.

The "⇒" part comes directly from the definition of maximal span-core (Definition 3): if k * were not larger than max{k , k }, then C k * [G ∆ ] would be dominated by another span-core both on the order and on the span (as both ∆ and ∆ are superintervals of ∆). For the "⇐" part, from Lemma 1 and Proposition 1 it follows that max{k , k } is an upper bound on the maximum order of a span-core of a superinterval of ∆. Therefore, k * > max{k , k } implies that there cannot exist any other span-core that dominates C k * [G ∆ ] both on the order and on the span.

Lemma 3 Given G, ∆, ∆ , ∆ , k , and k defined as in Lemma 2, let V = {u ∈ V | d ∆ (V, u) > max{k , k }}, and let C k * [G ∆ [ V ]] be the innermost core of Algorithm 2: Maximal-span-cores Input: A temporal graph G = (V, T, τ ). Output: The set C M of all maximal span-cores of G. 1 C M ← ∅ 2 K [t] ← 0, ∀t ∈ T 3 forall t s ∈ [0, 1, . . . , t max ] do 4 t * ← max{t e ∈ [t s , t max ] | E [ts,te ] = ∅} 5 k ← 0 6 forall t e ∈ [t * , t * -1, . . . , t s ] do 7 ∆ ← [t s , t e ] 8 lb ← max{K [t e ], k } 9 V lb ← {u ∈ V | d ∆ (V, u) > lb} 10 E ∆ [V lb ] ← {(u, v) ∈ E ∆ | u ∈ V lb , v ∈ V lb } 11 C ← innermost-core(V lb , E ∆ [V lb ]) 12 k * ← order of C 13 if k * > lb then 14 C M ← C M ∪ {C} 15 k ← max{k , k * }; K [t e ] ← max{K [t e ], k } G ∆ [ V ]. If k * > max{k , k }, then C k * [G ∆ [ V ]
] is a maximal span-core; otherwise, no maximal span-core exists for ∆.

Lemma 2 states that, to be recognized as a maximal span-core, the innermost core of G ∆ should have order larger than max{k , k }. This means that, if the innermost core of G ∆ is a maximal span-core, all vertices u / ∈ V cannot be part of it. Therefore, G ∆ yields a maximal span-core only if the innermost core of subgraph G ∆ [ V ] has order k * > max{k , k }. Lemma 3 provides the basis of our efficient method for extracting maximal span-cores. Basically, it states that, to verify whether a certain temporal interval ∆ = [t s , t e ] yields a maximal span-core (and, if so, compute it), there is no need to consider the whole graph G ∆ , rather it suffices to start from a smaller subgraph, which is given by all vertices whose temporal degree is larger than the maximum between the orders of the innermost cores of intervals ∆ = [t s -1, t e ] and ∆ = [t s , t e +1]. This finding suggests a strategy that is opposite to the one used for computing the overall span-core decomposition: a top-down strategy that processes temporal intervals starting from the larger ones. Indeed, in addition to exploiting the result in Lemma 3, this way of exploring the temporal-interval space allows us to skip the computation of complete core decompositions of the whole "singletoninterval" graphs {G [t,t] } t∈T , which may easily become a critical bottleneck, as they are the largest ones among the graphs induced by temporal intervals. The Maximal-span-cores algorithm. Algorithm 2 iterates over all timestamps t s ∈ T in increasing order (Line 3), and for each t s it first finds all the maximal span-cores that have span starting in t s . This way of proceeding ensures that a span-core that is recognized as maximal will not be later dominated by another span-core. Indeed, an interval [t s , t e ] can never be contained in another interval [t s , t e ] with t s < t s . For a given t s , all maximal span-cores are computed as follows. First, the maximum timestamp ≥ t s such that the corresponding edge set E [ts,te ] is not empty is identified as t * (Line 4). Then, all intervals ∆ = [t s , t e ] are considered one by one in decreasing order of t e (Lines 6-7): this again guarantees that a span-core that is recognized as maximal will not be later dominated by another span-core, as the intervals are processed from the largest to the smallest. At each iteration of the internal cycle, the algorithm resorts to Lemma 3 and computes the lower bound lb on the order of the innermost core of G ∆ to be recognized as maximal, by taking the maximum between K [t e ] and k (Line 8). K is a map that maintains, for every timestamp t ∈ [t s , t * ], the order of the innermost core of graph G ∆ , where ∆ = [t s -1, t] (i.e., K [t] stores what in Lemmas 2-3 is denoted as k ). Whereas k stores the order of the innermost core of G ∆ , where ∆ = [t s , t e + 1]. Afterwards, the sets of vertices V lb and of edges E ∆ [V lb ] that comply with this lower-bound constraint are built (Lines 9-10), and the innermost core of the subgraph (V lb , E ∆ [V lb ]) is extracted (Lines 11-12). Ultimately, based again on Lemma 3, such a core is added to the output set of maximal span-cores only if its order is actually larger than lb (Lines 13-14), and the values of k and K [t e ] are updated (Line 15). Specifically, note that the order k * of core C may in principle be less than k , as C is extracted from a subgraph of G ∆ . If this happens, it means that the actual order of the innermost core of G ∆ is equal to k . This motivates the update rules (and their order) reported in Line 15.

Theorem 2 Algorithm 2 is sound and complete for Problem 2.

The algorithm processes all temporal intervals ∆

T yielding a non-empty edge set E ∆ , in an order such that no interval is processed before one of its superintervals: this guarantees that a span-core recognized as maximal will not be dominated by another span-core found later on. For every ∆ it extracts a core C that is used as a proxy of the innermost core of graph G ∆ . C is added to the output set C M only if Lemma 3 recognizes it as a maximal spancore, otherwise it is discarded. This proves the soundness of the algorithm. Completeness follows from Lemma 1, which states that to extract all maximal span-cores it suffices to focus on the innermost cores of graphs {G ∆ | ∆ T }, and Lemma 3 again, which states the condition for a proxy core C to be safely discarded because it is a non-maximal span-core. Discussion. The worst-case time complexity of Algorithm 2 is the same as the algorithm for computing the overall span-core decomposition, i.e., O(|T | 2 ×|E|). It is worth mentioning that it is not possible to do better than this, as the output itself is potentially quadratic in |T |. However, as we will show in Section 7, the proposed algorithm is in practice much more efficient than computing the overall span-core decomposition and filtering out the non-maximal span-cores as, in this case, we avoid the visit of portions of the span-core search space and the computations are run over subgraphs of reduced dimensions.

To conclude, we discuss how the crucial operation of building the subgraph (V lb , E ∆ [V lb ]) may be carried out efficiently in terms of both time and space. Consider a fixed timestamp t s ∈ [0, . . . ,

Temporal community search

Community search in static graphs aims at finding a dense subgraph (community) containing a set of input query vertices [START_REF] Fang | A survey of community search over big graphs[END_REF][START_REF] Huang | Community search over big graphs: Models, algorithms, and opportunities[END_REF]. In the temporal setting it is very likely that the communities spanning the query vertices change over time. To be more precise, it may happen that a certain subgraph S is a wellrepresentative community for the given query vertices Q, but only for a certain time interval ∆. Instead, for another time interval ∆ , a relevant community for Q might correspond to a completely different subgraph S . For this reason, we formulate community search on temporal networks as the problem of finding h subgraphs (with h > 0 being an input parameter) containing the query vertices, together with their temporal span, such that the sum of the density of those subgraphs is maximized and the union of their temporal spans corresponds to the whole input temporal domain. Among the many densities proposed in the literature, here we follow the seminal work by Sozio and Gionis [START_REF] Sozio | The community-search problem and how to plan a successful cocktail party[END_REF] on community search and adopt the minimum degree. Formally:

Problem 3 (Temporal Community Search) Given a temporal graph G = (V, T, τ ), a set Q ⊆ V of

query vertices, and a positive integer

h ∈ N + , find a set { S i , ∆ i } h i=1 of h pairs such that (i) ∀1 ≤ i ≤ h : Q ⊆ S i ⊆ V , (ii)
1≤i≤h ∆ i = T , and (iii) the following is maximized:

h i=1 min u∈Si d ∆i (S i , u). (1)
The input integer h is a user-defined parameter that gives the analyst the flexibility of requiring a specific number of output temporal communities, which might vary from application to application.

Connection with Sequence Segmentation

Here we provide some theoretical insights into the Temporal Community Search problem. The main result we provide at the end of this subsection is an interesting connection with the well-established Sequence Segmentation problem [START_REF] Bellman | On the approximation of curves by line segments using dynamic programming[END_REF]. As shown in the next subsections, such a result forms the basis for algorithmic design.

Let us first consider a single-interval variant of Problem 3: for a fixed temporal interval ∆, find a subgraph containing the input set Q of query vertices that maximizes the minimum temporal degree within ∆. Formally: Problem 4 (Single Temporal Community Search) Given a temporal graph G = (V, T, τ ), a set Q ⊆ V of query vertices, and an interval ∆ T , find

S * = argmax Q⊆S⊆V min u∈S d ∆ (S, u).
It is easy to see that solving Problem 4 corresponds to solving minimumdegree-based community search on graph G ∆ . Therefore, a solution to Problem 4 can straightforwardly be computed by applying a standard result on minimum-degree-based community search, which states that the highest-order core containing all query vertices is a solution to that problem [START_REF] Barbieri | Efficient and effective community search[END_REF]. This finding is formalized next. Definition 4 ((Q, ∆)-highest-order-span-core) Given a temporal graph G = (V, T, τ ), a set Q ⊆ V of query vertices, and an interval ∆ T , the (Q, ∆)highest-order-span-core of G, denoted C * Q,∆ , is defined as the highest-order spancore among all span-cores of G with temporal span ∆ and containing all query vertices in Q. Let also v * Q,∆ denote the order of C * Q,∆ .

Fact 1 Given a temporal graph G = (V, T, τ ), a set Q ⊆ V of query vertices, and an interval ∆ T , the (Q, ∆)-highest-order-span-core of G is a solution to Problem 4 on input G, Q, ∆ .

Note that Problem 4 may have multiple solutions: C * Q,∆ is only one of those possibly many ones. C * Q,∆ can be computed by running a core decomposition on (static) graph G ∆ , and stopping it when the first core that does not contain all query vertices in Q has been encountered. Therefore, Problem 4 can be solved in O(|∆| × |E|) time.

In light of the above findings, an alternative yet equivalent way of formulating our Temporal Community Search problem is to ask for a segmentation (i.e., a partition) of the time domain T into a set {∆ i } h i=1 of h intervals so as to maximize the sum h i=1 v * Q,∆i of the orders of the (Q, ∆)-highest-order-spancores of those identified intervals. Once such an optimal segmentation of T has been computed, the ultimate { S i , ∆ i } h i=1 pairs are derived by simply setting

S i = C * Q,∆i , ∀1 ≤ i ≤ h. Formally:
Problem 5 (Alternative formulation of Problem 3) Given a temporal graph G = (V, T, τ ), a set Q ⊆ V of query vertices, and a positive integer

h ∈ N + , find a set { S i , ∆ i } h i=1 of h pairs such that (i) ∀1 ≤ i ≤ h : S i = C * Q,∆i , (ii) {∆ i } h
i=1 is a partition of T , and (iii) the following is maximized:

h i=1 v * Q,∆i . (2)
Correspondence between Problem 3 and Problem 5 easily follows from Fact 1 and from the observation that for any feasible solution { S i , ∆ i } h i=1 to Problem 3 with overlapping intervals, there exists an overlapping-interval-free feasible solution with not smaller objective-function value. To see the latter, for any two overlapping intervals ∆ i and ∆ j , simply replace one of the two intervals, say ∆ i , with

∆ i = ∆ i \ (∆ i ∩ ∆ j ). As ∆ i ∆ i , it holds that v * Q,∆ i ≥ v * Q,∆i
, therefore the resulting overlapping-interval-free solution will have objective-function value greater than or equal to the objective-function value of the starting solution with overlapping intervals.

Thanks to the reformulation in Problem 5, it is immediate to observe that our Temporal Community Search problem is an instance of the well-established Sequence Segmentation problem, which asks for partitioning a sequence of numerical values into b segments so as to minimize the sum of the penalties (according to some penalty function) on each identified segment [START_REF] Bellman | On the approximation of curves by line segments using dynamic programming[END_REF]: Problem 6 (Sequence Segmentation [START_REF] Bellman | On the approximation of curves by line segments using dynamic programming[END_REF]) Given a sequence X = (x 0 , x 1 , . . . , x max ) of numerical values, and a function p : {Y } Y X → R that assigns a penalty score to every subsequence Y of X, partition X into a set

{X i } b i=1 of b subsequences such that b i=1 p(X i ) is minimized. Fact 2 Temporal Community Search (Problem 3) on input G = (V, T, τ ), Q, h is an instance of Sequence Segmentation (Problem 6) with X = T , b = h, and ∀∆ T : p(∆) = -v * Q,∆ .
In the following two subsections we show how to exploit the result in Fact 2 (and a further important finding about maximal span-cores) to design efficient algorithms for our Temporal Community Search problem.

Algorithm 3: Temporal-community-search

Input:

A temporal graph G = (V, E, T ), a set Q ⊆ V of query vertices, an integer h ∈ N + . Output: A set { S i , ∆ i } h i=1 , where Q ⊆ S i ⊆ V , ∀1 ≤ i ≤ h, and {∆ i } h i=1 is a partition of T . /* Initialization */ 1 Compute v * Q,∆ and C * Q,∆ , ∀∆ T , via Q-constrained span-core decomposition 2 P ← an empty (|T | × h)-dimensional matrix // Penalty matrix 3 R ← an empty (|T | × h)-dimensional matrix // Reconstruction matrix 4 forall t ∈ T do 5 P[t, 0] ← -v * Q,[0,t] 6 R[t, 0] ← 0 /* Dynamic-programming step */ 7 forall t ∈ T do 8 forall i ∈ [1, h) do 9 P[t, i] ← min ∈[0,t] P[ , i -1] -v * Q,[ +1,t] 10 R[t, i] ← argmin ∈[0,t] P[ , i -1] -v * Q,[ +1,t]
/* Reconstruction of the solution */

11 ub ← t max 12 forall i ∈ (h, 0] do 13 lb ← R[ub, i] 14 ∆ i ← [lb, ub] 15 ub ← lb -1 16 forall i ∈ (h, 0] do 17 S i ← C * Q,∆i

A basic algorithm (based on all span-cores)

Sequence Segmentation can be solved in O(|X| 2 × h + τ p ) time via dynamic programming [START_REF] Bellman | On the approximation of curves by line segments using dynamic programming[END_REF], where τ p is the overall time spent for computing the penalty score of all subsequences of the input sequence X (according to the given penalty function p). Thanks to the connection shown in Fact 2, the dynamicprogramming algorithm for Sequence Segmentation can be easily adapted to solve Temporal Community Search as well. The pseudocode of this algorithm -termed Temporal-community-search -is reported as Algorithm 3, and described next.

The Temporal-community-search algorithm makes use of two (|T |×h)-dimensional matrices, i.e., P and R. Matrix P represents the penalty matrix. It contains, ∀t ∈ T , ∀i ∈ [0, h), the minimum cost of segmenting the sequence corresponding to the first t timestamps of T into i + 1 segments. As a result, P[t max , h -1] contains the objective-function value of the ultimate optimal solution to Prob-lem 5. Matrix R is the reconstruction matrix. It provides information about the optimal segmentation, and is used at the end of the algorithm to reconstruct the output {∆ i } h i=1 . Note that the algorithm does not explicitly compute the S i subgraphs corresponding to the optimal ∆ i intervals. In fact, as discussed above, each S i can be easily retrieved at the end of the algorithm, by simply setting it equal to the corresponding (Q, ∆ i )-highest-order-span-core C * Q,∆i . According to Fact 2, the penalty score of an interval ∆ T corresponds to -v * Q,∆ , i.e., the negative of the order of the (Q, ∆)-highest-order-span-core C * Q,∆ . All individual v * Q,∆ values, for all ∆ T , are efficiently computed altogether, at the beginning of the algorithm, via a "Q-constrained" variant of span-core decomposition (an alternative, but much less efficient strategy consists in computing every single v * Q,∆ from scratch, on the fly). Specifically, a simple (yet more efficient) variant of the span-core decomposition algorithm (Algorithm 1) is employed for this purpose, which outputs only those span-cores containing all the vertices in Q. This is easily achievable by stopping the core-decomposition subroutine, for every interval ∆ T , as soon as a core not containing all query vertices in Q has been encountered.

The time complexity of Algorithm 3 is

O(|T | 2 × h + τ sc )
, where τ sc is the time spent for computing the Q-constrained span-core decomposition of the input graph G.

A more efficient algorithm (based on maximal spancores)

A more efficient algorithm can be designed by noticing that, actually, one does not need to consider all timestamps in T in the dynamic-programming step. Rather, focusing on a subset T * ⊆ T -which is properly defined based on the maximal span-cores of the input graph, see next -allows for significantly reducing the dimensionality of the penalty matrix P and the reconstruction matrix R, hence the overall time complexity of the algorithm, without affecting optimality of the output solution. The following fact provides the theoretical basis for defining such a reduced temporal domain T * .

Fact 3 Given a temporal graph G = (V, T, τ ) and a set Q ⊆ V of query vertices, let C M (Q) be the set of all Q-constrained maximal span-cores of G. For a tem-

poral interval ∆ T , it holds that v * Q,∆ = max{0, max{k | C k,∆ ∈ C M (Q), ∆ ∆ }}.
Fact 3 states that the penalty score v * Q,∆ of an interval ∆ corresponds to the maximum among the orders of the Q-constrained maximal span-cores whose span includes ∆, if some exist. If an interval ∆ is not a subset of any span of a Q-constrained maximal span-core, then v * Q,∆ = 0. In that case, therefore, ∆ can be safely discarded, as it cannot be part of the optimal solution of the given Temporal Community Search problem instance (unless it is needed to fill possible "holes", see below). The ultimate consequence of this finding is that the aforementioned reduced temporal domain T * is identified by the timestamps covered by the spans of the maximal span-cores, along with auxiliary timestamps, which are needed to ensure a smooth execution of the dynamic-programming step, as well as a correct handling of some extreme cases. Specifically, let D = {∆ T | C k,∆ ∈ C M (Q)} be the set of the spans of the Q-constrained maximal span-cores of the input graph, and T D = ∆∈D ∆ be the set of timestamps that are part of a span of a Q-constrained maximal span-core. The first two sets of auxiliary timestamps correspond to the timestamps that immediately precede and succeed the intervals in D, i.e., the sets

T + D = {min{t e + 1, t max } | [t s , t e ] ∈ D} and T - D = {max{t s -1, 0} | [t s , t e ]
∈ D}, respectively. The timestamps in T + D and T - D (along with the last timestamp t max of the input temporal domain T ) are needed to allow the dynamic-programming step to identify a solution that actually covers the whole temporal domain T (as per Condition (ii) of Problem 3). In particular, such timestamps may be interpreted as a trick to give the dynamic-programming step the flexibility to select "holes" (i.e., time intervals in-between two consecutive but not necessarily contiguous timestamps in T D ). Moreover, we define T sup as the set of the first h

+ 1 -|T D ∪ T - D ∪ T + D ∪ {t max }| timestamps of T not contained in T D ∪ T - D ∪ T + D ∪ {t max }, i.e., T sup = {t i ∈ T \ (T D ∪ T - D ∪ T + D ∪ {t max }) | i ∈ [1, h + 1 -|T D ∪ T - D ∪ T + D ∪ {t max }|]}.
The timestamps in T sup are further auxiliary timestamps that are needed to return a correct h-sized solution when the timestamps in T D ∪ T - D ∪ T + D ∪ {t max } are less than h + 1 (the minimum number of timestamps required in T * to have a solution of size h). Note that

T sup is nonempty only if |T D ∪ T - D ∪ T + D ∪ {t max }| < h + 1. Ultimately, T * is defined as T * = T D ∪ T + D ∪ T - D ∪ {t max } ∪ T sup .
The proposed more efficient method for Temporal Community Search, termed Efficient-temporal-community-search, is summarized in Algorithm 4 and described next. The first five lines of the algorithm are devoted to the identification of T * . As said above, matrices P and R have here reduced dimensionality with respect to Algorithm 3: they are (|T * | × h)-dimensional matrices, where |T * | ≤ |T |. A mapping function M is used to assign an index within [0, |T * |) to every timestamp in |T * | (Line 6). Such a mapping is needed to have every timestamp in |T * | logically assigned to a row of matrices P and R. The rest of the algorithm resembles Algorithm 3, except for the fact that M is used every time that a row index has to be mapped to its corresponding timestamp (e.g., during the reconstruction of the solution).

An important point to clarify is that, during the execution of the Efficienttemporal-community-search algorithm, we might need the penalty score v * Q,∆ of intervals ∆ T corresponding to non-maximal (Q-constrained) span-cores. Therefore, the algorithm needs the v * Q,∆ score of all intervals ∆ T . To compute these v * Q,∆ scores (and, related to this, the set C M (Q) of Q-constrained maximal span-cores, at Line 1), there are two main options. The first one consists in computing the whole Q-constrained span-core decomposition (as done in Algorithm 3), keep the v * Q,∆ scores of all such cores, and eventually compute C M (Q) by simply filtering out non-maximal span-cores. The second option corresponds instead to compute C M (Q) directly, without passing through the whole Q-constrained span-core decomposition. This may be carried out by running a simple variant of the algorithm for computing maximal span-cores (Algorithm 2), where containment of query vertices is added as a further constraint. The computation of all the v * Q,∆ scores comes for free during the execution of this algorithm for Q-constrained maximal span-cores: these scores can therefore be retained by adding a few straightforward (constant-time) instructions to that algorithm. In our implementation we stick to the latter, as the Maximalspan-cores algorithm has been experimentally recognized as faster than the naïve filtering approach in all tested datasets.

The time complexity of the proposed Efficient-temporal-community-search algorithm is O(|T * | 2 × h + τ msc ), with τ msc being the time spent in computing the Q-constrained maximal span-cores and the penalty scores v * Q,∆ . As in practice (attested by our experiments) |T * | |T |, the proposed Efficient-temporalcommunity-search algorithm is expected to be much more efficient than its naïve counterpart, i.e., Algorithm 3.

Minimum community search

An instance of Temporal Community Search may admit several optimal solutions which might differ either in terms of output intervals {∆ i } h i=1 , or in terms of subgraphs assigned to the various identified intervals. More precisely, the latter refers to the fact that two optimal solutions might find the same segmentation {∆ i } h i=1 of the input temporal domain, but select different subgraphs S i for any interval ∆ i . Therefore, if the communities S i are not chosen carefully, they may result to be excessively large, not really cohesive, and containing redundant/outlying vertices. This is a well-recognized issue of minimum-degree-based community search [START_REF] Sozio | The community-search problem and how to plan a successful cocktail party[END_REF]. At the same time, large communities might include more cohesive and denser subgraphs that still exhibit optimality. Motivated by this, in this subsection we devise a method to refine the communities originally found by our algorithms for Temporal Community Search, specifically attempting to minimize their size while preserving optimality. The main idea behind our refinement method is based on the following result:

Proposition 2 (Community containment) Given a temporal graph G = (V, T, τ ), a set Q ⊆ V of

query vertices, and a positive integer

h ∈ N + , let { S i , ∆ i } h i=1 be a solution to Problem 3 on input G, Q, h with S i correspond- ing to the (Q, ∆ i )-highest-order-span-core of G, ∀i ∈ [1, h]. For every other solution { S i , ∆ i } h i=1 (referring to the same segmentation {∆ i } h i=1 ) to Prob- lem 3 on input G, Q, h it holds that S i ⊆ S i , ∀i ∈ [1, h].
Let k i be the minimum degree of S i , i.e., k i = v * Q,∆i is the order of the (Q, ∆ i )highest-order-span-core. Assume that there exists a solution S i to Problem 4 that is not contained in S i . This implies that (i) the minimum degree of a vertex of S i in ∆ i is k i , and (ii) the minimum degree of a vertex of S i ∪ S i in ∆ i is k i as well. This violates the maximality condition of the definition of span-core, since, by hypothesis, S i corresponds to the (Q, ∆ i )-highest-order-span-core of G.

The above proposition states that, given a solution { S i , ∆ i } h i=1 to the Temporal Community Search problem where every S i corresponds to the (Q, ∆ i )-highest-order-span-core of the input graph, one can focus on the various S i solely to refine the output communities, as such S i are guaranteed to contain all optimal solutions of the underlying problem instance (while keeping the segmentation {∆ i } h i=1 fixed). Within this view, we formulate the following optimization problem (which is a variant of Problem 4, with the additional constraint of requiring a smallest-sized solution): Consider (the optimization version of) the NP-hard mCST problem introduced by Cui et al. [START_REF] Cui | Local search of communities in large graphs[END_REF]: given a graph H = (V H , E H ) and a query vertex q ∈ V H , find a minimum-sized subgraph that contains q, is connected, and maximizes the minimum degree. Given an instance H, q of the mCST problem, construct an instance G, Q, ∆ of Problem 7 by defining G as composed by a single temporal snapshot corresponding to graph H, ∆ as a singleton interval composed of the single timestamp of G, and setting Q = {q}. It is straightforward to see that solving Problem 7 on input G, Q, ∆ is equivalent to solving mCST on input H, q , as the constraint about connectedness is automatically satisfied in Problem 7 for the special case of a single query vertex. As Problem 7 is NP-hard, we devise a heuristic that is inspired to the greedy one proposed for the Minimum Community Search problem in [START_REF] Barbieri | Efficient and effective community search[END_REF]. The proposed heuristic is outlined in Algorithm 5 and described next. In the pseudocode and in the following we denote as k * and k * min the minimum degree of S * and S * min , respectively, and as neigh ∆ (S, u) the neighbors of a vertex u ∈ V in the subgraph induced by S ⊆ V and ∆ T . Algorithm 5 iteratively adds vertices to the solution S * min according to a priority queue P . Priorities of vertices in P are defined based on a score that measures how promising a vertex is for making the current solution S * min reach the optimal minimum degree. Specifically, the score of a vertex u ∈ S * is defined as:

Problem 7 Given a temporal graph G = (V, T, τ ), a set Q ⊆ V of
score(u) = score + (u) -score -(u), where score + (u) = |{v ∈ neigh ∆ (S * min , u) | d ∆ (S * min , v) < k * }|; score -(u) = max{0, k * -d ∆ (S * min , u)}.
score + (u) is the gain effect of adding u to S * min , while score -(u) is the penalty effect. In particular, score + (u) counts the number of neighbors of u in S * min that would benefit from the inclusion of u to S * min , i.e., that have degree less than k * . On the other hand, score -(u) represents the number of neighbors of u still required in S * min so that u has degree at least k * . The algorithm starts by adding the query vertices to the queue P with priority +∞, in order to ensure that they will be selected at the very beginning. At each iteration of the main cycle of the algorithm (starting at Line 4), the vertex u exhibiting the highest priority is dequeued from P and is added to the solution S * min . As a consequence, a couple of updates are performed. First, u's neighbors not in the priority queue P are added to it (Lines 8-9). Note that this is the only step of the algorithm where the score of a vertex is computed from scratch and stored in A, a map that keeps the scores of all vertices in P up-to-date during the whole execution of the algorithm. The second update consists in recomputing the score of every v's neighbor w in the queue, if a vertex v ∈ S * min has reached the desired minimum degree k * after the addition of u.

Experiments

In this section we present an experimental evaluation to empirically assess the performance of all the proposed methods. Specifically, we focus on whole spancore decomposition (Section 7.1), maximal span-cores (Section 7.2), characterization of the extracted span-cores (Section 7.3), and temporal community search (Section 7.4). Datasets. We use eleven real-world datasets recording timestamped interactions between entities. For each dataset we select a window size to define a discrete time domain, composed of contiguous timestamps of the same duration, and build the corresponding temporal graph. If multiple interactions occur between two entities during the same discrete timestamp, they are counted as one. The characteristics of the resulting temporal graphs, along with the selected window sizes, are reported in Table 1.

The three smallest datasets were gathered by using wearable proximity sensors in schools, with a temporal resolution of 20 seconds. PrimarySchool2 contains the contact events between 242 volunteers (232 children and 10 teachers) in a primary school in Lyon, France, during two days [START_REF] Stehlé | High-resolution measurements of face-to-face contact patterns in a primary school[END_REF]. HighSchool 2 describes the close-range proximity interactions between students and teachers (327 individuals overall) of nine classes during five days in a high school in Marseilles, France [START_REF] Mastrandrea | Contact patterns in a high school: A comparison between data collected using wearable sensors, contact diaries and friendship surveys[END_REF]. HongKong reports the same kind of interactions for a primary school in Hong Kong, whose population consists of 709 children and 65 teachers divided into thirty classes, for eleven consecutive days [START_REF] Sapienza | Detecting anomalies in time-varying networks using tensor decomposition[END_REF].

ProsperLoans 3 represents the network of loans between the users of Prosper, a marketplace of loans between privates. Last.fm 3 records the co-listening activity of the Last.fm streaming platform: an edge exists between two users if they listened to songs of the same band within the same discrete timestamp. WikiTalk 3 is the communication network of the English Wikipedia. DBLP 3 is the co-authorship network of the authors of scientific papers from the DBLP computer science bibliography. StackOverflow 4 includes the answer-to-question interactions on the stack exchange of the stackoverflow.com website. Wikipedia 3 connects users of the Italian Wikipedia that co-edited a page during the same discrete timestamp. Finally, for both Amazon 3 and Epinions 3 , vertices are users and edges represent the rating of at least one common item within the same discrete timestamp. Implementation. All methods are implemented in Python (v. 2.7.16) and compiled by Cython. All the experiments were run on a machine equipped with Intel Xeon CPU at 2.1GHz. The experiments reported in Sections 7.1 and 7.2 used 64GB RAM, while the ones in Section 7.4 used 32GB RAM.

Span-core decomposition

We compare the two methods to compute a complete decomposition described in Section 4, i.e., the baseline Naïve-span-cores and the proposed Span-cores, in terms of execution time, memory, and total number of vertices input to the core-decomposition subroutine. We report these measures, together with the number of span-cores and maximal span-cores of each dataset, in Table 2.

In terms of execution time, Span-cores considerably outperforms Naïve-spancores in all datasets, achieving a speed-up from 2.1 up to two orders of magnitude. The speed-up is explained by the number of vertices processed by the core-decomposition subroutine, which is the most time-consuming step of the algorithms albeit linear in the size of the input subgraph. The difference of this quantity between Span-cores and Naïve-span-cores reaches over an order of magnitude in the WikiTalk, Wikipedia, and Epinions dataset, confirming the effectiveness of the "horizontal containment" relationships. The memory required by the two procedures is comparable in all cases since the largest structures needed in memory are the temporal graph itself and the set C of all span-cores.

Maximal span-cores

We compare our Maximal-span-cores algorithm to the naïve approach, described at the beginning of Section 5, based on running the Span-cores algorithm and filtering out the non-maximal span-cores, which we refer to as Naïve-maximalspan-cores. The results are again reported in Table 2.

Naïve-maximal-span-cores behaves very similarly to Span-cores: they only differ for the filtering mechanism which requires a few additional seconds in most cases. Maximal-span-cores is much faster than Naïve-maximal-span-cores for all datasets, with a speed-up from 1.3 for the Epinions dataset to one order of magnitude for the HongKong dataset. Except for the school datasets and Last.fm, the difference in terms of number of processed vertices is between one and 4 snap.stanford.edu three orders of magnitude, attesting the advantages of the top-down strategy of Maximal-span-cores, which avoids the visit of portions of the span-core search space and handles the overhead of reconstructing graphs, i.e., (V lb , E ∆ [V lb ]), efficiently. Finally, the memory requirements of the two methods are comparable for all datasets.

Span-cores characterization

We compare and characterize all span-cores against maximal span-cores. At first, Table 2 shows that span-cores are at least one order of magnitude more numerous than maximal span-cores for all datasets, with the maximum difference of three orders of magnitude for the HongKong dataset.

In Figure 2 we show the number (top) and the average size (bottom) of span-cores and maximal span-cores as a function of the order k for the DBLP and Epinions datasets. For both datasets, the number of maximal span-cores is at least one order of magnitude lower than the total number of span-cores up to a quarter of the k domain, where the span-cores are more numerous. Instead, in the rest of the domain, they mostly coincide due to the maximality condition over |∆|. The average size is also smaller for maximal span-cores, difference that wears thin when the gap between the numbers of span-cores and maximal span-cores starts decreasing since, for high values of k, most (or all) span-cores are maximal.

Figure 3 shows a different picture when numbers and average sizes of spancores are shown as a function of the size of the span |∆|. For both datasets, the number of span-cores and maximal span-cores is decreasing -which is expected since the number of intervals decreases when |∆| increases -with a constant gap close to one and two orders of magnitude, respectively. On the other hand, the behavior of the average size is quite different between the two datasets. For low values of |∆|, the average size of span-cores of the DBLP dataset is much higher than the average size of maximal span-cores, then the difference decreases and vanishes at the end of domain where a maximal span-core of |∆| = 37 dominates all other span-cores with |∆| ≥ 20. Instead, for the Epinions dataset, the average size of all span-cores and of maximal span-cores follow the same behavior, with a difference of less than an order of magnitude, because the maximality condition over k excludes the largest span-cores from the set of maximal span-cores.

Temporal community search

In this subsection we assess the performance of the proposed algorithms for temporal community search (presented in Sections 6.2-6.3), as well as the greedy procedure for reducing the size of the output communities (presented in Section 6.4). In the remainder of this subsection we refer to our basic algorithm (i.e., Algorithm 3, which precomputes the penalty scores via span-core decomposition) as SC-TCS, and to our more efficient algorithm (i.e., Algorithm 4, which exploits maximal span-cores to reduce the number of timestamps to be considered) as MSC-TCS. We also involve in the comparison a naïve version of Algorithm 3, where the penalty scores of the various intervals are computed from scratch during the execution of the algorithm, instead of precomputing them all via span-core decomposition. We refer to such a naïve method as Naïve-TCS.

The experimental setting we consider here is as follows. We vary the number |Q| of query vertices from 1 to 3. In particular, when |Q| = 1, we sample the single query vertex uniformly at random from the whole vertex set V . Instead, for |Q| > 1, we employ a more sophisticated sampling strategy that aims at finding meaningful query-vertex sets, i.e., vertices interacting with each other during the temporal observations, and, at the same time, independent from the specific form of the resulting span-core decomposition. Specifically, the sampling strategy we use is based on an adaptation of random walk to the temporal settings:

• Select a vertex uniformly at random from the whole V and add such a vertex to the set Q visited of visited vertices

• Starting from the first timestamp of the temporal domain T , iteratively:

-With probability p, move the random walker to a neighbor of the current vertex and add the neighbor to Q visited . If the current vertex has no neighbors in a given timestamp, the random walker jumps to the first next timestamp in which that vertex has at least one neighbor -With probability 1-p, keep the random walker at the current vertex, but go to the next timestamp

• Restart if the last timestamp of T is reached
• Stop when |Q visited | reaches a proper (user-defined) size ν

• Sample |Q| query vertices from Q visited with probability proportional to the frequency of the visits during the random walk

In our experiments we set p = 0.8 and ν = 3|Q|. As far as the number h of output communities, we consider the range h ∈ [START_REF] Bellman | On the approximation of curves by line segments using dynamic programming[END_REF][START_REF] Cheng | Efficient core decomposition in massive networks[END_REF][START_REF] Fang | Effective and efficient attributed community search[END_REF][START_REF] Goyal | Graph embedding techniques, applications, and performance: A survey[END_REF][START_REF] Kloumann | Community membership identification from small seed sets[END_REF][START_REF] Maslov | Specificity and stability in topology of protein networks[END_REF] on all datasets, with the exception of StackOverflow, for which we discard h = 60, and Epinions, for which we consider h ∈ [START_REF] Andersen | Communities from seed sets[END_REF][START_REF] Batagelj | Fast algorithms for determining (generalized) core groups in social networks[END_REF][START_REF] Berlingerio | Mining graph evolution rules[END_REF][START_REF] Bonchi | Core decomposition of uncertain graphs[END_REF][START_REF] Cheng | Efficient core decomposition in massive networks[END_REF][START_REF] Eidsaa | s-core network decomposition: A generalization of k-core analysis to weighted networks[END_REF]. For every parameter configuration, we perform five runs of every algorithm (in every run we sample a different query-vertex set). Note that we were not able to run the algorithms for temporal community search on the WikiTalk dataset due to memory constraints. Running time. In Figure 4 we show the running time of the proposed algorithms as a function of the number h of output communities, for the HighSchool, DBLP, Wikipedia, and Amazon datasets. The first general observation we make is that the running time of all algorithms increases as h gets higher. This in accordance with the time-complexity analysis reported in Section 6. Also, running times are independent of the selected query-vertex set Q. Looking at the individual performance, we notice that, as expected, the Naïve-TCS method has severe limitations in terms of efficiency: it takes hours to run on the HighSchool and Wikipedia datasets, while it is not able to terminate in less than 10 days on the remaining datasets. SC-TCS and MSC-TCS are much faster than Naïve-TCS, achieving a speedup of up to more than four orders of magnitude. MSC-TCS is in most cases faster than SC-TCS, with speedup up to one order of magnitude (on HighSchool, for h = 60). This confirms that the exploitation of the maximal span-cores is effective in both shortening the precomputation time and reducing the temporal domain considered in the dynamic-programming step. The only exception is the Wikipedia dataset. To dive deeper into the motivations of this exception, we report in Figure 5 the split of the average running time of SC-TCS and MSC-TCS into the time spent in the dynamic-programming step (DP) (which also includes the identification of the reduced temporal domain T * for MSC-TCS), and the precomputation time (i.e., the time required for computing all penalty scores via span-core decomposition or maximal span-cores).

Interestingly, what affects the most the running time is the precomputation of the scores. Apparently, the Q-constrained version of Span-cores is more efficient than Maximal-span-cores in some datasets, which we believe is due to the structure of the search space. On the other hand, these results confirm that the reduction of the temporal domain considered by the dynamic-programming step is actually effective since the DP running time of MSC-TCS is always less than (or equal to) the DP running time of SC-TCS.

Greedy-minimum-community-search. Here we evaluate the performance of the proposed Greedy-minimum-community-search algorithm (Algorithm 5) for reducing the size of the output communities. We recall that the proposed algorithms for Temporal Community Search (evaluated above) output communities corresponding to the (Q, ∆ i )-highest-order-span-cores for all {∆ i } h i=1 temporal intervals identified. The Greedy-minimum-community-search algorithm takes every (Q, ∆ i )-highest-order-span-core and attempts to reduce its size, while preserving optimality. Thus, the ultimate goal of the evaluation presented next is to show how well Greedy-minimum-community-search is able to reduce the size of the original span-cores, and what is its overhead in terms of running time.

Figure 6 compares the size of the starting (Q, ∆ i )-highest-order-span-cores and the size of the corresponding reduced community yielded by the Greedyminimum-community-search algorithm, for the PrimarySchool, HongKong, Last.fm, and Epinions datasets. It can be easily observed that, as a general trend, the reduced communities are much smaller than the original ones, in all datasets, up to four orders of magnitude. The results on the Epinions dataset are a bit different than the other three datasets. In fact, on that dataset, the original communities (CS) always include the whole 120k vertices of the graph, while the communities found by Greedy-minimum-community-search (minimum CS) have median size smaller than 10, and, in many cases, they correspond to communities composed of the query vertices only. This means that, on the Epinions dataset, for our tested queries, the algorithms for Temporal Community Search do not extract communities that are really cohesive around the query vertices. This way, the benefits of exploiting an a-posteriori community-size-reduction step are less evident. Also, we do not notice any evident pattern as a function of h, for any dataset.

In Table 3 we report the average running time of an execution of Greedyminimum-community-search, for all datasets. Note that this is the average time required to process one of the h communities in a solution to Temporal Community Search. Greedy-minimum-community-search runs in 8 seconds or less in all tested datasets. Therefore, the additional running time required by the algorithm is rather negligible.

To summarize, Greedy-minimum-community-search is empirically recognized as a powerful post-processing method for improving the quality of the solutions to Temporal Community Search: it finds much smaller communities at a very small additional computational cost. In this section we illustrate applications of (maximal) span-cores in the analysis of face-to-face interaction networks, and how the methods for Temporal Community Search can be profitably exploited in a task of graph classification. For these applications we use the three networks gathered in schools, i.e., PrimarySchool, HighSchool, and HongKong, which are described above, at the beginning of Section 7. We use a window size of 5 minutes and, in the analysis, we discard span-cores of |∆| = 1, i.e., having span of 5 minutes, since they represent short interactions, not significant for our purposes. In the following we show (i) three types of interesting temporal patterns (Section 8.1), i.e., social activities of groups of students within a school day, mixing of gender and class, and length of social interactions in groups; (ii) a procedure to detect anomalous contacts and intervals that exploits maximal span-cores (Section 8.2); and, (iii) an approach to graph classification based on temporal community search (Section 8.3).

Temporal patterns

Temporal activity. We first show how span-cores afford a simple temporal analysis of social activities of groups of people within a school day. The left side of Figure 8 reports colormaps of the order k of the span-cores as a function of their starting time t s (x axis) and of the size of their temporal span |∆| (y axis), for a school day of the PrimarySchool and HighSchool datasets. Darker gray indicates span-cores of high order and slots located in the upper part of the plots refer to span-cores of long span. It is important to notice that the linear decay in span duration is naturally due to the definition of span-core and to the shifting of the starting time t s ; therefore, it is not a distinguishing feature of the activity patterns found in the analyzed data. In both datasets, fluctuations of k and |∆| are observed along the day, which can be related to school events. Around 10 a.m., the size of the span |∆| reaches a local maximum in correspondence to the morning break, which means that students establish long-lasting interactions that hold beyond the break itself. Moreover, when classes gather for the lunch break, the order k reaches its maximum value since students tend to form larger and more cohesive groups.

In order to verify that these results are not trivially derived from the general temporal activity, as simply given by the number of interactions in each timestamp, we compare our findings to a null model. At each timestamp of the temporal graphs, we reshuffle the edges by the Maslov-Sneppen algorithm [START_REF] Maslov | Specificity and stability in topology of protein networks[END_REF] which consists in repeating the following operations up to when all edges have been processed: select at random two edges with no common vertices, e.g., (u, v) and (w, z), and transform them into (u, z) and (w, v), if neither (u, z) and (w, v) existed in the original timestamp. This reshuffling preserves the degree of each vertex in each timestamp and the global activity (i.e., the number of contacts per timestamp), but destroys correlations between edges of successive timestamps. In the right side of Figure 8 we show the results of the temporal analysis described above for the reshuffled datasets. In both, the values of |∆| and k reached are much smaller than in the original datasets. The size of the span |∆| is always shorter than 20 minutes, while in the original datasets it is much longer, up to 170 minutes, and the order k is always equal to 1, compared to the original maximum of 5. The time-evolving cohesive structures detected by the temporal core decomposition in the original datasets are completely lost on reshuffling, since only span-cores of short span and low coreness are observed in the latter case. This shows that the temporal structure exposed by the spancore decomposition is not simply a consequence of temporal patterns of global activity but that span-cores represent a concrete method to detect complex cohesive structures and their temporal evolution. Mixing patterns. We now show an analysis of mixing patterns of students with respect to gender and class. Such vertex attributes are indeed available for the individuals of the PrimarySchool dataset. We define as gender purity of a span-core the fraction of individuals of the most represented gender within the span-core. Class purity is analogously defined. The left plot of Figure 9 reports the temporal evolution of the average gender and class purity of the Gender purity is instead rather low. On the other hand, when students are gathered together, during the morning break at 10 a.m. and the lunch break between 12 a.m. and 2 p.m., the situation is overturned: gender purity reaches large values while class purity drastically decreases. This shows that primary school students group with individuals of the same class, disregarding the gender, only when they are forced by the schedule of the lessons, but prefer on average to form cohesive groups with students of the same gender during breaks. This is in agreement and complements a previous study of the same dataset focusing on single interactions in the static aggregated network [START_REF] Stehlé | Gender homophily from spatial behavior in a primary school: A sociometric study[END_REF].

The right plot of Figure 9 shows the temporal evolution of the average gender and class purity for a null model in which gender and class are randomly reshuffled among individuals. The two curves are more flat and the anti-correlation between them completely vanishes. This testifies that the results on the original dataset are not simply due to the relative abundance of individuals of each type interacting at each time, but reflect genuine mixing patterns and their temporal evolution. Interaction length. Finally, we analyze the duration of interactions of social groups in schools by studying the distribution of the size of the span of the maximal span-cores of the three datasets (Figure 10). All distributions are extremely skewed with broad tails: most maximal span-cores have duration less than 1 hour, but durations much larger than the average can also be observed. Interestingly, the three datasets at hand all exhibit the same functional shape, confirming a robust statistical behavior. We also note that similar robust broad distributions have been observed for simpler characteristics of human interactions such as the statistics of contact durations [START_REF] Stehlé | High-resolution measurements of face-to-face contact patterns in a primary school[END_REF][START_REF] Mastrandrea | Contact patterns in a high school: A comparison between data collected using wearable sensors, contact diaries and friendship surveys[END_REF]. Outliers appear also at very large durations, especially for the HongKong dataset that has maximal span-cores lasting up to 83 hours. Group interactions of such long span are Figure 10: Distribution of the size of the span of the maximal span-cores. The x axis reports the size of the span (in minutes), while the y axis the percentage of maximal span-cores having a given size of the span.

clearly abnormal and represent outliers in the distributions. We will show, in the following of this section, how to exploit such outliers to detect both irregular interactions and anomalous temporal intervals.

Anomaly detection

The identification of anomalous behaviors in temporal networks has been the focus of several studies in the last few years [START_REF] Mongiovi | Netspot: Spotting significant anomalous regions on dynamic networks[END_REF][START_REF] Sapienza | Detecting anomalies in time-varying networks using tensor decomposition[END_REF]. Based on the above findings, we devise a simple procedure to detect anomalous edges and intervals of the HongKong dataset that exploits maximal span-cores. The topmost plot of Figure 11 reports the number of edges for each timestamp of the original HongKong dataset. It is easy to notice that there is a lot of constant anomalous activity between school days and during the weekend, i.e., days six and seven: unexpectedly, the number of interactions per timestamp does not drop to zero. This happened in fact because proximity sensors were left in each class and close to each other, at the end of the lessons. In order to automatically detect these steady activity patterns that do not correspond to any genuine social dynamics, we apply the following procedure: (i) find a set of anomalously long temporal intervals supporting maximal span-cores, (ii) identify anomalous vertices, and, (iii) filter out anomalous edges.

The first step of this procedure requires to find the set of temporal intervals

I = {∆ T | C k,∆ ∈ C M ∧ |∆| > tr}
that are the span of a maximal span-core C k,∆ with size longer than a certain threshold tr. Then, for each timestamp t ∈ T , select as anomalous all those vertices that appear in the span-cores {C 1,∆ | ∆ ∈ I ∧ t ∈ ∆}, i.e., the span-cores of k = 1 whose span is in I and contains t. Finally, at each timestamp t ∈ T , remove edges that are incident to at least a vertex that has been marked as anomalous at time t. Consistently with the distribution of the span durations of the maximal span-cores, we select the threshold tr = 22 (110 minutes). The results of this filtering procedure are shown in the middle plot of Figure 11. The number of edges during school days remains approximately unchanged, while the activity noticeably decreases in-between. Identifying as positives the spurious interactions occurring when the school is closed and as negatives the genuine interactions observed when the school is open, this approach achieves a precision of 0.91 and a recall of 0.64. We can refine this anomaly detection process by identifying, in addition to anomalous edges, also anomalous temporal intervals. We define a timestamp t ∈ T as anomalous if the ratio between the number of original edges (top plot of Figure 11) and the number of filtered edges (middle plot of Figure 11) exceeds a given threshold. We apply this further filtering to the HongKong dataset with a threshold of 1.5 and report the results in the bottommost plot of Figure 11. The number of edges when the school is closed drops to zero, while the activity during school days is not modified, except for the last one, which is affected by the proximity to the end of the time domain. The overall procedure yields a slightly higher value of precision, 0.93, and substantially improves the recall to 0.99.

Graph embedding and (supervised) vertex classification

In this subsection we show how Temporal Community Search can be profitably exploited for classifying the vertices of a temporal graph. Specifically, the classification framework we set up is based on the paradigm of graph embedding, which has attracted a great deal of attention in the last few years, and whose goal is to assign to every vertex of a graph a numerical vector (i.e., an embedding) such that structurally similar vertices are represented by similar vectors, and vice versa [START_REF] Grover | node2vec: Scalable feature learning for networks[END_REF][START_REF] Epasto | Is a single embedding enough? learning node representations that capture multiple social contexts[END_REF][START_REF] Goyal | Graph embedding techniques, applications, and performance: A survey[END_REF]. Here, our framework simply consists in learning suitable embeddings for the vertices of the input graph, and then give them as input to some (well-established) classifier to ultimately accomplish the desired classification task. Thus, the main goal is to learn embeddings that are well-representative of the relationships among vertices, so as to help the classifier perform accurately. As our main result here, we show how an embedding strategy based a simple exploitation of the output of Temporal Community Search achieves results comparable to well-established vertex-embedding methods such as DeepWalk [START_REF] Perozzi | Deepwalk: Online learning of social representations[END_REF], LINE [START_REF] Tang | Line: Large-scale information network embedding[END_REF], and node2vec [START_REF] Grover | node2vec: Scalable feature learning for networks[END_REF].

Method. For every vertex of the input temporal graph, we build an embedding as an h-dimensional vector conveying the information provided by a solution to the Temporal Community Search problem on the same graph. Specifically, consider a vertex u ∈ V and a solution { S i , ∆ i } h i=1 to Temporal Community Search on query-vertex set Q = {u}. We define u's embedding as

X u = [v * Q,∆1 , v * Q,∆2 , . . . , v * Q,∆ h ],
which corresponds to the temporally-ordered sequence of minimum degrees of the h communities identified by the temporal-community-search solution. Below we show that this simple approach is sufficient to achieve interesting experimental results. Clearly, more sophisticated methods are possible, e.g., by simultaneously exploiting information from the S i communities. However, our main goal here is to give an idea of how the Temporal Community Search problem can be successfully leveraged in a relevant application scenario, rather than devise the best temporal-community-search-based graph-embedding method.

Evaluation. We assess the performance of our method on the PrimarySchool and HighSchool datasets. In these datasets vertices correspond to students, and vertex labels (to be predicted) are the classes that every student belongs to. We involve in the comparison the following state-of-the-art vertex-embedding methods:

• DeepWalk [START_REF] Perozzi | Deepwalk: Online learning of social representations[END_REF], a method that preserves the proximity between vertices by running a set of random walks and maximizing the sum of the loglikelihood of a set of vertices for each walk.

• LINE [START_REF] Tang | Line: Large-scale information network embedding[END_REF], which optimizes a suitable objective function preserving both first-order (one-hop) and second-order (two-hop) proximities. Neighborhoods are not explored via random walk, but in a breadth-first fashion.

• node2vec [START_REF] Grover | node2vec: Scalable feature learning for networks[END_REF], which is based on the same idea underlying DeepWalk, but allowing more flexibility on how random walks explore and leave the neighborhood of the current vertex. These three methods consider non-temporal graphs. Therefore, we feed them with aggregated graphs in which every edge exists if it exists in at least one timestamp. We tune the parameters p and q of node2vec as in the original paper [START_REF] Grover | node2vec: Scalable feature learning for networks[END_REF], i.e., by performing a grid search with p, q ∈ {0.25, 0.50, 1, 2, 4}, while keeping the dimensionality of the embeddings fixed to h = 200 and h = 625, for the PrimarySchool and HighSchool datasets, respectively. The other competing methods, DeepWalk and LINE, and our method based on temporal community search (which we refer to as TCS in the following) do not have parameters (apart from the dimensionality h of the output embeddings). After filtering out those vertices representing the teachers, we partition the remaining vertices (i.e., the students) into training and test sets with an 80-20 split. A standard scaler is applied to the features extracted by each embedding method and, then, a penalized logistic-regression classifier is trained.

In Figure 12 we report classification results in terms of Macro F 1 -score, with varying the dimensionality h of the embeddings. On the PrimarySchool dataset, for h ≥ 200, our TCS has performance close to 1 in terms Macro F 1 -score, similarly to the three baselines. It can be observed that the TCS results are better as h gets higher; in particular, TCS is even better than node2vec for h = |T |. This is expected and is motivated as, for higher h, TCS is allowed to rely on more temporal information about the vertices. On the HighSchool dataset, TCS is outperformed by all methods for smaller h. However, again, the performance of TCS becomes competitive for larger h, up to achieving comparable results to the best method(s) for h = |T |.

Conclusions

Temporal networks are a powerful representation of how relations are established and interrupted along time among a given population of entities. An interesting primitive for analyzing this type of networks is the extraction of relevant patterns, such as dense subgraphs, together with their time interval of existence (or span). Following this idea, we introduced in this paper a notion of temporal core decomposition where each core is associated with its span. Exploiting containment properties among cores we developed efficient algorithms for computing all the span-cores, and also only the maximal ones. We then introduced the problem of temporal community search and showed how it can be solved in polynomial time via dynamic programming. We also proved an interesting connection between temporal community search and maximal spancores, which made it possible to devise a considerably more efficient algorithm than the naïve dynamic-programming one. Finally, we presented applications on empirical networks of human close-range proximity, that illustrate the relevance of the notions of (maximal) span-core and temporal community search in a variety analyses and applications.

In future work we will study the role of maximal span-cores with large coreness and/or |∆| in spreading processes on temporal networks. Furthermore, span-cores represent features that can be used for network fingerprinting and classification as well as for model validation, and that could provide support for new ways of visualizing large-scale time-varying graphs. Finally, future work will include further detailed investigations of the application of span-cores in the presented case studies.

2. 1

 1 Core decompositionGiven a simple (static) graph G = (V, E), let d(S, u) denote the degree of vertex u ∈ V in the subgraph induced by vertex set S ⊆ V , i.e., d(S, u) = |{v ∈ S | (u, v) ∈ E}|. The notions of k-core and core decomposition are defined as follows:

  on graph G ∆ for each temporal interval ∆ T . Such a method has time complexity O( ∆ T (|∆| × |E|)), i.e., O(|T | 2 × |E|).

Theorem 3

 3 query vertices, and an interval ∆ T , let S * ⊆ V be the subset of vertices containing all the solutions to Problem 4 on input G, Q, ∆ (according to what stated in Proposition 2). Find S * min = argmin {S|Q⊆S⊆S * ,min u∈S d∆(S,u)≥min u∈S * d∆(S * ,u)} |S|. Problem 7 in NP-hard.

Figure 2 :Figure 3 :

 23 Figure 2: Top plots: number of span-cores and maximal span-cores as a function of the order k. Bottom plots: average size of all span-cores and maximal spancores as a function of the order k.

Figure 4 :

 4 Figure 4: Running time of the algorithms for Temporal Community Search, as a function of the number h of output communities. Each boxplot corresponds to 15 data points.

Figure 5 :

 5 Figure 5: Split of the average running time of the SC-TCS and MSC-TCS algorithms into dynamic programming (DP) and precomputation, for the Wikipedia and Last.fm datasets.

Figure 6 :

 6 Figure 6: Comparison of the size of the communities in the solutions to Temporal Community Search: original output of the algorithms for Temporal Community Search (CS) and after running the Greedy-minimum-communitysearch algorithm on top of them (minimum CS). Each boxplot corresponds to 15 data points.

Figure 7

 7 Figure 7: DP domain

Figure 8 :

 8 Figure 8: Temporal activity of a school day of the PrimarySchool and HighSchool datasets: the x axis reports the hour of the day at which the span of a span-core starts, the y axis specifies the size of the span (in minutes), and the color scale shows the order k. At a glance, it can be observed that the temporal structure of the span-core decomposition detects time-evolving cohesive structures in the original datasets (left plots) that completely disappear in the reshuffled datasets (right plots).

Figure 9 :

 9 Figure 9: Temporal evolution (time on the x axis) of average gender purity and average class purity (y axis) of the maximal span-cores of the PrimarySchool dataset. Original data on the left, reshuffled data on the right.

Figure 11 :

 11 Figure 11: HongKong dataset: number of edges per timestamp in the original data (top), after filtering anomalous edges (middle), and after filtering anomalous edges and intervals (bottom). Days 6 and 7 are weekend.

HighSchoolFigure 12 :

 12 Figure 12: Graph classification: Macro F 1 -score of the proposed temporalcommunity-search-based graph-embedding method TCS and the competing methods, with varying the dimensionality h of the output embeddings, on the PrimarySchool and HighSchool datasets.

Algorithm 4 :16 16 R 20 ∆ 21 ub ← lb - 1 22 forall i ∈ (h, 0] do 23 S i ← C * Q,∆i Algorithm 5 : 5 dequeue u from P 6 S

 4162021123556 Efficient-temporal-community-search Input: A temporal graph G = (V, E, T ), a set Q ⊆ V of query vertices, an integer h ∈ N + . Output:A set { S i , ∆ i } h i=1 , where Q ⊆ S i ⊆ V , ∀1 ≤ i ≤ h, and {∆ i } h i=1 is a partition of T . /* Identification of T * */ Compute the set C M (Q) of Q-constrained maximal span-cores of G 2 D ← {∆ T | C k,∆ ∈ C M (Q)} 3 T D ← ∆∈D ∆; T + D ← {min{t e +1, t max } | [t s , t e ] ∈ D}; T - D ← {max{t s -1, 0} | [t s , t e ] ∈ D} 4 T sup ← {t i ∈ T \ (T D ∪ T - D ∪ T + D ∪ {t max }) | i ∈ [1, h + 1 -|T D ∪ T - D ∪ T + D ∪ {t max }|]} 5 T * ← T D ∪ T + D ∪ T - D ∪ {t max } ∪ T sup /* Initialization */ Compute v * Q,∆ , ∀∆ T 7 M ← mapping function [0, |T * |) → T * 8 P ← an empty (|T * | × h)-dimensional matrix // Penalty matrix 9 R ← an empty (|T * | × h)-dimensional matrix // Reconstruction matrix 10 forall r ∈ [0, |T * |) do 11 P[r, 0] ← -v * Q,[0,M[r]] 12 R[r, 0] ← 0 /* Dynamic-programming step */ 13 forall r ∈ [0, |T * |) do 14 forall i ∈ [1, h) do 15 P[r, i] ← min ∈[0,r] P[ , i -1] -v * Q,[M[ +1],M[r]] [r, i] ← argmin ∈[0,r] P[ , i -1] -v * Q,[M[ +1],M[r]]/* Reconstruction of the solution */17 ub ← |T * | -1 18 forall i ∈ (h, 0] do 19 lb ← R[ub, i] i ← [M[lb], M[ub]] Greedy-minimum-community-search Input: A temporal graph G = (V, E, T ), a set Q ⊆ V ofquery vertices, an interval ∆ T , a subset of vertices S * ⊆ V containing all the solutions to Problem 4 on input G, Q, ∆ . Output: A subset S * min of vertices such that Q ⊆ S * min ⊆ S * and min u∈S * min d ∆ (S * min , u) ≥ min u∈S * d ∆ (S * , u). 1 S * min ← ∅; P ← ∅; A ← ∅ 2 add every q ∈ Q to P with priority +∞ 3 k * ← min u∈S * d ∆ (S * , u); k * min ← 0 4 while k * min < k * or Q ⊆ S * min do * min ← S * min ∪ {u} 7 forall v ∈ neigh ∆ (S * , u) \ S * min \ P do 8 A[v] ← score(v) 9 add v to P with priority A[v] 10 forall v ∈ neigh ∆ (S * min , u) do 11 if d ∆ (S * min , v) = k * then 12 forall w ∈ neigh ∆ (P, v) do 13 A[w] ← A[w] -1 14 k * min ← min v∈S * min d ∆ (S * min , v)

  ≤ t s and t e ≥ t e . Given an interval ∆ T , we denote E ∆ = t∈∆ E t the edges existing in all timestamps of ∆. Given a subset S ⊆ V of vertices, let E ∆

		1}
	is a function defining for each pair of vertices u, v ∈ V and each timestamp t ∈ T
	whether edge (u, v) exists in t. We denote E = {(u, v, t) | τ (u, v, t) = 1} the set
	of all temporal edges. Given a timestamp t ∈ T , E t = {(u, v) | τ (u, v, t) = 1} is
	the set of edges existing at time t. A temporal interval ∆ = [t s , t e ] is contained
	into another temporal interval ∆ = [t s , t e ], denoted ∆	∆ , if t s

  t max ]. The following reasoning holds for every t s . Let E -(t e ) = E [ts,te ] \ E [ts,te+1] be the set of edges that are in E [ts,te ] but not in E [ts ,te+1] , for t e ∈ [t s , . . . , t * -1]. As a first general step, for each t s , we compute and store all edge sets {E -(t e )} te∈[ts,t * -1] . These operations can be accomplished in O(|T |×|E|) overall time, because every E -(t e ) can be computed incrementally from E [ts ,te ] as E -(t e ) = {(u, v) ∈ E [ts,te ] | τ (u, v, t e + 1) = 0}. Moreover, for any timestamp t e , we keep a map D storing all vertices of G [ts,te ] organized by degree. Specifically, the set D[k] contains all vertices having degree > k in G [ts ,te] . Every vertex in D is thus replicated a number of times equal to its degree. This way, the overall space taken by D is O(|E|), i.e., as much space as G. D is initialized as empty (when t e = t * ) and repeatedly augmented as t e decreases, by a linear scan of the various E -(t e ). The overall filling of D (for all t e ) therefore takes O(|T | × |E|) time. Then, the desired V lb can be computed in constant time simply as V lb = D[lb]. As for E ∆ [V lb ], for any t e , we first reconstruct E [ts,te ] as E [ts,te +1] ∪ E -(t e ), having previously computed E [ts,te +1] . Note that storing all E -(t e ) takes O(|E|) space. That is why we store all E -(t e ) and reconstruct E [ts,te ] afterward (instead of storing the latter, which would take O(|T | × |E|) space). E ∆ [V lb ] is ultimately derived by a linear scan of E [ts,te ] , taking all edges in E [ts ,te] having both endpoints in V lb . This way, the step of building E ∆ [V lb ] for all t e takes again O(|T | × |E|) overall time.

Table 1 :

 1 Temporal graphs used in the experiments.

	dataset	|V |	|E|	|T |	window size	domain
	HighSchool	327	47k 1212	5 mins	face-to-face
	PrimarySchool 242	55k	390	5 mins	face-to-face
	HongKong	806	2M 2976	5 mins	face-to-face
	ProsperLoans	89k	3M	307	7 days	economic
	Last.fm	992	4M	77	21 days	co-listening
	WikiTalk	2M	10M 192	28 days	communication
	DBLP	1M	11M	80	366 days	co-authorship
	StackOverflow	2M	16M	51	56 days	question answering
	Wikipedia	343k 18M 101	56 days	co-editing
	Amazon	2M	22M 115	28 days	co-rating
	Epinions	120k 33M	25	21 days	co-rating

We use "network" and "graph" interchangeably throughout the paper.

sociopatterns.org

konect.cc