Nawal Ould-Amer
email: nawal.ould-amer@imag.fr

Philippe Mulhem
email: philippe.mulhem@imag.fr

Mathias Géry
email: mathias.gery@univ-st-etienne.fr

LIG at CLEF 2015 SBS Lab

Keywords: Fusion of scores, user profile, social links

This paper describes the work achieved by the MRIM research group of Grenoble, using some data from the LaHC of Saint-Étienne, in a way to test personalized retrieval of books for the Social Book Search Lab of CLEF 2015. Our proposal rely on a biased fusion of content-only retrieval, using BM25F and LGD retrieval models, user non-social profile based on the catalog of the requester, and social profiles using user/user links generated from their catalogs and ratings on books. The official results obtained show a clear positive impact of user profile, and a small positive impact of the social elements we used. Post official results that present non biased fusion scores are also presented.

Introduction

This paper describes our participation to INEX Social Book Search Suggestion Track challenge. The goal of this challenge is to evaluate approaches for supporting users in searching collections of books based on book metadata and associated user-generated content [START_REF] Koolen | Overview of the INEX 2014 social book search track[END_REF]. The work described here focuses on several aspects of personalized information retrieval that integrates social networks information. Our objectives during the participation was twofold: a) to rely as much as possible on Information Retrieval Systems to handle non-social and social profiles, and b) to provide a simple integration of the three elements (i.e., content, non-social profiles, social profiles) according to linear combination of scores. Relying heavily on existing tested IR tools allows us to focus on experimenting ideas. Proposing simple score fusions allows us to analyze more easily how configurations behave. More precisely, our experiments conducted for SBS 2015 emphasizes on:

-Studying the impact of linear fusions of score compared to classical weighted linear fusions; -Studying the impact of fusing several content-only results;

-Studying the impact of using a simple user profile as query extension (nonsocial profile); -Studying the impact of generated friend relations on the quality of the results (social profile).

From the data provided by the SBS 2015 dataset, the following elements were used at one time or another:

the fields title, summary, content and tags from the documents: all concatenated for unstructured retrieval, and separated for field-based retrieval using BM25F; the fields title, mediated query and narrative from the topics; the documents and ratings from the "topic users" (a topic user is the description of the user that asks a query): used to compute "friendship" relationships between users; the documents and ratings from the profiles of the non-topics users: used to compute "friendship" relationships between users.

The IR processes were achieved on the Terrier system3 [START_REF] Ounis | Terrier: A High Performance and Scalable Information Retrieval Platform[END_REF].

The section 2 focuses on the description of the fusion that was exploited: one original point relates to the biases that we propose. Section 3 tackles multiple content-only matching for the documents, as we found out that such integration is beneficial. Then, we introduce in section 4 the use of non-social profiles, and we detail how we defined friendship relations between users, using their catalogs and ratings, as well a the way we used the profiles of such friends when processing queries. Additional processing must be achieved on SBS data to get results. We discuss in section 5 some of these elements before depicting in section 6 the official, as well as some non-official, results obtained, before concluding in section 7.

Biased linear fusions of scores

Fusing scores of several IR systems is nontrivial problem. In our case, as described in the introduction, we propose to use biased linear fusions of scores, as an extension of the "Zero-one" normalization used by Wu, Crestani and Bi in [START_REF] Wu | Evaluating score normalization methods in data fusion[END_REF].

Let us focus on a fusion of two results lists L 1 and L 2 , composed of couples (doc,rsv). To be realistic, L 1 and L 2 are limited to the top n results. Assume that a document d has a score value of score(d, L i ) in L i , with i ∈ {1, 2}, and d is at rank rank(d, L i ) in L i ; that b i is the bias of L i ; and that h i is the horizon (a rank position) above which we do not look at the in results list L i . The normalized score of d in L i is then:

f (d, L i ) = (1 -vmax(Li)-score(d,Li) vmax(Li)-vmin(Li) ) + b i if rank(d, L i ) ≤ h i 0 otherwise
with vmin and vmax the minimal and maximal value of scores in a result list.

Compared to the fitting used by [START_REF] Wu | Evaluating score normalization methods in data fusion[END_REF], our idea is that we allow different search results to fit into different intervals. This is independent of the way different result lists are combined, but a kind of "boosts" that forces the final score values for a result list to be in {0} ∪ [b i , b i + 1] (the value 0 denotes that the document does not occur in the top h i elements of the list). This boost is independent from the way the scores are fused afterward. If we make a parallel with the general fitting proposed by [START_REF] Wu | Evaluating score normalization methods in data fusion[END_REF], our proposal allows an independent scaling for each list fused.

Then, the overall fusion computes a weighted average of the normalized scores (COMB-sum from [START_REF] Shaw | Combination of multiple searches[END_REF]) using a parameter α that denotes the relative importance of L 1 over L 2 , and rerank the results according to the new fused scores. Compared to a usual weighted average, the difference here comes mainly from the b i . Assigning 0 to all b i s leads to a usual weighted average COMB-sum.

We discuss the impact of such biases in the section dedicated to the experiments.

Fusion of content-only scores (run LIG 1)

On experiments conducted over the SBS 2014 dataset, we noticed that fusing several content-only runs had a positive impact with a relative nDCG@10 improvement larger than 10%. That is why we propose to fuse one result coming from BM25F [START_REF] Robertson | The probabilistic relevance framework: BM25 and beyond[END_REF] run (parameters values taken from [START_REF] Hafsi | LaHC at INEX 2014: Social book search track[END_REF]) and one result coming from a Log logistic model [START_REF] Clinchant | A Log-Logistic Model for Information Retrieval[END_REF]. Grid optimization of parameters on SBS 2014 data led to the parameters used for the official run tagged LIG 1, described in table 1. The fusion score is computed as follows:

