Edoardo Galimberti
email: edoardo.galimberti@isi.it

Alain Barrat
email: alain.barrat@cpt.univ-mrs.fr

Francesco Bonchi
email: francesco.bonchi@isi.it

Ciro Cattuto
email: ciro.cattuto@isi.it

Francesco Gullo
email: gullof@acm.org

Mining (maximal) span-cores from temporal networks

When analyzing temporal networks, a fundamental task is the identification of dense structures (i.e., groups of vertices that exhibit a large number of links), together with their temporal span (i.e., the period of time for which the high density holds). We tackle this task by introducing a notion of temporal core decomposition where each core is associated with its span: we call such cores span-cores.

As the total number of time intervals is quadratic in the size of the temporal domain T under analysis, the total number of span-cores is quadratic in |T | as well. Our first contribution is an algorithm that, by exploiting containment properties among span-cores, computes all the span-cores efficiently. Then, we focus on the problem of finding only the maximal span-cores, i.e., span-cores that are not dominated by any other span-core by both the coreness property and the span. We devise a very efficient algorithm that exploits theoretical findings on the maximality condition to directly compute the maximal ones without computing all span-cores.

Experimentation on several real-world temporal networks confirms the efficiency and scalability of our methods. Applications on temporal networks, gathered by a proximity-sensing infrastructure recording face-to-face interactions in schools, highlight the relevance of the notion of (maximal) span-core in analyzing social dynamics and detecting/correcting anomalies in the data.

INTRODUCTION

A temporal network is a representation of entities (vertices), their relations (links), and how these relations are established/broken along time. Extracting dense structures (i.e., groups of vertices exhibiting a large number of links among 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. This type of patterns enables fine-grain analysis of the network dynamics and can be a building block towards more complex tasks (such as finding temporally recurring subgraphs or anomalously dense ones) and applications. For instance, they can help in studying the contact networks among individuals to quantify the transmission opportunities of respiratory infections, modeling situations where the risk of transmission is higher, with the goal of designing mitigation strategies [START_REF] 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, in real-time, events and buzzing stories [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]. In scientific collaboration and citation networks 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 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.

To the best of our knowledge, this type of core, which we call span-core, has never been studied so far.

Challenges and contributions. As the total number of time intervals is quadratic in the size of the temporal domain T under analysis, also the total number of span-cores is, in the worst case, quadratic in T . Nevertheless, exploiting nice containment properties we devise an efficient algorithm for computing all the span-cores. Then, we shift our attention to the problem of finding only the maximal spancores, i.e., span-cores that are not dominated by any other span-core by both the coreness property and the span. A straightforward way of approaching the maximal-span-core-mining 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 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 a complete decomposition. The design of an algorithm of this kind is an interesting challenge, as it contrasts 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.

The contributions of this paper can be summarized as follows:

• We introduce the notion of span-core decomposition and maximal span-core in temporal networks. We characterize structure and size of the search space, and prove 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 a number of theoretical findings about the relationship among maximal span-cores and exploit them to devise an algorithm that is more efficient than computing all span-cores and discarding the non-maximal ones (Section 5). • We provide a comprehensive experimentation on several realworld temporal networks, with millions of vertices, tens of millions of edges, and hundreds of timestamps, which attests efficiency and scalability of our methods (Section 6). • We present applications on face-to-face interaction networks, that illustrate the relevance of the notion of (maximal) spancore in real-life analyses (Section 7).

The next section overviews the related literature, while Section 8 discusses future work and concludes the paper.

BACKGROUND AND RELATED WORK

Core decomposition. In standard graphs, among the many definitions of dense structures, core decomposition plays a central role as it can be computed in linear time [START_REF] Batagelj | Fast algorithms for determining (generalized) core groups in social networks[END_REF][START_REF] Matula | Smallest-last ordering and clustering and graph coloring algorithms[END_REF], and can speedup/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], it can be used to approximate the densest-subgraph problem [START_REF] Kortsarz | Generating sparse 2-spanners[END_REF], and betweenness centrality [START_REF] Healy | Characterization of graphs using degree cores[END_REF].

Given a simple 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}|. Definition 1 (Core Decomposition). 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 has been established as an important tool to analyze and visualize complex networks [START_REF] Alvarez-Hamelin | Large scale networks fingerprinting and visualization using the k-core decomposition[END_REF][START_REF] Batagelj | Partitioning approach to visualization of large graphs[END_REF] in several domains, e.g., bioinformatics [START_REF] Bader | 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] Garcia | Social resilience in online communities: The autopsy of friendster[END_REF][START_REF] Kitsak | Identifying influential spreaders in complex networks[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] Li | Efficient core maintenance in large dynamic graphs[END_REF][START_REF] Sariyüce | Streaming algorithms for k-core decomposition[END_REF], and diskbased [START_REF] Cheng | Efficient core decomposition in massive networks[END_REF], and for various types of graph, such as uncertain [START_REF] Bonchi | Core decomposition of uncertain graphs[END_REF], directed [START_REF] Giatsidis | D-cores: measuring collaboration of directed graphs based on degeneracy[END_REF], and weighted graphs [START_REF] Garas | A k -shell decomposition method for weighted networks[END_REF].

