Yvonne Anne Pignolet

Matthieu Roy

Stefan Schmid

Gilles Trédan

Gilles Tredan

The many faces of graph dynamics

Keywords: Network dynamics, Graph evolution PACS numbers: 89.20.Ff: Computer science and technology, 05.10.-a: Computational methods in statistical physics and nonlinear dynamics

come

Introduction

How do real-world networks evolve with time? While empirical studies provide many intuitions and expectations, many questions remain open. In particular, we lack tools to characterize and quantitatively compare temporal graph dynamics. In turn, such tools require good observables to quantify the (temporal) relationships between networks.

In particular, the few network dynamics models that currently exist are often oblivious of the network type. This is problematic, as complex networks come in many different flavors, including social networks, biological networks, or physical networks. It seems highly unlikely that these very different graphs evolve in a similar manner.

A natural prerequisite to measure evolutionary distances are good metrics to compare graphs. The classic similarity measure for graphs is the Graph Edit Distance (GED) [START_REF] Gao | A survey of graph edit distance[END_REF]: the graph edit distance d GED (G 1 , G 2 ) between two graphs G 1 and G 2 is defined as the minimal number of graph edit operations that are needed to transform G 1 into G 2 . The specific set of allowed graph edit operations depends on the context, but typically includes node and link insertions and deletions. While graph edit distance metrics play an important role in computer graphics and are widely applied to pattern analysis and recognition, GED is not well-suited for measuring similarities of networks in other contexts [START_REF] Faloutsos | On power-law relationships of the Internet topology[END_REF]: the set of graphs at a certain graph edit distance d from a given graph G exhibit very diverse characteristics and seem unrelated; being oblivious to semantics, the GED does not capture any intrinsic structure typically found in realworld networks.

A similarity measure that takes into account the inherent structure of a graph may however have many important applications. A large body of work on graph similarities focusing on a variety of use cases have been developed in the past (see our discussion in Section 6). Depending on the context in which they are to be used, one or another is more suitable. In particular, we argue that graph similarities and graph distance measures are also an excellent tool for the analysis, comparison and prediction of temporal network traces, allowing us to answer questions such as: Do these two networks have a common ancestor? Are two evolution patterns similar? or What is a likely successor network for a given network? However, we argue that in terms of graph similarity measures, there is no panacea: rather, graphs and their temporal patterns, come with many faces. Accordingly, we in this paper, propose to use a parametric, centrality-based approach to measure graph similarities and distances, which in turn can be used to study the evoluation of networks.

More than one century ago, Camille Jordan introduced the first graph centrality measure in his attempt to capture "the center of a graph". Since then the family of centrality measures has grown larger and is commonly employed in many graphrelated studies. All major graph-processing libraries commonly export functionality for degree, closeness, betweenness, clustering, pagerank and eigenvector centralities. In the context of static graphs, centralities have proven to be a powerful tool to extract meaningful information on the structure of the networks, and more precisely on the role every participant (node) has in the network. In social network analysis, centralities are widely used to measure the importance of nodes, e.g., to determine key players in social networks, or main actors in the propagation of diseases, etc.

Today, there is no consensus on "good" and "bad" centralities: each centrality captures a particular angle of a node's topological role, some of which can be either crucial or insignificant, depending on the application. Am I important because I have many friends, because I have important friends, or because without me, my friends could not communicate together? The answer to this question is clearly context-dependent.

In this paper, we argue that the perceived quality of network similarities or distances measuring the difference between two networks depends on the focus and application just as much. Instead of debating the advantages and disadvantages of a set of similarities and distances, we provide a framework to apply them to characterize network evolution from different perspectives. In particular, we leverage centralities to provide a powerful tool to quantify network changes. The intuition is simple: to measure how a network evolves, we measure the change of the nodes' roles and importance in the network, by leaving the responsibility to quantify node importance to centralities.

Our Contributions This paper is motivated by the observation that centralities can be useful to study the dynamics of networks over time, taking into account the individual roles of nodes (in contrast to, e.g., isomorphism-based measures, as they are used in the context of anonymous graphs), as well as the context and semantics (in contrast to, e.g., graph edit distances). In particular, we introduce the notion of centrality distance d C (G 1 , G 2 ) for two graphs G 1 , G 2 , a graph similarity measure based on a node centrality C.

We demonstrate the usefulness of our approach to identify and characterize the different faces of graph dynamics. To this end, we study five generative graph models and seven dynamic real world networks in more details. Our evaluation methodology comparing the quality of different similarity measures to a random baseline using data from actual graph evolutions, may be of independent interest.

In particular, we demonstrate how centrality distances provide interesting insights into the structural evolution of these networks and show that actual evolutionary paths are far from being random. Moreover, we build upon the centrality distance concept to construct dynamic graph signatures. The intuition is simple: we measure the probability of an update to be considered as an outlier compared to a uniformly random evolution. This allows us to quantify the deviation of a given dynamic network from a purely random evolution (our null-model) of the same structure for a set of centrality distances. The signature consisting of the resulting deviation values enables the comparison of different dynamisms on a fair basis, independently from scale and sampling considerations.

Examples To motivate the need for tools to analyse network evolution, we consider two simple examples.

Example 1. [Local/Global Scenario] Consider three graphs G 1 , G 2 , G 3 over five nodes {v 1 , v 2 , . . . , v 5 }: G 1 is a line, where v i and v i+1 are connected; G 2 is a cycle, i.e., G 1 with an additional link {v 1 , v 5 }; and G 3 is G 1 with an additional link {v 2 , v 4 }.

In this example, we first observe that G 2 and G 3 have the same graph edit distance to

G 1 : d GED (G 1 , G 2 ) = d GED (G 1 , G 3 ) = 1
, as they contain one additional edge. However, in a social network context, one would intuitively expect G 3 to be closer to G 1 than G 2 . For example, in a friendship network a short-range "triadic closure" [START_REF] Kossinets | Empirical analysis of an evolving social network[END_REF] link may be more likely to emerge than a long-range link: friends of friends may be more likely to become friends themselves in the future. Moreover, more local changes are also expected in mobile environments (e.g., under bounded human mobility and speed). As we will see, the centrality distance concept of this paper can capture such differences.

Example 2. [Evolution Scenario] As a second synthetic example, consider two graphs G L and G S , where G L is a line topology and G S is a "shell network" (see also Figure 1). How can we characterize evolutionary paths leading from the G L topology to G S ? Note that the graph edit distance does not provide us with any information about the likelihood or the role changes of evolutionary paths from G L to G S , i.e., on the order of edge insertions: there are many possible orders in which the missing links can be added to G L , and these orders do not differ in any way when comparing them with the graph edit distance. In reality, however, we often have some expectations on how a graph may have evolved between two given snapshots G L and G S . For example, applying the triadic closure principle to our example, we would expect that the missing links are introduced one-by-one, from left to right. The situation may look different in technological, man-made networks. Adding links from left to right only slowly improves the "routing efficiency" of the network: after the addition of t edges from left to right, the longest shortest path is n -t hops, for t < n -1. A more efficient evolution of the network is obtained by connecting v 1 to the furthest node, adding links to the middle of the network, resulting in a faster distance reduction: after t edge insertions, the distance is roughly reduced by a factor t.

Thus, different network evolution patterns can be observed in real networks. Instead of defining application-dependent similarities with design choices focusing on which evolution patterns are more expected from a certain network, we provide a framework that allows the joint characterization of graph dynamics along different axes.

Organization The remainder of this paper is organized as follows. Section 2 provides the reader with the necessary background. Section 3 introduces our centrality distance framework and Section 4 our methodology to study the different graph dynamics empirically. Section 5 reports on results from analyzing real and generated networks. After reviewing related work in Section 6, we conclude our contribution in Section 7.

Preliminaries

This paper considers labeled graphs G = (V, E), where vertices v ∈ V have unique identifiers and are connected via undirected edges e ∈ E. In the following, we denote as Γ(v) the set of neighbors of node v:

Γ(v) = {w ∈ V s.t. {v, w} ∈ E}. A temporal network trace is a sequence T = [G 0 , G 1 , . . . , G l ], where G i (V, E i ) represents the network at the i th snapshot.
We focus on node centralities, a centrality being a real-valued function assigning "importance values" to nodes. Obviously, the notion of importance is contextdependent, which has led to many different definitions of centralities. We refer to [START_REF] Borgatti | A graph-theoretic perspective on centrality[END_REF] for a thorough and formal discussion on centralities.

Definition 1 (Centrality

) A centrality C is a function C: (G, v) → R+ that, given a graph G = (V, E) and a vertex v ∈ V (G), returns a non-negative value C(G, v). The centrality function is defined over all vertices V (G) of a given graph G.
By convention, we define the centrality of a node without edges to be 0. We write C(G) to refer to the vector in R n + where the i th element is C(G, v i ) for a given order of the identifiers.

Centralities are a common way to characterize networks and their vertices. Frequently studied centralities include the degree centrality (DC), the betweenness centrality (BC), the closeness centrality (CC), and the pagerank centrality (PC) among many more. A node is DC-central if it has many edges: the degree centrality is simply the node degree; a node is BC-central if it is on many shortest paths: the betweenness centrality is the number of shortest paths going through the node; a node is CC-central if it is close to many other nodes: the closeness centrality measures the inverse of the distances to all other nodes; and a node is PC-central if the probability that a random walk on G visits this node is high. We use the classical definitions for centralities, and the exact formulas are presented in appendix for sake of completeness.

Finally, throughout this paper, we will define the graph edit distance GED between two graphs G 1 and G 2 as the minimum number of operations to transform G 1 into G 2 (or vice versa), where an operation is one of the following: link insertion and link removal. To deal with a different node sets V (G 1 ) = V (G 2 ), we take the union of the two node sets and treat absent nodes as nodes with degree 0. In general, in order to compare and measure distances between multiple graphs, we will take the union over the node sets of all involved graphs.

Centrality Distance

The canonical distance measure is the graph edit distance, GED. However, GED often provides limited insights into the graph dynamics in practice. Figure 1 shows an example with two evolutionary paths: an incremental (left) and a binary (right) path that go from G L to G S . With respect to GED, there are many equivalent shortest paths for moving from G L to G S . However, intuitively, not all traces are equally likely for dynamic networks, as the structural roles that nodes in networks have are often preserved and do not change arbitrarily. Clearly, studying graph evolution with GED thus cannot help us to understand how structural properties of graphs evolve.

Observation 1 The graph edit distance GED does not provide much insights into graph evolution.

We in this paper aim to enrich the graph similarity measure with semantics. At the heart of our approach lies the concept of centrality distance: a simple and flexible tool to study the similarity of graphs. Essentially, the centrality distance measures the similarity between two centrality vectors. It can be used to measure the distance between two arbitrary graphs, not only between graphs with graph edit distance 1.

Definition 2 (Centrality Distance) Given a centrality C, we define the centrality distance d C (G 1 , G 2 ) between any two graphs as the sum of the node-wise difference of the centrality values:

d C (G 1 , G 2 ) = ||C(G 1 ) -C 2 (G 2 )|| 1 = v∈V |C(G 1 , v) -C(G 2 , v)|
Thus, the centrality distance intuitively measures the magnitude by which the roles of different nodes change. While we focus on the 1-norm in this paper, the concept of centrality distance can be useful also for other norms.

Both the importance of node roles as well as the importance of node role changes is application-dependent. Due to the large variety of processes dynamic graphs can capture, there is no one-size-fits-it-all measure of importance. To illustrate this point, let us consider the "intuitive" similarity properties proposed by Faloutsos et al. [START_REF] Faloutsos | DELTACON: A principled massive-graph similarity function[END_REF]. For instance, the proposed edge importance property should penalize changes that create disconnected components more than changes that maintain the connectivity properties of the graphs. Now imagine a cycle graph of 100 nodes c 1 , .., c 100 , and a single additional node v connected to c 1 . According to the proposed edge importance property the most important link is (c 1 , v). Indeed, it is the only link whose removal would create a disconnected component (containing v alone). Yet the removal of any other link would double the diameter of the structure. Or in an information dissemination network all nodes would have to update half of their routing tables. So which link is more important? The answer clearly depends on the context. Similar examples can be found for other properties proposed in [START_REF] Faloutsos | DELTACON: A principled massive-graph similarity function[END_REF], e.g., regarding submodularity and focus-awareness. Not only are these properties hard to formalize, their utility varies from application to application.