RSV LIG 1 (Q, d) = α BM 25F (Score BM 25F (Q, d) + b BM 25F ) + α LGD (Score LGD (Q, d) + b LGD ) (1)
where α BM 25F and α LGD are the relative importance of BM25 scores and LGD score respectively, b BM 25F and b LGD are bias of each results list. The normalized scores use an horizon h at 1000 documents. What we depict here as "non-social" corresponds to the individual user data. In our case, these data refer to the catalog of the user. We assume that Cat u denotes the catalog (list of books) of a given user u (from the corpus U of users). To construct a user profile, we take inspiration from Cai and Li who consider each user profile as a vector of tags and use a L 1 normalized term frequency (NTF) to denote the preference degree of user on a tag [START_REF] Cai | Personalized search by tag-based user profile and resource profile in collaborative tagging systems[END_REF]. Similarly, we describe the profile P rof u of a user u as a weighted vector based on Cat u , where each term is weighted by its NTF. In a way to keep only the major interests of a user, we consider only the top n terms according to their values. In our runs, we keep the top n = 100 terms in a profile. Such profile is used as an expansion of initial query. In a way to reflect the relative importance of a term in a profile, we define a function Exp(Q, u) that expands the query by a fixed number of terms, and the relative importance of each term in the profile is reflected as corresponding number of occurrences of this term in the expanded query. For instance, if the value corresponding to the term t in a user profile accounts for 40% of the occurrences of terms in the profile, and suppose that we fix the number of terms added in the query to 100, then the query will be expanded by 0.4 * 100 = 40 occurrences of the term t. Then a BM25 retrieval is achieved on the documents corpus.

We noticed in SBS 2014 data that such expansion does not provides good results, but that the fusion of the results of such expanded queries and the usual content-only queries lead to better results. That is why we experimented such fusion with the parameters defined in table 2, where N SP rof denotes the parameters related to the non social profile fusion. The overall score for LIG 2 is:

RSV LIG 2 (Q, d, u) = α BM 25F (Score BM 25F (Q, d) + b BM 25F ) + α LGD (Score LGD (Q, d) + b LGD ) + α N SP rof (Score BM 25 (Exp(Q, u), d) + b N SP rof ) (2)
where α BM 25F , α LGD , α N SP rof are the relative importance of BM25 result list, LGD results list, the non social profil list respectively. Also, b BM 25F , b LGD , b N SP rof are the respective bias of each results list. Moreover, the normalized scores use a horizon h of 1000, as presented in the table 2.

Friendship link generation

For the social user profile, we choose to generate "friendship" links between topic users and the non-topic users provided by SBS. To achieve that, we assume that what makes (topic or non-topic) users similar to others is their catalog and the ratings they provide. We represent then all the non-topics users as a text document corresponding to concatenation of the document ids from the user catalog. We include the ratings (integer values) by using the ratings as the tf values for the number of occurrences of the documents ids.

To be able to find the non-topic users similar to topic users, we describe the users topics in the same way as the non-topic users as described above. Then we used the topic-users descriptions as queries on the corpus of non-topic users using a classical BM25 matching. For first experimentation, we filter the relationships to the top 2 most similar non-topic users for each topic user, and we plan to experiment the top k similar users in future works.

Usage of "friends"

Once 2 closer friends of a topic user are obtained, we apply a process similar to section 4 to generate the non-social profiles of the friends, and then we match the topic query with the friends profiles to get documents that match the query. The matching is computed as follows:

RSV LIG 3 (Q, d, u) = α BM 25F (Score BM 25F (Q, d) + b BM 25F ) + α LGD (Score LGD (Q, d) + b LGD ) + α N SP rof (Score P rof il (Q, d, u) + b N SP rof ) + α F ri1 (Score BM 25 (Exp(Q, F ri1), d) + b F ri1 ) + α F ri2 (Score BM 25 (Exp(Q, F ri2), d) + b F ri2 ) (3)
The fusion parameters used for the officially submitted run LIG 3 are given in table 3, with F ri1 and F ri2 the two friends of u. One important point to notice is that the post processing of the obtained results have a dramatic impact on the results. For instance, as the initial corpus ids (isbn) are not the ones on which the results are evaluated (LibraryThing ids), and because of potential duplicates generated, it is not obvious to handle the translation. Our approach for such duplicate removal was the same that is provided by the organizers of SBS. Additionally, for our runs for SBS 2015, we focused on integrating the users examples to post-process the queries. Our idea was that a user might be interested if he finds as answers documents that he read and that he appreciated, as this would be an indicator that the system is providing relevant documents to him. We declined this hypothesis in two ways:

Reranking: Achieve a reranking where the documents a user likes are boosted, and the documents he dislikes are removed for the result. After a "Zero-one" score normalization [START_REF] Wu | Evaluating score normalization methods in data fusion[END_REF] between 0 and 1 of the overall score, we add 1 for the documents that the user likes and set the score to 0 for the documents that he dislikes. This process is then a post-processing that is run after the fusion, and is the result of our official run LIG 4. It is worth noting that, if several retrieved documents are liked by the user, their relative initial ranking is preserved;

Relevance Feedback: Define a relevance feedback, positive for the documents that the topic user likes, and negative for the documents he does not like.

