Marco Biazzini
email: marco.biazzini@inria.fr

Martin Monperrus
email: martin.monperrus@univ-lille1.fr

Benoit Baudry
email: benoit.baudry@inria.fr

On Analyzing the Topology of Commit Histories in Decentralized Version Control Systems

Empirical analysis of software repositories usually deals with linear histories derived from centralized versioning systems. Decentralized version control systems allow a much richer structure of commit histories, which presents features that are typical of complex graph models. In this paper we bring some evidences of how the very structure of these commit histories carries relevant information about the distributed development process. By means of a novel data structure that we formally define, we analyze the topological characteristics of commit graphs of a sample of GIT projects. Our findings point out the existence of common recurrent structural patterns which identically occur in different projects and can be consider building blocks of distributed collaborative development.

I. INTRODUCTION

Centralized version control systems (CVCS) such as CVS or SVN have a rather sequential history. There is a linear history of committed change sets (or commits), stored on a central server. Branching makes up for some parallelism, but its capability to improve successful collaboration has been thoroughly questioned [START_REF] Shihab | The effect of branching strategies on software quality[END_REF].

On the contrary, the history of Decentralized Version Control Systems (DVCSs) such as Mercurial or GIT is much richer. In decentralized version control systems, each developer has the full commit history of the codebase locally available. This allows for a much more flexible way to handle different concurrent branches. The extreme ease of branch manipulation and combination results in software histories that are much more complex than what is typically found in a traditional centralized systems software.

Bird and colleagues have shown that the analysis of DVCS presents several issues for traditional repository mining techniques and metrics [START_REF] Bird | The promises and perils of mining git[END_REF], In DVCSs, there are concurrent branches that start from a common ancestor, run in parallel, split, merge together or with other branches, then are finally merged in a commit which gives a "current stable version" of the software product. Such a canopy of development lines demands to redefine concepts such as "developer collaboration", "current state of the code", "amount of contribution", which are fairly easy to establish for CVCSs.

In this paper, we propose to use graph concepts and metrics to characterize DVCSs such as GIT. We consider commit histories of DVCSs as directed acyclic graphs (DAGs) and talk about software development using a general graph characterization (topology, patterns, metrics, etc.). The structure of commit history DAGs is given by the way developers use branches. Their topology reflects the way the software is modified, improved, fixed, in one word, evolved.

Thus there is information hidden in the very structure of the commit history graph, which is relevant to understand key characteristics of the development process typical of DVCSs. In this paper we show that the topology of commit graphs presents recognizable patterns, whose recurrence is due to the nature of the underlying development process itself. Such patterns are not purposely designed by developers, who rather pursuit goals related to the state of their codebase. They thus emerge from the topologically rich structure of DVCSs and characterize the way the codebase evolves over time.

To sum up, this paper makes the following contributions:

-The definition of a novel data structure, the repository Metagraph, that captures all the relevant information about the DVCSs repositories.

-A classification of the elements of a DVCS commit history, based on their topological relevance in their history graph.

-An analysis of topological properties of the commit history of several open source GIT-based project repositories.

We thus propose a novel way to analyze DVCS-based software project and discuss the evidences that signal its potential in leading to novel insights about the process of collaborative development.

The rest of the paper is organized as follows. Section II presents and formally defines our contribution. Section III describes the settings of our experiments. Section IV discusses our findings and motivates their relevance. Section V presents related work and Section VI draws our conclusion.

II. TOPOLOGICAL ANALYSIS OF COMMIT GRAPHS

The commit history of a decentralized repository can be modeled by a directed acyclic graph whose nodes are commits and edges are parent/child relations between them.

As the history of a project evolves, parallel branches are created and joined in a distributed process of incremental manipulation of the code base. In general (as backed up by statistics we present in the following), the majority of commits belongs to single branches, while fewer are those where the creation or the join of the branches themselves occur.

For the purpose of understanding the global structure of the commit history, i.e. the topology of the commit graph, these latter commits are much more relevant than the former. We propose to classify, from the standpoint of their topological interest, the commits populating a history graph as follows:

c1 c2 c3 c4 c5 c6 c7 c11 c8 c9 c10 c12 c13 [c2 -c5] c1 c6 c10 c13 [c7 -c9] [c11 -c12]
-Terminal. Commits having no parent or no child.

-Sequential. Commits having exactly one parent and one child.

-Structural. Non-terminal commits whose union set of parents and children has more than 2 elements.

These categories are devised so that (i) they capture the whole set of commits in a GIT history and (ii) a given commit can belong to one and only one of them. To bridge these definitions with the standard GIT terminology, terminal commits are either first commits or HEADs; sequential commits are non-merging and non-branching ones, excluding first commits and HEADs; structural commits are merging and/or branching commits, which are not HEADs.

Terminal commits are thus the boundaries of the graph, while structural commits are the nodes which define its structure. Sequential commits do not play any role in determining the topology of the graph, being just enqueued in development lines (the branches) which lead from a merge (or branch) commit to another. Sequential commits are clearly important from the standpoint of the developer contribution to the codebase. They should anyway be bypassed, when analyzing how branches feed each other and the parallel development gets organized in the repository, in order to get rid of topologically irrelevant information, which would bias any metrics. Thus, a way must be devised to meet conflicting goals:

• Avoiding the overhead and the information noise of sequential commits while analyzing the topology of a commit history graph, in order to be able to obtain meaningful results

• Saving the information about the developer contributions that the sequential commits incorporate, along with their position in the commit history, in order to be able to relate the results of the topological analysis with those derived by other kinds of data mining, which focus on code metrics or process metrics.

We define in the following a data structure and a set of properties that allow to positively solve both issues.

A. The Repository Metagraph

We define an original data structure, based on this classification of GIT commits. This structure, called Metagraph, encompasses a commit history, focusing on the topologically relevant commits. The Metagraph retains all the information from in the commit history. It aims at simplifying structural analyses performed on the repository commit logs of a GIT repository.

Def. -Metagraph

A Metagraph M g of a commit history graph G = V, E is a multi-graph M g = V e, M e , where V e is the set of nodes which correspond to terminal and structural commits in V and M e is a set of metaedges (see next definition). We call root the node in V e associated to the first commit of G.

Def. -metaedge Given a Metagraph M g of a commit history graph G, a metaedge is a directed edge between commits in the set of nodes V e of M g.

A metaedge me between two nodes V e 1 and V e 2 exists in M g if and only if a path in G exists between the corresponding nodes V 1 and V 2 , which is composed uniquely by sequential commits. The list of (sequential) commits composing this path in V is associated (as metadata) to the metaedge.

We call V e 1 (resp. V e 2 ) first (resp. last) node of me. Figure 1 illustrates a Metagraph (right) built from a commit history graph (left). Our definition of metaedges serves two main purposes: (i) it simplifies the topology of a commit history by excluding sequential commits from its structure, while preserving the information they carry and (ii) it makes the Metagraph a model that focuses on parallel development events (occurrences of branching or merging in the commit history graph G).

Our analysis of Metagraphs extracted from GIT repositories is based on the following properties:

Def. -Metagraph's layer For any v i ∈ V e, let dist(v i ) : V e → N be a function that maps each node of M g to its maximum distance from the root of M g, measured in number of metaedges. A layer L n in a Metagraph M e is defined as

L n ⊆ V e ∈ M e : l i ∈ L n ⇐⇒ dist(l i ) = n.
Layer L n is thus the set of all nodes having the same maximum distance n from the root. We call n the index of the layer. By construction, roots are the only nodes belonging to L 0 .

Supposing the example in Figure 1 represents a complete Metagraph, we have L 0 = c1, L 1 = c6 and L 2 = c10, c13. The set of layers of a Metagraph is a convenient partitioning of its nodes, which groups commits according to their distance from the first commit, measured in terms of number of parallel development events, as captured by the metaedges.

Def. -Width of a layer. The width of a layer L n is equal to its cardinality |L n |.

Def. -Density of a layer. We call density of a layer L n the number of metaedges whose last node is in L m , m ≥ n.