We conclude by noting that given two centralities C 1 and C 2 and two arbitrary graphs G 1 and G 2 with n nodes, the respective distances are typically different, i.e.,

d C 1 (G 1 , G 2 ) = d C 2 (G 1 , G 2 )
. Hence, using a set of different centrality distances, we can explore the variation of the graph dynamics in more than one "dimension".

Methodology

In order to characterize the different faces of graph dynamics and to study the benefits of centrality-based measures, we propose a simple methodology. Intuitively, given a centrality capturing well the roles of different nodes in a real-world setting, we expect the centrality distance between two consecutive graph snapshots G t and G t+1 to be smaller than the typical distance from G t to other graphs that have the same GED.

To verify this intuition, we define a null model for evolution. A null model generates networks using patterns and randomization, i.e., certain elements are held constant and others are allowed to vary stochastically. Ideally, the randomization is designed to produce a pattern that would be expected in the absence of a particular mechanism [START_REF] Gotelli | Null models in ecology[END_REF]. Applied to our case, this means that starting from a given snapshot G t , that represents the fixed part of the null model, if the evolution follows a null model, then any graph randomly generated from G t at the same GED is evenly likely to appear.

Concretely, for all consecutive graph pairs G t and G t+1 of a network trace, we determine the graph edit distance (or "radius") R = d GED (G t , G t+1 ). Then we generate a set S t+1 of k = 100 sample graphs H i at the same GED R from G t uniformly at random. That is, in H i the edges to be added or deleted are selected at random. Such randomly built samples allow us to assess the impact of a uniformly random evolution of the same magnitude from the same starting graph

G t : ∀H i , d GED (G t , H i ) = d GED (G t , G t+1 ).
Here, the pattern of the null model is G t , and the stochastic evolution at distance R is the random part of the null model.

As a next step, given a centrality C, we compare G t+1 with the set S t+1 that samples the evolution following the null model. We consider that G t+1 does not follow the null model if it is an outlier in the set S t+1 for the centrality C. Practically, G t+1 is considered an outlier if the absolute value of its distance from G t minus the mean distance of S t+1 to G t is at least twice the standard deviation, i.e., if

|d C (G t , G t+1 ) -µ({d C (G t , x), x ∈ S t+1 })| > 2σ({d C (G t , x), x ∈ S t+1 }).
Given a temporal trace T , we define p C,T as the fraction of outliers in the trace for centrality C. An ensemble of such values p C i ,T for a set of centralities C = {C 1 , . . . , C k } is called a dynamic signature of T .

Experimental Case Studies

Based on our centrality framework and methodology, we can now shed some light on the different faces of graph dynamics, using real world data sets.

• Caida (AS): This data captures the Autonomous Systems relationships as captured by the Caida project. Each of the 400 snapshots represents the daily interactions of the 1000 first AS identifiers from August 1997 until December 1998 [START_REF] Kunegis | KONECT -The Koblenz Network Collection[END_REF].

• ICDCS (ICDCS): We extracted the most prolific authors in the ICDCS conference (IEEE International Conference on Distributed Computing Systems) and the co-author graph they form from the DBLP publication database (http: //dblp.uni-trier.de). This trace contains 33 snapshots of 691 nodes and 1076 collaboration edges. The timestamp assigned to an edge corresponds to the first ICDCS paper the authors wrote together. Clearly, the co-authorship graph is characterized by a strictly monotonic densification over time.

• UCI Social network (UCI): The third case study is based on a publicly available dataset [START_REF] Opsahl | Clustering in weighted networks[END_REF], capturing all the messages exchanges realized on an online Facebooklike social network between 1882 students at University of California, Irvine over 7 months. We discretized the data into a dynamic graph of 187 time steps representing the daily message exchanges among users.

• Hypertext (HT): Face-to-face interactions of the ACM Hypertext 2009 conference attendees. 113 participants were equipped with RFID tags. Each snapshot represents one hour of interactions [START_REF] Kunegis | KONECT -The Koblenz Network Collection[END_REF].

• Infectious (IN): Face-to-face interactions of the "Infectious: Stay away" exhibition held in 2009. 410 Participants were equipped with RFID tags. Each snapshot represents 5 minutes of the busiest exhibition day [START_REF] Kunegis | KONECT -The Koblenz Network Collection[END_REF].

• Manufacture (MA): Daily internal email exchange network of a medium-size manufacturing company (167 nodes) over 9 months of 2010 [START_REF] Kunegis | KONECT -The Koblenz Network Collection[END_REF].

• Souk (SK): This dataset captures the social interactions of 45 individuals during a cocktail, see [START_REF] Killijian | Social Observation of hUman Kinetics[END_REF] for more details. The dataset consists of 300 snapshots, describing the dynamic interaction graph between the participants, one time step every 3 seconds [START_REF] Killijian | Social Observation of hUman Kinetics[END_REF].

Figure 2 provides a temporal overview on the evolution of the number of edges in the network and the GED between consecutive snapshots. Some of the seven datasets exhibit very different dynamics: one can observe the time-of-day effect of attendees interactions on Hypertext, and the day-of-week effect on Manufacture. UCI, Hypertext, Infectious and Manufacture all exhibit a high level of dynamics with respect to their number of links. This is expected for Infectious, as visitors come and leave regularly and rarely stay for long, but rather surprising for Manufacture.

The density of Caida slowly increases, and with a steady GED. Similarly, the number of co-author edges of ICDCS steadily increases over the years, while the number of new edges per year is relatively stable. The number of days of the conference Hypertext and the fact that conference participants sleep during the night and do not engage in social activity is evident in the second trace. The dynamic pattern of the online social network UCI has two regimes: it has a high dynamics for the first 50 timestamps, and is then relatively stable, whereas Souk exhibits a more regular dynamics. Generally, note that GED can be at most twice as high as the maximal edge count of two consecutive snapshots.

Centrality Distances over Time

Figure 3 presents examples of the results of our comparison of random graphs with the same graph edit distance GED as real-world network traces. The red dashed lines represent the centrality distances of G t and G t+1 . The distribution of d C values from G t to the 100 randomly sampled graphs of S t+1 is represented as follows: the blue line is the median, while the gray lines represent the 2σ outlier detection window.

For most graphs under investigation and for most centralities it holds that the induced centrality distance between G t and G t+1 is often lower than between G t and arbitrary other graph with the same distance. There are however a few noteworthy details.

Hypertext and Infectious exhibit very similar dynamics compared from a GED perspective as shown in Figure 2. Yet from the other centralities perspective, their dynamism is very different. Consider for instance Infectious for PC, where the measured distance is consistently an order of magnitude less than the sampled one. This can be understood from the link creation mechanics: in Infectious, visitors at different time periods never meet. By connecting these in principle very remote visitors, the null model dynamics creates highly important links. This does not happen in Hypertext where the same group of researchers meet repeatedly. In the monotonically growing co-authorship network of ICDCS, we can observe that closeness and (ego) betweenness distances grow over time, which is not the case for the other networks in Figure 3.

When looking at other centrality distances, we observe that even though the local structure changes, a different set of properties remains mostly unaltered across different networks. Moreover, for some (graph, distance) couples, like KC on ICDCS, CC on Hypertext, or PC on Infectious, the measured distance is orders of magnitude lower than the median of the sampled ones. This underlines a clear difference between random evolution and the observed one from this centrality perspective: the link update dynamics is biased. with respect to the null model for the corresponding centralities. Interestingly, this "distinction ratio" is not uniform among datasets. On Caida, Infectious and UCI, the ratio is high for local centralities such as PageRank and Clustering, and low for global centralities such as Closeness or Betweenness. On the contrary, Hypertext and Manufacture exhibit large ratios for global centralities and small ratios for local centralities. Both local and global centralities perform well on Souk. The difference of these behaviors show that these graphs adhere to different types of dynamics.

Dynamics Signature

To complement our observations on real networks with graph snapshots produced according to a model, we investigated graph traces generated by some of the most wellknown models: Erdős-Rényi ER [START_REF] Erdős | On the evolution of random graphs[END_REF], random regular RR [START_REF] Steger | Generating random regular graphs quickly[END_REF], Barabasi-Albert BA [START_REF] Barabási | Emergence of Scaling in Random Networks[END_REF] and preferential attachment [START_REF] Chung | Complex graphs and networks[END_REF] graphs with an equal number of node and edge events (CMHALF) and with the number of node events depending logarithmically on the time (CMLOG). Perhaps the most striking observation is that all tested dynamic network models have low p C,T values for all C. This is partly due to the fact that the graph edit distance between two subsequent snapshots is one and thus the centrality vectors do not vary as much as between the snapshots and the sampled graphs of the same graph edit distance for the real networks. Moreover, these randomized synthetic models are closer to the null model, and lack some of the characteristics (like link locality) of real world networks. Furthermore, we observe that each random network model exhibits distinct dynamics signatures, with ER being closest to the null model.

Related Work

To the best of our knowledge, our paper is the first to combine the concepts of centralities and graph distances. In the following, we review related work in the two fields in turn, and subsequently discuss additional literature on dynamic graphs.

Graph characterizations and centralities. Graph structures are often characterized by the frequency of small patterns called motifs [START_REF] Boccaletti | Complex networks: Structure and dynamics[END_REF][START_REF] Milo | Network motifs: Simple building blocks of complex networks[END_REF][START_REF] Schreiber | Frequency concepts and pattern detection for the analysis of motifs in networks[END_REF][START_REF] Wernicke | Efficient detection of network motifs[END_REF], also known as graphlets [START_REF] Przulj | Biological network comparison using graphlet degree distribution[END_REF], or structural signatures [START_REF] Contractor | Testing multitheoretical organizational networks: An analytic framework and empirical example[END_REF]. Another important graph characterization, which is studied in this paper, are centralities [START_REF] Brandes | Network Analysis: Methodological Foundations[END_REF]. Dozens of different centrality indices have been defined over the last years, and their study is still ongoing, with no unified theory yet. We believe that our centrality distance framework can provide new inputs for this discussion.

Graph similarities and distances. Graph edit distances have been used extensively in the context of inexact graph matchings in the field of pattern analysis. We refer the reader to the good survey by Gao et al. [START_REF] Gao | A survey of graph edit distance[END_REF]. Soundarajan et al [START_REF] Soundarajan | A guide to selecting a network similarity method[END_REF] compare twenty network similarities for anonymous networks. They distinguish between comparison levels (node, community, network level) and identify vector-based, classifierbased, and matching-based methods. Surprisingly they are able to show that the results of many methods are highly correlated. NetSimile [START_REF] Berlingerio | Network similarity via multiple social theories[END_REF] allows to assess the similarity between k networks, possibly with different sizes and no overlaps in nodes or links. NetSimile uses different social theories to compute similarity scores that are size-invariant, enabling mining tasks such as clustering, visualization, discontinuity detection, network transfer learning, and re-identification across networks. The Deltacon method [START_REF] Faloutsos | DELTACON: A principled massive-graph similarity function[END_REF] is based on the normed difference of node-to-node affinity according to a Belief Propagation method. More precisely, the similarity between two graphs is the Root Euclidean Distance of their two affinity matrices or an approximation thereof. The authors provide three axioms that similarities should satisfy and demonstrate using examples and simulations that their similarity features the desired properties of graph similarity functions. Our work can be understood as an attempt to generalize the interesting approach by Faloutsos et al. in [START_REF] Faloutsos | DELTACON: A principled massive-graph similarity function[END_REF], which derives a distance from a normed matrix difference, where each element depends on the relationships among the nodes. In particular, are argue that there is no one-size-fits-it-all measure, and propose an approach parametrized by centralities. Interestingly, we also prove that distances derived in our framework satisfy the axioms postulated in [START_REF] Faloutsos | DELTACON: A principled massive-graph similarity function[END_REF].

Dynamic graphs. Among the most well-known evolutionary patterns are the shrinking diameter and densification [START_REF] Leskovec | Graph evolution: Densification and shrinking diameters[END_REF]. A lot of recent work studies link prediction algorithms [START_REF] Allali | Internal link prediction: A new approach for predicting links in bipartite graphs[END_REF][START_REF] Liben-Nowell | The link prediction problem for social networks[END_REF][START_REF] Yang | Like like alike: joint friendship and interest propagation in social networks[END_REF]. Others focus on methods for finding frequent, coherent or dense temporal structures [START_REF] Jin | Discovering frequent topological structures from graph datasets[END_REF][START_REF] Shah | Timecrunch: Interpretable dynamic graph summarization[END_REF][START_REF] Sun | Graphscope: parameter-free mining of large time-evolving graphs[END_REF], or the evolution of communities and user behavior [START_REF] Ferlez | Monitoring network evolution using mdl[END_REF][START_REF] Zhao | Multi-scale dynamics in a massive online social network[END_REF].

Another line of research attempts to extend the concept of centralities to dynamic graphs [START_REF] Costa | Time centrality in dynamic complex networks[END_REF][START_REF] Kim | Temporal node centrality in complex networks[END_REF][START_REF] Lerman | Centrality metric for dynamic networks[END_REF][START_REF] Tabirca | Snapshot centrality indices in dynamic fifo networks[END_REF]. Some researchers study how the importance of nodes changes over time in dynamic networks [START_REF] Tabirca | Snapshot centrality indices in dynamic fifo networks[END_REF]. Others define temporal centralities which to rank nodes in dynamic networks and study their distribution over time [START_REF] Kim | Temporal node centrality in complex networks[END_REF][START_REF] Lerman | Centrality metric for dynamic networks[END_REF]. Time centralities which describe the relative importance of time instants in dynamic networks are proposed in [START_REF] Costa | Time centrality in dynamic complex networks[END_REF]. In contrast to this existing body of work, our goal is to facilitate the direct comparison of entire networks and their dynamics, not only parts thereof.

A closely related work but using a different approach is by Kunegis [START_REF] Kunegis | On the spectral evolution of large networks[END_REF]. Kunegis studies the evolution of networks from a spectral graph theory perspective. He argues that the graph spectrum describes a network on the global level, whereas eigenvectors describe a network at the local level, and uses these results to devise link prediction algorithms.

Bibliographic note. An early version of this work appeared at the ACM FOMC 2013 workshop [START_REF] Roy | Modeling and measuring graph similarity: The case for centrality distance[END_REF].

Conclusion

This paper was motivated by the observation that in terms of graph similarity measures, there is no "one size fits it all". In particular, we have proposed a centrality-based distance measure, and introduced a simple methodology to study the different faces of graph dynamics. Indeed, our experiments confirm that the evolution patterns of dynamic networks are not universal, and different networks need different centrality distances to describe their behavior. We observe that the edges in networks represent structural characteristics that are inherently connected to the roles of the nodes in these networks. These structures are maintained under changes, which explains the inertia of centrality distance which capture these properties. This behavior can be used to distinguish between natural and random network evolution. After analyzing a temporal network trace with a set of distance centralities, one can guess with confidence for future snapshots if they belong to the trace.

We believe that our work opens a rich field for future research. In this paper, we focused on five well-known centralities and their induced distances, and showed that they feature interesting properties when applied to the use case of dynamic social networks. However, we regard our approach as a similarity framework, which can be configured with various additional centralities and metrics, which may not even be restricted by distance metrics, but can be based on the angles between centrality vectors or use existing correlation metrics (e.g., Pearson correlation, Tanimoto coefficient, log likelihood). Finally, exploiting the properties of centrality distances, especially their ability to distinguish and quantify between similar evolutionary traces, also opens the door to new applications, such as graph interpolation (what is a likely graph sequence between two given snapshots of a trace) and extrapolation, i.e., for link prediction algorithms based on centralities.

Acknowledgements

The authors would like to thank Clément Sire for insightful remarks on a previous version of this document.

Appendix A. Centrality Definitions Degree Centrality DC: Recall that Γ(v) is the set of neighbors of a node v. The degree centrality is defined as:

DC(G, v) = |Γ(v)|.
Betweenness Centrality BC: Given a pair (v, w) ∈ V (G) 2 , let σ(v, w) be the number of shortest paths between v and w, and σ x (v, w) be the number of shortest paths between v and w that pass through x ∈ V . The betweenness centrality is:

BC(G, v) =
x,w∈V σ v (x, w)/σ(x, w).

For consistency reasons, we consider that a node is on its own shortest path, i.e., σ v (v, w)/σ(v, w) = 1, and, by convention, σ v (v, v)/σ(v, v) = 0. If G is not connected, each connected component is treated independently (σ(x, w) = 0 ⇒ ∀v, σ v (x, w)/σ(x, w) = 0). Ego Centrality EC: Let G v be the subgraph of G induced by (Γ(v) ∪ {v}). The ego centrality is:

EC(G, v) = BC(G v , v).
Closeness Centrality CC: Let δ G (a, b) be the length of a shortest path between vertices a and b in G. The closeness centrality is defined as: w) .