We achieved such relevance feedback on the Log logistic run LGD for our official run LIG 5, and also on both content-runs, i.e., BM25F and Log logistic, for our official run LIG 6. The relevance feedback uses all the positive documents and selects the top 10 terms according to the default selection of Terrier [START_REF] Ounis | Terrier: A High Performance and Scalable Information Retrieval Platform[END_REF].

Results

We present here two elements. First, we list the official results obtained for our 6 runs officially submitted to SBS 2015. Second, we discuss additional results generated after the release of the SBS 2015 qrels, presenting the impact of the "biases" we used (see section 2) over "unbiased" results.

Official Results

We comment here mainly the lines of table 4 corresponding to boldfaced run ids that use nor reranking neither relevance feedback. We notice then that the impact of the user non-social profile is clearly beneficial, however the p-value of a bilateral paired Student t-test on LIG 1 versus LIG 2 equal 5.45%, thus with a significance threshold of 5% this difference is not statistically significant. Such value is even larger between LIG 1 and LIG 3. We notice a slight improvement of nDCG@10 results when integrating the 2 best "friends", however our generation or usage of relationships between users does not seem to be effective enough.

According to what we defined for our fusion (see section 2), we also notice that the weights assigned to the friends are very small, 0.05. With higher relative values the results degrade. So we conclude for now that our proposal does not outperform the integration of non-social user information. As we see on table 4, the results with reranking or relevance feedback lower the quality of the results, but these elements are related to our interpretation of the catalogs and examples that are incompatible with the interpretation of the SBS organizers. In fact, our interpretation was somewhat the exact contrary of what decided the SBS organizers (they choose that the catalog + examples must not be part of the result), this explains why these additional runs behave worse than our initial runs.

Impact of biases

We describe in table 5 the impact of using the biases as defined in section 2. To be fair compared to the official results, we choose to only remove the bias from the configurations used for the official runs and to compare the relative gain or loss (between parentheses) with respect to the biased respective runs from table 4. In this table, the values use 3 digit precision numbers, where the percentages are computed on 4 digit precision numbers. We notice that the effect of the bias are positive for all the measures for the runs LIG 2 and LIG 3, and have almost no effect of the content only LIG 1 run. So, the effect of the biases seem to be more positive as we fuse many lists.

Conclusion

We presented in this paper the experiments that were conducted for the participation of LIG to the SBS 2015 lab evaluation. Our main finding, according to our integration of non-social and social profiles, is that the use of non-social profile has a clear positive impact on the quality of the retrieval, where the integration of generated friendship relationships does not really increase the quality of the system provided. One important conclusion that we draw from the SBS experiments is that the post processing of results has a dramatic impact on the quality of the results, and then must be carefully studied.

The experiments reported here depict our first steps to grasp the complexity of personalized information retrieval in social context, and many efforts will focus on refining and characterizing the numerous elements involved in such retrieval process.

Table 1 .

 1 Parameters for the content-only run LIG 1

		α	b	h
	BM 25F	0.4	0.5	1000
	LGD	0.6	0.4	1000

Table 2 .

 2 Parameters for the content + non social profile run LIG 2

		α	b	h
	BM 25F	0.4	0.5	1000
	LGD	0.5	0.5	1000
	N SP rof	0.1	0.5	1000

Table 3 .

 3 Parameters for the content + Non Social profile + Friends profiles run LIG 3

		α	b	h
	BM 25F	0.35	0.5	1000
	LGD	0.45	0.5	1000
	N SP rof	0.1	0.6	1000
	F ri1	0.05	0.6	1000
	F ri2	0.05	0.5	1000

Table 4 .

 4 Official results for the 6 LIG runs

	Rank	Run	nDCG@10 MRR	MAP R@1000 Profiles
	6	LIG 3	0.098	0.189	0.069	0.514	yes
	7	LIG 2	0.096	0.185	0.069	0.514	no
	8	LIG 4	0.095	0.181	0.068	0.514	yes
	13	LIG 5	0.093	0.179	0.067	0.515	yes
	14	LIG 6	0.092	0.174	0.067	0.513	yes
	15	LIG 1	0.090	0.173	0.063	0.508	no

Table 5 .

 5 Unofficial results without bias

	Run	nDCG@10	MRR	MAP	R@1000
	LIG 1 no bias	0.090 (0.0 %) 0.173 (-1,2 %) 0.063 (0.0 %) 0.507 (-0.1 %)
	LIG 2 no bias	0.096 (-0.8 %) 0.182 (-1.6 %) 0.068 (-1.0 %) 0.513 (-0.2 %)
	LIG 3 no bias	0.097 (-0.7 %) 0.181 (-4.2 %) 0.068 (-3.0 %) 0.508 (-1.2 %)

Terrier: http://www.terrier.org

Acknowledgment

This work is supported by Région Rhône-Alpes through the ReSPIr project.


Clémence Magnien

Fabien Tarissan

Time Evolution of the Importance of Nodes in dynamic Networks

Keywords: centrality, network dynamics, temporal paths, node importance

For a long time now, researchers have worked on defining different metrics able to characterize the importance of nodes in networks. Among them, centrality measures have proved to be pertinent as they relate the position of a node in the structure to its ability to diffuse an information efficiently. The case of dynamic networks, in which nodes and links appear and disappear over time, led the community to propose extensions of those classical measures. Yet, they do not investigate the fact that the network structure evolves and that node importance may evolve accordingly. In the present paper, we propose temporal extensions of notions of centrality, which take into account the paths existing at any given time, in order to study the time evolution of nodes' importance in dynamic networks. We apply this to two datasets and show that the importance of nodes does indeed vary greatly with time. We also show that in some cases it might be meaningless to try to identify nodes that are consistently important over time, thus strengthening the interest of temporal extensions of centrality measures.