The density of a layer L n is thus the number of metaedges terminating either in L n or in a layer which is farther from the root. By definition, the density of L 0 = 0. Let c n be a cut of M g partitioning its nodes in two sets:

V e 1 = v i : dist(v i ) < n and V e 2 = v j : dist(v j ) ≥ n.
Then, the density of L n is the number of metaedges crossing c n .

Def. -Diameter of a Metagraph. The diameter of a Metagraph is equal to the length of the longest path in the Metagraph. By construction, it is equal to the greatest layer index of the Metagraph.

B. Development Patterns

Since the Metagraph captures the structural properties of a commit graph, we now look for evidence of the presence (or lack thereof) of recurrent development patterns in repository metagraphs.

A way to spot such patterns is to find recurring subgraphs in a Metagraph over different projects. Since any subgraph of a Metagraph can only be composed by merging and/or branching commits of the project history, the fact that the same subgraph occurs several times in a project Metagraph would denote the emergence of the same collaborative pattern at different moments of the project history.

Moreover, the fact that the same subgraph repeatedly occurs in Metagraphs which model the history of different projects would point out emergent patterns characterizing collaborative development itself, rather than the collaboration habits of a specific community of developers.

The problem of finding all isomorphic subgraphs of a given graph is in general NP-complete [START_REF] Wegener | Complexity Theory: Exploring the Limits of Efficient Algorithms[END_REF]. Even limiting the size of the subgraphs to target, the feasibility of such a task heavily depends on the structural complexity of the Metagraph. Several efficient algorithms exist, though, to find single subgraphs within larger graphs. By restricting the number of targets and narrow down the search to each one of them, we can find all occurrences of specific patterns of a given size (number of nodes).

A way to choose target patterns is needed. We are interested in enlightening the very structure of the Metagraphs. Terminal nodes are the ever-changing boundaries of the Metagraphs and thus not really relevant for our purposes. We can focus on structural nodes and on the metaedges that start from or arrive to structural nodes.

Let us therefore consider the subgraph Sg = V s, M s of a Metagraph M g, composed by the set V s of all structural nodes of M g, along with the set M s of all metaedges of M g whose first and last nodes are both in V s. Recalling that, by construction, any metaedge in M s must either start form or end to a node in V s, it is easy to see that all subgraphs of Sg are either isomorphic to simple polygons or to polygons composed by adjacent polygons of smaller size. Figure 3 exemplifies our point by showing two isomorphic graphs.

Thus the quest for patterns becomes the search for all polygon subgraphs in Sg. Finding simple polygons is enough, because it is easy to spot out composed polygons, by tracking common nodes among simple (smaller) polygons. Such a task is accomplished by finding induced subgraphs in M g, which are isomorphic to simple polygons.

We thus propose the following definition.

Def. -Pattern

We call pattern any induced subgraph of a Metagraph, which is isomorphic to a polygon graph.

As metaedges are always directed, there are several different (i.e., non-isomorphic) patterns of any given size s, s > 3.