CC(G, v) = w∈V \v 2 -δ G (v,
Pagerank Centrality PC: Let 0 < α < 1 be a damping factor (e.g., the probability that a random person clicks on a link [START_REF] Page | The pagerank citation ranking: Bringing order to the web[END_REF]). The pagerank centrality of G is defined as:

PC(G, v) = 1 -α n + α

Figure 1 .

 1 Figure 1. Two evolutionary paths from a line graph G L to a shell graph G S .

Figure 2 .

 2 Figure 2. Number of edges and graph edit distance GED in the network traces.

Figure 3 .

 3 Figure 3. Centrality distance between G t and G t+1 in dashed red lines and between G t and 100 graphs with the same GED as G t and G t+1 in solid blue lines representing the median, 2σ bars in grey. EC: Ego centrality, BC: Betweenness centrality, CC: Closeness centrality, KC: Cluster centrality, PC: Pagerank centrality.

Figure 4 Figure 4 .

 44 Figure 4 summarizes the p C,G signatures for C ∈ {CC, EC, BC, PC, KC} applied to 7 real and 5 synthetic graphs in the form of an histogram chart-for synthetic graphs, each point is the average of 50 independent realizations of the model, and |S t | = 100-. That is, each chart represents the probability of having graph evolutions being outliers

  w∈V \v PC(G, w) |Γ(w)| . Cluster Centrality KC: The cluster centrality of a node v is the cluster coefficient of v, i.e., the number of triangles in which v is involved divided by all possible triangles in v's neighborhood. By convention, KC(G, v) = 0 for |Γ(v)| = 0, and KC(G, v) = 1 for |Γ(v)| = 1. For higher degrees: KC(G, v) = 2|{{j, k} s.t. (j, k) ∈ Γ(v) 2 , (j, k) ∈ E}| |Γ(v)|(|Γ(v)| -1) .


Michael Bulois
email: michael.bulois@univ-st-etienne.fr

ON THE NORMALITY OF THE NULL-FIBER OF THE MOMENT MAP FOR θ-AND TORI REPRESENTATIONS

Keywords: 14L24, 17B20, 17B70, 20G05, 53D20 theta-representations, torus, commuting variety, moment map, symplectic reduction, orbifold

Let (G, V ) be a representation with either G a torus or (G, V ) a locally free stable θ-representation. We study the fiber at 0 of the associated moment map, which is a commuting variety in the latter case. We characterize the cases where this fiber is normal. The quotient (i.e. the symplectic reduction) turns out to be a specific orbifold when the representation is polar.

In the torus case, this confirms a conjecture stated by C. Lehn, M. Lehn, R. Terpereau and the author in a former article. In the θ-case, the conjecture was already known but this approach yield another proof.

Introduction

Let k be an algebraically closed field of characteristic zero. Let (G, V ) be a representation of a connected reductive algebraic group G on a finite dimensional k-vector space V . Let g be the Lie algebra of G. We define the moment map

µ : V ⊕ V * → g * (x, ϕ) → (g → ϕ(g • x))
Among the fibers of the moment map, the most special one is µ -1 (0). When the representation (G, V ) is the adjoint action of G on g, µ -1 (0) can be identified wih the commuting scheme of g. According to a long-standing conjecture, this scheme should be normal. One of the aim of this work is to study the normality of the scheme µ -1 (0) in some nice cases. For instance, if (G, V ) is visible and locally free, we already know that µ -1 (0) is a complete intersection and the normality question reduces to singular locus questions thanks to Serre's criterion (see e.g. Corollary 1.7 and Remark 1.8). Using this, Panyushev [Pan] has shown that µ -1 (0) is reduced and normal in the case of the representation associated to a symmetric Lie algebra of maximal rank.

There are some natural generalizations of adjoint representations and symmetric Lie algebras: the so-called θ-representations ( or θ-groups) of Vinberg [Vin] and, more generally, the polar representations of Dadok and Kac [DK]. Recall that a θ-representation is a representation (G, V ) isomorphic to some (H 0 , h 1 ) where H is a connected reductive group acting on its Lie algebra h, with h equipped with a Z m -grading i∈Zm h i and where H 0 is the connected subgroup of H whose Lie algebra is h 0 . It turns out that the geometry of µ -1 (0) can be a bit more involved in this setting of θ-representations than for the classical adjoint representation. For instance, it is possible to find examples of such representations where µ -1 (0) is non-irreducible [START_REF] Panyushev | The Jacobian modules of a representation of a Lie algebra and geometry of commuting varieties[END_REF][START_REF] Bulois | Irregular locus of the commuting variety of reductive symmetric Lie algebras and rigid pairs[END_REF], non-reduced or irreducible non-normal [BLLT]. In this paper, we classify the locally free stable θ-representations for which µ -1 (0) is normal. It turns out (Theorem 4.6) that this normality property holds in all the classical cases and we find only 5 non-normal examples of exceptional cases, each of rank 1. We take the opportunity to generalize some properties of decompositions classes to the θ-cases in Section 4. The θ-case is partly based on the study of some specific tori representations. This is one motivation for studying µ -1 (0) for a general representation of a torus in Section 2. The fiber turns out to be normal as soon as it is irreducible and we give a combinatorial criterion for this in terms of the weights of the representation (Theorem 2.2).

The variety µ -1 (0) is also involved in the symplectic reduction (V ⊕ V * )/ / /G := µ -1 (0)/ /G where X/ /G denotes the categorical quotient of an affine G-variety X. If µ -1 (0) is normal, then the symplectic reduction is also normal. Following a theorem of Joseph [Jos] in the Lie algebra case, and a conjecture stated in [BLLT] in the complex case (see conjecture 1.3 here), the variety (V ⊕ V * )/ / /G should be isomorphic to a specific orbifold whenever (G, V ) is visible and polar. The results of the present paper yield a proof of this conjecture when G is a torus (Corollary 3.10), and allows to recover it when (G, V ) is a stable locally free θ-representation (Remark 4.13). In the torus case, we also get that that the visibility assumption is necessary (Proposition 3.9) but that the scheme (V ⊕ V * )/ / /G is nevertheless reduced (Theorem 2.2) and normal (Proposition 3.4) in general.

One should note that, as the torus case suggests, we put light on representations which are far from being irreducible. Part of the results concerning tori (e.g., the normality of the symplectic reduction) were written independantly in the recent preprint [HSS]. The general philosophy of [HSS] is to focus on "large" representations (ex: 2-large) whereas the polar representations are "small".

Acknowledgements. Section 4 of this paper was essentially included in early versions of [BLLT]. I want to thank my co-authors to allow me to reuse this material here.

This work has benefited from the support of the project GeoLie (ANR-15-CE40-0012) and of the LABEX MILYON (ANR-10-LABX-0070) of Université de Lyon within the program "Investissements d'Avenir" (ANR-11-IDEX-0007) operated by the French National Research Agency (ANR).

Generalities

In this section, we introduce some classical material to study null fibers of moment maps. Even if some results are stated in a greater generalities, most of this section is heavily inspired by [Pan]. Popov's article [Po] is also a source of inspiration.

We work over an algebraically closed field k of characteristic zero. We use the language of scheme even if these schemes will always be separated of finite type over k and will often be reduced, i.e. varieties. We do not require that the varieties are irreducible. When speaking about the irreducible components of a scheme, we always mean the irreducible components of the corresponding reduced variety and we do not consider embedded components.

If A is a subset of a vector space, A stands for the subspace generated by A.

Definition 1.1. An element x ∈ V is said to be

• semisimple if G.x is closed, • nilpotent if 0 ∈ G.x.
Equivalently, x is nilpotent if and only if π(x) = π(0) where π : V → V / /G is the categorical quotient map.

Definition 1.2. The representation (G, V ), is said to be

• locally free, if dim G.x = dim G for some x ∈ V .
• visible, if there are finitely many nilpotent G-orbits.

• stable, if there is an open subset of V , consisting of semisimple elements

• polar, if there exists v ∈ V such that dim c v = dim V //G where c v := {x ∈ V | g • x ⊂ g • v}.
We then say that c v is a Cartan subspace of V .

Examples of visible and stable representations are given by the adjoint action of G on g, or a θ-representation arising from a Z 2 -grading (so-called symmetric Lie algebras). In general, θ-representations are always visible but not necessarily stable [Vin]. Polar representations, as introduced in [DK], can be neither stable nor visible. Examples of locally free representations are given by symmetric Lie algebras of maximal rank. It is worth noting that no adjoint representation (G, g) is locally free.

When k = C and (G, V ) is polar, we write c and c ∨ for dual Cartan subspaces of V and V * , following [START_REF] Bulois | Towards a symplectic version of the Chevalley restriction theorem[END_REF](3.4),(3.6)], together with dual decompositions