I. INTRODUCTION

Scientists studying complex networks have been interested for a long time in the question of evaluating the importance of a node. This has lead to the introduction of several measures of importance, such as for instance degree, closeness or betweenness centrality, Katz centrality, or PageRank.

Most centrality measures are based on the study of paths in the network: a node will be important for instance if the paths from it to other nodes are short, or if it lies on shortest paths between many pairs of nodes. One motivation for this is that links can act as a dissemination medium for some phenomena occurring on the network. For instance individuals can exchange information when they communicate, or a message can be forwarded from computer to computer until it reaches its destination.

Researchers have acknowledged for some time that networks are dynamic in nature: nodes and links come and go with time. This has led to a stream of works aiming at understanding and modelling these dynamics. In particular in the case of centrality, some works have been concerned with efficiently updating the centrality values of the nodes when a change occurs in the network. In many cases however, the time scale at which the network evolves is the same as the one at which a dissemination phenomena may occur on the network. This is the case for instance when a disease propagates among individuals when they are in contact, or when an information is disseminated by email messages. In this case, it becomes necessary to consider paths that are not instantaneous but instead are spread between a beginning and an ending time, while respecting the network dynamics. Such a temporal path follows links that happen one after the other (see Section III for a rigorous definition).

In this case, our key argument is that paths change during the network time span, and thus the importance of nodes varies. Consider indeed the toy example of Figure 1. This small network composed of five nodes evolves during four distinct time steps. One can see that, intuitively, the importance of node b is much stronger at time t = 1 than at time t = 3. Indeed, at time t = 1 it forms a bridge between node a and nodes c, d and e, thanks to the links that exist at time t = 2.

Several works have introduced extensions of centrality notions for the case of dynamic networks. However, most of these works consider only paths starting at the beginning of the dataset; they obain in this way a single figure for node centrality, representative only of what happens at very early times. Other works consider paths throughout the dataset time span, but still consider that node importance can be represented by a single figure rather than by a time-evolving metric.

Though it is quite straightforward to extend these metrics in order to consider the time evolution of node centrality, no work up to our knowledge has attempted to study this question.

In this paper, we study a natural extension of the closeness centrality to the case where paths may start at any time during the network's time span. This temporal closeness characterizes the importance of any node at any given time. We study two datasets and observe that: 1) node importance does vary with time, and therefore capturing the global importance of a node with an aggregate value might be misleading; 2) in some cases the dynamic of the network is such that it is meaningless to identify nodes more important than others; in other cases, temporal closeness may help identifying a node consistently important for the whole network time span;

This work is organized as follows. First we present the existing work related to the notion of centrality in static and dynamic networks (Section II) before providing the definitions necessary to the present study (Section III). Then we present the two datasets (Section IV) on which we apply the proposed metrics and present the obtained results (Section V). Finally, we conclude the paper with some perspectives (Section VI).

II. RELATED WORK

Many papers have studied the importance of nodes in static networks, i.e. networks that don't evolve with time. Among the metrics that have been introduced, one may cite the degree centrality, closeness centrality [START_REF] Bavelas | Communication patterns in task-oriented groups[END_REF], betweenness centrality [START_REF] Freeman | A set of measures of centrality based on betweenness[END_REF] and the Katz centrality [START_REF] Katz | A new status index derived from sociometric index[END_REF]. Closeness and betweenness centrality are based on the shortest paths, while the Katz centrality takes into account the paths of all lengths between two nodes. Some papers who have studied dynamic networks have been concerned with efficiently computing the static centrality at all times. For instance, Kas et al. [START_REF] Kas | Incremental closeness centrality for dynamically changing social networks[END_REF] propose an algorithm that, given the knowledge of the distances between all pairs of nodes and given a network change (edge appearance of disappearance), computes the new distance values (which allows the computation of distance-related centrality measures) by updating the previous values rather than computing them all from scratch again. This is relevant, e.g. in contexts where the network evolves at a much slower scale than the one on which disseminations take place.

However, in many contexts the dissemination phenomena in the network happen on the same time scale as the network evolution. It then becomes necessary to consider temporal paths [START_REF] Bui-Xuan | Computing shortest, fastest, and foremost journeys in dynamic networks[END_REF], [START_REF] Pan | Path lengths, correlations, and centrality in temporal networks[END_REF], i.e. link sequences that are time-respecting, as opposed to paths composed of links that all exist at the same time. For instance, in the dynamic network of Figure 1, there is a temporal path from node a to node e going through the link (a, b) at t = 1 and the link (b, e) at time t = 2.

Several definitions of temporal paths have been studied in the literature. Some of them can be computed more easily than others. Whitbeck et al. [START_REF] Whitbeck | Temporal reachability graphs[END_REF] propose an efficient algorithm to approximate the existence of paths in the most difficult case, and show that the study of the notion of reachability, i.e. which nodes can be reached from which ones, and at which times in the network's time span, provides enlightening insight on the network's dynamics.

Notions of centrality taking into account temporal paths have also been introduced.

Nicosia et al. [START_REF] Nicosia | Temporal Networks[END_REF] introduce notions of temporal closeness and betweenness centralities. Their definition of a shortest path however considers only paths whose starting point is at the beginning of a dataset's time span. Some propositions acknowledge that the distances between nodes, and therefore nodes' importance, vary with time [START_REF] Braha | Time-dependent complex networks: dynamic centrality, dynamic motifs, and cycles of social interaction[END_REF], [START_REF] Shamma | Tweet the debates: Understanding community annotation of uncollected sources[END_REF], [START_REF] Kim | Temporal node centrality in complex networks[END_REF], [START_REF] Pan | Path lengths, correlations, and centrality in temporal networks[END_REF] . However, in practice they still represent the varying importance of a node by a single value that is supposed to represent its overall importance throughout the network global time span.