Core decomposition in multilayer networks has been studied in [START_REF] Galimberti | Core decomposition and densest subgraph in multilayer networks[END_REF]. As any subset of layers is allowed in this setting, the total number of cores is intrinsically exponential. Although temporal networks can be seen as a special case of multilayer networks (where each timestamp is interpreted as a layer), the sequentiality of time represents an important structural constraint: in this paper we are interested in cores that span a temporal interval, and not simply any subset of (potentially non-contiguous) timestamps. As a consequence, the search space and the number of cores are no longer exponential as in the multilayer case. A type of core decomposition for temporal networks has been proposed by Wu et al. [START_REF] Wu | Core decomposition in large temporal graphs[END_REF], who define the (k, h)-core as the largest subgraph in which every vertex has at least k neighbors and at least h temporal connections with each of them. Therefore, even in the Wu et al.'s definition the sequentiality of connections is not taken into account and noncontiguous timestamps can support the same core. Our temporal cores have instead a clear temporal collocation and continuous spans, thus the Wu et al.'s definition cannot be reduced to ours (or vice versa). As we will see in Section 7, such a temporal collocation is important in applications. Patterns in temporal networks. Semertzidis et al. [START_REF] Semertzidis | Best friends forever (bff): Finding lasting dense subgraphs[END_REF] introduce the problem of identifying a set of vertices that are densely connected in all or at least k timestamps of a temporal network. Similarly, Jethava and Beerenwinkel [START_REF] Jethava | Finding dense subgraphs in relational graphs[END_REF] formulate the densestcommon-subgraph problem on an input that can be interpreted as a special type of temporal network, i.e., a set of graphs sharing the same vertex set. The notion of ∆-clique has been proposed in [START_REF] Himmel | Enumerating maximal cliques in temporal graphs[END_REF][START_REF] Viard | Computing maximal cliques in link streams[END_REF], as a set of vertices in which each pair is in contact at least every ∆ timestamps. Complementary approaches study the problem of discovering dense temporal subgraphs whose edges occur in short time intervals considering the exact timestamp of the occurrences [START_REF] Rozenshtein | Finding dynamic dense subgraphs[END_REF], and the problem of maintaining the densest subgraph in the dynamic graph model [START_REF] Epasto | Efficient densest subgraph computation in evolving graphs[END_REF]. A slightly different, but still related body of literature focuses on frequent evolution patterns in temporal attributed graphs [START_REF] Berlingerio | Mining graph evolution rules[END_REF][START_REF] Desmier | Cohesive co-evolution patterns in dynamic attributed graphs[END_REF][START_REF] Inokuchi | Mining frequent graph sequence patterns induced by vertices[END_REF], link-formation rules in temporal networks [START_REF] Bringmann | Learning and predicting the evolution of social networks[END_REF][START_REF] -K. Leung | Mining interesting link formation rules in social networks[END_REF], and the discovery of dynamic relationships and events [START_REF] 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].

PROBLEM DEFINITION

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, 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 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 ∆ [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 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 spancore decomposition of a temporal graph G, i.e., all span-cores of G.

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 spancores

C k, ∆ , C k ′ , ∆ ′ of a temporal graph G it holds that k ′ ≤ k ∧ ∆ ′ ⊑ ∆ ⇒ C k, ∆ ⊆ C k ′ , ∆ ′ .
Proof. 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 argument 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.
As far as the second argument, 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. □ 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 ∆ ).
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 O(|T | 2 × k max ),
where k max is the largest value of k for which a (k, ∆)-core exists. The number of span-cores is thus quadratic in |T |, which may be too large an output for human 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 spancore

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 experimentally, 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 spancores 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 (Section 5) is whether one can exploit the maximality condition to develop faster algorithms that can directly extract the maximal ones, without computing all the span-cores.

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 2,[1,2] 3,[1,2] 1,[1,2] 2,[1,1] 3,[1,1] 1,[1,1] 2,[0,1] 3,[0,1] 1,[0,1] 2,[0,0] 3,[0,0] 1,[0,0] 2,[2,2] 3,[2,2] 1,[2,2] 2,[2,3] 3,[2,3] 1,[2,3] 2,[3,3] 3,[3,3] 1,[3,3] 1,[0,3] 2,[1,3] 3,[1,3] 1,[1,3] 2,[0,2] 3,[0,2] 1,[0,2] 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 (

distinction between solid and dotted arrows is for visualization sake only).

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] on graph G ∆ for each temporal interval ∆ ⊑ T . Such a method has time complexity