V = c ⊕ (g • c) ⊕ U and V * = c ∨ ⊕ (g • c ∨ ) ⊕ U ∨ . Write W for the Weyl group N G (c)/C G (c).
The following was Conjecture A in [BLLT].

Conjecture 1.3. Assume that (G, V ) is visible and polar, then we have an isomorphism of Poisson varieties

(V ⊕ V * )/ / /G ∼ = (c ⊕ c ∨ )/W . Remark 1.4. Assume k = C. From [BLLT, Proposition 3.3&3.5], we have a injective natural morphism c × c ∨ /W → µ -1 (0)/ /G of Poisson varieties. Since c ⊕ c ∨ /W is normal, Conjecture 1.3 is equivalent to: (1) The morphism c × c ∨ /W → µ -1 (0)/ /G is dominant (i.e. it is bijective.) (2) µ -1 (0)/ /G is normal
When studying the null fiber of the moment map, it is enlightening to study the modality of (G, V ). The modality of a G-subvariety X ⊆ V is defined as

mod(G, X) := max Y ⊆X min x∈Y (codim Y G.x)
where the maximum is taken over all irreducible subvarieties Y ⊆ X.

In the remaining of the section we will consider a finite cover of V ,

V = i J i such that • Each J i is G-stable, irreducible and locally closed in V of constant orbit dimension (that is ∃m i ∈ N, ∀x ∈ J i , dim G • x = m i ), • J i = J j ⇒ i = j.
Exemples of such cover includes sheets of (G, V ) or decomposition classes in the case of the adjoint action. Note that if the cover is disjoint V = i J i , then the second condition follows from the first one. Since the J i are of constant orbit dimension, we have mod(G, J i ) = dim J im i . Moreover, from finiteness and locally closeness, each irreducible subvariety Y ⊂ V intersects at least one J i as a dense open subset of Y and we have

min x∈Y codim Y G.x = mod(G, J i ). Hence (1) mod(G, V ) = max i mod(G, J i ).
Given a subvariety X ⊆ V , we write

(2)

(µ -1 (0)) X := {(x, ϕ) ∈ µ -1 (0)|x ∈ X} = {(x, ϕ) ∈ X × V * | ϕ ∈ (g.x) ⊥ }
seen as a subvariety of µ -1 (0). This allows for instance to decompose µ -1 (0), as a finite union:

(3)

µ -1 (0) = i (µ -1 (0)) Ji . Lemma 1.5. (i) Each (µ -1 (0)) Ji is an irreducible and locally closed subvari- ety of µ -1 (0) of dimension dim V + mod(G, J i ). (ii) Each irreducible component of µ -1 (0) is of the form (µ -1 (0)) Ji for some i.
(iii) There is a bijection between the set of irreducible components of µ -1 (0) of maximal dimension dim V + mod(G, V ) and the set of J i with maximal modality mod(G,

J i ) = mod(G, V ). Proof. (i) From (2), (µ -1 (0)) Ji is a subbundle in J i × V * of codimension m i . In particular, it is an irreducible subvariety of µ -1 (0) of dimension (4) dim V + dim J i -m i = dim V + mod(G, J i ).
(ii) is clear from (i) and (3).

(iii) By considering projection on the first variable, (µ -1 (0)) Ji = (µ -1 (0)) Jj can happen only if J i = J j , that is only if i = j. The bijection is then clear from (i) and (ii).

Another classical result is the following characterization of the smooth locus of µ -1 (0). If y belongs to a G-module Y (e.g. Y = V or Y = V ⊕ V * ), we let g y := {g ∈ g| g.y = 0} be the centralizer of y in g.

Proposition 1.6. The following assertions are equivalent for an element

(x, ϕ) ∈ µ -1 (0) ⊂ V ⊕ V * (i) (x, ϕ) is a smooth point of the scheme µ -1 (0) (ii) (x, ϕ) belongs to a unique irreducible component (µ -1 (0)) Ji for some J i , and dim g x,ϕ = mod(G, J i ) + dim g -dim V
Proof. The tangent space of µ -1 (0) at z = (x, ϕ) is Ker d z µ. The dual map of d z µ has the following expression

(d z µ) * : g → (V ⊕ V * ) * g → [(y, ψ) → ψ(g.x) + ϕ(g.y)]
In particular,

Ker(d z (µ)) * = {g ∈ g| g • x = 0 = g • ϕ} = g x,ϕ . Hence dim Ker d z µ = 2 dim V -dim g + dim g x,ϕ .
Recall that smooth points on a scheme belong to a unique irreducible component. Let (x, ϕ) belong to a unique irreducible component (µ -1 (0)) Ji for some

J i . Since dim(µ -1 (0)) Ji = dim V + mod(G, J i ) (Lemma 1.5), we get that (x, ϕ) is a smooth point of µ -1 (0) if and only if dim V -dim g + dim g x,ϕ = mod(G, J i ), hence the equivalence. Corollary 1.7. Assume that mod(G, V ) = dim V -dim G. Then (i) (G, V ) is locally free. (ii) µ -1 (0) is a complete intersection of dimension 2 dim V -dim G.
(iii) The smooth points of the scheme µ -1 (0) are the points (x, ϕ) satisfying g x,ϕ = {0}. (iv) µ -1 (0) is irreducible if and only if mod(G, J i ) < mod(G, V ), for any i such that J i = V . If it is the case, the scheme µ -1 (0) is also reduced (v) µ -1 (0) is reduced and normal if and only if it is irreducible and the following holds

(5) ∀i, mod(G, J i ) = mod(G, V ) -1 ⇒ ∃(x, ϕ) ∈ (µ -1 (0)) Ji s.t. g x,ϕ = {0} Proof. (i) Let i 0 be the index such that J i0 = V . Then m i0 is the maximum orbit di- mension in V and we get mod(G, V ) mod(G, J i0 ) = dim V -m i0 dim V -dim G.
From the hypothesis, we have equalities so m i0 = dim G.

(ii) The irreducible components of maximal dimension of µ -1 (0) have codimension

2 dim V -(dim V + mod(G, V )) = dim G in V ⊕ V * . Since µ -1 (0) is defined in V ⊕ V * by dim g equation, (ii) follows.
(iii) From (ii), µ -1 (0) is equidimensional and its irreducible components have dimension 2 dim Vdim G. From proof of Proposition 1.6, we see that the tangent space of µ -1 (0) at (x, ϕ) has dimension 2 dim Vdim g + dim g x,ϕ . The result follows.

(iv) We have already seen in (i) that mod(G, J i0 ) = mod(G, V ) for i 0 such that J i0 = V . The characterization of the irreducibility of µ -1 (0) then follows from equidimensionality and Lemma 1.5 (iii). For x ∈ J i0 , we have g x = {0}. So (µ -1 (0)) Ji 0 is in the smooth locus of µ -1 (0) by (iii). Hence µ -1 (0) is reduced as soon as it is irreducible. (v) Recall now that a variety is normal if and only if it satisfies Serre's condition (S 2 ) and its singular locus has codimension at least 2. The former is provided by (ii). Under the irreducibility assumption, the latter is equivalent to (5). Indeed, the singular locus of µ -1 (0) is a closed subset of i =i0 (µ -1 (0)) Ji . But, it follows from Lemma 1.5(i) that an irreducible component of a closed subset of

i =i0 (µ -1 (0)) Ji of codimension 1 in µ -1 (0) contains at least one (µ -1 (0)) Ji with mod(G, J i ) = mod(G, V ) -1.
Remark 1.8. In the notation of the proof of (i), we have, for a general representation [Pan], see (2.2) and Corollary 2.5 in loc. cit. Then Proposition 3.1 in loc. cit. asserts that this condition hold when (G, V ) is visible. In particular, hypothesis of the above corollary are satisfied when (G, V ) is locally free and visible. Similarily, condition (F 1 ) in loc. cit. is equivalent to the condition appearing in Corollary 1.7 (iv). Related statements to corollary 1.7 can be found in Theorems 2.4, 3.1 and 3.2 in loc. cit.

(G, V ): mod(G, V ) dim V -m i0 . The limit case mod(G, V ) = dim V -m i0 corresponds to condition (F 0 ) of

Null-fiber of the moment map -torus case

In this section V is an n-dimensional representation of an r-dimensional torus

G = T ∼ = (k × ) r . The weight space X * (T ) is isomorphic to Z r . We let W Q := X * (T ) ⊗ Z Q. It is a Q-vector space of dimension r. Recall that the irreducible representations of T are one-dimensional. So we can decompose V = n i=1 V i , with T acting on V i ∼ = k with weight s i = s j i j∈[[1,r]] ∈ X * (T ). That is, the action of an element t = (t j ) j∈[[1,r]] ∈ T on an element v = (v i ) i∈[[1,n]] ∈ V is given by t • v =     r j=1 t (s j i ) j   v i   i . We introduce the n × r matrix S := (s j i ) i,j . Given I ⊂ [[1, n]] or i ∈ [[1, n]], we also define the #I × r-matrix S I := (s j i ) (i,j)∈I×[[1,r]] and the (n -1) × r-matrix S î := S [[1,n]]\{i} .
In the sequel we need a partition of V by suitable strata. These are indexed by subsets I ⊂ [[1, n]] and are given by

J I := {(v i ) i ∈ V | v i = 0 ⇔ i ∈ I}. Remark 2.1. Each J I is a locally closed irreducible T -stable subvariety whose clo- sure is V I := {(v i ) i ∈ V | ∀i / ∈ I, v i = 0}. Moreover, there is a T -equivariant action of (C × ) n on V given by (λ i ) i • (v i ) i = (λ i v i ) i .
The orbits of this action are precisely the strata J I . Hence many geometric properties of the action of T on a point v ∈ V (dimension of orbit, nilpotency, semisimplicity, . . . ) are preserved along the stratum J I containing v. It will then be convenient to make the computations only at v I := (δ i∈I ) i where δ is the Kronecker symbol. It is now clear that V = I J I is a cover satisfying the assumptions of Section 1.