Several papers introduce and study a variant of the Katz centrality [START_REF] Laflin | Discovering and validating influence in a dynamic online social network[END_REF], [START_REF] Alsayed | Betweenness in time dependent networks[END_REF]. Among those, Lerman et al. [START_REF] Lerman | Centrality metric for dynamic networks[END_REF] acknowledge the fact that node importance may evolve with time, but no systematic study is performed. Moreover, the introduced metric is dependant on parameters defining what are considered as relevant path lengths and path durations, which complicates the analysis.

Finally, Cotsa et al. [START_REF] Costa | Time centrality in dynamic complex networks[END_REF] notice that not all time instants are equivalent in a dynamic network, and introduce the notion of time centrality; this is a measure of how fast a dissemination process can reach a significant portion of the nodes at a given time t. However, this notion does not analyze the importance of individual nodes in the dissemination process, which is our goal in this paper.

All in all, and to the best of our knowledge, if many papers acknowledge the fact that the temporal evolution of networks impact the value of centrality measures and propose variations of standard metrics to account for the dynamics, no paper propose a complete and systematic study of the evolution of centrality measures for all nodes and all time steps of the network's evolution. Instead, they all propose average computations either over all nodes of the networks, either over all the network time span. We argue in this paper that discarding either of those two aspects lead to severe misunderstanding of the real nature of node's importance in the context of dynamic networks III. DEFINITIONS A dynamic network G = (V, E) consists of a set V of nodes1 and a set E of timed links of the form (u, v, t) where u, v ∈ V and t is a timestamp. Throughout the paper we consider networks as undirected, i.e. a link (u, v, t) is equivalent to a link (v, u, t).

A temporal path in a dynamic network consists of:

• a starting time t s , and

• a sequence of links (u 0 , v 0 , t 0 ), (u 1 , v 1 , t 1 ), . . . , (u k , v k , t k ) such that: 1) for all i, i = 0..k -1, u i+1 = v i ; 2) for all i, i = 0..k -1, t i < t i+1 . 3) t 0 ≥ t s ;
We say that such a path is a path from u 0 to v k starting at time t s . Its duration is equal to t kt s . We will say that a path from u to v starting at time t s is a shortest path if it has the least duration among all paths from u to v starting at time t s . We define the distance from u to v at time t to be the duration of a shortest path from u to v starting at time t, and we denote it by d t (u, v). If there is no path from u to v starting at time t, we consider that d t (u, v) = ∞.

Note that a path starting at time t might imply waiting times at all nodes, including the first one, in the same way that a person starting at a given time a train trip with connections must wait for the train in the first station, and then at each connecting station.

For example, in the dynamic network of Figure 1, there are two temporal paths from e to b starting at time t = 2. The first one consists of the single link (e, b, 2), and its duration is 0; the second one consists of the links (e, d, 3) and (d, b, 4) and its duration is 2. The temporal distance from e to b at time 2 is therefore d 2 (e, b) = 0. Note that the temporal distance from e to b at time 1 is d 1 (e, b) = 1: the temporal shortest path has the same link sequence than the one starting at t = 2 (it is the single link (e, b, 2)), but the starting time is different. Since there is no temporal path from c to e starting at time t = 3,

d 3 (c, e) = ∞.
Several variants have been introduced in the literature, most notably concerning the constraint t i < t i+1 . Some variants weaken it to t i ≤ t i+1 , while others strengthen it to t i ≤ t i+1 + δ, where δ is a parameter representing the time needed to send a message along a link. The relevance of these variants depends on the context. See [START_REF] Whitbeck | Temporal reachability graphs[END_REF] for more details. Preliminary work shows that this has little influence on the results.

It is worth noticing that our definition of a dynamic network consists of links without a duration. Again, this is relevant in some contexts (e.g., an email is sent at a precise time) and less in others (a phone call has an intrinsic duration). Notice however that our notion of a temporal path can be easily adapted in the latter case; the condition becomes that a path going through node u at time t i can continue to a node v provided that there is a link between u and v that ends after t i .

We recall that the closeness of a node u in a non-evolving network is defined as [START_REF] Bavelas | Communication patterns in task-oriented groups[END_REF]:

v =u 1 d(u, v)
,

where d(u, v) is the classical graph distance.
The average of the closeness of all nodes has been defined as network efficiency [START_REF] Latora | Efficient Behavior of Small-World Networks[END_REF] 2 .

Though some extensions of the closeness have been defined for the case of dynamic networks [START_REF] Kim | Temporal node centrality in complex networks[END_REF], [START_REF] Nicosia | Temporal Networks[END_REF], their goal is not to take fully into account the fact that temporal distances vary according to the paths' starting time. We therefore here define the temporal closeness of a node u at time t as:

C t (u) = v =u 1 d t (u, v)
, 2 There are several variants of the closeness in the litterature, depending on a normalisation constant, and the efficiency depends of this. Since for both metrics this is a constant that does not vary with time, we use the simplest version for the closeness which is the sum of the inverses of the distances. and we define the temporal efficiency E t (G) of network G as the average over all nodes of the temporal closeness at time t.

Building upon this notion of efficiency, we can study another metric that quantifies the impact a node has on a network. The notion of delta-centrality [START_REF]A measure of centrality based on the network efficiency[END_REF] characterizes how much a given node (or group of nodes) impacts the efficiency. It is defined as the relative change of the network efficiency when the considered node (or group of node) is removed from the network.