Thus the relevance of a pattern may not be given only by its size, but also by its very topology. Since we are interested in characterizing the way collaborative development shapes commit histories, we propose a simple way to discriminate between patterns of incremental development and patterns of code integration. Clearly both aspects are always present in any pattern, but their relative relevance may differ, as we exemplify in the following. Being our patterns simple acyclic digraphs of degree 2, each pattern is composed of two or more walks. The lengths of these walks fall in the interval ]0, 1, . . . , N [, where N is the size of the pattern. Considering the topology of a pattern, the presence (resp. absence) of few longer walks indicates a greater (resp. smaller) relevance of incremental developing w.r.t. code integration. Figure 4 intuitively shows how three identically sized patterns can be different from this standpoint.

In order to classify patterns of different size w.r.t. the kind of collaboration they entail, and, more generally, to compare them w.r.t. this criterion, we propose to compute their slenderness, defined as follows:

Def. -Pattern's slenderness The slenderness of a pattern is a real number in [0 . . . 1[, computed as the number of vertexes that are internal to its walks, divided by the size of the pattern.

Intuitively, a higher (resp. lower) slenderness denotes a pattern where incremental development (resp. code integration) dominates over its counterpart. For instance, the patterns in Figure 4 have a slenderness of 8/10 = 0.8 (left), 6/10 = 0.6 (top right) and 0/10 = 0 (bottom right), which well denotes the fact that the first pattern is strongly incremental, while the second balance increments and integration (with a slight dominance of the first) and the third pattern is all about integration. The results presented in the following show that recurring patterns indeed characterize commit histories of a sample of GIT-based projects.

We underline that such patterns would not be detectable on "raw" commit history graphs, because sequential commits "overwhelm" their structure destroying relevant topology properties. Thanks to the transformation to Metagraphs, the very structure of commit graphs can be successfully mined from a topological standpoint.

III. EXPERIMENTAL DESIGN

We present an experiment that aims at identifying development patterns in a sample of GIT repositories, collected from GITHUB. For each repository, we build a Metagraph modeling its commit history. We then detect patterns in the topology of the Metagraphs and analyze their characteristics.

A. Experimental Data

The experimental data comes from GITHUB, an Internet hosting service for open source software. According to FLOSSmole [START_REF] Howison | Flossmole: A collaborative repository for floss research data and analyses[END_REF] (Free Libre Open Source Software) statistics, GITHUB had 191765 repositories publicly available in May 2012. In order to obtain a statistically representative sample of GITHUB hosted projects, we order these projects according to the number of watchers. To discard outliers and less significant entries, we decide to cut off the extrema of the range, i.e. projects whose number of watchers is less than 2 or more than 1000. Then we select 1% of the projects in each of three subsets:

• Projects that had from 2 to 9 watchers (total: 30236; sampled: 303)

• Projects that had from 10 to 99 watchers (total: 3554; sampled: 36)

• Projects that had from 100 to 999 watchers (total: 286; sampled: 3)

This way, we obtain a set of 342 GIT repositories. We then discard those having a too poor structure, which we define as less than 10 metaedges in their Metagraph. We finally obtain a set of 87 projects, listed in Tables I and II.

B. Patterns and Metagraph Properties

As explained above, we define patterns as polygonal induced subgraphs of our Metagraphs. We limit our analysis to patterns from size 3 to size 10, because small patterns are trivial and large patterns are too costly to compute. There are 125 non-isomorphic patterns within this size range. For instance, there is only one pattern of size 3, which corresponds to a triangle. Figure 2 shows all patterns of size 4 and 5.

To ease the references to each pattern in the following, we use some arbitrary nicknames, composed by the greek name of numbers from three to ten and by a numerical index. Table III summarizes the information about the "families" of patterns we consider. The third column reports the number of existing non-isomorphic instances of each pattern.

It is important to recall that any pattern can only occur in a Metagraph of a commit history where two or more parallel lines of development exist, since patterns are composed by structural nodes, which by themselves imply the existence of more than one branch. Thus, whenever a pattern is found in a Metagraph, it is implied that those nodes whose in-degree and out-degree is equal to 1 within the pattern are actually linked to other nodes of the Metagraph, which are not part of the same pattern.

We define two sets of patterns, named increment and integration. All patterns having a slenderness greater or equal to 0.5 are assigned to the first set, while the others fall into the second.

In the following, we use the expression category to refer to any of the families and sets of patterns we just defined.

C. Implementation

In order to perform our analysis, we developed a toolset called GitWorks, as a pure Java application. GitWorks uses JGit 1 to extract information from GIT repositories, then build 1 http://eclipse.org/jgit/ Metagraphs and extract several features from the collected data. GitWorks is freely available on GITHUB 2 .

In order to extract the occurrences of patterns in the Metagraph, we use the Grochow-Kellis subgraph detection algorithm, based on symmetry breaking [START_REF] Grochow | Network motif discovery using subgraph enumeration and symmetry-breaking[END_REF]. The implementation of the algorithm has been provided by the authors.

D. Research Questions

R.Q. 1 -Can we find significant recurring structures in DVCS histories?

Our purpose is to see whether there are patterns in commit histories which repeatedly occur. For smaller patterns (e.g., of size 3 and 4), such a phenomenon can be an explicit choice of developers, which implies that such patterns are found useful for their collaborative job. For larger patterns, repeating occurrences can be considered emergent features of the topology of the repository. We want to study their relation with the structure of the commit history and with the activity of the developers.

R.Q. 2 -Does the structure of DVCS evolve over time?

If structural patterns can be detected, we want to understand how they change along the history of a project, i.e. whether some collaboration patterns are more frequent at the beginning of a project or in its maturity. This may be relevant for a further analysis of each repository. If a commit history is morphologically characterized by specific patterns at specific stages of its evolution, it may be worth investigating for information about the way developer collaboration change over time.

R.Q. 3 -Is the occurrence of patterns correlated with increased concurrent development activities?

2 https://github.com/marbiaz/GitWorks Whenever patterns appear, they may signal a particular increase of activity in the project. Patterns that tend to appear whenever activity increases or decreases may then be correlated to the strengthening of the project in terms of development or code base.

R.Q. 4 -Are there structural similarities among DVCS histories?

We aim at finding evidences of the existence (or the lack thereof) of same subgraphs in unrelated projects. Such a finding would indicate that there are "universal" patterns of development collaboration. This could then highlight common problems or strong points of different development communities.

IV. EXPERIMENTAL RESULTS

In this section, we present the outcomes of our analysis and discuss their relevance. We first present our results related to the properties of the Metagraphs and the detection of patterns. Then we discuss their meaning and propose our answers to the research questions.

A. Metagraph Properties

The Metagraphs that model the commit graphs of our sample are indeed quite diverse, from very simple parallel organization to very complex structures. Figure 5 depicts a topologically rich Metagraph.

In order to spot relevant characteristics, we analyzed basic Metagraph features (listed in Tables I and II) and layer-related properties.

Table IV shows the linear correlation between each couple of Metagraph features, plus the number of authors per repository, measured over the whole ensemble of repositories. Interestingly, Metagraph features are more correlated to the dimension of the developer community (number of authors) than to their total amount of contributions (number of commits).

Metagraph's layers present high variability in terms of time range: from few seconds to hundreds of days elapse between two consecutive layers. We thus measured, in each Metagraph the time range spanned by layers and we tested the correlation of their minimum, median and maximum value with the properties of their respective Metagraphs, defined in Section II-A. Among the reported values, we see a fairly high correlation between diameter and layer maximum density. It indicates that the two sizes of the Metagraphs are positively correlated: the more the layers in a Metagraphs, the more they tend to be dense. Thus incremental development and synchronization practices follow a similar trend.

The inverse correlation between diameter and minimum layer time range is also noteworthy. The more the layers, the shorter is the time span they tend to cover

B. Patterns

We first detect, in each repository Metagraph, all patterns from size 3 to size 10. Figure 6 shows, for each Metagraph, the number of patterns belonging to the increment and integration categories.

The Metagraphs are sorted according to the number of increment patterns. It is visible a trend that somehow backs up the correlation values in Table V. Integration patterns tend to be more as the number of increment patterns grows, but the trend seems to be stable only for larger repositories (which happen to be on the right side of the plot).

We also notice that integration patterns are found in smaller repositories where increment patterns are not. This outcome is due to the fact most of pattern of size s < 5 fall into the integration category.

In order to investigate if and how the properties of the Metagraph are associated with occurrences of patterns, we analyze the relations between patterns and the structural properties of the Metagraph (diameter, layer width and density).

Figure 8 shows the occurrences of patterns in one of the largest Metagraphs of our sample. The same figure also gives a synopsis of layer densities and widths. All patterns, but tri and to some extent tetra * , seem to be particularly sensitive to layer properties, thus clustering more where layers are denser. Patterns occur at different moments of projects histories. Figure 7 shows the distribution of timestamps of Metagraphs vertexes belonging to patterns for each category we defined. Data are aggregated over all the Metagraphs, thus we normalize the timestamps in the interval [0..1], by simply computing the relative displacement of every commit timestamp w.r.t. the minimum and maximum timestamp in each Metagraph. The boxplots are standard interquartile plus whiskers to cover 95% of data points. Outliers are not shown, to improve legibility.

For instance, the boxplot related to the tetra * category shows that, considering the whole ensemble of repository in our sample, these patterns occur anywhere after 10% of the age of a repository is elapsed, half of them is found in the last 20% of repository lifetime (check the position of the median) and they get closer to each other in time as projects grow old (check the different size of the two halves of box and whiskers).

We see how patterns of higher size tend to occur later than smaller ones. The skew towards the top is somehow biased by the fact that we compare project of different age and size, thus, in our case, the normalization of outcomes of smaller project tends to give high values. Nonetheless, it is true that larger patterns are definitely more numerous in the second half of projects' life.

The first two boxplots show that increment patterns tend to occur substantially later than integration pattern.

Table VI presents the results of a comparative analysis of the number of authors and commits among metaedges which belong to patterns and which do not. In order to summarize a large amount of data, we present these results as dominance scores of the main aggregates. Each triplet reports the number of projects where a given aggregate (i.e., minimum, median or maximum) measured in a pattern is less_than-equal_to-greater_than the same aggregate measured in metaedges non belonging to a pattern. For instance, the first case on the left tells that the minimum number of distinct authors in metaedges belonging to increment patterns is greater than the minimum of metaedges non belonging to any patterns in 40 projects out of 59. Only projects where the considered patterns appear are taken into account, thus the triplets sum up to less than 87.

We see that pattern metaedges consistently dominate the others w.r.t. the minimum and the median number of distinct authors, while they usually carry less sequential commits.

-0-0 21-0-0 octa* 0-4-13 2-7-8 12-3-2 4-13-0 16-1-0 17-0-0 enna* 0-4-15 2-6-11 14-4-1 4-15-0 17-0-2 18-0-1 deca* 0-2-13 2-4-9 12-2-1 2-13-0 14-0-1 15-0-0

C. Discussion

As said, the definition of Metagraphs as models of commit graphs allows a novel kind of topological analysis of repositories.

Several properties of the Metagraphs offer interesting standpoints for further analysis of single projects. The results we present aggregate measures of diverse repositories and are not meant to offer a precise description of any of them. They rather point out interesting features which shall be further investigated both at the aggregate level and project by project, in order to reveal their specific importance.

In the following, we discuss our results by recalling and answering our research questions.

R.Q. 1 -Can we find significant recurring structures in DVCS histories?

Answer -The patterns we discover are the very evidence of concurrent development in a GIT repository. As Figure 8 shows, in general patterns, and most of all smaller ones (size 3 to 5), are distributed across Metagraph layers. This means that they are not related to a particular "development stage" of the software (which may be identified at given sets of subsequent layers), but rather to the parallel development process itself.

Nonetheless, most patterns are found where the "footprint" of the Metagraph (the layer width and density) increase. This dependence on the topology of the Metagraph is stronger as the patterns get larger. But we could find no evident commonality among the "footprints" of the various Metagraphs.

These findings are common to several of the largest Metagraphs, the exception occurring mostly among the smaller projects. So far, we can say that, while smaller patterns are usually independent from a given topology and common to more repositories, others are strongly related to the structure of the Metagraphs and seem to occur in repositories having similar structures, in terms of diameter, layer width and density.

This outcome somehow supports the hypothesis about the intentionality of patterns: smaller patterns are direct product of developer decisions (they decide to involve one, two or three branches in some operation), while larger patterns emerges where the topology of the Metagraphs can support them.

A further analysis of each project, which combine the characterization of the Metagraph topology and its patterns with information about developer activity history and state of the software (bug tracks, release issues, etc.) could potentially achieve interesting novel insights on the collaborative development process.

R.Q. 2 -Does the structure of DVCS evolve over time?

Answer -Figure 7 shows that patterns mostly appear later in time, if not "in space". We find an interesting distinction between the timing of codebase evolution and the changes in its commit topology, at least as described in terms of Metagraph layers. The number of layers appears to grow faster as the project get older, which may mean that authors get more confident about merging and branching practices, or simply that more authors join a project.

We cannot attempt a generalization of this trend, because of the limited size of our sample and because of what we can consider an "internal bias" of several large repositories. We found that many of them have been automatically converted to GIT from a pre-existing CVCS. They thus initially exhibit a mostly linear topology which, e.g. for long-lasting successful projects, can encompass a significant portion of their total age. Wherever the topology starts becoming complex and the Metagraphs denser, we see that layers do not subscribe to any regularity w.r.t. the pace of collaboration. We find layers whose time span is of few seconds and others which encompass several months. This fact may suggest that automatic merging is used in the first case. But, depending on the number of separate branches belonging to the layers, it may simply reveal highly synchronous development activity.

Thus, if we can see that larger patterns do tend to occur later in time w.r.t. smaller ones, we cannot answer so far an interesting question: whether is there a feed-back loop between the structural complexity of a commit history (the Metagraph getting longer and denser) and the behavior of the developers (the fact that they branch and merge within shorter time).

We think that deepening this kind of analysis may reveal specific practices of integration and development which may affect the quality of the code, either positively or negatively.

R.Q. 3 -Is the occurrence of patterns correlated with increased concurrent development activities?

Answer -We found some apparently conflicting evidences in our outcomes, summarized in Table VI.

On the one hand, we see that pattern metaedges present a higher concentration of authors w.r.t. most of other metaedges. On the other hand, they do not seem to carry a particularly high number of internal commits. Based on the first observation, we can say that patterns do identify portions of the commit history where authors collaboration becomes more evident. At the same time, quite clearly higher collaboration does not entail a higher number of commits per branch.

Our hypothesis -which will need a more thorough analysis of the single projects to be confirmed -is that commits that brings most novelties to a codebase are made by fewer authors, who work in branches which do not directly end up in patterns, but merge with other "local integration" branches, which then lead the modifications to the main integration structures. Thus, metaedges which comprise higher numbers of authors do not include higher numbers of commits. This is an interesting finding that open a novel perspective on how to determine the strength and the extent of author collaboration in a distributed project. By combining the analysis of author presence in metaedges with, for instance, code-based analysis about authors modifying the same files or components, it is possible to deepen the comprehension of collaboration practices in developer communities.

R.Q. 4 -Are there structural similarities among DVCS histories?

Answer -We can positively answer this question and from two diverse perspectives.

First, as Table IV shows, the structural properties of commit histories are more correlated with the size of the developer community than with the number of commits they produce. Thus it is reasonable to think that projects whose community size is close would exhibit structures of similar richness, at least from the standpoint of aggregate measuring.

Then, we find the same patterns in otherwise very diverse software repositories. Figure 6 shows that increment patterns tend to occur more, but repositories with a richer structure tend to have anyway a higher number of occurrences of both categories. The occurrence of same patterns in unrelated software repositories suggests that development practices of different teams produce similar topologies in the repositories. Common patterns across repositories may reveal common vantage points or flaws in the way the software is developed, which may impact the quality of the software product itself.

Patterns that rarely occur in our repository sample are interesting as well. Their occurrence may be related to a particular necessity or may happen only in specific topologies. If further analysis found that they present some drawback, it would be interesting to understand which structural configuration let them emerge, in order to devise better practices.

D. Threats to validity

The reasons behind the detection of patterns in commit histories may be questioned, given the absence of evidences that support their relevance. In this paper, our main effort is giving some empirical evidence of the fact that these common sub-structures occur in complex development histories, though they may be hidden in a standard commit graph topology.

We present results which concern patterns of maximum size equal to 10. It is certainly feasible and interesting to scale up, though the computation of all possible polygons of a given size gets exponentially harder as the size increases. Anyway, the main purpose of the present work is to show relevant characteristics that, to some extent, are common to pattern of different size and are mainly due to their topological properties.

Our repository sample is of limited size, thus some of our results may not generalize on larger ensembles. It has then been chosen with no known bias towards any specific topological structure. Due to the novelty of the analysis, though, it is possible that we are not aware of specific features of the Metagraph topology, which somehow affect the emergence of the patterns.

Finally, the toolset we used to perform the computations has been developed by us and manually tested. We cannot exclude the presence of unnoticed bugs which could affect the correctness of our results. The subgraph detection algorithm has been provided by its author and has not been thoroughly tested by us.

V. RELATED WORK

The works which use graph-based techniques to analyze repositories focus either on characterizing the sourcecode, or on finding patterns in the social networks of developers.

In the first group, Posnett et alii propose models derived from ecological inference to analyze code at different hierarchical levels (files, packages, modules) [START_REF] Posnett | Ecological inference in empirical software engineering[END_REF]. They show that properties inferred at a given level may not hold at a different one or often be mistakenly considered to hold in general.

Demeyer et alii [START_REF] Demeyer | Finding refactorings via change metrics[END_REF] propose metrics to detect refactoring. Valverde e Solé [START_REF] Valverde | Logarithmic growth dynamics in software networks[END_REF] show how large scale software architectures can be modeled by dynamic logarithmic networks.

These and similar works focus on the content of contributions, rather than on the topology of commit histories.

In the second group, Posnett et alii propose graph-based models to infer developer focus [START_REF] Posnett | Dual ecological measures of focus in software development[END_REF], showing correlation with bug occurrences and issue solving performance. Bhattacharya et alii [START_REF] Bhattacharya | Graphbased analysis and prediction for software evolution[END_REF] combine the analysis of code organization and developer networks. They characterize both in terms of graph metrics and they show how it is possible to predict several indicators of software quality by using these metrics.

In [START_REF] Valverde | Self-organization versus hierarchy in opensource social networks[END_REF] the authors analyze how different social organizations of developers impact the quality of the development in open source communities.

Several relevant works target open source software development [START_REF] Mockus | A case study of open source software development: the apache server[END_REF], [START_REF] Rodriguez-Bustos | How distributed version control systems impact open source software projects[END_REF]. A recent paper [START_REF] Thung | Network structure of social coding in github[END_REF] analyze the social structure of developer networks on a large sample of GITHUB projects.

These works apply complex network theory to the analysis of interactions among developers and to the characterization of their contribution to projects.

A thorough analysis of GITHUB-based software development, with a deep comparative analysis of centralized and decentralized versioning systems is given in [START_REF] Brindescu | How do centralized and distributed version control systems impact software changes?[END_REF].

Though recent publications pay more and more attention to GIT-based repositories and their distributed development paradigm [START_REF] Shihab | The effect of branching strategies on software quality[END_REF], [START_REF] Dabbish | Social coding in github: transparency and collaboration in an open software repository[END_REF], to the best of our knowledge no study focuses on the characterization of the topology of commit histories.

VI. CONCLUSION

Decentralized version control systems produce structurally rich commit graphs. The commit history of projects that use these systems is thus a highly non-linear graph, whose topology can be analyzed by means of techniques, which are typical of complex graph analysis.

As for many other domains, rich and complex commit histories incorporate recurring substructures that reveal similarities among otherwise unrelated projects. They characterize the development process from a purely topological standpoint. We discuss in this paper the reasons why the analysis of commit graph topology is relevant and the challenges of such a task.

We define the Metagraph, a novel data structure that makes it possible to perform a topological analysis of commit history graphs, in order to detect recurrent subgraphs hidden in their structure. We define and analyze several topological properties of the Metagraphs and we identify a class of subgraphs that we call patterns, which may be consider building blocks of the very topology of Metagraphs.

We find empirical evidences of the recurring presence of several patterns in a sample of open source GIT repositories available on GITHUB. We analyze the characteristics of these patterns and their relations with the properties of the repository Metagraphs. Our results support the conclusion that commit histories of otherwise unrelated projects are characterized by rich topologies, which exhibit similar properties and feature common patterns. These findings open several different research directions. We plan to dig further the relation between patterns and properties of commit graphs, such as number of commits, authors and size of commit changesets. We think it is possible to devise novel models to characterize developer collaboration, which are based on common contributions to the same metaedges or patterns of a given Metagraph.

The novel kind of analysis we propose is not an alternative, but rather a complement to all existing techniques. By focusing entirely on topological features, it can guide to new insights on the emergent properties of distributed collaborative development.

Fig. 1 .

 1 Fig. 1. Example of commit history to Metagraph transformation

Fig. 2 .

 2 Fig. 2. Patterns of size 4 and 5.

Fig. 3 .

 3 Fig. 3. Isomorphic simple acyclic digraphs of degree 2.

Fig. 4 .

 4 Fig. 4. Patterns of size 10 showing a different slenderness.

Fig. 5 .

 5 Fig. 5. Metagraph of the ace project. Root at the bottom; other red nodes are branches' heads.

Fig. 6 .

 6 Fig.6. Occurrences of increment and integration patterns.

Fig. 7 .Fig. 8 .

 78 Fig. 7. Distribution of timestamps of structural commits per pattern.

TABLE I .

 I THE GIT REPOSITORIES UNDER STUDY -PART I. THE COLUMNS REPORT THE PROJECT'S NAME, THE NUMBER OF COMMITS, THE NUMBER OF EDGES AND NODES OF ITS Metagraph.

	Project	commits	edges	nodes
	OpenLeague	43		25
	BroadleafCommerce	4722	784	496
	Fridgemagnet	67		10
	AutoSave	124		12
	OryzoneBoilerplateBundle	60		14
	ketama	18		7
	Edaha	185		9
	Tolmey	61		21
	Ai_Class_Octave_Functions	23		10
	WPide	152		17
	sexpistol	37		10
	ace	3220	1139	693
	contracted	72		8
	gitpython	163		25
	tcesp	81		18
	bempp	1530	375	246
	FReD	211		31
	testlol	77		9
	configs	40		14
	pool	42		10
	q4wine	966		54
	pylibemu	59		8
	sarah	312		14
	ConcurrenTree	632		59
	ProWiC	61		22
	java	95		33
	flour	209		29
	Telephus	272		43
	arkilloid	177		27
	RLLVMCompile	87		15
	pants	643		40
	pelm	415	103	68
	jump	49		23
	a4a	206		46
	PySynergy	278		16
	caveman	211		14
	cocoagit	756		57
	stsh	239		26
	zap	28		7
	iamhanchang	600	202	123
	Locke	29		8
	ConfigServiceProvider	43		12
	Twittia	86		11
	MiniCart	124		11

TABLE III .

 III THE PATTERNS WE CONSIDER.

	Name	Size	How many
	tri	3	1
	tetra*	4	3
	penta*	5	3
	exa*	6	8
	epta*	7	9
	octa*	8	20
	enna*	9	28
	deca*	10	53

TABLE IV .

 IV METAGRAPH FEATURES CORRELATIONS.

		nodes	edges	commits
	edges	0.99978	-	-
	commits	0.86953	0.86000	-
	authors	0.91235	0.91190	0.77873

Table V

 V shows the resulting Spearmans' correlation values. It only reports values that have been found statistically significant, with p -values << 0.01.

TABLE VI

 VI

	.	DOMINANCE COUNTS FOR AUTHORS AND COMMITS IN
			PATTERNS.
	Patterns		Authors			Commits
		min	med	max	min	med	max
	increment	1-18-40	10-33-16	34-19-6	21-35-3	57-1-1	56-1-2
	integration	1-24-46	7-34-30	41-20-10	26-44-1	65-4-2	63-2-6
	tri	1-24-46	9-33-29	40-19-12	26-44-1	64-5-2	63-2-6
	tetra*	1-16-38	9-30-16	31-18-6	18-35-2	54-1-0	53-0-2
	penta*	0-9-26	7-15-13	24-9-2	9-26-0	32-2-1	33-0-2
	exa*	0-7-25	4-17-11	19-8-5	8-23-1	30-1-1	31-1-0
	epta*	0-5-16	2-11-8	15-4-2	5-16-0	21

VII. ACKNOWLEDGMENTS

The authors thank Joshua Grochow, who kindly provided the sourcecode of his algorithm, and Nataliia Bielova for their help and fruitful discussions. This work is partially supported by the EU FP7-ICT-2011-9 No. 600654 DIVERSIFY project and by the rgion Bretagne SoftLive project.


F Anstett-Collin

J Goffart
email: jeanne.goffart@univ-savoie.fr

L Denis-Vidal
email: lilianne.denis-vidal@math.univ-lille1.fr

Sensitivity analysis of complex models: coping with dynamic and static inputs

Keywords: Global sensitivity analysis, dynamic and static inputs, Karhunen-Loève expansion, building energy model

In this article, we address the issue of conducting a sensitivity analysis of complex models with both static and dynamic uncertain inputs. While several approaches have been proposed to compute the sensitivity indices of the static inputs (i.e. parameters), the ones of the dynamic inputs (i.e. stochastic fields) have been rarely addressed. For this purpose, we first treat each dynamic as a Gaussian process. Then, the truncated Karhunen-Loève expansion of each dynamic input is performed. Such an expansion allows to generate independent Gaussian processes from a finite number of independent random variables. Given that a dynamic input is represented by a finite number of random variables, its variance-based sensitivity index is defined by the sensitivity index of this group of variables. Besides, an efficient samplingbased strategy is described to estimate the first-order indices of all the input factors by only using two input samples. The approach is applied to a build-

Introduction

Nowadays, one important feature when designing high-performance buildings is to reduce the energy consumption, for both economical and environmental purposes. Thus, the need for a better control and optimization of the energy consumption of buildings and houses arises since last three decades. In this framework, softwares for thermal building performance simulation have been developed and are constantly updating due to the evolution of construction techniques and materials. This leads to complex, high-dimensional and multi-physics models, presenting uncertain inputs due to measurements, expert judgements or simply ignorance. Thus, the problem of the reliability of these models arises. Sensitivity Analysis (SA) can help evaluating the impact of this lack of knowledge onto the model responses. SA aims at determining the most influential input factors onto the model responses. Numerous studies, in many different application fields (see for example [START_REF] Saltelli | Sensitivity Analysis[END_REF][START_REF] Blatman | Sparse polynomial chaos expansion and adaptive stochastic finite element using a regresion approach[END_REF][START_REF] Borgonovo | A new uncertainty importance measure[END_REF][START_REF] Cukier | Nonlinear sensitivity analysis of multiparameter model systems[END_REF][START_REF] Frey | Identification and review of sensitivity analysis methods[END_REF][START_REF] Sobol | Sensitivity estimates for nonlinear mathematical models[END_REF][START_REF] Kiebre | Sensitivity analysis for the study of influential parameters in tyre models[END_REF]), have focused on the sensitivity analysis of models with static inputs (i.e. parameters). Global SA is generally preferred because the input factors are varied simultaneously in a large uncertainty range and can reveal possible interactions between the inputs. Global SA are often based on the analysis of the model response variance and are known as ANOVA (ANalysis Of VAriance) methods [START_REF] Homma | Importance measures in global sensitivity analysis of model output[END_REF][START_REF] Saltelli | A quantitative model independent method for global sensitivity analysis of model output[END_REF].

Regarding building energy modeling, existent surveys have only analysed the influence of static inputs onto building models, such as the effects of the materials thermophysical properties [START_REF] Tian | A review of sensitivity analysis methods in building energy analysis[END_REF]. However, some phenomena previously neglected for energy-consuming building may become preponderant in the consumption of low energy buildings 1 ,a st h ec o n s i d e r a t i o no fw e a t h e r data variability, not only the temperature but also the solar radiation, the relative humidity, the wind speed, etc. Indeed, it is expected that meteorological inputs play a crucial role in designing high-performance buildings. There are very few studies that try to assess the influence of the weather inputs because they are time-dependent (dynamic inputs). This can be explained by the fact that considering coherent long-term "typical" weather data is not obvious. As stated in [START_REF] Degelman | Simulation and uncertainty: weather predictions[END_REF], if the weather data, usually on an hourly basis are available, there is no need to simulate them. However, when the hourly data are lacking, there is a real need to simulate weather sequences. Even if they are available, sometimes it might only represent a few years of record which is anecdotal and cannot represent long-term typical weather. The only 1 The term "low energy consumption building" refers to standard for energy efficiency in buildings. This eco-label is assigned to buildings satisfying some standards, mainly related to the annual total primary energy consumption of the building. In France, the average annual requirement for heating, cooling, ventilation, hot water and lighting must be lower than 50 kWh/m 2 (in primary energy) for new buildings and lower than 80 KWh/m 2 for renovations. These limits are set by the French Ministry for Ecology, Energy, Sustainable Development and Territorial Development, according to the European Commission policy (see http://www.europarl.europa.eu/committees/en/home.html). The values can differ from one European country to the other, depending on their climate.

way to represent the full spectrum of weather conditions is to collect data from many years of hourly weather data. Very few weather sites have reliable contiguous weather data available for extremely long periods of time. Thus, an alternative is to simulate hourly weather data using a model. But, it is not straightforward to generate time series that satisfy the desired random field distribution.

The aim of this study is to assess the impact of uncertain inputs, such as the weather data and the thermophysical properties of materials, onto the heat consumption of an actual high-energy performance house. This problem is challenging because it implies to perform the sensitivity analysis of atimeconsumingcomputermodelwithuncertainstaticandspatio/temporal inputs. Such an issue is rarely addressed in the literature (for instance, in [START_REF] Lilburne | Sensitivity analysis of spatial models[END_REF]). The uncertain static inputs are treated as independent random variables defined by their marginal distribution while the dynamic inputs are treated as Gaussian processes (GP) defined by a temporal mean and a covariance function. In a Monte Carlo approach, sampling the independent static inputs can be achieved with a space filling sampler such as the Latin Hypercube sampling [START_REF] Helton | Survey of sampling-based methods for uncertainty and sensitivity analysis[END_REF] or a LPτ sequence [START_REF] Kuchrenko | The identification of model effective dimensions using global sensitivity analysis[END_REF]. It is more challenging to generate Gaussian processes and especially to assess their influence. AG Pc a nb er e p r e s e n t e da sas e r i e se x p a n s i o ni n v o l v i n gac o m p l e t es e t of deterministic functions with corresponding random coefficients [START_REF] Grigoriu | On the spectral representation method in simulation[END_REF][START_REF] Zhang | Orthogonal series expansions of random processes in reliability analysis[END_REF], as the truncated Karhunen-Loève (KL) expansion [START_REF] Huang | Convergence study of the truncated Karhunen-Loeve expansion for simulation of stochastic processes[END_REF][START_REF] Phoon | Simulation of second order processes using Karhunen-Loeve expansion[END_REF]. KL series expansion is based on the eigen-decomposition of the covariance function, involving orthogonal deterministic basis functions and the orthogonal uncorrelated random coefficients. This allows the optimal encapsulation of the informa-tion contained in the GP into a set of discrete independent random variables.

The GP can then be represented by a linear combination of the deterministic functions depending on time whose coefficients are independent random variables. For sensitivity analysis purposes, the influence of the dynamic inputs onto the model response is then given by the one of these random coefficients of the Karhunen-Loève decomposition, which is the originality of the present paper.

The paper is organized as follows. In Section 2, SA for static inputs is briefly recalled and then extended to inputs depending on time. The procedure to carry out a SA of model with uncertain static and dynamic inputs is provided. In section 3, the proposed approach is applied to a building energy model to quantify the impact of each weather data input and each thermophysical material properties on the energy performance of a real low-energy consumption house.

Sensitivity analysis

Model with static inputs

First, let us recall that variance-based sensitivity index is computed when the model is only function of static inputs. Consider the following model:

y(θ)=g(ω s (θ)) (1)
where y = {y 1 ,...,y m } is the set of m model responses of interest, g the model function which is known, ω s = {ω s 1 ,...,ω s Ns } the set of N s uncertain static inputs, θ 2 Ω where Ω is the space of random events. The stochastic variable θ represents the elementary event of a probability space. It is used to indicate the randomness of the input and the output. In the following, we assume that random variables ω s i are independent and defined by their marginal distribution.

The effect of the uncertain inputs ω s i onto y j can be assessed by its first-order sensitivity index given by:

S j i = V (E(y j |ω s i )) V (y j ) (2)
where V (E(y j |ω s i )) is the variance of the conditional expectation of y j when ω s i is set and V (y j )i st h et o t a lv a r i a n c eo ft h eo u t p u ty j .T h efi r s to r d e r sensitivity index S i represents the amount of variance of y j due to ω s i alone. The value of S j i lies between 0 and 1. The closer to 1 its value is, the more input ω s i contributes to the total variance of the output. In particular, when Ns X 1=1 S j i ⇠ 1t h er e l a t i o n s h i pb e t w e e ny j and the inputs ω s is additive. Then, S j i can be used to rank the inputs by order of importance. Sensitivity indices of higher order can also be computed to assess the influence of the input interactions but it is not presented here, see [START_REF] Saltelli | Sensitivity Analysis[END_REF] for more details.

The definition of the variance-based sensitivity index of one single input variable Eq.( 2) is easily extended to the sensitivity index of the group of input variables ω s u ⇢{ω s 1 ,...,ω s Ns } (also called the closed-order effect),

S j u = V (E(y j |ω s u )) V (y j ) (3)

Estimating the sensitivity indices with two LHS samples

Some models may be complex with a high number of inputs so that analytical calculations of the previous sensitivity index become time consuming or even impossible. It is therefore necessary to estimate them. For this purpose, several approaches have been proposed in the literature (e.g. [START_REF] Cukier | Nonlinear sensitivity analysis of multiparameter model systems[END_REF][START_REF] Blatman | Efficient computation of global sensitivity indices using sparse polynomial chaos expansions[END_REF][START_REF] Crestaux | Polynomial chaos expansion for sensitivity analysis[END_REF][START_REF] Frey | Identification and review of sensitivity analysis methods[END_REF][START_REF] Sudret | Global sensitivity analysis using polynomial chaos expansion[END_REF], among others). In the present work, the sampling-based method proposed in [START_REF] Mara | Comparison of some efficient methods to evaluate the main effect of computer model factors[END_REF] is employed for two reasons. Firstly, it only requires two Latin Hypercube (LH) samples [START_REF] Helton | Survey of sampling-based methods for uncertainty and sensitivity analysis[END_REF] to estimate all the first-order sensitivity indices. Secondly, it can cope with group of random inputs which is the key of our methodology to estimate the influence of dynamic inputs. Note that, although Quasi Monte Carlo sampling technique is known to have a better coverage of the input space [START_REF] Kuchrenko | The identification of model effective dimensions using global sensitivity analysis[END_REF][START_REF] Kucherenko | Comparison of Lagin Hypercube and Quasi Monte Carlo sampling techniques[END_REF], LHS is preferred here because we have to deal with a very high number of inputs (thousands) and the sampling design proposed in [START_REF] Mara | Comparison of some efficient methods to evaluate the main effect of computer model factors[END_REF] (similar to rLHS [START_REF] Mckay | Evaluating prediction uncertainty[END_REF]) is suited to LHS. Then, a second input LH sample Ω 2 is generated from Ω 1 by arbitrarily defining an independent rank matrix R 2 of size N s ⇥ d and setting,

Ω 2 = Ω 1 • R 2 .
Note that, the new Ω 2 is also an LH sample and this column-wise permutation trick is equivalent to the replicated LH sampling [START_REF] Mckay | Evaluating prediction uncertainty[END_REF]. After running the model with this new sample, a second model response vector

Y 2 = g(Ω 2 ) is obtained. The model responses Y 1 =[ y 1 1 ,...,y 1 d ]a n dY 2 =[ y 2 1 ,...,y 2
d ] allow to estimate the first-order sensitivity index of each static input as fol-lows,

Ŝj i = (N -1) -1 P Ns k=1 (y r i kj -μj 1 )(y 2 kj -μj 2 ) σj 1 σj 2 (4)
where, y r i kj is k-th element of the response vector obtained after reordering the y 1 j (j =1,...,m) accordingly with r i ,t h a ti s ,

y r i = y 1 j (r i ). ( 5
)
The empirical mean of the two response vectors y 1 j and y 2 j are respectively μj 1 and μj 2 while σj 1 and σj 2 are their respective standard deviation. We note that ( 5) is nothing but a reordering of the response vector y 1 j such that compared to y 2 j the values of each input variable have been varied except the sample of ω s i that has been fixed. Finally, if the sensitivity indices of groups of input variables are investigated (say K groups), then R 2 is a matrix of size N s ⇥K and the second sample Ω 2 is deduced by column-wisely permuting the values of Ω 1 such that the values of the variables in the same group are reordering identically. Equation (4) then estimates closed-order effect of the i-th group.

Model with static and dynamic inputs

Consider the following model presenting uncertain static and dynamic inputs:

y(t, θ)=g(ω d (t, θ), ω s (θ),t)( 6 )
where y of components {y 1 ,...,y m } is the vector of m model responses, As previously, we assume that random variables ω s i are independent and defined by their marginal distribution. We further assume that the random fields, indexed on a bounded domain D,a r eG a u s s i a np r o c e s s e s ,t h a t is,

t
ω d i ⇠GP(ω i d (t),C i (t 1 ,t 2 )), i =1 ,...,
i (t 1 ,t 2 )=σ 2 i e η i |t 2 -t 1 | n i .
According to [START_REF] Phoon | Simulation of second order processes using Karhunen-Loeve expansion[END_REF], the random field ω d i ,c a nbea p p r o x i m a t e du s i n gt h et r u ncated KL series:

ω d i (t, θ) ' ωi d (t)+ M i X ki=1 p λ ki ξ ki (θ)f ki (t)( 7 )
where λ ki and f ki are the deterministic eigenvalues and eigenfunctions of the covariance function C i (t 1 ,t 2 ), ξ i is a set of independent standard normal variables and M i is the number of KL-terms. In practice, we retain the first M i eigenmodes that contain the 95% of the variance of the input ω d i .T h en u mber of eigenmodes retained depends on the choice of the covariance function and may be very different from one input to another.

The key feature for simulating random fields using KL expansion lies on the ability to determine accurately the eigenvalues and eigenfunctions of the covariance function. They are given from the spectral decomposition of the covariance function C i (t 1 ,t 2 ), requiring to solve the homogeneous Fredholm integral equation of the second kind given by:

Z D C i (t 1 ,t 2 )f ki (t 1 )dt 1 = λ ki f ki (t 2 )( 8 )
For some covariance functions (first-order Markov or Wiener-Levy processes, for example), the equation ( 8) can be twice differentiable with respect to t 1 . The resulting differential equation can be solved analytically and eigenvalues can be obtained as well. But in most cases, solving equation [START_REF] Homma | Importance measures in global sensitivity analysis of model output[END_REF] requires numerical methods, such as the Galerkin one [START_REF] Ghanem | Stochastic finite elements -A spectral approach[END_REF]. To avoid tedious quadratures and alleviating computational effort, an alternative is to use a wavelet-Galerkin approach [START_REF] Phoon | Simulation of second order processes using Karhunen-Loeve expansion[END_REF][START_REF] Maleknejada | Using Wavelet for Numerical Solution of Fredholm Integral Equations[END_REF]. In this case, the representation of integral operators is made in wavelet basis and can be performed without numerical integration. The comparison of wavelet-Galerkin method with other available methods in solving the Fredholm integral equation can be found in [START_REF] Huang | Convergence study of the truncated Karhunen-Loeve expansion for simulation of stochastic processes[END_REF].

Once the eigenmodes are obtained for all the dynamic inputs ω d i (t, θ)u sing KL decomposition [START_REF] Kiebre | Sensitivity analysis for the study of influential parameters in tyre models[END_REF], the influence of ω d i (t, θ) is then given by the one of the random coefficients ξ ki (θ)p r o p a g a t e dt oy(t, θ). In fact, once the KL decomposition of a given dynamic input ω i (t, θ) is performed, the randomness of this dynamic input ω i (t, θ)l i e so nt h ei n d e p e n d e n ts t a n d a r dn o r m a l variables ξ ki (θ). Thus, the randomness of the dynamic input ω i (t, θ)ispr opagated to the output y through the associated modes ξ ki .T h ei n fl u e n c eo f the given dynamic input ω i (t, θ)o nt h eo u t p u ty is then represented by the one of all the modes ξ i associated to ω i (t, θ)i nt h eK Ld e c o m p o s i t i o n . T h e

Summary of the proposed approach

The computation of the sensitivity indices for model [START_REF] Sobol | Sensitivity estimates for nonlinear mathematical models[END_REF] presenting uncertain static and spatio/temporal inputs requires the following steps.

Generation of the static inputs

Use a random sampling scheme to generate the N s static inputs ω s i with the prescribed marginal distribution. (2) and ( 10).

Generation of the dynamic inputs

In the next section, the proposed approach is applied to a building energy model.

Application to a building energy model

Building energy model

The building energy model studied in this work represents a real building located on an experimental platform, introduced by the National Institute of Solar Energy and located in Chambéry, in France. This place presents at e m p e r a t ec o n t i n e n t a lc l i m a t ew i t ha l p i n ei n fl u e n c e . T h eb u i l d i n gi sa single-detached house with low energy consumption (figure 1). The house has double-glazed on each facade except at the north one where it is tripleglazed. The thickness of the wall is 50 cm, made of 15 cm of perpend, 20 cm of insulating material and again 15 cm of perpend. The house contains hundreds of sensors to quantify its thermal behavior. Details about the house can be found in [START_REF] Spitz | Pratical application of uncertainty and sensitivity analysis on an experimental house[END_REF] and in the table provided in the appendix.

The building is divided into several thermal zones, but only the living rooms The 51 uncertain static inputs (N s =51)represen tthethermoph ysicalproperties of the material as its density, the thermal conductivity, the transmissivity at each facade, the albedo, the airtightness at the different floors, ... They are listed in Appendix A. All the static inputs follow a Gaussian distribution with standard deviation equal to 5% of the mean value, except for the airtightness. In fact, the airtightness is one of the most uncertain static inputs in the building thermal behavior. Anormal distribution with standard deviation equal to 25% of the mean value is assumed for this parameter. The six uncertain dynamic inputs (N d =6 )r e p r e s e n tt h ew e a t h e r data as the outdoor air temperature, the direction and speed of wind, the direct and diffuse radiation and the relative humidity.

A previous study [START_REF] Goffart | Generation of stochastic weather data for uncertainty and sensitivity analysis of complex energy systems[END_REF], not presented here, has focused on the statistical analysis of the weather data. One month of january representative of typical winter from 20 years of observations has been used, since the heat consumption is the highest and the most costly, during this period of time, at this place. Moreover, considering only one season allows to respect stationarity of data. From the study in [START_REF] Goffart | Generation of stochastic weather data for uncertainty and sensitivity analysis of complex energy systems[END_REF], the statistical characteristics of a given input, the covariance function and the hourly mean, on one day, has been determined.

From the hourly mean ωd i and the covariance function C i (t 1 ,t 2 ), the sample generation of the dynamic inputs ω d can be carried out, as explained in Section 2, using the Fast Haar wavelet algorithm to solve the Fredholm integral [START_REF] Homma | Importance measures in global sensitivity analysis of model output[END_REF]. To do so, the Matlab software has been used. This leads here to 512 modes for each of the six inputs, that is M i =5 1 2 ,8i = {1,...,6}. The 51 uncertain static inputs are generated using Latin Hypercube sampling, according to their prescribed distribution (Gaussian distribution with mean value and standard deviation given in Appendix A). Here, 2 sets of 1000 samples are used to estimate the sensitivity indices ( 2) and ( 10), according to the estimator provided in [START_REF] Mara | Application of global sensitivity analysis of model output to building thermal simulations[END_REF]. Then, the model is simulated with the generated static and dynamic inputs, using the dedicated software EnergyPlus [START_REF] Crawley | Energyplus: creating a new generation building energy simulation program[END_REF]. Each simulation lasts 1 minute. The computational time for 2000 simulations is approximatively 32 hours, but with a quad core it can be reduced to 8 hours.

Results

Figure 2 shows the dispersion of the ideal heat consumption, at the ground and first floors. The consumption mean value is 9.25 ⇥ 10 8 Jw ithav ariance of 9.44⇥10 15 at the ground floor and 9.32⇥10 8 Jwithavarianceof4.90⇥10 15 at the first floor. The heat consumption is almost the same at the ground and first floors but with a slight prevalence of the first floor. The two thermal zones under study have the same surface but there is more glass surface at the ground floor, especially at south facade. Thus, it may be assumed that the solar gain is more important at this floor, during winter.

Figure 3 shows the sensitivity indices at each floor. At the ground floor, the direct solar radiation has the highest sensitivity index (0.48), explaining almost 50% of the heat consumption dispersion. Then, the temperature and the airtightness follow (0.30 and 0.13, respectively). However, for the first floor, the airtightness and the outdoor temperature have almost the same sensitivity index (0.42 and 0.38, respectively), followed by the direct solar radiation (0.21). The airtightness is more influent at the first floor since the direct solar radiation is less influent at this floor. On the other hand, the sensitivity indices of the other parameter can be neglected showing that they are not influential. It is worth noting that these inputs are not influential in the studied model. This conclusion can be different for other models, in the way these variables are taken into account for the calculation of the energy balance. For example, humidity is not relevant here because the ideal heating device considered does not account for the impact of the humidity onto the consumption.

To sum up, at each floor, only 3 inputs among the 57 are influent. Among these 3 inputs, only one static input is influent here (airthightness) and 2 dynamic ones (outdoor air temperature and direct solar radiation), in a different proportion according to the given floor. It can be noticed that the total sensitivity indices are 0.92 for the consumption at the ground floor and 1 for the consumption at the first floor, showing insignificant interaction between inputs.

To conclude, the results highlight the capacity of the passive house to exploit the solar gains during winter, especially at the ground floor. In fact, the solar radiation has a greater impact on a high-insulated passive building than on an energy-consuming one. This is relevant to minimize the heat consumption during winter in this kind of low energy house.

Conclusion

In this paper, a method to perform sensitivity analysis of complex models presenting uncertain static and spatio/temporal inputs has been provided.

While assessing the influence of a static input of computer models is common, it is an issue to estimate the influence of a dynamic input. For this purpose, the latter is treated as a random process and its eigen-decomposition is performed. This is achieved with the Karhunen-Loève transformation. Then, the influence of the random process of interest is given through the one of its eigenmode variables. Finally, the influence of the random process can be quantified using the well-known Sobol' sensitivity indices for group of variables. Subsequently, a sampling-based strategy has been used to compute the closed-order effect of the group of variables with only two samples. This approach has been applied to a building energy model. The latter is defined by a set of 51 uncertain parameters and 6 stochastic weather inputs.

It was found that only four input factors were relevant for predicting the energy needs of the passive house. In this case, sensitivity analysis can be seen as a tool to help designing strategies to reduce the energy consumption of passive houses.

  Let us consider an LH sample Ω 1 of the static inputs of size N s ⇥ d and denote by Y 1 = g(Ω 1 )theassociatedmodelresponsev ector(av ectorofsize N s ⇥ m). We denote by R 1 the rank matrix associated with Ω 1 .W er e c a l l that R 1 =[ r 1 ,...,r d ]i sd e d u c e df r o mΩ 1 by column-wisely replacing the smallest value of Ω 1 by 1 and the highest value by N s . As a consequence, an element of r i (i =1,...,d)i sa ni n t e g e rw i t h i n[ [ 1 ,N s ]] .

3 .

 3 (a) Perform a 2D wavelet transform of C i (t 1 ,t 2 ), using the Fast Haar wavelet transform algorithm to obtain the eigenvalues λ ki and the eigenfunctions f ki . (b) Use a random sampling scheme to generate the independent standard normal variables ξ i . (c) Generate the N d dynamic inputs ω d i using (7). Computation of the sensitivity indices (a) Simulate the model with the generated dynamic and static inputs, ω d and ω s ,t oo b t a i nt h em od e lr e s po n s ey(t, θ)( e q . 6 ) . (b) Compute the sensitivity indices of {ξ 1 ,...,ξ N d , ω s },accordingto

  at the ground and the first floors are studied. The solar gains are maximized in winter and minimized in summer thanks to the glazed surfaces distribution and solar shading. The goal of the study is to quantify and characterize the capacity of the building to exploit environmental energy gain, taking into account uncertainties of material properties and natural variability of weather data. The outputs of interest are energy needs at the ground and at the first floors (m =2)inordertomain tainthermalcomfortintheserooms. Theseoutputs are the most important ones for the designer to assess the building performance. Very often, the technical choices made during the design stage aim at decreasing the energy need. The model involves 57 uncertain input factors, among them, 51 are static inputs and 6 are dynamic inputs.

The figures 4

 4 to 9 show, for each dynamic input, the cumulative distribution function of the 24 time steps (hours) for every day of january. The left figure shows the cumulative distribution function randomly chosen over the 1000 samples. The right figure shows the cumulative distribution function from the source file used to extract the statistical characteristics of the dynamic inputs.

  Figure 1: INCAS passive house

Figure 2 :

 2 Figure 2: Data dispersion for the heat consumption at the ground and first floors. The central mark in red is the median and the edges of the blue box are the 25th and 75th percentiles.

Figure 3 :

 3 Figure 3: Sensitivity indices for the heat consumption at the ground floor and first floor

Figure 4 :

 4 Figure 4: Cumulative distribution function for the outdoor air temperature -left: generated samples, right : source file

Figure 5 :

 5 Figure 5: Cumulative distribution function for the direct solar radiation -left: generated samples, right : source file

Figure 6 :

 6 Figure 6: Cumulative distribution function for the diffuse solar radiation -left: generated samples, right : source file

Figure 7 :

 7 Figure 7: Cumulative distribution function for the relative humidity -left: generated samples, right : source file

  2D⇢R the time variable, ω d of components {ω d 1 ,...,ω d N d } the set of N d uncertain dynamic inputs (random fields) depending on time t. As previously, ω s of components {ω s 1 ,...,ω s Ns } is the set of N s uncertain static inputs (random variables). It can be worth noting that in another context, t can also represent the space variable instead of the time. In this case, the following still holds.

Acknowledgment This work has been supported by French National Research Agency (ANR) through HABISOL program (project FIABILITE n • ANR-10-HABISOL-004-02) and by the French National Research Center through ASenDyn PEPS project.

sensitivity index of the modes grouped together represent the influence of the dynamic input ω i (t, θ).

Consider the M i -dimensional random coefficient ξ i ,g r o u p i n gt h eM i modes of the input ω d i :

Thus, SA of the model output y(t, θ) is performed through the random vectors {ξ 1 ,...,ξ N d , ω s },w i t hξ i given by [START_REF] Saltelli | A quantitative model independent method for global sensitivity analysis of model output[END_REF]. Consequently, the effect of the group of factors ξ i is the one of the dynamic input ω d i and so on. The sensitivity indices of the group of factors ξ i = {ξ 1i ,...,ξ M i i } can be computed as:

where V (E(y j |ξ 1i ,...,ξ M i i )) is the variance of the conditional expectation of y j when ξ 1i , ξ 2i ,... and ξ M i i are set.

The sensitivity of the static input ω s can then be computed using [START_REF] Blatman | Sparse polynomial chaos expansion and adaptive stochastic finite element using a regresion approach[END_REF].

The proposed approach is an alternative to the Pick and Freeze method [START_REF] Fort | Estimation of the Sobol indices in a linear functional multidimensional model[END_REF][START_REF] Gamboa | Sensitivity indices for multivariate outputs[END_REF][START_REF] Janon | Asymptotic normality and efficiency of two Sobol index estimators[END_REF]. However, the Pick and Freeze method is computationally demanding because it requires N ⇥(N d +1) model runs where N d is the number of input factors and N is the sample size. In our study, we employ the random balance design trick (also used in replicated Latin Hypercube [START_REF] Mckay | Evaluating prediction uncertainty[END_REF]) that allows to estimate the entire set of first-order sensitivity indices with only two samples of size N (see [START_REF] Mara | Comparison of some efficient methods to evaluate the main effect of computer model factors[END_REF]).

The proposed approach is summed up in the next section.