For v ∈ V , writing X v :=     v 1 . . . v n     , we have (6) t • v = (s j i v i ) i∈[[1,n]] | j ∈ [[1, r]] = Im(X v S) = X v Im(S).
where Im(S) (resp. Im(X v S)) denote the image space of the linear maps k r → k n associated to S (resp. X v S) in the canonical basis. It follows from ( 6) that, for v ∈ J I , we have

(7) dim T.v = rk S I .
In particular, the modality of J I is given by ( 8)

mod(T, J I ) = #I -rk S I = dim Ker( t S I ).
where Ker( t S I ) is the kernel of the linear map k #I → k r associated to t S I . Via the natural identifications

k #I ∼ = V I ⊂ V ∼ = k n , Ker( t S I ) is identified with Ker( t S)∩V I . Assume that I 1 ⊂ I 2 are two subsets of [[1, n]], then Ker( t S) ∩ V I1 ⊂ Ker( t S) ∩ V I2 . So (9) I 1 ⊂ I 2 ⇒ mod(T, J I1 ) mod(T, J I2 ),
From (1), we get

(10) mod(T, V ) = mod(T, J [[1,n]] ) = dim V -rk S.
We can apply (2) to X = J I to define (µ -1 (0)) JI . This yields a partition of µ -1 (0) into a disjoint union of irreducible locally closed (Lemma 1.5) subsets

µ -1 (0) = I (µ -1 (0)) JI Theorem 2.2. Assume that (T, V
) is a reprentation with T a torus. Then, under above notation: (8). This last condition is the one expressed in (ii).

(i) µ -1 (0) is a reduced complete intersection of dimension 2 dim V -rk S. (ii) The irreducible components of µ -1 (0) are the subsets of the form (µ -1 (0)) JI with rk S -rk S I = n -#I. (iii) µ -1 (0) is irreducible if and only if, for any i ∈ [[1, n]], we have rk(S î) = rk S. (iv) µ -1 (0) is normal if and only if it is irreducible. Proof. By Lemma 1.5, the irreducible components of µ -1 (0) of maximal dimension dim V + mod(T, V ) = 2 dim V -rk S (10) are the (µ -1 (0)) JI with #I -rk S I = n -rk S
Then, from (9), µ -1 (0) has a single irreducible component of maximal dimension if and only if mod(T,

J I ) < mod(T, J [[1,n]] ) for any I of the form [[1, n]] \ {i}. If I = [[1, n]] \ {i}, it follows from (8), that mod(T, J I ) = mod(T, J [[1,n]] ) -1 if rk S î = rk S mod(T, J [[1,n]] ) if rk S î = rk S -1 .
In the next paragraph, we show that µ -1 (0) is a complete intersection, hence equidimensional. Together with the above arguments, this implies that (ii) and (iii) holds.

Consider the kernel of the representation (T, V ),

K := {t ∈ T | ∀i, s i (t) = 1}. Its Lie algebra is k := {t ∈ t ∼ = k r |St = 0} = Ker(S). Applying (7) to a general element v ∈ V , we get dim(T /K) • v = dim T • v = rk S = dim t -dim k. So the representation (T /K, V
) is not only faithul but locally free. Note that T /K is also a torus and that µ -1 (0) is the same for (T, V ) and (T /K, V ). Therefore, there is no loss of generality in assuming that (T, V ) is locally free in order to prove (i) and (iv). Under this assumption, important features are rk S = dim T (7) and mod(T, V ) = dim Vdim T (10). In particular, we can apply Corollary 1.7 and get that µ -1 (0) is a complete intersection.

Assuming that (T, V ) is locally free, we claim that

(11) ∀I ⊂ [[1, n]], ∃(x, ϕ) ∈ (µ -1 (0)) JI , t (x,ϕ) = {0}.
Under this claim, (ii) and Corollary 1.7 (iii) imply that each irreducible component of µ -1 (0) has smooth points. Hence µ -1 (0) is reduced and this ends the proof of (i). The claim also implies that condition ( 5) is automatically satisfied so (iv) follows from Corollary 1.7 (v).

Proof of claim (11

) Let I ⊂ [[1, n]]. The decomposition V = i V i induces to a decomposition V * = V * i ∼ = k n . We set x = v I = (δ i∈I ) i ∈ J i ⊂ V and ϕ := (δ i / ∈I ) i ∈ V *
with respect to these decompositions. Since t • x ⊂ V I , we have ϕ ∈ (t • x) ⊥ so (x, ϕ) ∈ (µ -1 (0)) JI . Also, let t ∈ T stabilizing (x, ϕ). Then s i (t) = 1 for any i ∈ I and 1/(s i (t)) = 1 for any i / ∈ I. Hence t is in the kernel of the representation. By local freeness, we get t x,ϕ = {0}.

Symplectic reduction for tori representations

We keep the notation and setting of the previous section. The aim of this section is to study the symplectic reduction (V ⊕ V * )/ / /T := µ -1 (0)/ /T . We prove Conjecture 1.3 in the context of representations of tori (Corollary 3.10). Moreover, we show that that the conjecture is essentially false for non-visible action (Proposition 3.9), but that the symplectic reduction remains normal in this case (Proposition 3.4).

In this section, many properties depend on considerations on the convex hull of some of the weights

s i ∈ X * (T ). If ∅ = A ⊂ X * (T ) ⊂ W Q = X * (T ) ⊗ Z Q, we denote by CH(A), the convex hull of A in W Q . We also denote by • CH(A) the interior (for the classical topology) of CH(A) in A . Alternatively, • CH(A) is the set of convex combination a∈A α a a with each α a positive. It is an elementary result on convex hull that 0 / ∈ CH(A) (resp. 0 / ∈ • CH(A)) if and only if ∃φ ∈ W * Q s. t. ∀ a ∈ A, φ(a) > 0 (resp. φ(a) 0 and φ(A) = {0})
. Note that such φ can be multiplied by a sufficiently large integer so that we can always assume ϕ ∈ X * (T ).

In our context of weights on a group, this translates as follows.

× ρ ֒→ T such that ∀a ∈ A, ∃b a ∈ N * (resp. b a ∈ N with at least one a ∈ A s.t. b a = 0), ∀t ∈ C × , a(ρ(t)) = t ba . Proposition 3.2. Let ∅ = I ⊆ [[1, n]] and v ∈ J I . (1) v ∈ V is nilpotent if and only if 0 / ∈ CH({s i |i ∈ I}). (2) v ∈ V is semisimple if and only if 0 ∈ • CH({s i |i ∈ I}).
Proof. First, recall that the elements of J I all share the same orbit dimension. In particular, an element y ∈ T.v \ T.v lies in J I ′ for some

I ′ I. Then, from Hilbert- Mumford criterion, v = (v i ) i ∈ V \ {0} is nilpotent (resp.
is not semi-simple) if and only if there exists a one-parameter subgroup C × ρ ֒→ T such that ρ(t).v i = t bi v i with b i positive for each i ∈ I (resp. non-negative for each i ∈ I and at least one b i non-zero) . Since t bi = s i (ρ(t)), the result then follows from Lemma 3.1.

Given (T, V ) and associated weights

(s i ) i∈[[1,n]] , we split [[1, n]] into (12) I d := {i ∈ [[1, n]]| rk S î = rk S}, I f := I \ I d = {i ∈ [[1, n]]| rk S î = rk S -1}. Corollary 3.3. The representation (T, V ) is stable if and only if 0 ∈ • CH({s i |i ∈ [[1, n]]}).
In this case I f = ∅ and µ -1 (0) is irreducible and normal Proof. A generic element of V lies in J [[1,n]] so the first assertion follows from Proposition 3.2. If we can write 0 as a convex combination of the (s i ) i∈ [[1,n]] with non-zero coefficients, I f is empty so the second statement follows from Theorem 2.2. Proposition 3.4. There is an isomophism

(V ⊕ V * )/ / /T ∼ = (V I d ⊕ V * I d )/ / /T . In particular, (V ⊕ V * )/ / /T is normal.
Proof. We denote by µ I d the moment map

V I d ⊕ V * I d → t * .
Recall that µ -1 (0) and µ -1 I d (0) are reduced by Theorem 2.2. Hence so are (V ⊕ V * )/ / /T = µ -1 (0)/ /T and

(V I d ⊕ V * I d )/ / /T = µ -1 I d (0)/ /T .
Note that V * I d can be identified with the subrepresentation of V * generated by the isotypical components associated to the weights {-s i |i ∈ I d }. This allows us to consider µ -1 I d (0) as a T -stable closed subscheme of µ -1 (0). Therefore, we have a closed immersion µ -1 I d (0)/ /T → µ -1 (0)/ /T . To show that this is an isomorphism, there remains to prove that this map is a surjective. For this, we are going to show that the only closed orbits in µ -1 (0) lie in µ -1 I d (0). Let (x, y) ∈ µ -1 (0) and assume that x / ∈ V I d . From the assumption on x, we know that there exists i such that x i = 0 and rk S î < rk S. Then there exists an element t ∈ s

j | j = i ⊥ ⊂ t such that s i (t) = 1. So t • x = x i and V {i} ⊂ t • x.
Since y ∈ (t • x) ⊥ , we get y i = 0. Then a one-parameter subgroup C × ρ ֒→ T given by s j (ρ(t)) = t δi,j acts on (x, y) via t • y = y and lim t→0 t • x = x ′ with x ′ j = x j if j = i and x ′ i = 0. Hence (x ′ , y) ∈ T.(x, y) \ T.(x, y). A similar argument shows that T.(x, y) is also non-closed as soon as y / ∈ V * I d . Let us now show that (V I d (0) is irreducible and normal, so the same holds for its quotient by T .

I d ⊕ V * I d )/ / /T is normal. For each i ∈ I f , s i is not a linear combination of the other s j (j = i). Hence {s i | i ∈ I f } induces a basis of s i | i ∈ [[1, n]] / s i | i ∈ I d
We have the following useful characterization of a visible action:

Proposition 3.5. The representation (T, V ) with weight (s i ) i∈[[1,n]] is visible if and only if there is a partition [[1, n]] = l j=0 I j satisfying (i) s i | i ∈ [[1, n]] = l j=0 s i | i ∈ I j (ii) dim s i | i ∈ I j = #I j if j = 0 #I j -1 if j 1 (iii) ∀j 1, 0 ∈ • CH({s i |i ∈ I j }).
Note that the subset I 0 in the proposition has to coincide with I f defined in (12) and that I d = j 1 I j .

Proof. "if " part: Assume that such a partition exists. Let x ∈ V be nilpotent and let Ĩ be such that x ∈ J Ĩ . Define Ĩj := Ĩ ∩ I j . Assume that j is a positive index such that Ĩj = ∅. Since x is nilpotent and Ĩj ⊂ Ĩ, it follows from Proposition 3.2 that 0 / ∈ CH({s i |i ∈ Ĩj }). By (iii), Ĩj is a proper subset of I j . On the other hand, (iii) also implies that there is a convex combination i∈Ij α i s i = 0 with each α i > 0. By (ii), this combination is the unique linear relation (up to scalar multiplication) between the (s i ) i∈Ij . In particular, the family (s i ) i∈ Ĩj is linearly independant. The same hold if j = 0 by (ii). By (i), we get that (s i ) i∈ Ĩ is linearly independent.

Then, by ( 7), dim T.x = rk S Ĩ = # Ĩ = dim J Ĩ . Hence T.x is open in J Ĩ . Since this holds for any x ∈ J Ĩ , we get T.x = J Ĩ . Since there are finitely many possible index set Ĩ, the representation (T, V ) is visible.

"only if " part: We will argue by induction on dim V . Assume dim V = 1. If s 1 = 0, we set l = 0 and I 0 := {s 1 }. If s 1 = 0, we set l := 1, I 0 := ∅ and I 1 := {s 1 }.

Assume now that the result holds true for any visible representation of T of dimension n -1 and consider a visible representation (T, V ) of dimension n. Since