Following this, we study the extension of the deltacentrality to the dynamic case. The temporal delta-centrality of a node v at time t is defined by:

E t (G) -E t (G\v) E t (G) ,
where G\v is the network obtained from G by removing node v and all its adjacent links.

The program we used to compute the above metrics is available [START_REF]Source code for the temporal centrality metrics[END_REF].

IV. DATA SETS

In order to study the behaviors of the metrics introduced above, we study two datasets that present different characteristics and come from two very different contexts:

• Rollernet [START_REF] Tournoux | The Accordion Phenomenon: Analysis, Characterization, and Impact on DTN Routing[END_REF]: this dataset was collected during a rollerblade tour in Paris in August 2006. The tour is a weekly event and gathers approximately 2500 participants. Among these, 62 were equipped with wireless sensors recording when they are at a communication distance from one another. The dataset therefore contains the proximity links between the persons carrying the sensors. The total dataset duration is approximately 2 hours and 45 minutes (with a break of approximately 30 minutes).

• Enron [START_REF] Shetty | Discovering important nodes through graph entropy the case of Enron email database[END_REF]: this dataset contains the 252 759 emails that 151 Enron employees exchanged during three years. It records information on the senders, receivers, and the moment they were sent. Note that by nature, the links are directed but for a fair comparison with the Rollernet dataset, we treated them as undirected in the present study.

Before studying the importance of nodes (see next section), it is enlightening to make some global observations related to the dynamic of the networks.

To do so, we present in Figure 2 the fraction of pairs of nodes for which there is a temporal path starting at the beginning of the dataset and ending before time t, as a function of t. In other words, it represents the proportion of pairs of nodes that are reachable from one another at time t or sooner. Notice that, though the shapes of the plots are similar, the time scales are very different: for Rollernet, all pairs of nodes that are eventually connected are so within less than half an hour, i.e. quite early in the dataset. For Enron, on the other hand, the time scale is larger and we can see that less than 10% of the pairs of nodes are reachable from one another after one year; new pairs become reachable for the whole dataset duration, and some paths only end very close to the end of the dataset. This difference between the datasets does not come from an artifact at the beginning of Rollernet: we have observed that we can find short paths from any node to any other node at almost any starting time (except close to the end). This seems to indicate that nodes will be overall less important in Rollernet than in Enron. Indeed, in the first case we may expect that a given node's closeness will be only marginally larger than an other one's, whereas in Enron we may expect that all paths to a given node must go the same node, which will then be quite important. Our observations in the next section confirm this intuition.

V. RESULTS

We now present the results obtained using the different notions introduced in Section III on the two dynamic networks presented above.

A. Temporal efficiency and temporal closeness over time

Figure 3 presents the time evolution of the temporal efficiency for each dataset. We can see that the value fluctuates widely for both of them. Notice that for Enron, even though it fluctuates, the efficiency tends to increase with time 3 . This is caused by the fact that, as shown previously, the number of pairs that are reachable from one another increases with time throughout the dataset duration. The final collapse stems from the fact that, towards the end of the dataset, less and less temporal paths exist.

We expect that these fluctuations in the efficiency will impact the individual nodes' closeness.

Turning to the temporal closeness, we first present in Figure 4 the time evolution of this metric for randomly chosen nodes in our datasets. It appears clearly that the closeness of a node can be very bursty. Values vary on a wide range in both cases, and along several orders of magnitude in the case of Enron. This burstiness makes the plots difficult to interpret, and highlights our claim that the importance of a node varies greatly with time.

However, the fact that a node's closeness fluctuates with time does not mean that this node does not have a relatively large (or small) closeness overall. To evaluate this, we need to compare the values between nodes. We do this in the next section.

B. On the relative importance of a node

In order to get a better sense of whether a node consistently has a large closeness with respect to other nodes, we proceeded in the following way: for each time step t, we sorted all nodes by increasing order of their temporal closeness at time t. This gives to each node a rank that varies with time: node x has rank 1 at time t if it has the lowest temporal closeness among all nodes at time t, and rank n (where n is the number of nodes) if it has the highest temporal closeness.

Figure 5 shows the time evolution of the ranks of the same randomly chosen nodes as Figure 4. We can observe several things. First, as expected, there seems to be a correlation between closeness and rank: at many times, the higher the closeness, the higher the rank. However, this correlation is not perfect: for the Enron node, for instance, there is a period of increasing closeness between two peaks after The closeness at this time is larger than at times 0-600 days, but the corresponding rank is lower. We also observe an artefact for large times in the Enron case: we observe that the closeness drops to 0 after approximately 900 days; however the rank increases during this period. This is due to the finite duration of the dataset. Since fewer and fewer temporal paths exist between pairs of nodes, the closeness of more and more nodes drops to zero (we observed the corresponding decrease in the efficiency in Figure 3). The rank among those nodes is then arbitrary.

Finally, we observe different behaviors between the Rollernet and the Enron nodes. While the Rollernet node's rank fluctuates between very low and high ranks (except at the beginning of the trace), the Enron node's rank is rather stable for a significant part of the dataset's duration, before starting fluctuating (but not as drastically as the Rollernet one). In conclusion, neither of these nodes has a high or low closeness globally. The Enron node has a low closeness for a significant duration of the dataset, but still reaches very high ranks at Fig. 6. Total duration for which rank is in the 25% lowest (x-axis) vs total duration for which rank is in the 25% highest (y-axis). Top: Rollernet; Bottom: Enron.