O( ∆⊑T (|∆| × |E|)), i.e., O(|T | 2 × |E|).
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] Alvarez-Hamelin | Large scale networks fingerprinting and visualization using the k-core decomposition[END_REF][START_REF] Angel | Dense subgraph maintenance under streaming edge weight updates for real-time story identification[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] Alvarez-Hamelin | Large scale networks fingerprinting and visualization using the k-core decomposition[END_REF][START_REF] Angel | Dense subgraph maintenance under streaming edge weight updates for real-time story identification[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 6. The next straightforward corollary of Proposition 1 states that, not only [START_REF] Alvarez-Hamelin | Large scale networks fingerprinting and visualization using the k-core decomposition[END_REF][START_REF] Angel | Dense subgraph maintenance under streaming edge weight updates for real-time story identification[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 tem- poral 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,[1,2] : 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 start the core decomposition from

(C 1, ∆ + ∩ C 1, ∆ -), i.e.

, the smallest intersection of cores containing

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, ∆ 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 start the core decomposition, thus it has 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).

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] Epasto | Efficient densest subgraph computation in evolving graphs[END_REF][START_REF] Eppstein | Listing all maximal cliques in sparse graphs in near-optimal time[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 misses 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] 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], [START_REF] Angel | Dense subgraph maintenance under streaming edge weight updates for real-time story identification[END_REF][START_REF] Angel | Dense subgraph maintenance under streaming edge weight updates for real-time story identification[END_REF], and [START_REF] Bader | An automated method for finding molecular complexes in large protein interaction networks[END_REF][START_REF] Bader | An automated method for finding molecular complexes in large protein interaction networks[END_REF]. [START_REF] Alvarez-Hamelin | Large scale networks fingerprinting and visualization using the k-core decomposition[END_REF][START_REF] Angel | Dense subgraph maintenance under streaming edge weight updates for real-time story identification[END_REF] , and intersects C 1, [START_REF] Angel | Dense subgraph maintenance under streaming edge weight updates for real-time story identification[END_REF][START_REF] Angel | Dense subgraph maintenance under streaming edge weight updates for real-time story identification[END_REF] and C 1, [START_REF] Bader | An automated method for finding molecular complexes in large protein interaction networks[END_REF][START_REF] Bader | An automated method for finding molecular complexes in large protein interaction networks[END_REF] to initialize C 1, [START_REF] Angel | Dense subgraph maintenance under streaming edge weight updates for real-time story identification[END_REF][START_REF] Bader | An automated method for finding molecular complexes in large protein interaction networks[END_REF] . Then, it continues with the intervals of size 3: it intersects C 1,[0,1] and C 1, [START_REF] Alvarez-Hamelin | Large scale networks fingerprinting and visualization using the k-core decomposition[END_REF][START_REF] Angel | Dense subgraph maintenance under streaming edge weight updates for real-time story identification[END_REF] to initialize C 1,[0,2] and so on.

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,
The next theorem formally shows soundness and completeness of our Span-cores algorithm. Theorem 1. Algorithm 1 is sound and complete for Problem 1.

Proof. 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] Alvarez-Hamelin | Large scale networks fingerprinting and visualization using the k-core decomposition[END_REF][START_REF] Angel | Dense subgraph maintenance under streaming edge weight updates for real-time story identification[END_REF] in Figure 1: we know that it is a subset of C 2, [START_REF] Alvarez-Hamelin | Large scale networks fingerprinting and visualization using the k-core decomposition[END_REF][START_REF] Angel | Dense subgraph maintenance under streaming edge weight updates for real-time story identification[END_REF] ("vertical" ) and of 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] and C 3, [START_REF] Angel | Dense subgraph maintenance under streaming edge weight updates for real-time story identification[END_REF][START_REF] Angel | Dense subgraph maintenance under streaming edge weight updates for real-time story identification[END_REF] ("horizontal" ). One could consider intersecting all these three span-cores before computing C 3, [START_REF] Alvarez-Hamelin | Large scale networks fingerprinting and visualization using the k-core decomposition[END_REF][START_REF] Angel | Dense subgraph maintenance under streaming edge weight updates for real-time story identification[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 6.

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 span-core 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 efficient 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 non-empty 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 .
Proof. Every C k, ∆ ∈ C M is the innermost core of the nontemporal 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.

Proof. 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 G ∆ [ V ]. If k * > max{k ′ , k ′′ }, then C k * [G ∆ [ V ]]
is a maximal span-core; otherwise, no maximal span-core exists for ∆.

Proof. 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 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 l b ← {u ∈ V | d ∆ (V , u ) > lb } 10 E ∆ [V l b ] ← {(u, v ) ∈ E ∆ | u ∈ V l b , v ∈ V l b } 11 C ← innermost-core(V l b , E ∆ [V l b ]) 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 ′′ }
(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 "singleton-interval" 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.

Proof. 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 span-core, 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 6, 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 spancore 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, . . . ,

EXPERIMENTS

In this section we present a performance comparison of our algorithms, as well as a characterization of span-cores extracted. Datasets. We use eight real-world datasets recording timestamped interactions between entities. 1 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 (in days), are reported in Table 1.

ProsperLoans represents the network of loans between the users of Prosper, a marketplace of loans between privates. Last.fm 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 is the communication network of the English Wikipedia. DBLP is the co-authorship network of the authors of scientific papers from the DBLP computer science bibliography. StackOverflow includes the answerto-question interactions on the stack exchange of the stackoverflow.com website. Wikipedia connects users of the Italian Wikipedia that co-edited a page during the same discrete timestamp. Finally, for both Amazon and Epinions, 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.12) and compiled by Cython. The experiments run on a machine equipped with Intel Xeon CPU at 2.1GHz and 64GB RAM. Reproducibility. Our code is available at goo.gl/4WmrPc.

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 numbers of span-cores and maximal span-cores of each dataset, in Table 2. In terms of execution time, Span-cores considerably outperforms Naïve-span-cores 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 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 ad the beginning of Section 5, based on running the Span-cores algorithm and filtering out the non-maximal spancores, which we refer to as Naïve-maximal-span-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 9.4 for the WikiTalk dataset. Except for the datasets Last.fm and Epinions, the difference in terms of number of processed vertices is between two and three orders of magnitude, proving 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. Characterization. We finally compare and characterize all spancores against maximal span-cores. At first, Table 2 shows that spancores are at least one order of magnitude more numerous than maximal span-cores for all datasets, with the maximum difference of two orders of magnitude for the Epinions 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 are shown as a function of the size of the span |∆|. For both datasets, the number of span-cores and maximal span-cores decreases with, on average, a constant gap of one and two orders of magnitude, respectively, since the number of intervals decreases as |∆| increases. On the other hand, the behavior of the average size is quite different between the two datasets. For the DBLP dataset, the average size of span-cores is much higher than the average size of maximal span-cores for low values of |∆|, then the difference decreases and vanishes at the end of domain where a maximal span-core of |∆| = 37 dominates all other span-cores of |∆| ≥ 20. Instead, for the Epinions dataset, the average size of all span-cores and maximal span-cores follows 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.