V ′ := V [[1,n-1]] is a subrepresentation of V , it is also visible. By the inductive hypothesis, there exists a partition [[1, n -1]] = l ′ j=0 I ′ j satisfying (i), (ii) and (iii). If s n / ∈ s i | i ∈ [[1, n -1]] ,
we can set I 0 := I ′ 0 ∪ {n} and I j := I ′ j for any j 1. From now on, we assume that

s n ∈ s i | i ∈ [[1, n -1]] . As a first step, we claim that there is a subset Ĩ ⊂ [[1, n -1]] and some non-zero rational coefficients (β i ) i∈ Ĩ such that • s n := i∈ Ĩ β i s i • Ĩ ∩ I ′ j = I ′ j for any j 1 • β i > 0 for i ∈ j 1 I ′ j ∩ Ĩ.
Indeed, start with a combination with rational coefficients

s n := i∈[[1,n-1]] β ′ i s i . Fix j
1. From (iii) and (ii), there is a combination with positive coefficients

0 = i∈I ′ j α i s i . Let λ j := max i∈I ′ j {-β ′ i /α i }. Set β i := β ′ i + λ j α i for i ∈ I ′ j .
So β i 0 for any i ∈ I ′ j and β i = 0 for at least one i ∈ I ′ j . Then set Ĩ := {i|β i = 0} and the claim is shown.

From the property Ĩ ∩ I ′ j = I ′ j and (i), (ii), (iii)" we get that (s i ) i∈ Ĩ is linearly independant as in the proof of the "if part". So, up to scalar multiplication, the only relation between {s i |i ∈ Ĩ ∪ {n}} is given by the above coefficients β i (i ∈ Ĩ). Assuming that β i > 0 for some i ∈ Ĩ (e.g. if Ĩ ∩ j 1 I ′ j = ∅), we get 0 / ∈ CH({s i |i ∈ Ĩ ∪{n}}) so orbits in J Ĩ∪{n} are nilpotent by Proposition 3.2. From ( 7), these orbits are of dimension rk S Ĩ∪{n} = # Ĩ = dim J Ĩ∪{n} -1. This contradicts the visibility of (T, V ). As a result, Ĩ ⊂ I 0 and β i < 0 for each i ∈ I 0 . Setting l := l ′ + 1, I l := Ĩ ∪ {n}, I 0 := I ′ 0 \ Ĩ and I j := I ′ j for j ∈ [[1, l ′ ]] then yield (i), (ii) and (iii) for the representation (T, V ).

Remark 3.6. We can re-interpret Proposition 3.5 as follows. The visible tori actions are essentially made of two part: a part of rank 0 provided by I 0 and several stable blocks of rank 1, each looking very much like [START_REF] Bulois | Towards a symplectic version of the Chevalley restriction theorem[END_REF]Example 8.6]. There are other appearence of stable blocks of rank 1 in Lemma 4.9.

Corollary 3.7. Any visible representation of a torus is polar.

Proof. Let (T, V ) be a visible representation and adopt notation of Proposition 3.5. For w := (w 1 , . . . , w l ) ∈ C l , we consider x(w) as the element (x i ) i∈ [[1,n]] given by x i := 0 if i ∈ I 0 and x i := w j if i ∈ I j (j 1). From (6), we get t • x(w) = X x(w) Im(S). From Proposition 3.5 (i), Im(S) = j Im(S Ij ). Since X x(w) acts by w j Id on Im(S Ij ), we get that t • x(w) is included in t • x(1, . . . , 1). The subspace c := {x(w)|w ∈ C l } is our candidate for being a Cartan subspace of (T, V ) and there remains to show that l = dim V / /T , [DK].

Since (T, V ) is visible, a general fiber of the quotient map V → V / /T is the closure of a general orbit in V . Hence, by (7), dim V / /T = dim Vrk S. This is equal to l by Proposition 3.5.

Let us now take a closer look at (V ⊕ V * )/ / /T , that is at closed orbits of µ -1 (0). A first observation is the following.

Lemma 3.8. If (x, y) ∈ µ -1 (0) is such that x ∈ V and y ∈ V * are semisimple, then (x, y) is semisimple in V ⊕ V * .
Proof. Consider the set of weigths for the action of T on V ⊕V * . Denote by A x (resp. A y , A x,y ) the set of weights corresponding to the support of x (resp. y, (x, y)). By Proposition 3.2, 0 ∈

• CH(A x ) and 0 ∈ • CH(A y ). So 0 ∈ • CH(A x ∪ A y ) = • CH(A x,y ).
The result follows.

Proposition 3.9. The representation (T, V ) is visible if and only if closed orbits of µ -1 (0) are those of the form T.(x, y) with T.x and T.y closed.

Proof. • Assume that (T, V ) is visible. With similar arguments to those of Proposition 3.4, we are going to show that, whenever x ∈ V is not semisimple, (x, y) ∈ µ -1 (0) cannot be semisimple. A symmetric argument on y ∈ V * and Lemma 3.8 then allow to conclude for the "only if" part.

Let x ∈ J Ĩ for some Ĩ ⊂ [[1, n]]. The representation (T, V Ĩ ) is also visible, so we can apply Proposition 3.5 (with Ĩ instead of [[1, n]]) and get a partition Ĩ = l j=0 Ĩj . Apply also Proposition 3.5 to V , so that we get a partition [[1, n]] = j I j .

Assuming that x is not semisimple amounts to assume that Ĩ0 = ∅ (Proposition 3.2). If Ĩ0 ∩ I 0 = ∅, Proposition 3.4 states that any element of µ -1 (0) of the form (x, y) is not semisimple. From now on, we assume that there exists j 1 such that Ĩ0 ∩ I j = ∅. From property (ii) of Proposition 3.5 on Ĩ0 and I j , we also know that

I j \ Ĩ0 = ∅. Fix i 0 ∈ Ĩ0 ∩ I j and i 1 ∈ I j \ Ĩ0 .
The relation between the (s i ) i∈Ij can be written as i∈Ij α i s i = 0 with the α i positive integers. Then we can define a one parameter subgroup ρ: C × ֒→ T , via

s i (ρ(t)) =      t αi 1 if i = i 0 t -αi 0 if i ′ = i 1 1 else Then V {i0} = Lie(ρ(C × )) • x ⊂ t •
x and, whenever (x, y) ∈ µ -1 (0), we have y i0 = 0. Since ρ(t) acts on y i1 by multiplication by t αi 0 , we get that lim t→0 (ρ(t) • (x, y)) exists and that its first component lies in J Ĩ\{i0} . In particular, T.(x, y) is not closed.

• Assume now that (T, V ) is not visible. We want to find (x, y) semisimple such that x is not semisimple. Let I ⊂ [[1, n]] be such that J I contains infinitely many nilpotent orbits. Then 0 / ∈ CH({s i |i ∈ I) (Proposition 3.2) and rk S I < dim J I = #I (7). Thus there exists non-trivial linear relations i∈I α i s i = 0 with integer coefficients and for any such relation the α i are not all of the same sign.

We can therefore write a relation of the form i∈I ′ β i s i = i∈I ′′ β i s i with each β i positive, I ′ , I ′′ = ∅ and

I ′ ⊔ I ′′ ⊂ I. Let x = (x i ) i ∈ J I ′ and, analogously in V * , let y = (y i ) i ∈ J I ′′ ⊂ V * I ′′ ⊂ V * . From this, we get that x is non-zero nilpotent, that y ∈ V * I ′′ ⊂ (V I ′ ) ⊥ ⊂ (t • x) ⊥ and that T.(x, y) ⊂ (x ′ , y ′ ) ∈ V I ′ × V * I ′′ i∈I ′ (x ′ i ) βi i∈I ′′ (y ′ i ) βi = i∈I ′ (x i ) βi i∈I ′′ (y i ) βi .
This last subset is a T -invariant closed subset of V which does not intersect {0}×V * . Let (x ′ , y ′ ) be in the closed orbit of T.(x, y). Since x ′ ⊂ J Ĩ with Ĩ ⊂ I ′ , x ′ is non-zero nilpotent hence not semisimple.

Proposition 3.9 shows that the visibility assumption in Conjecture 1.3 is necessary, since the statement fails set-theoretically in any non-visible case.. When k = C, we can state the following:

Corollary 3.10. Conjecture 1.3 holds true for representations of tori Proof. Note that the polar assumption is redundant by Corollary 3.7. According to Proposition 3.9, the generic elements of the irreducible (Proposition 3.4) variety V ⊕ V * / / /T are closed orbits of the form T.(x, y) with x regular (i.e. with T.x closed of maximal dimension among closed orbits). We may assume that x ∈ c. 4. Null-fiber of the moment map -θ case A standard reference for the theory of θ-representations is [Vin]. These representations are visible and polar but they are not always stable. A classification of the irreducible θ-representations with their main features can be found in [START_REF] Kac | Some remarks on nilpotent orbits[END_REF]§3].

Then y ∈ (t • x) ⊥ = (t • c) ⊥ = c ∨ ⊕ U ∨
Let us first introduce some notation. Let h = i∈Zm h i be a reductive Lie algebra equipped with a Z m -grading, that is [h i , h j ] ⊂ h i+j . Let H be any connected algebraic group having h as its Lie algebra. We consider the adjoint representation of G := H 0 on V := h 1 where H 0 is the connected subgroup of H with Lie algebra h 0 . Fix ω an m-th root of 1. We denote by θ the automorphism of h given by θ(x) = ω i x for x ∈ h i . If a is a θ-stable subspace of h, we can decompose a = a i with a i := a ∩ h i . We then denote the dual direct sum by a * = a ∨ i . We will identify a ∨ i and (a i ) * . We need to understand µ -1 (0). From [Vin, §1.2 and §2.2], the θ-representation k) ) i which are either simple or abelian. The ((H (k) ) 0 , (h (k) ) 1 ) with h simple are called the simple components of (H 0 , h 1 ). Then µ -1 (0) is the direct product of the µ -1 k (0) where µ k is the moment map associated to the representation ((H (k) ) 0 , (h (k) ) 1 ). In the abelian case, µ -1 (0) = h 1 ⊕ h * 1 . From now on, we will assume that h is simple.

(H 0 , h 1 ) is isomorphic to ( k (H (k) ) 0 , (h (k) ) 1 ) for some graded Lie algebras h (k) = (h (
The Killing form L(•, •) is a non-degenerate symmetric bilinear form on h × h which is invariant under H and θ. Via L, V * ∼ = h ∨ 1 identifies to h -1 . If x ∈ h and a ⊂ h, we denote the centraliser of x in a by a

x = {y ∈ a | [x, y] = 0}. Assume that ϕ ∈ V * corresponds to y ∈ h -1 via L. Then the condition ϕ ∈ (g • x) ⊥ is read 0 = L([g, x], y) = L(h 0 , [x, y]), that is [x, y] = 0 since [x, y] ∈ h 0 and L is non-degenerate on h 0 ⊕ h 0 . Thus µ -1 (0) is isomorphic to the commuting scheme: (13) µ -1 (0) ∼ = {(x, y) ∈ h 1 × h -1 | [x, y] = 0}.
We now want to define a suitable locally closed cover of h 1 satisfying the conditions stated in Section 1 Definition 4.1. We say that a Levi subalgebra l of h arises from h 1 if there exists a semisimple element s ∈ h 1 such that l = h s .

In other words, (z l ) reg ∩ h 1 = ∅ where z l is the center of l and (z l ) reg denotes the set of elements of z l whose H-orbit is of maximal dimension. Such a Levi l is clearly θ-stable. Hence l = l i gives rise to a Z m -graded reductive Lie algebra. We denote by L 0 the connected subgroup of H with Lie algebra l 0 .

Recall from [Vin] that any x ∈ h 1 has a Jordan decomposition x s + x n with x s , x n ∈ h 1 , the semisimple and nilpotent part of x, respectively. Definition 4.2. Given l a Levi subalgebra of h arising from h 1 , and O a nilpotent L 0 -orbit in l 1 , we define the decomposition class associated to (l, O) as

J(l, O) := H 0 • {(z l ) reg ∩ h 1 + O} Alternatively, x ∈ J(l, O) if and only if x is H 0 -conjugate to an element x ′ ∈ l 1 such that l = h x ′ s and O = L 0 • x ′ n .
Hence decomposition classes are equivalence classes, so they form a partition of h 1 . Next, we adapt some results of [Br] (see also [START_REF] Tauvel | Lie algebras and algebraic groups[END_REF]§39]).

Proposition 4.3. Let J(l, O) be a decomposition class. (i) If x ∈ J(l, O), then J(l, O) = H 0 • {y ∈ h 1 | h y = h x } (ii) J(l, O) is an irreducible locally closed subset of h 1 . (iii) If x ∈ J(l, O) then dim H 0 .x = dim h 1 -dim l 1 + dim O. (iv) mod(H 0 , J(l, O)) = dim(z l ) 1 .
Proof. There is no loss of generality in assuming that x satisfies h xs = l and O = L 0 • x n .

(i) From [START_REF] Tauvel | Lie algebras and algebraic groups[END_REF]35.3.3,39.1.2,39.1.1], we have {y ∈

h 1 | h y = h x } = {y ∈ l 1 | h ys = l, (l ′ ) yn = (l ′ ) xn } where l ′ := [l, l]. Since L 0 acts trivially on (z l ) reg , this yields J(l, O) ⊂ H 0 • {y ∈ h 1 |h y = h x }.
Note that the condition h ys = l implies that y, y s , y n ∈ l 1 . In order to prove the converse inclusion, it is therefore enough to show that