some times, at which it plays an important role in the network connectivity. The Rollernet node has no clear period within which its rank is rather stable.

C. On the global importance of some nodes

In order to study all nodes in a more systematic manner, we computed, for each node in each dataset, the total duration during which its rank was among the 25% lowest, and the total duration during which its rank was among the 25% highest. We plot in Figure 6 these two quantities for each node for the Rollernet (top) and Enron (bottom) case. Notice that the shape of the scatterplot is limited by the fact that the sum of both coordinates cannot exceed the dataset duration.

In both datasets we observe that all nodes are not equivalent: most nodes are in the top 25% ranks for a longer duration than they are in the bottom 25%, or conversely. However, this does not happen with the same magnitude in both datasets. In Rollernet, the maximum total duration for which a node is in the top or bottom 25% ranks is approximately 1.5 hours, which represents approximately half the dataset duration. This means that no node has a globally high or low closeness throughout the whole dataset duration. In Enron however, some nodes are predominantly either in the highest or lowest 25% ranks during almost all the dataset's time span, meaning that these nodes consistently have a high (or low) temporal closeness comparatively to all other nodes.

In order to deepen the study of whether some nodes play an overall important role in the network (or conversely, have consistently a low impact), we identfied the node for which the rank was in the top (resp. bot) 25% for the longest period of time, for each dataset. We plot the time evolution of these nodes' rank in Figures 7 (Rollernet) and 8 (Enron).

Again, we observe different behaviors between the datasets. For Rollernet, the longest duration a node is in the 25% highest ranks is approximately 1 hour and 10 minutes, which is significantly less than half the duration of the dataset. We can moreover observe that the corresponding node's rank fluctuates a lot (Figure 7 top) and never stays in the highest ranks during a significant amount of time.

The case of the node with the most time in the lowest ranks is different (Figure 7 bottom). It has a very low rank in approximately the second half of the dataset. Indeed, this node is only active for the first half of the dataset, and does not have any link in the second half. Its temporal closeness therefore drops to zero (but, as seen in Figure 4 it has then an arbitrary rank among all nodes with a null closeness). However, it is quite interesting to observe that, while this node is active, its rank fluctuates a lot and often reaches very high ranks, meaning that it is among the most influential nodes at these times. In fact, this node spends slightly more than 15 minutes in total among the 25% highest ranks, while being active only 1h30 in total. Altogether, the conclusion for Rollernet is that no node is globally important or unimportant for a long time; global importance may not be a relevant notion for this dataset.

By contrast, the situation is quite different for the Enron case. Although the rank of the node with the longest duration in the highest ranks fluctuates with time (Figure 8, top), we can observe that it consistently stays within the highest 50% ranks for approximately the first half of the dataset's time span. Moreover, even though its rank tends to decrease in the second half, it never goes in the lowest 33% ranks. This node is therefore globally important in the dataset.

In the same way, the node with the longest duration in the lowest ranks (Figure 8, bottom) is consistently unimportant. It is quite interesting to notice that there is a point at which this node reaches a very high rank (rank 149 out of 151 nodes). A manual study indicates that this node is actually inactive for most of the dataset time span. Its only activity consists in exchanging two messages with the same node, shortly before 1 000 days. It is striking that these two links are enough to bring this node to the third highest rank among all nodes. This indicates that these links are very important in the network, and/or that the network dynamics undergoes a particular event at this time. We leave the detailed investigation of such phenomena to future work.

D. Delta-centrality

In order to further study the importance of a node, we turn now to the temporal delta-centrality as defined in section III, which quantifies the impact of a node on the network.

We made the same systematic study for delta-centrality as the one we did for closeness: we computed the delta-centrality for all nodes at each time step; then for each time-step we sorted the nodes by increasing order of the delta-centrality, thus ranking them from 1 (lowest temporal delta-centrality) to n (where n is the number of nodes, for the highest deltacentrality). Doing so, we observed that the temporal closeness is a very good estimator for the delta-centrality 4 . In general, the higher the temporal closeness, the higher the temporal delta-centrality; the rankings and their time evolution are also very close for most nodes. In the same way, the duration a node's rank is amont the highest (resp. lowest) 25% ranks for the temporal closeness is very highly correlated with the duration for which its ranks is in the same range for the temporal delta-centrality. Figure 9 strong in both cases, and even stronger in the case of the lowest ranks.

We performed a detailed comparison of the temporal closeness and the temporal delta-centrality for individual nodes, and in particular for all nodes for which the correlation was the weakest. In such cases we observed in general that the corresponding nodes are not globally important or unimportant nodes: their coordinates in the scatteplots of Figure 6 are not very large. Moreover the time evolution of the rank for both centrality metrics are very similar in most cases, even though the ranks are not exactly the same. In most cases, the differences come from the fact that the rank is close to the 25% limit for a significant duration.

For a very small number of nodes, however, we observed a somewhat significant difference; in particular a few nodes tend to have a relative temporal delta-centrality that is higher than their relative temporal closeness. Such nodes therefore have a high impact on paths (when they are removed, the network temporal efficiency decreases), without being particularly close to other nodes. These nodes therefore play a peculiar role in the network, and do not follow the general network behavior. We leave a detailed study of the causes of this phenomenon, as well as the identification of such anomalous nodes, to future work.

VI. CONCLUSION

Our central point in this paper is that temporal distances in dynamic networks may vary a lot with time; all distancebased centrality measures should therefore be considered as time-dependant, contrary to what has been mostly done in the litterature.