APPLICATIONS

In this section we illustrate applications of (maximal) span-cores in the analysis of face-to-face interaction networks. We use three datasets gathered by a proximity-sensing infrastructure with a resolution of 20 seconds. The first dataset, named PrimarySchool 2 , contains the contact events between 242 individuals (232 children and 10 teachers) in a primary school in Lyon, during two days [START_REF] Stehlé | High-resolution measurements of face-to-face contact patterns in a primary school[END_REF]. The HighSchool 2 dataset gives the interactions between students and teachers (327 individuals overall) of nine classes during five days in a high school in Marseilles [START_REF] Mastrandrea | Contact patterns in a high school: A comparison between data collected using wearable sensors, contact diaries and friendship surveys[END_REF]. Finally, the HongKong dataset describes the interactions of people in a primary school in Hong Kong for eleven consecutive days [START_REF] Sapienza | Detecting anomalies in time-varying networks using tensor decomposition[END_REF]. The school population consists of 709 children and 65 teachers divided into thirty classes. For all three datasets we use a window size of 5 minutes and discard span-cores of |∆| = 1, i.e., having span of 5 minutes, since they represent extremely short group interactions, not significant for our purposes. On these datasets we show three types of interesting temporal patterns, i.e., social activities of groups of students within a school day, mixing of gender and class, and length of social interactions in groups.

Temporal patterns

Temporal activity. We first show how span-cores a simple temporal analysis of social activities groups of people within a school The left side of Figure 4 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 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). This reshuffling preserves degree of each vertex in each timestamp and global activity (i.e., number of contacts per timestamp), but destroys correlations between edges of successive timestamps. In the right side of Figure 4 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 communities detected in the original datasets are completely lost after the reshuffling, where no temporal structure of the span-cores is observed. This proves that the temporal schema of span-core decomposition is not simply a consequence of the overall activity but that span-cores represent a concrete method to detect complex structures evolving in time. Mixing patterns. We now show analysis of mixing patterns of students with respect to gender and class. Such metadata is 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 5 reports the temporal evolution of gender and class purity during the first school day of the PrimarySchool dataset: at each timestamp t, the curves represent the average purities of the maximal span-cores spanning t. During lessons, when students are in their own classes, class purity has naturally very high values, very close to 1. 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 to interact with students of the same gender during breaks, in agreement with a previous study of the same dataset [START_REF] Stehlé | Gender homophily from spatial behavior in a primary school: A sociometric study[END_REF].