U := {n ∈ l ′ 1 | (l ′ ) n = (l ′ ) xn } ⊂ O. Let n ∈ U. Then l n 0 = l xn 0 so dim L 0 • n = dim L 0 • x n = dim O. The subset U is a dense open subset of (l ′ 1 )
xn by [START_REF] Tauvel | Lie algebras and algebraic groups[END_REF]35.3.3], hence U is irreducible. From [START_REF] Tauvel | Lie algebras and algebraic groups[END_REF]35.3.4], U is included in the nilpotent cone of l ′ 1 which consists of fintely many L 0 -orbits. Let O ′ be the L 0nilpotent orbit whose intersection with U is dense in U. Then U ⊂ O ′ . Since all the elements of U share the same L 0 -orbit dimension and x n ∈ O ∩U, we can eventually conclude that O = O ′ and U ⊂ O.

(ii) It is clear from the definition that J(l, O) is irreducible. Set m = dim h x for some x ∈ J(l, O). By (i), it does not depend on the choice of x. The map ϕ : y → h y , from {y ∈ h| dim h y = m} to the Grassmannian of m-dimensional subspaces in h, is a morphism of varieties [START_REF] Tauvel | Lie algebras and algebraic groups[END_REF]19.7.6,29.3.1].

By (i), J(l, O) = h 1 ∩ ϕ -1 (H 0 • (h x ))
with h x seen as an element of the Grassmannian. As orbits are locally closed sets, so are their inverse images by morphisms of varieties. Hence J(l, O) is locally closed in {y ∈ h| dim h y = m} and the result follows.

(iii) Consider ad x as an endomorphism of h. Then l is its generalized eigenspace associated to 0. Let us denote by q the sum of the other generalized eigenspaces. We have h = l ⊕ q and h •

x = [l ⊕ q, x] = (ad x)(l) ⊕ (ad x)(q) = (ad x n )(l) ⊕ q. Intersect with h 1 yields h 0 • x = l 0 • x n ⊕ q 1 . In particular, codim h1 H 0 • x = codim l1 L 0 • x n .
(iv) From the computations in (iii), we also get that h • x has trivial intersection with z l . Since

h 0 • x + (z l ) 1 is the tangeant space of J(l, O) at x, we get dim J(l, O) = dim H 0 • x + dim(z l ) 1 .
Since the elements of J(l, O) all share the same orbit dimension, we have mod(H 0 , J(l, O)) = dim J(l, O)dim H 0 • x. The result follows.

From Proposition 4.3, the decomposition classes satisfy the requirements of the covers used in Section 1. However, note that two different data (l i , O i ), i = 1, 2 can give rise to the same decomposition class. In the sequel, we fix a Cartan subspace c ⊂ h 1 , that is a maximal subspace of commuting semisimple elements. The number dim c is called the rank of (H 0 , h 1 ). Definition 4.4. We say that a property P is hereditary if, whenever P holds on a θ-representation (H 0 , h 1 ), it holds on the restricted θ-representation ((H s 0 ) • , h t 1 ) for any semisimple element t ∈ h 1 . Here, (H s 0 ) • is the connected subgroup of H 0 whose Lie algebra is g s 0 .

Next, we recall a few classical facts.

Lemma 4.5. Let (H 0 , h 1 ) be a θ-representation with Cartan subspace c ⊂ h 1 .

(i) For an element in general position s ∈ c, we have Proof. (i) follows from [START_REF] Vinberg | The Weyl group of a graded Lie algebra[END_REF]§3.2]. Since θ-representations are visible, it follows from Remark 1.8 that mod(H 0 , h 1 ) = dim h 1m 0 where m 0 is the maximal orbit dimension in h 1 . By (i), Proposition 4.3 (iv) and ( 1), the maximal modality of a decomposition class is mod(H 0 , h 1 ) = dim c. Assertion (ii) follows. From Proposition 4.3 (iii), an element x = x s +x n can have maximal orbit dimension in h 1 only if L 0 • x n is of maximal dimension in l 1 with l = h xs . This is possible with x n = 0 only if l ′ 1 = {0} where l ′ = [l, l]. Since l 1 contains a Cartan subspace, this implies that l 1 is a Cartan subspace. On the other hand, assume that there exists s ∈ c such that

h s = h c and (z(h s )) 1 = c. (ii) (H 0 , h 1 ) is locally free if and only if dim h 1 = dim h 0 + dim c. (iii) (H 0 , h 1 )
h s 1 = z(h s ) 1 = c. Then J(h s , {0}) is a decomposition class of dimension dim H 0 • s + mod(H 0 , J(h s , {0})) = dim h 1 -dim h s 1 + 0 + dim z(h s ) 1 = dim h 1 by Proposition 4.3. Hence J(h s , {0}
) is the open class in h 1 . Since it is made of semisimple elements, the representation is stable. (iv) follows from [START_REF] Bulois | Towards a symplectic version of the Chevalley restriction theorem[END_REF]Lemma 6.3].

Recall from [START_REF] Bulois | Towards a symplectic version of the Chevalley restriction theorem[END_REF]Proposition 4.3] that µ -1 (0) can be irreducible only if (H 0 , h 1 ) is stable.

Theorem 4.6. Assume that (H 0 , h 1 ) is a stable and locally free θ-representation with h simple, then i) µ -1 (0) is an irreducible and reduced complete intersection ii) µ -1 (0) is normal if and only if (H 0 , h 1 ) does not belong to Table 1 Corollary 4.7. Under the hypothesis of the previous theorem and if h is of classical type, then µ -1 (0) is normal From [Pan, Theorem 3.2] (or, alternatively, Remark 1.8 and Corollary 1.7), (i) holds. The remaining of the section is devoted to the proof of Theorem 4.6 (ii).

Type

Kac diagram m n w

E

(1) 6

1 1 0 1 1 1 1 9 x α2+α4 +x α3+α4 +x α5+α4
x α4

E

(1) 7

1 1 1 0 1 1 1 1 14 idem idem

E

(1) 8

1 1 0 1 1 1 1 1 1 24 idem idem 1 1 0 1 0 1 1 1 1 20 x α4+α5+α6 +x α6+α7
x α6

1 0 1 0 1 0 1 1 0 15

x α2+α3+α4 +x α2+α4+α5 +x α5+α6+α7 +x α7+α8

x α2 , x α7 Recall that all Cartan subspaces of h 1 are conjugate. From Lemma 4.5 (i) (iii) and Proposition 4.3 (iv), the decomposition class J(h c , {0}) is the only one with maximal modality mod(H 0 , h 1 ) = dim c. Moreover, the decomposition classes with mod(H 0 , J(l, O)) = dim c -1 are the ones such that dim(z l ) 1 = dim c -1 and O arbitrary. The condition on l means that (L 0 , l ′ 1 ) is a θ-representation of rank one, where l ′ is the derived subalgebra of l.

Recall that, for x ∈ h 1 with l = h xs , we have h x,y 0 ⊂ h x ⊂ l and that l 0 = l ′ 0 by Lemma 4.5 (iv). Hence, using Corollary 1.7 (v), we have: Lemma 4.8. Under hypothesis of Theorem 4.6, µ -1 (0) is normal if and only if

(P) ∀n ∈ l ′ 1 nilpotent, ∃n ′ ∈ (l ′ ) n -1 such that (l ′ ) (n,n ′ ) 0 = {0}.
for any Levi subalgebra l ⊂ h arising from h 1 such that (L 0 , l ′ 1 ) is of rank one:

In other words, µ -1 (0) is normal if and only if the same holds for the semisimple part of any Levi subalgebra arising from h 1 whose associated θ-representation is of rank one. The main difference with the symmetric Lie algebra case studied in [Pan] is that we have many θ-representations of rank one. We now aim to classify them. For this, we recall a few features of the so-called Kac diagrams. The reader is referred to [START_REF] Kac | Some remarks on nilpotent orbits[END_REF]§3] or [START_REF] Vinberg | The Weyl group of a graded Lie algebra[END_REF]§8] for a detailed treatment.

• A Kac diagram is an affine (possibly twisted) Dynkin diagram X (ℓ) n equipped with an integer label for each node. Up to isomorphisms of representations, it is enough to consider labels in {0, 1, 2}. If we focus on representations of positive rank, one can restricts to labels in {0, 1}.

• If X n (ℓ) with a labelling (v 0 , . . . , v n ) form a Kac diagram, then it gives rise to a Z m -grading on a reductive Lie algebra h, where m = ℓ v i .

• The Lie algebra h 0 is a reductive algebra whose semisimple part is the Lie algebra corresponding to the subdiagram of 0-labelled nodes. n ( 1). They give rise to the only θ-representations of positive rank (H 0 , h 1 ) where H 0 is a torus. Lemma 4.9. Let (H 0 , h 1 ) be a θ-representation corresponding to a Kac diagram of the form X (ℓ) n ( 1). Then (H 0 , h 1 ) is stable locally free of rank 1, and µ -1 (0) is a normal variety.

Proof. In this case, h 0 is just the Cartan subalgebra of h (associated with the Dynkin diagram without the extended node α n+1 ) and h 1 is the sum of root spaces

h αi , i ∈ [[1, n + 1]].
Local freeness is clear since α 1 , . . . α n is a basis of h * 0 . By Lemma 4.5 (ii), the rank of (H 0 , h 1 ) is one. Since α n+1 is the opposite of the highest root, there is a single relation linking the α i : α n+1 = i∈ [[1,n]] a i α i with a i < 0. By Corollary 3.3, (H 0 , h 1 ) is stable and µ -1 (0) is normal.

Proposition 4.10. Let (H 0 , h 1 ) be a stable and locally free θ-representation of rank 1 obtained from a simple Lie algebra h. Then (H 0 , h 1 ) corresponds to a Kac diagram of the form X (ℓ) n ( 1) or which appears in Table 1 or Table 2 Proof. When the Lie algebra h is exceptional we use the software [GAP] and its package [SLA]. We proceed as follows 1 .

Given h of exceptional type (respectively of type D 4 ), the first step consists in listing the Kac-diagrams relative to h (resp. with underlying Dynkin diagram D

(3) 4 ) with labels in {0, 1}. Then we select the corresponding gradings for which dim h 1 = dim h 0 + 1. There are few of them. For each selected grading, we choose a random element x ∈ h 1 and compute its semisimple part s. Since the rank of (H 0 , h 1 ) is at least 1, the element s should be non-zero (otherwise choose another x). Then, (H 0 , h 1 ) is stable locally free of rank 1 if and only if dim h s 1 = 1 (Lemma 4.5). In addition to the X (ℓ) n ( 1), the only other Kac diagrams arising in this way are those of Tables 1 and2.