In order to investigate this, we studied the notion of temporal path with a starting time, and the corresponding notion of distance between two nodes at a given time. We then proposed temporal extensions of two importance measures, the closeness centrality and the delta-centrality. Using these notions, we studied two datasets coming from different contexts in order to investigate whether different network properties impact the observations.

Our observations can be summarized as follows:

1) node importance varies with time: a given node may be very important at one time, and not so important at another time; therefore it is not relevant to consider only aggregate values that summarize the importance of nodes on the whole network time span; 2) different datasets have different properties regarding node importance; for one of our datsets, the importance of all nodes fluctuates extremely rapidly between high and low values; it is meaningless in this case to state that one node is more important than another, except for a very limited time span; for our other dataset however, we find that some nodes are consistently important (or unimportant) for the whole network time span; 3) our studies have highlighted some specific nodes with atypical behaviors; this suggests that temporal centrality metrics could lead to methods for event and/or anomalous behavior detection.

Our work opens several interesting perspectives.

First, if the choice of two dataset stemming from very different contexts strengthen the conclusions drawn from the present study, we would like to apply the approach on more dataset involving dynamic networks. This would allow to confirm our findings and might help identify specific patterns of the evolution of node's importance that are context-dependant.

Following up on the precedent point, it would be very interesting for many real applications to be able to detect specific patterns in the evolution of centrality measures. This would indeed allow to predict which nodes are likely to be important in the future, which turns out to be of key importance for several applications, ranging from protocols of communication to recommendation systems.

On a more formal perspective, our definition of closeness of a node v relies on the computation of the distances from v to all other nodes. This is particularly relevant in our context, where we are concerned by the importance of a node in the dissemination process: a node will be important if it can reach many other nodes quickly. In other contexts however, the importance of a node v may be more closely related to the fact that the distances from all other nodes to v short. This may be the case for instance in Web graphs, in which the importance of a page comes from the links towards it, not from its outgoing links. Comparing these two notions of closeness would lead to interesting insights.

We have seen that some of our observations allow to detect nodes that have an atypical behaviour, and/or moments where something unusual happens in the network's dynamics. We have observed this both when studying the time-evolution of the closeness of individual nodes, and when comparing different importance measures. This suggests that temporal centrality measures are relevant metrics when trying to detect anomalies in the network, which is a crucial question in many contexts [START_REF] Heymann | Outskewer: Using Skewness to Spot Outliers in Samples and Time Series[END_REF]. In particular, it seems that nodes that are important with respect to one metric but not to another have a particularly interesting behavior. A systematic comparison of different metrics would therefore certainly lead to very interesting insight about the considered dataset.

In the same way, we have seen that some links play an extremely important role. It would be quite interesting to define a reliable method for identifying important links. On the one hand, this would lead to another approach for event detection in the network, complementary to the one sketched above. On the other hand, notions of link centrality have been successfully used in the case of static networks for community detection [START_REF] Girvan | Community structure in social and biological networks[END_REF]. Using a notion of importance in a dynamic network for dynamic community detection is therefore a promising idea.

Finally, there is yet no consensus on relevant generative models for dynamic networks. Since we have observed that different networks have different properties regarding the temporal closeness centrality, this is probably an important ingredient to take into account when proposing a new model.

Fig. 1 .

 1 Fig. 1. A small example of a dynamic network. The links existing at time t = 1 are shown on the top left corner, the ones existing at t = 2 in the top right corner, and so on.

Fig. 2 .

 2 Fig.2. Fraction of pairs of nodes for which there exists a temporal path starting at the beginning of the dataset and ending at time t or sooner, as a function of t. Top: Rollernet; Bottom: Enron.

Fig. 3 .Fig. 4 .

 34 Fig. 3. Time-evolution of the temporal efficiency. Top: Rollernet; Bottom: Enron.

Fig. 5 .

 5 Fig. 5. Time-evolution of the rank of randomly chosen nodes in our datasets. Top: Rollernet; Bottom: Enron.

Fig. 7 .Fig. 8 .

 78 Fig. 7. Time evolution of the rank in the Rollernet dataset, for the node with the longest duration in the highest 25% ranks (top) and the node with the longest duration in the lowest 25% ranks (bottom).

  illustrates this. We observe that the correlations are

	Temp. d.-centr. / time (days)	0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6	0		0.2 top 25% 0.4 bottom 25%	0.6	0.8	1	1.2	1.4	1.6
					Temp. closeness / time (days)
	Temp. d.-centr. / time (days)	0 200 400 600 800 1000 1200	0	200 top 25% bottom 25%	400	600	800	1000	1200
					Temp. closeness / time (days)
	Fig. 9. Correlation between duration spent in lowest 25% or highest 25%
	ranks for temporal closeness (x-axis) and temporal delta-centrality (y-axis).
	Top: Rollernet; Bottom: Enron.

We assume that the set of nodes does not evolve with time.

Note that we used a log scale on the y-axis for this plot. The peaks spanning several orders of magnitude make it unreadable with a linear scale.

Note that the delta-centrality computation is much more costly than the closeness centrality, as the delta-centrality computation requires the computation of all distances between all pairs of nodes, both in the original network and in the network where the considered node has been removed; the temporal closeness requires only to compute the distance from one node to all other nodes.

ACKNOWLEDGEMENTS

The authors would like to thank Thibault Rieutord for enlightening preliminary discussions on this work and in particular the algorithmic aspects.

This project was partly funded by a grant from the French program "PIA -Usages, services et contenus innovants" under grant number O18062-44430, and by the French National Research Agency contract CODDDE ANR-13-CORD-0017-01.