The right plot of Figure 5 shows the temporal evolution of gender and class purity with gender and class 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 over time.

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 6). 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, similar functional shapes are shown by the three datasets, 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] Mastrandrea | Contact patterns in a high school: A comparison between data collected using wearable sensors, contact diaries and friendship surveys[END_REF][START_REF] Stehlé | High-resolution measurements of face-to-face contact patterns in a primary school[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 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 contacts 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 an extremely simple procedure to detect anomalous contacts and intervals of the HongKong dataset that exploits maximal span-cores. The topmost plot of Figure 7 reports the number of contacts, i.e., 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 contacts per timestamp does not drop to zero because proximity sensors were left in each class, close to each other, at the end of the lessons. In order to automatically detect these steady activity patterns, 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 contacts. 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 , filter out the contacts having at least an anomalous endpoint at time t. Coherently to the distribution of the size of the span 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 7. The number of contacts during school days remains substantially unchanged, while the activity noticeably decreases in-between. Identifying as positives the contacts occurring when the school is closed and as negatives all the others (i.e., 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 contacts, also anomalous temporal intervals. We define a timestamp t ∈ T as anomalous if the ratio between the number of original contacts (top plot of Figure 7) and the number of filtered contacts (middle plot of Figure 7) 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 The number of contacts 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.

CONCLUSIONS

In this paper we introduced a notion of temporal core decomposition where each core is associated with its span, and developed efficient algorithms for computing all the span-cores, and only the maximal ones. In our future work we will exploit span-cores for the computation of related notions, such as community search or densest subgraph in temporal networks. We will also study the role of maximal span-cores with large ∆ in spreading processes on temporal networks. Furthermore, span-cores represent features that can be used for network finger-printing and classification, model validation, and could provide support for new ways of visualizing large-scale time-varying graphs.

Figure 2 :

 2 Figure2: Top plots: number of all span-cores and maximal spancores (y axis) as a function of the order k (x axis). Bottom plots: average size of all span-cores and maximal span-cores (y axis) as a function of the order k (x axis).

Figure 3 :

 3 Figure 3: Top plots: number of all span-cores and maximal spancores (y axis) as a function of the size of the temporal span |∆ | (x axis). Bottom plots: average size of all span-cores and maximal spancores (y axis) as a function of the size of the temporal span |∆ | (x axis).

  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. In both datasets, fluctuations of k and |∆| are observed along the day, which can be 2 Available at sociopatterns.org.

Figure 4 :

 4 Figure 4: 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 spancore decomposition detects time-evolving community structures in the original datasets (left plots) that completely disappears in the reshuffled datasets (right plots).

Figure 5 :

 5 Figure 5: 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 6 :

 6 Figure 6: 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.

Figure 7 :

 7 Figure 7: HongKong dataset: number of contacts (y axis) per timestamp (x axis) in the original data (top), after filtering anomalous contacts (middle), and after filtering anomalous contacts and intervals (bottom).

Figure 7 .

 7 Figure 7. The number of contacts 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.

Table 1 :

 1 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 )} t e ∈[t s ,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]. Temporal graphs used in the experiments. -(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.

	window

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

Table 2 :

 2 Evaluation of the proposed algorithms: number of output span-cores, time, memory, and number of processed vertices.

			# output	time	memory # processed
	dataset	method	span-cores	(s)	(GB)	vertices
	ProsperLoans	Naïve-span-cores Span-cores Naïve-maximal-span-cores Maximal-span-cores	4 273 293	101 46 48 8	2 2 2 2	55M 27M 27M 980k
	Last.fm	Naïve-span-cores Span-cores Naïve-maximal-span-cores Maximal-span-cores	126 819 1 670	707 199 202 57	0.5 0.5 0.5 0.5	2M 531k 531k 271k
	WikiTalk	Naïve-span-cores Span-cores Naïve-maximal-span-cores Maximal-span-cores	19 693 632	322 302 1 084 1 194 126	36 36 36 35	25B 555M 555M 2M
	DBLP	Naïve-span-cores Span-cores Naïve-maximal-span-cores Maximal-span-cores	6 135 268	10 506 278 292 116	11 11 11 11	1B 150M 150M 620k
	StackOverflow	Naïve-span-cores Span-cores Naïve-maximal-span-cores Maximal-span-cores	1 238 129	5 360 245 245 128	10 10 10 10	1B 127M 127M 3M
	Wikipedia	Naïve-span-cores Span-cores Naïve-maximal-span-cores Maximal-span-cores	125 191 2 147	17 155 522 537 201	4 4 4 4	1B 35M 35M 320k
	Amazon	Naïve-span-cores Span-cores Naïve-maximal-span-cores Maximal-span-cores	29 318 303	10 415 409 580 123	18 18 18 18	2B 247M 247M 688k
	Epinions	Naïve-span-cores Span-cores Naïve-maximal-span-cores Maximal-span-cores	63 111 320	699 186 201 154	4 4 4 5	39M 3M 3M 129k

All datasets are made available by the KONECT Project (http://konect.cc), except for StackOverflow which is part of the SNAP Repository (http://snap.stanford.edu).


Imane Idris

Thibault Tannoux

Fazia Derridj

Vincent Dorcet

Julien Boixel

Veronique Guerchais

Jean-François Soulé

Henri Doucet

Effective Modulation of 2,1,3-Benzothiadiazoles and 2,1,3-Benzoselenadiazoles Photoluminescence Properties by Pd-Catalyzed C-H Bond Arylations

A one step procedure towards 4-aryl-2,1,3-benzothiadiazoles, 4,7-diaryl-2,1,3-benzothiadiazoles and 4-aryl-2,1,3benzoselenadiazoles using palladium-catalyzed regioselective C-H bond arylations of 2,1,3-benzothiadiazole and 2,1,3benzoselenadiazole was developed. A donor-acceptor compound was also synthetized via two successive C-H bond arylations at C4 and C7 positions of the 2,1,3-benzothiadiazole unit. One of the major achivement of this methodoly refer from the fine modulation of the fluorescence wavelength with emission colors covering the blue to the red part of the visible spectrum by the simple introduction of the suitable aryl group on the 2,1,3-benzothiadiazole unit.

Introduction

Organic functional materials are finding more and more applications. Among them π-systems of polycyclic aromatic or heteroaromatic compounds such as 2,1,3-benzothiadiazole and 2,1,3-benzoselenadiazole are being actively investigated as cheap replacement of traditional inorganic semiconductors for the development of organic light-emitting diodes (OLED), 1 organic photovoltaics (OPV) 2 and bioprobes for bioimaging analyses.

3

These strong electron acceptor heterocycles represent a pivotal framework for the construction of organic donor-acceptor (D-A) dyes. 4 As example, in 2005, Ho and coworkers developed a new class of organics dyes (compound I) based on benzothiadiazole and benzoselenadiazole chromophores, which display a good power conversion efficiency (Figure 1, left). 5 Benzothiadiazoles are also used as acceptor units in donor acceptor (D-A) conjugated polymers, such as the polymer solar cell II (Figure 1, middle). Despite these wide applications of 4-aryl-substituted 2,1,3benzoselenadiazoles and 2,1,3-benzoselenadiazoles, their synthesis remains challenging and often requires multi-steps synthesis.

Protocols involving bromination followed by palladium catalyzed Suzuki, 7 Stille, 8 or Hiyama 7a, 9 crosscoupling reactions are the most commonly employed (Figure 2a). Negishi reactions using an organozinc reagent prepared from benzofurazan through a magnesiation with bis (2,2,6,6-tetramethylpiperidin-1-yl)magnesium-lithium chloride complex (TMP 2 Mg•2LiCl) followed by transmetalation with zinc chloride, have also been reported (Figure 2b). Since the discovery by Nakamura 11 and Otha 12 of the Pd-catalyzed C-H bond arylation of heteroarenes using aryl halides, this methodology has emerged as one of the most reliable for the eco-friendly formation of C-C bonds for the access to a wide variety of arylated heterocycles. 13 In 2013, Marder and coworkers reported the first example of C-H bond activation of 5,6-difluoro-2,1,3-benzothiadiazole using 10 mol% Pd(OAc) 2 associated to 20 mol% di-tert-butyl(methyl)phosphonium tetrafluoroborate (Figure 2c). 14 However, 2,1,3benzothiadiazole was not reactive under these reactions conditions, demonstrating the huge impact of fluorine atom in Pd-catalyzed C-H arylations via concerted-metalation deprotonation pathway. 15 This C-H bond protocol was then applied in polymerization using dibromobenzene derivatives, 16 and for the synthesis of organic dyes containing electron-rich (donor) and electron-poor (acceptor) sections. 17 An example of direct arylation at C4 position of 5-fluoro-2,1,3benzothiadiazole has also been reported.

18

Latter, Marder and co-workers extended the substrate scope to other electron deficient 2,1,3-benzoselenadiazoles such as 5,6dicyano-and 5,6-dinitro-substituted ones (Figure 2d). 19 To our knowledge there is no report on direct arylation, via a metalcatalyzed C-H bond activation, of unsubstituted 2,1,3benzothiadiazole and 2,1,3-benzoselenadiazoles. Recently, we disclosed that phosphine-free palladium acetate catalyzes the C-H bond arylation of benzofurazan (Figure 2e). 20 Therefore, we decided to investigate the reactivity of unsubstituted 2,1,3benzothiadiazole and 2,1,3-benzoselenadiazole in palladium-

ARTICLE

catalyzed C-H bond arylation for the straightforward access to 4-arylated 2,1,3-benzothiadiazoles and 2,1,3benzoselenadiazoles (Figure 2e).

Results and Discussion

Based on our recent results on palladium-catalyzed direct arylation of benzofurazan using aryl bromides as aryl source, 20 we examined the reactivity of 2,1,3-benzothiadiazole (Table 1). Using our previously reported reaction conditions, namely 1 mol% Pd(OAc) 2 in the presence of KOAc in DMA at 120 ºC, no reaction occurred between 2,1,3-benzothiadiazole and 4bromobenzonitrile (Table 1, entry 1). Using a higher reaction temperature (i.e. 150 ºC), arylated 2,1,3-benzothiadiazole 1, resulting from C-H bond activation at the C4 position, was obtained in 52% yield (Table 1, entry 2). When the reaction was performed in the presence of K 2 CO 3 as base, no reaction occurred; while the used of potassium pivalate (PivOK) and potassium adamantane-1-carboxylate (AdCO 2 K) allowed the formation of 1 in 84% and 65% yields, respectively. Other palladium sources were evaluated (Table 1, entries 6-8). PdCl 2 displayed a similar reactivity than Pd(OAc) 2 , as the arylated product 1 was isolated in 82% yield (Table 1, entry 6). Palladium dimer complex [Pd(C 3 H 5 )Cl] 2 gave a slightly lower yield in 1 of 72% (Table 1,entry 7). A diphosphine palladium catalysts such as PdCl(C 3 H 5 )(dppb) did not allow to increase the yield compared to phosphine-free procedure (Table 1,entry 8). With the best conditions in hands, namely 1 mol% phosphinefree Pd(OAc) 2 associated to PivOK as base in DMA at 150 ºC, we payed close attention to the scope of the reaction (Scheme 1). First, we examined the reactivity of para-substituted aryl bromides.

Electron-deficient 4-bromonitrobenzene, 4bromobenzaldehyde, ethyl 4-bromobenzoate, 4bromopropiophenone and 4-bromobenzophenone reacted nicely to deliver the 4-arylated 2,1,3-benzothiadiazoles 2-6 in 65-74% yields. 1-Bromo-4-chlorobenzene displayed a lower reactivity, as the desired product 7 was isolated in only 55% yield, due to the formation of a side product arising from the homocoupling of this aryl bromide. It should be noted that under these reaction conditions, the C-Cl bond did not react. Bromobenzene, 1-bromo-4-(tert-butyl)benzene and 4bromoanisole have been successfully employed using this phosphine-free palladium coupling to give 8-10 in 60%-65% yields. A meta-substituent on the aryl bromide had almost no effect, as the desired arylated products 11-14 were obtained in good yields from 3-bromobenzonitrile, 1-bromo-3-(trifluoromethyl)benzene, 3-bromonitrobenzene, and 1bromo-3-chlorobenzene.

The reaction was almost not sensitive to the steric hindrance, as ortho-substituted aryl bromides such as 2-bromobenzonitrile, and 2bromobenzaldehyde afforded the desired products 15 and 16 in good yields. 1,3-Benzodioxol motif has been introduced on the 2,1,3-benzothiadiazole 17, which was isolated in 45% yield from 2,1,3-benzothiadiazole and 5-bromo-1,3-benzodioxole. Then, in order to show the potential of this method for the preparation of organic materials, we employed some  -extended aryl bromides as coupling partners.

2-Bromonaphthalene was efficiently coupled with 2,1,3benzothiadiazole affording 18 in 60% yield. Its X-ray diffraction analysis confirmed the structure. Using this methodology, we also carried out the straightforward synthesis of an unsymmetrical 4,7-diaryl-2,1,3benzothiadiazole via two successive Pd-catalyzed C-H bond arylations (Scheme 3). Starting from 17, a second arylation using 1-bromo-3,5-bis(trifluoromethyl)benzene afforded the 4,7-unsymmetrical diaryl 2,1,3-benzothiadiazole 28 in 38% yield, which should display push-pool properties. Syntheses of selenium containing compounds and the further utilization of these compounds in organic synthesis for the preparation of organic materials attracted less attention.

22

While a wide variety of thiadiazole containing compounds are known, on the contrary, a limited number of selenadiazoles containing compounds have been prepared. 23 Therefore, we turned our attention to the reactivity of 2,1,3benzoselenadiazole in Pd-catalyzed C-H bond arylation (Scheme 4). For these reactions, we employed the same reaction conditions than for direct arylation of 2,1,3benzothiadaziole, namely, 1 mol% Pd(OAc) 2 associated with PivOK as base in DMA at 150 ºC. Using 4-bromobenzonitrile, 1bromo-4-(tert-butyl)benzene and 1-bromo-3,5bis(trifluoromethyl)benzene, we successfully prepared the 4aryl-2,1,3-benzoselenadiazoles 28-30 in 52-57% yields. The regioselectivity of the arylation of 2,1,3-benzoselenadiazole was confirmed by X-ray diffraction analysis of 30. [21] It should be noted that the reactions with 2,1,3-benzoselenadiazole are more sluggish than the reactions with 2,1,3-benzothiadiazole giving some unidentified decomposition products, which might explain that arylated products are obtained in lower yields. Finally, in order to determine the interest of these new compounds as chromophores, preliminary photophysical studies have been conducted. UV-visible absorption spectra of the mono-substituted 9, 17, 19, 20 and the di-substituted 24, 26, 27 2,1,3-benzothiadiazoles, and the benzoselenadiazole derivative 29 were recorded in dichloromethane solution at room temperature, (see Figures 3 and4) and the corresponding data are summarized in Table 2. As common feature for all the investigated compounds, their electronic absorption spectra exhibit characteristic set of absorption bands for benzothiadiazole and benzoselenadiazole derivatives, with intense and well-resolved absorption bands in the UV region, from 250 to 350 nm, together with a moderately intense and broad absorption band tailing up in the visible region of the spectrum. The mono-substituted 2,1,3-benzothiadiazole 9, bearing a tert-butyl group on the aryl substituent is considered as a reference compound for the studied series. 24 The absorption spectrum of 9 shows, in the UV region, a broad band centered at 250 nm and well-resolved bands from 280 to 325 nm, while at lower energy a weaker and broad band which tails up to 420 nm is observed (Figure 3). According to previous studies, the UV absorption bands of 9 arises from 1 (π-π*) transitions of the p-tert-butylphenyl substituent and the benzothiadiazole core, respectively.

24c At lower energy, from 325 to 420 nm, the broad absorption band is assigned to charge transfer transition (CT) from the electrondonating aryl substituent to the π* accepting benzothiadiazole moiety. 24c Replacing the p-tert-butylaryl substituent by the benzodioxole in 17, red-shifts the CT transition of 50 nm, as a result of larger electron-donating properties of the dioxole group. In comparison with 9, the fluorene-based 2,1,3benzothiadiazole 19 exhibits higher absorptivity within the whole spectrum, due to additional 1 (π-π*) transitions of this πextended system but with no significant shift of the absorption bands. Similarly, replacing the fluorenyl ( 19) by a pyrenyl group (20), gives rise to very intense absorption bands in the UV region, the absorption profile of the benzothiadiazole core being overlapped by the intense and well-resolved absorption bands of the pyrene moiety. The pyrene moiety in 20 induces a small red-shifted of the CT band (∆λ = 15 nm), compared with the fluorene substituent in 19. Based on previous experimental and theoretical studies of benzothiadiazole derivatives, the observed spectral changes by incorporation of various aromatic substituents can be interpreted as a modification of the highest-occupied molecular orbital (HOMO) while the lowest-unoccupied molecular orbital (LUMO), centered on the core, stays almost unchanged. 24c In other words, increasing the electron-richness ( 17) and/or extension of the π-system (19, 20) destabilize the HOMO energy level resulting in a decrease of the HOMO-LUMO gap with respect to 9. As far as the di-substituted 2,1,3benzothiadiazoles are concerned, compounds 24 bearing two p-chlorophenyl and 26 having with two 3,5bis(trifluoromethyl)aryl groups, exhibit similar absorption profiles with a blue-shift of the charge-transfer band in 24, compare to 26, attributed to the strong electron-withdrawing CF 3 groups (Figure 4). As expected, the compound 27 shows the lowest-energy CT band centered at 400 nm, due to the presence of both electron-donating dioxole substituent and electron-accepting (CF 3 ) 2-Ar) and benzothiadiazole groups, which give rise to strong charge-transfer transitions.

Absorption

Emission at 298 K a λabs a /nm (ε 10 Interestingly, the seleno-derivative 29 displays similar absorption profile than its sulfur analogue 9, with absorption bands corresponding to 1 (π-π*) transitions on the tertbutylphenyl substituent of the benzoselenodiazole core and at lower-energy, a moderately intense band arising from the charge-transfer transition (Figure 3). Notably, compared with 9 the seleno-derivative 29 exhibits a large red-shift of the absorption bands belonging to the benzoselenodiazole core and a moderately bathochromic effect of the CT transitions, a feature in agreement with previous reports on related benzoselenodiazole compounds. The emission spectra of 9, 17, 19, 20, 24, 26, 27 and 29 are shown in Figure 5 and the emission data are compiled in Table 2. Except compound 20, all investigated compounds are strongly emissive in dichloromethane solution at room temperature. Remarkably, they exhibit good to excellent photoluminescence quantum yield (Φ) in solution as high as 90 % ( 19), whatever the nature of the substituent. Interestingly, the emission color goes from the blue (λ em = 449 nm for 26) to the red (λ em = 555 nm for 27) part of the spectrum, strongly depending on the nature of the incorporated aryl group on the benzothiadiazole core. The emission wavelength is fine-tuned by changing the electronic richness of the system and/or by introducing an extended π-system (fluorene, pyrene), as well as by replacing the sulfur atom by Se (9 vs. 29). The emission can be controlled by the CT transitions. For instance, the multi-polar derivative 27 displays the more red-shifted emission, consistently with CT absorption bands at lowerenergy. However, this red-shifted fluorescence is accompanied with a decrease of the photoluminescence quantum yield (Φ = 19 %), in agreement with the energy gap law. Compounds 9 and 26 display a blue emission, while 17 and 19 bearing an electron donating aryl or a fluorenyl group, respectively, emit in the orange-red region of the spectrum. The benzoselenodiazole 29 displays luminescence with a maximum at 503 nm, red-shifted by about 35 nm with respect to the analogue 9, a feature comparable to that reported for related benzoselenodiazole compounds. Note that compound 20 is non-emissive in fluid solution. This behavior can be explained by the presence of the pyrenyl group since pyrenes are known to be subject to self-quenching through the formation of aggregates or excimers in solution.

Interestingly, the luminescence of 20 can be turned-on in the solid state. The solid-state fluorescence, measured on a drop casted film at 298 K (from dichloromethane solution), is characterized by a broad emission band centered at 530 nm, likely originated from the excimer state (Figure 6).

ARTICLE

Conclusions

In summary, 2,1,3-benzothiadiazole and 2,1,3benzoselenadiazole can be efficiently arylated at C4/C7 positions via palladium catalyzed C-H bond activation. Simple phosphine-free palladium acetate associated to KOAc as base in DMA was found to be the best reaction conditions. A wide range of functions such as methoxy, chloro, formyl, propionyl, benzoyl, ester, nitrile, trifluoromethyl or nitro on the aryl bromide is tolerated. Some sterically hindered, π-extended and heteroaromatic aryl bromides have also been employed successfully, demonstrating the potential of this methodology for the preparation of organic materials. Interestingly, this method allows the introduction of aryl substituents with different electronic properties in one step resulting in a fine modulation of the fluorescence wavelength with emission colors covering the blue to the red part of the visible spectrum. The combination of these photophysical effects make such materials especially interesting for photovoltaic and OLED applications.

6 Figure 1 .

 61 Figure 1. Examples of Useful Molecules Containing 4-Aryl-Benzothiadiazole or 4-Aryl-Benzoselenadiazole Units.

10

 10

Figure 2 .

 2 Figure 2. Previous Strategies to Synthetize 4-Aryl 2,1,3-Benzothiadiazoles and 2,1,3-Benzoselenadiazoles

21 3 -Scheme 2 .

 32 Scheme 1. Scope of Aryl Bromides in Palladium-Catalyzed Direct C4 Arylation of 2,1,3-Benzothiadiazole

Scheme 3 .

 3 Scheme 3. Example of Synthesis of a "Push-Pull" 4,7-Unsymmetrical Diaryl 2,1,3benzothiadiazole by Iterative Palladium-Catalyzed C-H Bond Arylations

Scheme 4 .

 4 Scheme 4. Scope of Aryl Bromides in Palladium-Catalyzed Direct C4 Arylation of 2,1,3-Benzoselenadiazole

Figure 3 .

 3 Figure 3. Absorption Spectra in CH2Cl2 at 298 K (C ≈ 10 -5 M) of the Mono-Substituted Compounds 9 (red line), 17 (blue line), 19 (green line), 20 (black line) and 29 (red dotted line).

Figure 4 .

 4 Figure 4. Absorption Spectra in CH2Cl2 at 298 K (C ≈ 10 -5 M) of the Di-Substituted Compounds 24 (blue line), 26 (black line) and 27 (red line).

Figure 5 .

 5 Photograph of 2,1,3-Benzothiadiazole Derivatives in CH2Cl2 Solution under 350 nm Irradiation

26 Figure 6 .

 266 Figure 6. Emission Spectrum of 20 in a Drop Cast Film from CH2Cl2 solution, with λex = 350 nm.

Table 1 .

 1 Optimization of the Reaction Conditions

	Entry	[Pd]	Base	T (ºC)	Yield in 1
					(%) [a]
	1	Pd(OAc)2	KOAc	120	0
	2	Pd(OAc)2	KOAc	150	52
	3	Pd(OAc)2	K2CO3	150	0
	4	Pd(OAc)2	PivOK	150	84
	5	Pd(OAc)2	AdCO2K	150	65
	6	PdCl2	PivOK	150	82
	7	[Pd(C3H5)Cl]2	PivOK	150	77
	8	PdCl(C3H5)(dppb)	PivOK	150	76

[a] isolated yield

Table 2 .

 2 Photophysical Data of the Investigated Compounds.

  3 /M -1 cm -1 )

			λem a /nm	φa,b
	9	306 (5.8), 316 (7.0), 358	468	0.88
		(3.0)
	17	266 (7.2), 308 (6.1), 318	530	0.79
		(5.7),376 (2.3)
	19	284 (19.4), 306 (18.2),	510	0.90
		316 (15.7),376 (7.5)
	20	268 (24.7), 378 (39.0),	530 d	nd
		316 (24.8), 326 (28.4),
		344 (36.9), 382 (6.3)
	24	270 (11.7), 320 (3.3), 384	492	0.53
		(1.9)
	26	272 (18.1), 312 (10.8),	449	0.89
		320 (9.8), 362 (10.8)
	27	291 (5.9), 318 (3.4), 400	555	0.19
		(3.4)
	29	250 (6.6), 333 (6.3), 383	503	0.42
		(1.9)

a Measured in CH2Cl2 solution at 298 K (C ≈ 10 -5 M), with 350 nm excitation. b ref : Ru(bpy)3Cl2.

c

Measured in a drop casted film, from CH2Cl2 solution, λex = 350 nm.

23b, 25

Acknowledgements

We thank the Algerian "Ministry of Higher Education and Scientific Research" for a fellowship to I.I. We thank CNRS and "Rennes Metropole" for providing financial support.

Notes and references

Conflicts of interest

There are no conflicts to declare.