Assume now that h ⊂ gl(V ) is classical. Our goal is to show that the only stable and locally free θ-representatons of rank 1 are those arising from the X (ℓ) n ( 1). The strategy is similar to the exceptional case, except that we rather rely on the description of classical θ-representations of Vinberg [START_REF] Vinberg | The Weyl group of a graded Lie algebra[END_REF]§7]. We refer to this paper and we use the notation therein. In particular, there are four subcases to consider:

First case: θ is an inner automorphism of h = sl(V ) (type A); Second case: h is of type B or D; Third case: h is of type C; Fourth case: θ outer and h of type A.

In the first three cases (respectively in the fourth case) θ (respectively θ 2 ) is an automorphism of order m 0 given by g → aga -1 for some a ∈ GL(V) satisfying a m0 ∈ {±Id}. For θ of order 1 or 2, the only locally free case of rank 1 is A

(1) 1 ( 1) so we may assume that m 0 > 1. Then V = λ∈S V (λ) where V (λ) = {x ∈ V |a.x = λx} and S = {λ|λ m0 = +1} or S = {λ|λ m0 = -1}. That is S = {λ 0 ω j 0 |j ∈ Z m0 } for λ 0 = 1 or exp( 2iπ 2m0 ) and ω 0 := exp( 2iπ m0 ). For j ∈ Z m0 , we set λ j := λ 0 ω j 0 and k j := dim V (λ j ). The elements x ∈ h k satisfy x.V (λ j ) ⊂ V (λ j+k ) for any j ∈ Z m0 .

We first look at the first case. From [Vin], the rank of (H

0 , h 1 ) is min j∈Zm 0 k j . Since h 0 ∼ = sl(V ) ∩ j∈Zm 0 gl(V j )) and h 1 ∼ = j∈Zm 0 Hom(V j , V j+1 ), we have dim h 1 -dim h 0 =   j∈Zm 0 k j k j+1   -   j∈Zm 0 k 2 j -1   = 1 - 1 2 j∈Zm 0 (k j -k j+1 ) 2 .
From Lemma 4.5 (ii), we want that this number is 1. The only possibility is that k j = k j ′ for any j, j ′ ∈ Z m0 and the condition on the rank forces this common value to be 1. In this particular case, H 0 is a torus so this must coincide with a grading given by a Kac diagram of the form A

(1) n ( 1) (inner automorphism).

From now on we focus on the last three cases. In each of these cases, a nondegenerate bilinear form comes into play. This form induces a duality between V (λ) and V (λ) and we have k j = kj where j denotes the element of Z m0 satisfying λj = λ j . Depending on whether each elements 1 and -1 belong to S or not, the corresponding θ-representations may have different behavior. For ν ∈ {±1}, we set η ν := 1 if ν ∈ S -1 if ν / ∈ S . Set also ǫ 1 := 1 in the 2nd and 4th case -1 in the 3rd case and ǫ -1 := 1 in the 2nd case -1 in the 3rd and 4th case . We then have a uniform formula

dim h 1 -dim h 0 = 1 2   j k j k j+1 - j k 2 j + (ǫ 1 η 1 k 0 + ǫ -1 η -1 k m ′ )   = 1 4   - j (k j -k j+1 ) 2 + 2ǫ 1 η 1 k 0 + 2ǫ -1 η -1 k m ′  
In a nutshell, h 0 is a product of the gl(V j ) ∼ = gl(Vj) for λ j / ∈ {±1} and possible copies of so(V j ) or sp(V j ) for λ j ∈ {±1}. A similar combinatoric holds for h 1 . In the fourth case, the assumption m 0 > 1 ensures that kId V lies in a k-th part of the grading in gl(V ) satisfying k / ∈ {0, 1}. We choose m ′ ∈ Z m0 such that Re(λ m ′ ) is minimal. By convention, the argument of a complex number is taken in [0, 2π[. Choosing j min ∈ Z m0 such that k j is minimal and Im(λ j ) 0, we define I = j arg(λ j ) < arg(λ jmin ) or arg(λ m ′ ) arg(λ j ) < arg(λ jmin ) , I = j arg(λ jmin ) arg(λ j ) < arg(λ m ′ ) or arg(λ jmin ) arg(λ j ) .

Using the equality n 2 = n(n -1) + n, we can write

dim h 1 -dim h 0 = 1 4   - j∈I (k j -k j+1 )(k j -k j+1 -1) - j∈J (k j+1 -k j )(k j+1 -k j -1) + j∈I (k j+1 -k j ) + j∈J (k j -k j+1 ) + 2ǫ 1 η 1 k 0 + 2ǫ -1 η -1 k m ′  
The first two terms are non-positive and the rest of the expression is equal to

(k jmin -k 0 ) + (k jmin -k m ′ ) + (k jmin -k m ′ ) + (k jmin -k 0 ) + 2ǫ 1 η 1 k 0 + 2ǫ -1 η -1 k m ′ = 2 [(ǫ 1 η 1 -1)k 0 + k jmin ]+2 [(ǫ -1 η -1 -1)k m ′ + k jmin ].
Each of the terms in brackets is either equal to k jmin if ǫ ν η ν = 1, or is not greater than -k jmin if ǫ ν η ν = -1. In particular, dim h 1dim h 0 can be positive only if ǫ ν η ν = 1 for ν ∈ {±1}. Hence, it is of type I in the terminology of [START_REF] Vinberg | The Weyl group of a graded Lie algebra[END_REF]§7.2], and its rank is k jmin . Then, it follows from our formulas and Lemma 4.5 that the only locally free cases of rank 1 are the following ones

   k jmin = 1, ∀j ∈ I, k j -k j+1 ∈ {0, 1}, ∀j ∈ J, k j+1 -k j ∈ {0, 1}    and      ±1 ∈ S
in the 2nd case ±1 / ∈ S in the 3rd case 1 ∈ S, -1 / ∈ S in the 4th case .

In the last three cases, the action is not stable in general. Given subspaces U (λ) ⊂ V (λ) of dimension 1, we can construct a non-zero semisimple element C ∈ h 1 such that C(U (λ)) = U (ω 0 λ). Then V ′ := Ker(C) decomposes as V ′ := λ V ′ (λ); the decomposition in two summands V = ( λ U (λ)) ⊕ V ′ is orthogonal and the derived subalgebra of gl(V ) C can be identified with sl(V ′ ). If there exists j ∈ Z m0 such that k j , k j+1 2, then we can construct in each case a non-zero element N in h C 1 ∩ sl(V ′ ) with N (V ′ (λ j )) ⊂ V ′ (λ j+1 ), N (V ′ (λ j+1 )) ⊂ V ′ (λ j ) and N (U (λ)) = 0 = N (V ′ (λ k )) for any λ ∈ S and any k / ∈ {j, j + 1}. This contradicts the stability hypothesis since N ∈ h C \ kC, see Lemma 4.5 (iii). Thus, the only stable gradings to consider are those with k j = 1 for j such that λ j / ∈ {±1} k j ∈ {1, 2} for j such that λ j ∈ {±1} .

The different possibilities are listed in Table 3 (up to multiplication of a by -1 in type B, which gives rise to the same grading). Once again, H 0 is a torus in each case so the corresponding grading must be obtained from a Kac diagram of the form X (ℓ)

n ( 1). These Kac diagrams are identified in the last column of Table 3 . In each case, it turns out that there exists i such that w i = {0}. Hence (P) must fail in these cases. An example

  and rk S I d = rk S -#I f . Assuming that rk S I d \{i} = rk S I d -1 for some i ∈ I d , we would then have rk S î rk S I d -1 + #(I f ) = rk S -1, which contradicts the assumption i ∈ I d . So rk S I d \{i} = rk S I d for any i ∈ I d and (T, V I d ) satisfies hypothesis of Theorem 2.2 (iii-iv). Hence µ -1

  and, since T.y is closed, we get y ∈ c ∨ [DK, Corollary 2.5]. Hence (1) of Remark 1.4 holds Statement (2) follows from Proposition 3.4.

  is stable if and only if there exists s ∈ c such that h s 1 = z(h s ) 1 = c. (iv) Stability and local freeness are both hereditary properties.

Table 1 .

 1 Exceptional non-normal

	Type	Kac diagram

Table 2 .

 2 Exceptional normalFor this, we first rephrase condition (5) in Lemma 4.8. Then we list all the θrepresentations of rank one in Proposition 4.10. In Lemma 4.11, we check which of them satisfies condition (P). Finally, we check that the non-normal cases of rank one do not yield any non-normal example of greater rank in Lemma 4.12.

  The rank of h 0 is that of the finite Dynkin diagram giving rise to X

			(ℓ) n .
	For instance, for each affine Dynkin diagram X	(ℓ) n appearing in the classification
	of Kac [Kac, §3, Table 1], we can label each node of X	(ℓ) n with 1. We denote such
	a Kac diagram by X	(ℓ)

.

  Lemma 4.11. If (H 0 , h 1 ) is a θ-representation associated to aKac diagram of Table 1 (resp. Table 2) then it does not satisfy (resp. it satisfies) condition (P) of Lemma 4.8. The proof of this lemma relies on computer-based computations. First, we list representatives of the nilpotent H 0 -orbits on h 1 . For any such representative n i , we choose a random element n ′ i ∈ h n -1 . Then we compute h . It turns out to be {0} for each i in cases of Table 2 so (P) holds. In cases of Table 1, we compute w i := {y ∈ h ni 0 | [y, h ni -1 ] = {0}} = z∈h n i

		(ni,n ′ i ) 0
	-1	(ni,z) h 0

The detail of the GAP-computations used in Propositions 4.10 and Lemmas 4.11 and 4.12 can be found in the auxilary file "computations_rk1.txt"

Case

Parity of m 0 Parity of dim(V ) Condition on the k j X (ℓ)

n ( 1)

First case / / ∀j, k j = 1 A

(1)

Second case even

n ( 1)

Third case even even ∀j, k j = 1 C

(1)

Fourth case odd even

2p ( 1) Table 3. Stable classical locally free grading of rank 1 of such n i , w i is given in the table, using the numbering of the roots as in [Bo] and where x α denotes a root vector for the root α.

Lemma 4.12. Let (H 0 , h 1 ) be a locally free stable θ-representation with h simple. Then there is no proper Levi l arising from h 1 such that (L 0 , l ′ 1 ) corresponds to a Kac diagram of Table 1.

Proof. Assume that such a proper Levi exists. Then h is of type E 7 or E 8 and the Cartan subspace of h 1 is of dimension 2 or 3. Moreover the order of the automorphism θ giving rise to the graduation is a multiple of 9 or 14. We can now consider all the possible Kac diagrams of type E 7 or E 8 such that dim g 1dim g 0 ≥ 2. After computation, it turns out that the resulting Z m -gradings have order which are not multiple of 9 or 14, which is a contradiction. Remark 4.13. Conjecture 1.3 in the case of a locally free stable θ-representation follows from [START_REF] Bulois | Towards a symplectic version of the Chevalley restriction theorem[END_REF]Theorem 1.2]. We briefly explain here how to recover it using the results of this paper. First, note that the 5 exceptional cases of Table 1 are of rank one. Then it follows from [START_REF] Bulois | Towards a symplectic version of the Chevalley restriction theorem[END_REF]Proposition 3.4 & 5.1] that the natural map c ⊕ c ∨ /W → V ⊕ V * / / /G is a dominant closed immersion, hence an isomorphism. In the other cases, Theorem 4.6 ensures that µ -1 (0) is normal. So the same holds for the symplectic reduction and the result follows from [START_REF] Bulois | Towards a symplectic version of the Chevalley restriction theorem[END_REF]Proposition 5.1] and Remark 1.4. Note that the ground results on polar representations of [DK] are known for θrepresentations over any algebraically closed field of characteristic zero. Thus, we don't need the assumption k = C used in [BLLT].