Florent Krzakala

Cristopher Moore

Elchanan Mossel

Joe Neeman

Allan Sly

Lenka Zdeborova

Pan Zhang

Lenka Zdeborová

Spectral redemption in clustering sparse networks

Detecting communities or modules is a central task in the study of social, biological, and technological networks. Two of the most popular approaches are statistical inference, where we fix a generative model such as the stochastic block model to the network [START_REF] Holland | Stochastic blockmodels: First steps[END_REF][START_REF] Wang | Stochastic Blockmodels for Directed Graphs[END_REF]; and spectral methods, where we classify vertices according to the eigenvectors of a matrix associated with the network such as its adjacency matrix or Laplacian [START_REF] Luxburg | A tutorial on spectral clustering[END_REF].

Both statistical inference and spectral methods have been shown to work well in networks that are sufficiently dense, or when the graph is regular [START_REF] Bickel | A nonparametric view of network models and Newman-Girvan and other modularities[END_REF][START_REF] Coja-Oghlan | A Spectral Approach to Analyzing Belief Propagation for 3-Coloring[END_REF][START_REF] Coja-Oghlan | Graph partitioning via adaptive spectral techniques[END_REF][START_REF] Mcsherry | Spectral partitioning of random graphs[END_REF][START_REF] Nadakuditi | Graph spectra and the detectability of community structure in networks[END_REF]. However, for sparse networks with widely varying degrees, the community detection problem is harder. Indeed, it was recently shown [START_REF] Decelle | Phase transition in the detection of modules in sparse networks[END_REF][START_REF] Decelle | Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications[END_REF][START_REF] Mossel | Stochastic Block Models and Reconstruction[END_REF] that there is a phase transition below which communities present in the underlying block model are impossible for any algorithm to detect. While standard spectral algorithms succeed down to this transition when the network is sufficiently dense, with an average degree growing as a function of network size [START_REF] Nadakuditi | Graph spectra and the detectability of community structure in networks[END_REF], in the case where the average degree is constant these methods fail significantly above the transition [START_REF] Zhang | Comparative study for inference of hidden classes in stochastic block models[END_REF]. Thus there is a large regime in which statistical inference succeeds in detecting communities, but where current spectral algorithms fail.

It was conjectured in [START_REF] Mossel | Stochastic Block Models and Reconstruction[END_REF] that this gap is artificial and that there exists a spectral algorithm that succeeds all the way to the detectability transition even in the sparse case. Here, we propose an algorithm based on a linear operator considerably different from the adjacency matrix or its variants: namely, a matrix that represents a walk on the directed edges of the network, with backtracking prohibited. We give strong evidence that this algorithm indeed closes the gap.

The fact that this operator has better spectral properties than, for instance, the standard random walk operator has been used in the past in the context of random matrices and random graphs [START_REF] Mckay | The expected eigenvalue distribution of a large regular graph[END_REF][START_REF] Sasha | Random matrices, nonbacktracking walks, and orthogonal polynomials[END_REF][START_REF] Friedman | A proof of Alon's second eigenvalue conjecture and related problems[END_REF]. In the theory of zeta functions of graphs, it is known as the edge adjacency operator, or the Hashimoto matrix [START_REF] Hashimoto | Zeta functions of finite graphs and representations of p-adic groups. Automorphic forms and geometry of arithmetic varieties[END_REF]. It has been used to show fast mixing for the non-backtracking random walk [START_REF] Alon | Non-backtracking random walks mix faster[END_REF], and arises in connection to belief propagation [START_REF] Watanabe | Graph zeta function in the Bethe free energy and loopy belief propagation[END_REF][START_REF] Vontobel | Connecting the Bethe entropy and the edge zeta function of a cycle code[END_REF], in particular to rigorously analyze the behavior of belief propagation for clustering problems on regular graphs [START_REF] Coja-Oghlan | A Spectral Approach to Analyzing Belief Propagation for 3-Coloring[END_REF]. It has also been used as a feature vector to classify graphs [START_REF] Ren | Graph characterization via Ihara coefficients[END_REF]. However, using this operator as a foundation for spectral clustering and community detection appears to be novel.

We show that the resulting spectral algorithms are optimal for networks generated by the stochastic block model, finding communities all the way down to the detectability transition. That is, at any point above this transition, there is a gap between the eigenvalues related to the community structure and the bulk distribution of eigenvalues coming from the random graph structure, allowing us to find a labeling correlated with the true communities. In addition to our analytic results on stochastic block models, we also illustrate the advantages of the non-backtracking operator over existing approaches for some real networks. Here n = 4000, cin = 5, and cout = 1, and we average over 20 realizations. Even though the eigenvalue λc = 3.5 given by ( 2) satisfies the threshold condition (1) and lies outside the semicircle of radius 2 √ c = 3.46, deviations from the semicircle law cause it to get lost in the bulk, and the eigenvector of the second largest eigenvalue is uncorrelated with the community structure. As a result, spectral algorithms based on A are unable to identify the communities in this case.

I. SPECTRAL CLUSTERING AND SPARSE NETWORKS

In order to study the effectiveness of spectral algorithms in a specific ensemble of graphs, suppose that a graph G is generated by the stochastic block model [START_REF] Holland | Stochastic blockmodels: First steps[END_REF]. There are q groups of vertices, and each vertex v has a group label g v ∈ {1, . . . , q}. Edges are generated independently according to a q × q matrix p of probabilities, with Pr[A u,v = 1] = p gu,gv . In the sparse case, we have p ab = c ab /n, where the affinity matrix c ab stays constant in the limit n → ∞.

For simplicity we first discuss the commonly-studied case where c has two distinct entries, c ab = c in if a = b and c out if a = b. We take q = 2 with two groups of equal size, and assume that the network is assortative, i.e., c in > c out . We summarize the general case of more groups, arbitrary degree distributions, and so on in subsequent sections below.

The group labels are hidden from us, and our goal is to infer them from the graph. Let c = (c in + c out )/2 denote the average degree. The detectability threshold [START_REF] Decelle | Phase transition in the detection of modules in sparse networks[END_REF][START_REF] Decelle | Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications[END_REF][START_REF] Mossel | Stochastic Block Models and Reconstruction[END_REF] states that in the limit n → ∞, unless

c in -c out > 2 √ c , (1)
the randomness in the graph washes out the block structure to the extent that no algorithm can label the vertices better than chance. Moreover, [START_REF] Mossel | Stochastic Block Models and Reconstruction[END_REF] proved that below this threshold, it is impossible to identify the parameters c in and c out , while above the threshold the parameters c in and c out are easily identifiable. The adjacency matrix is defined as the n × n matrix A u,v = 1 if (u, v) ∈ E and 0 otherwise. A typical spectral algorithm assigns each vertex a k-dimensional vector according to its entries in the first k eigenvectors of A for some k, and clusters these vectors according to a heuristic such as the k-means algorithm (often after normalizing or weighting them in some way). In the case q = 2, we can simply label the vertices according to the sign of the second eigenvector.

As shown in [START_REF] Nadakuditi | Graph spectra and the detectability of community structure in networks[END_REF], spectral algorithms succeed all the way down to the threshold (1) if the graph is sufficiently dense. In that case A's spectrum has a discrete part and a continuous part in the limit n → ∞. Its first eigenvector essentially sorts vertices according to their degree, while the second eigenvector is correlated with the communities. The second eigenvalue is given by

λ c = c in -c out 2 + c in + c out c in -c out . ( 2
)
The question is when this eigenvalue gets lost in the continuous bulk of eigenvalues coming from the randomness in the graph. This part of the spectrum, like that of a sufficiently dense Erdős-Rényi random graph, is asymptotically distributed according to Wigner's semicircle law [START_REF] Wigner | On the distribution of the roots of certain symmetric matrices[END_REF]

P (λ) = 1 2πc 4c -λ 2 .
-1

1 2 3 -1.5 -1.0 -0.5 0.5 1.0 1.5 µ c
FIG. 2: The spectrum of the non-backtracking matrix B for a network generated by the block model with same parameters as in Fig. 1. The leading eigenvalue is at c = 3, the second eigenvalue is close to µc = (cin -cout)/2 = 2, and the bulk of the spectrum is confined to the disk of radius √ c = √ 3. Since µc is outside the bulk, a spectral algorithm that labels vertices according to the sign of B's second eigenvector (summed over the incoming edges at each vertex) labels the majority of vertices correctly.

Thus the bulk of the spectrum lies in the interval

[-2 √ c, 2 √ c]. If λ c > c
, which is equivalent to (1), the spectral algorithm can find the corresponding eigenvector, and it is correlated with the true community structure. However, in the sparse case where c is constant while n is large, this picture breaks down due to a number of reasons. Most importantly, the leading eigenvalues of A are dictated by the vertices of highest degree, and the corresponding eigenvectors are localized around these vertices [START_REF] Krivelevich | The largest eigenvalue of sparse random graphs[END_REF]. As n grows, these eigenvalues exceed λ c , swamping the community-correlated eigenvector, if any, with the bulk of uninformative eigenvectors. As a result, spectral algorithms based on A fail a significant distance from the threshold given by [START_REF] Holland | Stochastic blockmodels: First steps[END_REF]. Moreover, this gap grows as n increases: for instance, the largest eigenvalue grows as the square root of the largest degree, which is roughly proportional to log n/ log log n for Erdős-Rényi graphs. To illustrate this problem, the spectrum of A for a large graph generated by the block model is depicted in Fig. 1.

Other popular operators for spectral clustering include the Laplacian L = D -A where D uv = d u δ u,v is the diagonal matrix of vertex degrees, the random walk matrix Q uv = A uv /d u , and the modularity matrix

M uv = A uv -d u d v /(2m).
However, all these experience qualitatively the same difficulties as with A in the sparse case. Another simple heuristic is to simply remove the high-degree vertices (e.g. [START_REF] Coja-Oghlan | Graph partitioning via adaptive spectral techniques[END_REF]), but this throws away a significant amount of information; in the sparse case it can even destroy the giant component, causing the graph to fall apart into disconnected pieces [START_REF] Bollobas | The phase transition in inhomogeneous random graphs[END_REF].

II. THE NON-BACKTRACKING OPERATOR

The main contribution of this paper is to show how to redeem the performance of spectral algorithms in sparse networks by using a different linear operator. The non-backtracking matrix B is a 2m × 2m matrix, defined on the directed edges of the graph. Specifically,

B (u→v),(w→x) = 1 if v = w and u = x 0 otherwise .
Using B rather than A addresses the problem described above. The spectrum of B is not sensitive to high-degree vertices, since a walk starting at v cannot turn around and return to it immediately. Other convenient properties of B are that any tree dangling off the graph, or disconnected from it, simply contributes zero eigenvalues to the spectrum, since a non-backtracking walk is forced to a leaf of the tree where it has nowhere to go. Similarly one can show that unicyclic components yield eigenvalues that are either 0, 1 or -1.

As a result, B has the following spectral properties in the limit n → ∞ in the ensemble of graphs generated by the block model. The leading eigenvalue is the average degree c = (c in + c out )/2. At any point above the detectability threshold (1), the second eigenvalue is associated with the block structure and reads

µ c = c in -c out 2 . (3)
Moreover, the bulk of B's spectrum is confined to the disk in the complex plane of radius √ c, as shown in Fig. 2.

As a result, the second eigenvalue is well separated from the top of the bulk, i.e., from the third largest eigenvalue in absolute value, as shown in Fig. 3.

The eigenvector corresponding to µ c is strongly correlated with the community structure. Since B is defined on directed edges, at each vertex we sum this eigenvector over all its incoming edges. If we label vertices according to the sign of this sum, then the majority of vertices are labeled correctly (up to a change of sign, which switches the two communities). Thus a spectral algorithm based on B succeeds when µ c > √ c, i.e. when (1) holds-but unlike standard spectral algorithms, this criterion now holds even in the sparse case. We present arguments for these claims in the next section.

III. RECONSTRUCTION AND A COMMUNITY-CORRELATED EIGENVECTOR

In this section we sketch justifications of the claims in the previous section regarding B's spectral properties, showing that its second eigenvector is correlated with the communities whenever (1) holds. Let us start by recalling how to generalize equation ( 2) for the adjacency matrix A of sparse graphs. We follow [START_REF] Mossel | Stochastic Block Models and Reconstruction[END_REF], who derived a similar result in the case of random regular graphs.

With µ = µ c defined as in (3), for a given integer r, consider the vector

f (r) v = µ -r u:d(u,v)=r σ u , (4)
where σ u = ±1 denotes u's community. By the theory of the reconstruction problem on trees [START_REF] Kesten | Additional limit theorems for indecomposable multidimensional Galton-Watson processes[END_REF][START_REF] Mossel | Information flow on trees[END_REF], if (1) holds then the correlation f (r) , σ /n is bounded away from zero in the limit n → ∞.

We will show that if r is large but small compared to the diameter of the graph, then f (r) is closely related to the second eigenvector of B. Thus if we label vertices according to the sign of this second eigenvector (summed over all incoming edges at each vertex) we obtain the true communities with significant accuracy.

First we show that f (r) approximately obeys an eigenvalue equation that generalizes [START_REF] Wang | Stochastic Blockmodels for Directed Graphs[END_REF]. As long as the radius-r neighborhood of v is a tree, we have

(Af (r) ) v = µ -r   u:d(u,v)=r+1 σ u + (d v -1) u:d(u,v)=r-1 σ u   , so (Af (r) ) v = µf (r+1) v + (d v -1)µ -1 f (r-1) v . (5)
Summing over v's neighborhood gives the expectation

E u∈N (v) σ u = µσ v ,
and summing the fluctuations over the (in expectation) c r vertices at distance r gives

f (r) v -f (r±1) v = O(c r/2 µ -r ) .
If µ = µ c and (1) holds so that µ c > √ c, these fluctuations tend to zero for large r. In that case, we can identify f (r) with f (r±1) , and (5) becomes

Af = µf + (D -1)µ -1 f . (6)
In particular, in the dense case we can recover (2) by approximating D with c1, or equivalently pretending that the graph is c-regular. Then f is an eigenvector of A with eigenvalue

λ c = µ + (c -1)µ -1 .
We define an analogous approximate eigenvector of B,

g (r) u→v = µ -r (w,x):d(u→v,w→x)=r σ x ,
where now d refers to the number of steps in the graph of directed edges. We have in expectation

Bg (r) = µg (r+1) ,
and as before |g (r) -g (r+1) | tends to zero as r increases. Identifying them gives an approximate eigenvector g with eigenvalue µ,

Bg = µg . (7)
Furthermore, summing over all incoming edges gives u∈N (v)

g u→v = f v ,
giving signs correlated with the true community memberships σ v . We note that the relation between the eigenvalue equation ( 7) for B and the quadratic eigenvalue equation ( 6) is exact and well known in the theory of zeta functions of graphs [START_REF] Hashimoto | Zeta functions of finite graphs and representations of p-adic groups. Automorphic forms and geometry of arithmetic varieties[END_REF][START_REF] Bass | The Ihara-Selberg zeta function of a tree lattice[END_REF][START_REF] Angel | The non-backtracking spectrum of the universal cover of a graph[END_REF]. More generally, all eigenvalues µ of B that are not ±1 are the roots of the equation

det µ 2 1 -µA + (D -1) = 0 . ( 8
)
This equation hence describes 2n of B's eigenvalues. These are the eigenvalues of a 2n × 2n matrix,

B = 0 D -1 -1 A . (9)
The left eigenvectors of B are of the form (f, -µf ) where f obeys [START_REF] Coja-Oghlan | Graph partitioning via adaptive spectral techniques[END_REF]. Thus we can find f by dealing with a 2n × 2n matrix rather than a 2m × 2m one, which considerably reduces the computational complexity of our algorithm.

Next, we argue that the bulk of B's spectrum is confined to the disk of radius √ c. First note that for any matrix

B, 2m
i=1 |µ i | 2r ≤ tr B r (B r ) T .
On the other hand, for any fixed r, since G is locally treelike in the limit n → ∞, each diagonal entry (u → v, u → v) of B r (B r ) T is equal to the number of vertices exactly r steps from v, other than those connected via u. In expectation this is c r , so by linearity of expectation E tr B r (B r ) T = 2mc r . In that case, the spectral measure has the property that

E(|µ| 2r ) ≤ c r .
Since this holds for any fixed r, we conclude that almost all of B's eigenvalues obey |µ| ≤ √ c. Proving rigorously that all the eigenvalues in the bulk are asymptotically confined to this disk requires a more precise argument and is left for future work.

As a side remark we note that (8) yields B's spectrum for d-regular graphs [START_REF] Angel | The non-backtracking spectrum of the universal cover of a graph[END_REF]. There are n pairs of eigenvalues µ ± such that

µ ± = λ ± λ 2 -4(d -1) 2 , ( 10
)
where λ are the (real) eigenvalues of A. These are related by µ + µ -= d -1, so all the non-real eigenvalues of B are conjugate pairs on the circle of radius √ d -1. The other eigenvalues are ±1. For random regular graphs, the asymptotic spectral density of B follows straightforwardly from the well known result of [START_REF] Mckay | The expected eigenvalue distribution of a large regular graph[END_REF] for the spectral density of the adjacency matrix.

Finally, the singular values of B are easy to derive for any simple graph, i.e., one without self-loops or multiple edges. Namely, BB T is block-diagonal: for each vertex v, it has a rank-one block of size d v that connects v's outgoing edges to each other. As a consequence, B has n singular values d v -1, and its other 2m -n singular values are 1. However, since B is not symmetric, its eigenvalues and its singular values are different-while its singular values are controlled by the vertex degrees, its eigenvalues are not. This is precisely why its spectral properties are better than those of A and related operators.

IV. MORE THAN TWO GROUPS AND GENERAL DEGREE DISTRIBUTIONS

The arguments given above regarding B's spectral properties generalize straightforwardly to other graph ensembles. First, consider block models with q groups, where for 1 ≤ a ≤ q group a has fractional size n a . The average degree of group a is c a = b c ab n b . The hardest case is where c a = c is the same for all a, so that we cannot simply label vertices according to their degree.

The leading eigenvector again has eigenvalue c, and the bulk of B's spectrum is again confined to the disk of radius √ c. Now B has q -1 linearly independent eigenvectors with real eigenvalues, and the corresponding eigenvectors are correlated with the true group assignment. If these real eigenvalues lie outside the bulk, we can identify the groups by assigning a vector in R q-1 to each vertex, and applying a clustering technique such as k-means. These eigenvalues are of the form µ = cν where ν is a nonzero eigenvalue of the q × q matrix

T ab = n a c ab c -1 . (11)
In particular, if n a = 1/q for all a, and c ab = c in for a = b and c out for a = b, we have µ c = (c in -c out )/q. The detectability threshold is again µ c > √ c, or

|c in -c out | > q √ c . (12)
More generally, if the community-correlated eigenvectors have distinct eigenvalues, we can have multiple transitions where some of them can be detected by a spectral algorithm while others cannot.

There is an important difference between the general case and q = 2. While for q = 2 it is literally impossible for any algorithm to distinguish the communities below this transition, for larger q the situation is more complicated. In general (for q ≥ 5 in the assortative case, and q ≥ 3 in the disassortative one) the threshold (12) marks a transition from an "easily detectable" regime to a "hard detectable" one. In the hard detectable regime, it is theoretically possible to find the communities, but it is conjectured that any algorithm that does so takes exponential time [START_REF] Decelle | Phase transition in the detection of modules in sparse networks[END_REF][START_REF] Decelle | Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications[END_REF]. In particular, we have found experimentally that none of B's eigenvectors are correlated with the groups in the hard regime. Nonetheless, our arguments suggest that spectral algorithms based on B are optimal in the sense that they succeed all the way down to this easy/hard transition.

Since a major drawback of the stochastic block model is that its degree distribution is Poisson, we can also consider random graphs with specified degree distributions. Again, the hardest case is where the groups have the same degree distribution. Let a k denote the fraction of vertices of degree k. The average branching ratio of a branching process that explores the neighborhood of a vertex, i.e., the average number of new edges leaving a vertex v that we arrive at when following a random edge, is

c = k k(k -1)a k k ka k = k 2 / k -1 .
We assume here that the degree distribution has bounded second moment so that this process is not dominated by a few high-degree vertices. The leading eigenvalue of B is c, and the bulk of its spectrum is confined to the disk of radius √ c, even in the sparse case where c does not grow with the size of the graph. If q = 2 and the average numbers of new edges linking v to its own group and the other group are cin /2 and cout /2 respectively, then the approximate eigenvector described in the previous section has eigenvalue µ = (c in -cout )/2. The detectability threshold (1) then becomes µ > √ c, or cin -cout > 2 √ c. The threshold [START_REF] Zhang | Comparative study for inference of hidden classes in stochastic block models[END_REF] for q groups generalizes similarly.

V. DERIVING B BY LINEARIZING BELIEF PROPAGATION

The matrix B also appears naturally as a linearization of the update equations for belief propagation (BP). This linearization was used previously to investigate phase transitions in the performance of the BP algorithm [START_REF] Coja-Oghlan | A Spectral Approach to Analyzing Belief Propagation for 3-Coloring[END_REF][START_REF] Decelle | Phase transition in the detection of modules in sparse networks[END_REF][START_REF] Decelle | Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications[END_REF][START_REF] Richardson | Modern coding theory[END_REF].

We recall that BP is an algorithm that iteratively updates messages η v→w where (v, w) are directed edges. These messages represent the marginal probability that a vertex v belongs to a given community, assuming that the vertex w is absent from the network. Each such message is updated according to the messages η u→v that v receives from its other neighbors u = w. The update rule depends on the parameters c in and c out of the block model, as well as the expected size of each community. For the simplest case of two equally sized groups, the BP update [START_REF] Decelle | Phase transition in the detection of modules in sparse networks[END_REF][START_REF] Decelle | Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications[END_REF] can be written as

η + v→w η - v→w := e -h u∈N (v)-w η + u→w c in + η - u→w c out u∈N (v)-w η + u→w c out + η - u→w c in . ( 13
)
Here + anddenote the two communities. The term e h , where h = (c in -c out )(n BP + -n BP -) and n BP ± is the current estimate of the fraction of vertices in the two groups, represents messages from the non-neighbors of v. In the assortative case, it prevents BP from converging to a fixed point where every vertex is in the same community.

The update (13) has a trivial fixed point η v→w = 1/2, where every vertex is equally likely to be in either community. Writing η ± u→v = 1/2 ± δ u→v and linearizing around this fixed point gives the following update rule for δ,

δ v→w := c in -c out c in + c out u∈N (v)-w δ u→v ,
or equivalently

δ := c in -c out c in + c out Bδ . (14)
More generally, in a block model with q communities, an affinity matrix c ab , and an expected fraction n a of vertices in each community a, linearizing around the trivial point and defining η a u→v = n a + δ a u→v gives a tensor product operator

δ := (T ⊗ B)δ , (15)
where T is the q × q matrix defined in [START_REF] Mossel | Stochastic Block Models and Reconstruction[END_REF]. We can also describe the linearization of BP in terms of the 2n × 2n matrix B defined in [START_REF] Decelle | Phase transition in the detection of modules in sparse networks[END_REF]. Specifically, if we define δ in and δ out as the qn-dimensional vectors where δ in v = u∈N (v) δ a u→v and δ out v = u∈N (v) δ a v→u are the sum of δ over v's incoming and outgoing edges respectively, then

δ out δ in = (T ⊗ B ) δ out δ in . (16)
Thus we can analyze BP to first order around the trivial fixed point by keeping track of just 2qn variables rather than 2qm of them. This shows that the spectral properties of the non-backtracking matrix are closely related to belief propagation. Specifically, the trivial fixed point is unstable, leading to a fixed point that is correlated with the community structure, exactly when T ⊗ B has an eigenvalue greater than 1. However, by avoiding the fixed point where all the vertices belong to the same group, we suppress B's leading eigenvalue; thus the criterion for instability is νµ 2 > 1 where ν is T 's leading eigenvalue and µ 2 is B's second eigenvalue. This is equivalent to [START_REF] Zhang | Comparative study for inference of hidden classes in stochastic block models[END_REF] in the case where the groups are of equal size.

In general, the BP algorithm provides a slightly better agreement with the actual group assignment, since it approximates the Bayes-optimal inference of the block model. On the other hand, the BP update rule depends on the parameters of the block model, and if these parameters are unknown they need to be learned, which presents additional difficulties [START_REF] Zhang | Comparative study for inference of hidden classes in stochastic block models[END_REF]. In contrast, our spectral algorithm does not depend on the parameters of the block model, giving an advantage over BP in addition to its computational efficiency. In Fig. 4, we compare the spectral algorithm based on the non-backtracking matrix B with those based on various classical operators: the adjacency matrix A, the modularity matrix M , the Laplacian L, and the random walk matrix Q. We see that there is a regime where standard spectral algorithms do no better than chance, while the one based on B achieves a strong correlation with the true group assignment all the way down to the detectability threshold. We also show the performance of belief propagation, which is believed to be asymptotically optimal [START_REF] Decelle | Phase transition in the detection of modules in sparse networks[END_REF][START_REF] Decelle | Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications[END_REF].

VI. EXPERIMENTAL RESULTS AND DISCUSSION

We measure the performance as the overlap, defined as

1 n u δ gu,gu - 1 q 1 - 1 q . ( 17
)
Here g u is the true group label of vertex u, and gu is the label found by the algorithm. We break symmetry by maximizing over all q! permutations of the groups. The overlap is normalized so that it is 1 for the true labeling, and 0 for a uniformly random labeling.

Karate q=2

Overlap: 1 FIG. 6: Spectrum of the non-backtracking matrix in the complex plane for some commonly used benchmarks for community detection in real networks taken from [START_REF] Adamic | The political blogosphere and the 2004 US Election: Divided They Blog[END_REF][START_REF] Zachary | An information flow model for conflict and fission in small groups[END_REF][START_REF] Newman | Finding community structure in networks using the eigenvectors of matrices[END_REF][START_REF] Girvan | Community structure in social and biological networks[END_REF][START_REF] Lusseau | The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations[END_REF][START_REF]The network was compiled by Valdis Krebs and can[END_REF]. The radius of the circle is the square root of the largest eigenvalue, which is a heuristic estimate of the bulk of the spectrum. The overlap is computed using the signs of the second eigenvector for the networks with two communities, and using k-means for those with three and more communities. The non-backtracking operator detects communities in all these networks, with an overlap comparable to the performance of other spectral methods. As in the case of synthetic networks generated by the stochastic block model, the number of real eigenvalues outside the bulk appears to be a good indicator of the number q of communities.

In Fig. 5 we illustrate clustering in the case q = 3. As described above, in the detectable regime we expect to see q -1 eigenvectors with real eigenvalues that are correlated with the true group assignment. Indeed B's second and third eigenvector are strongly correlated with the true clustering, and applying k-means in R 2 gives a large overlap. In contrast, the second and third eigenvectors of the adjacency matrix are essentially uncorrelated with the true clustering, and similarly for the other traditional operators.

Finally we turn towards real networks to illustrate the advantages of spectral clustering based on the nonbacktracking matrix in practical applications. In Fig. 6 we show B's spectrum for several networks commonly used as benchmarks for community detection. In each case we plot a circle whose radius is the square root of the largest eigenvalue. Even though these networks were not generated by the stochastic block model, these spectra look qualitatively similar to the picture discussed above (Fig. 2). This leads to several very convenient properties. For each of these networks we observed that only the eigenvectors with real eigenvalues are correlated to the group assignment given by the ground truth. Moreover, the real eigenvalues that lie outside of the circle are clearly identifiable. This is very unlike the situation for the operators used in standard spectral clustering algorithms, where one must decide which eigenvalues are in the bulk and which are outside.

In particular, the number of real eigenvalues outside of circle seems to be a natural indicator for the true number q of clusters present in the network, just as for networks generated by the stochastic block model. This suggests that in the network of political books there might in fact be 4 groups rather than 3, in the blog network there might be more than two groups, and in the NCAA football network there might be 10 groups rather than 12. However, we also note that large real eigenvalues may correspond in some networks to small cliques in the graph; it is a philosophical question whether or not to count these as communities.

Note also that clustering based on the non-backtracking matrix works not only for assortative networks, but also for disassortative ones, such as word adjacency networks [START_REF] Newman | Finding community structure in networks using the eigenvectors of matrices[END_REF], where the important real eigenvalue is negative-without being told which is the case.

A Matlab implementation with demos that can be used to reproduce our numerical results can be found at [START_REF]A matlab demo[END_REF].

VII. CONCLUSION

While recent advances have made statistical inference of network models for community detection far more scalable than in the past (e.g. [START_REF] Decelle | Phase transition in the detection of modules in sparse networks[END_REF][START_REF] Ball | Efficient and principled method for detecting communities in networks[END_REF][START_REF] Chen | Fitting community models to large sparse networks[END_REF][START_REF] Gopalan | Scalable inference of overlapping communities[END_REF]) spectral algorithms are highly competitive because of the computational efficiency of sparse linear algebra. However, for sparse networks there is a large regime in which statistical inference methods such as belief propagation can detect communities, while standard spectral algorithms cannot.

We closed this gap by using the non-backtracking matrix B as a new starting point for spectral algorithms. We showed that for sparse networks generated by the stochastic block model, B's spectral properties are much better than those of the adjacency matrix and its relatives. In fact, it is asymptotically optimal in the sense that it allows us to detect communities all the way down to the detectability transition. We also computed B's spectrum for some common benchmarks for community detection in real-world networks, showing that the real eigenvalues are a good guide to the number of communities and the correct labeling of the vertices.

Our approach can be straightforwardly generalized to spectral clustering for other types of sparse data, such as real-valued similarities between objects. The definition of B extends to B (u→v),(w→x) = s(u, v) if v = w and u = x 0 otherwise , where s(u, v) is the similarity index between u and v. As in the case of graphs, we cluster the vertices by computing the top eigenvectors of B, projecting the rows of B to the space spanned by these eigenvectors, and using a lowdimensional clustering algorithm such as k-means to cluster the projected rows [START_REF] Luxburg | A tutorial on spectral clustering[END_REF]. However, we believe that, as for sparse graphs, there will be important regimes in which using B will succeed where standard clustering algorithms fail. Given the wide use of spectral clustering throughout the sciences, we expect that the non-backtracking matrix and its generalizations will have a significant impact on data analysis.

FIG. 1 :

 1 FIG.1:The spectrum of the adjacency matrix of a sparse network generated by the block model (excluding the zero eigenvalues).Here n = 4000, cin = 5, and cout = 1, and we average over 20 realizations. Even though the eigenvalue λc = 3.5 given by (2) satisfies the threshold condition (1) and lies outside the semicircle of radius 2 √ c = 3.46, deviations from the semicircle law cause it to get lost in the bulk, and the eigenvector of the second largest eigenvalue is uncorrelated with the community structure. As a result, spectral algorithms based on A are unable to identify the communities in this case.

FIG. 3 :

 3 FIG.3:The first, second and third largest eigenvalues µ1, µ2 and |µ3| respectively of B as functions of cin -cout. The third eigenvalue is complex, so we plot its modulus. Values are averaged over 20 networks of size n = 10 5 and average degree c = 3. The green line in the figure represents µc = (cin -cout)/2, and the horizontal lines are c and √ c respectively. The second eigenvalue µ2 is well-separated from the bulk throughout the detectable regime.

FIG. 4 : 1 FIG. 5 :

 415 FIG. 4:The accuracy of spectral algorithms based on different linear operators, and of belief propagation, for two groups of equal size. On the left, we vary cin -cout while fixing the average degree c = 3; the detectability transition given by (1) occurs at cin -cout = 2 √ 3 ≈ 3.46. On the right, we set cout/cin = 0.3 and vary c; the detectability transition is at c ≈ 3.45. Each point is averaged over 20 instances with n = 10 5 . Our spectral algorithm based on the non-backtracking matrix B achieves an accuracy close to that of BP, and both remain large all the way down to the transition. Standard spectral algorithms based on the adjacency matrix, modularity matrix, the Laplacian, and the random walk matrix fail well above the transition, doing no better than chance.

Acknowledgments

We are grateful to Noga Alon, Brian Karrer, Mark Newman, Nati Linial, and Xiaoran Yan for helpful discussions. C.M. and P.Z. are supported by AFOSR and DARPA under grant FA9550-12-1-0432. F.K. and P.Z. have been supported in part by the ERC under the European Union's 7th Framework Programme Grant Agreement 307087-SPARCS. E.M and J.N. were supported by NSF DMS grant number1106999 and DOD ONR grant N000141110140.


Ms Claire Revol

Henri Lefebvre's Rhythmanalysis as a form of Urban Poetics

Lefebvre's texts on rhythmanalysis are open to a variety of readings. By placing rhythmanalysis in the broader context of Lefebvre's work, the rhythmanalytical project emerges as what I have argued to be an urban poetics. A progressive reading of the different texts Lefebvre wrote on rhythmanalysis shows that, beyond rhythmanalysis' contribution to the critical theory of urban space and time, the imagination becomes an alternative for the creation of time-spaces in the form of experimental utopias and the creation of lifestyles. Rhythmanalysis can then be understood as a general quest for the appropriation of time and space in the renewal of the possibility of the urban to become a human oeuvre. This chapter will outline the development of Lefebvrian urban poetics through the rhythmanalytical project.

Introduction

At first sight, it is difficult to define the boundaries of the rhythmanalytical project and demonstrate precisely how it is related to Lefebvre's critical theory, notably in terms of the conceptual framework that he developed for urban planning and the production of space in general. Lefebvre did not detail the full implications of what remained a 'project', nor did he reveal the 'elements' of his 'secret garden', as his friend and colleague, Rene Lourau, who posthumously published Lefebvre's unfinished writings as Éléments de rythmanalyse (Lefebvre 1992(Lefebvre , 2004) would later describe it.

Texts mentioning the rhythmanalytical project have been written over a long period of time and have been redefined according to evolutions in Lefebvre's thinking. In the second Critique of everyday life (Lefebvre 1961), inspired by Bachelard's book written in 1936 The dialectic of duration [START_REF] Bachelard | La dialectique de la durée[END_REF], Lefebvre first mentions it as an approach to studying social time. He then alludes to it in The production of space (Lefebvre 1974), Towards an architecture of enjoyment written in 1973 (Lefebvre 2014) and his writings on music, before finally describing it as a consistent project in the third Critique of everyday life (Lefebvre 1981) as well as the articles 'The rhythmanalytical project' in 1985 (Lefebvre 2004) and an 'Attempt at the Rhythmanalysis of Mediterranean Cities' in 1986 (Lefebvre 2004).

Elements of Rhythmanalysis: An introduction to the Understanding of Rhythms (Lefebvre 1992;[START_REF]Rhythmanalysis: Space, Time and Everyday Life[END_REF]) is a collection of chapters that provides no linear argumentation for the reader. It is rather a collection of fragments, a series of 'preludes', to appropriate Lefebvre's description of the structure of his book, Introduction to modernity (Lefebvre 1962). It is hard to believe that these writings were unfinished because of the lack of time. Lefebvre is a prolific author. He has written more than sixty books, some of them in but a few months. As opposed to Introduction to modernity, Elements of Rhythmanalysis is written in a lapidary way, with most of the terms referring to Lefebvrian concepts without any form of explanation. If we consider these texts to be a general view, or a synthetic picture of the rhythmanalytical quest-which could explain why some of the terms are written in bold or italic letterswe are still without an explanation of their status in his critical theory. Curiously, even though Lefebvre grounds his theory of rhythms in aesthetics, he rarely refers either to space or the urban question. If the Elements of Rhythmanalysis is an 'introduction' to the knowledge of rhythms, how do we then complete it without overinterpreting it? I shall seek to establish how rhythmanalysis fits into the general framework of lefebvrian theory through an exploration of the particular texts in which he refers to the rhythmanalytical project. I assume that Lefebvrian critical theory unfolds along the lines of his development of a 'poetics' and that the rhythmanalytical project, which borrows its intuitions from Bachelard's poetics, can be read as a contribution to urban poetics. I have developed this point of view in my doctoral thesis in philosophy, Henri Lefebvre's Rhytmanalysis as a form of Urban Poetics [START_REF] Revol | La rythmanalyse chez Henri Lefebvre (1901-1991): contribution à une poétique urbaine[END_REF].

Lefebvre develops rhythmanalysis by means of his contact with artistic practices, especially those of the Situationist International. Against his critique of abstraction as the inherent process of urban space and time, Lefebvre proposes rhythmanalysis as a way to construct an appropriate space-time, including the ability to transform urban society and reconfigure the 'total body' so that the urban can instead be considered as a work of art.

Lefebvre thus provides more than a qualitative methodology for the observation of rhythms, he outlines a rhythmanalytic experimentation that can be associated with the practices of an experimental utopia.

Rhythmanalysis therefore offers the guidelines for an applied poetics; it goes as far as creating forms, textures and styles for urban living. This urban poetics, as a creative act steeped in knowledge, proceeds through experimentation; it restores the rhythmic game that enriches our aesthetic experience of urban space and time. Thus Lefebvre's writings on space and time should not be considered as a purely social theory, but rather as an integral part of urban poetics. Lefebvre developed the anthropological dimension of his poetics in his book Métaphilosophie (Lefebvre 1965b), that I will analyse as a combination of his writings on social theory and urban poetics.

Rhythmanalysis and the social production of space-time

The point of departure for the rhythmanalytical project can be found in the second volume of the Critique of everyday life -Foundations for a Sociology of the Everyday (Lefebvre 1961), in which Lefebvre defines his sociology as a radical and critical theory.

The critique of everyday life that Lefebvre explores is rooted in his project of structuring a critical knowledge of modern man and the modern world through his reading of Marx's first texts and his understanding of alienation.

He developed this particular theorization of dialectical materialism in the 1930s with Norbert Guterman, notably in the introduction to Lenin's Hegel Notebooks, (Lefebvre and Guterman 1935), The Mystified Consciousness [START_REF] Lefebvre | La conscience mystifiée[END_REF] and Dialectical Materialism (Lefebvre 1939b). The main thesis is that the banality of ideas in the functioning of daily society makes awareness of alienation difficult. Critical theory must study forms of consciousness in human practices (ideas, institutions, cultures) as concrete forms of the lifestyles and existence of human beings (Lefebvre 1939b: 67). Thus critical theory is a theory of praxis that dialectically exposes the production of ideas and things (Lefebvre 1935: 17-8) from the study of material human praxis, and aims to transform it.

Revolution is not to be understood as the obtention of political power, or solely the change in the economic relations of production, but as the transformation of everyday life.

The publication of the first Critique of everyday life (Lefebvre 1947) in the context of the development of sociology as a leading discipline in post-war France provides the strategic background for Lefebvre's definition of the study of praxis on a sociological basis. But praxis can more broadly and originally be understood as the sum of the practical human relationships to the world and to others in society, or the practices by which human beings define their relationships to nature and their own nature. It is thus open to exploration by a plurality of disciplines. Critical theory aims to find ways by which to raise awareness, to orient and transform praxis. The lefebvrian dialectic sees overcoming as an act that is based on a creative dynamic, a 'thinking-acting' ('une pensée-acte ' Lefebvre 1939b: 58) inspired by his reading of Nietzsche's tragedy as the aspiration towards the 'total man' (Lefebvre 1939a). This creative dynamic takes life itself for its central goal and opens new possibilities for lifestyles considered collectively rather than individually. Lefebvre considers art as a way to accomplish the transformation of praxis.

This theoretical background determines the conceptual tools Lefebvre mobilises to study society and argue for the conscious transformation of life.

To study praxis is to combine sentient and embodied experiences of daily reality, for example the act of gazing at an agrarian landscape, as described in the first version of the Critique of everyday life (Lefebvre 1947: 141).

This experience is then replaced by the shock of the experience of the new town of Mourenx, as described in the Introduction to modernity (Lefebvre 1962), and the transition from rural sociology to urban sociology becomes the focal point of the study of modern man. Yet Lefebvre does not abandon his intellectual project of a theory of praxis. Critical theory is fuelled by its intellectual context and Lefebvre associates himself with avant-garde groups such as the Situationist International, especially Guy Debord, whose relations with Lefebvre were remarkably intense and difficult [START_REF] Ross | An interview with Henri Lefebvre[END_REF][START_REF] Merrifield | Henri Lefebvre: A Critical Introduction[END_REF]). Regardless of the conflict, their exchanges came to inspire a generation of urban theorists, critical of State Planning [START_REF] Stanek | Henri Lefebvre on Space: Architecture, Urban Research[END_REF][START_REF] Breton | our une criti ue de la ille la sociologie ur aine ran aise, 1950-1980[END_REF].

Though Bachelard is far removed from critical theory, Lefebvre admires his attempt to reconcile science and poetry, particularly in his Poetics of Space, as he writes in his autobiography La Somme et le Reste (Lefebvre 1959: 142-3). Lefebvre does not just borrow the term "rhythmanalysis" from Bachelard, he articulates his own scientific project with a theory of the poetics of the everyday experience as informed by Bachelard. Though critical theory produces empirical studies of urban society, Stanek notes that Lefebvre's bibliography for his courses in urban sociology includes descriptions of cities in philosophy and literature such as those of Heidegger, Sue, Steinbeck, Dos Passos, and Lowry alongside the theoretical writings of planners such as Lynch and Alexander (Stanek 2011: 21). In the second tome of his Critique of everyday life (Lefebvre 1961), Lefebvre defines the principal categories of his sociology and considers a social rhythmology or rhythmanalysis to study the interactions of cyclic and linear periods of time or rhythms.

His enquiry on temporalities is directly linked with his critique of modernity. Cyclic rhythms compose the temporalities of agrarian and traditional societies, in which repetitions of periods in social life are ritualized to become part of symbolic exchanges between life and death, or the cosmic relation of the community to the earth (Lefebvre 1961: 52-4).

Lefebvre sees modernity as a process of abstraction (Lefebvre 1962), as it introduces linear temporalities marked by the advent of machines, and above all clocks, representing a time that is fictitiously homogeneous and fragmentable. This measurable time becomes everyday time in accordance with the work time. Lefebvre shows that cyclic rhythms correspond to natural and vital rhythms, and to non-cumulative processes (Lefebvre 1961: Ch. 5). They are predominant in archaic societies (Lefebvre 1961: 318-9), linked to ancient symbols that ritualize social practices, introducing rhythms in order to include individuals in a community.

In the modern world, where cumulative processes like economic growth are predominant, signs and signals replace older symbols, as Lefebvre claims in his theory of the semantic field (Lefebvre 1961: Ch.4). Because omnipresent signals are conditioning behaviours by means of their linear repetition and participation in the programming of life with all of its satisfactions, linear repetition can bring about monotony, boredom and tiredness. Lefebvre analyses alienation in everyday life in the modern world as a form of this integral programming of time that affects even leisure and rest, to which he opposes enjoyment. Rhythmanalysis is dedicated to the analysis of the persistence of the cyclic rhythms and their interaction with linear rhythms.

Bachelard's rhythmanalysis [START_REF] Bachelard | La dialectique de la durée[END_REF]) is alien to the study of social time. The contemplative philosopher prefers solitary time, free from the requirements of social life. Bachelard focuses on lived time and on how lived instants are dialectically related through rhythms, criticizing Bergson's concept of duration. The temporal 'fortune' and 'efficiency' [START_REF] Bachelard | La dialectique de la durée[END_REF], arises from the way instants are arranged in rhythmic patterns.

Bachelard imagines rhythmanalysis as a personal practice aimed at orientating how energy is spent, especially in thinking activities (learning, memory, creative imagination…) and human relationships. It has a therapeutic or pedagogical goal, completing other practices like psychoanalysis, and responds to the fundamental human need for a temporal dialectic, alternating between full and void. But these temporal practices rely on ever-present social temporalities, isolation being possible in accord with rhythmic social modalities. Thus both can be included in the critique of everyday life as ways of transforming and creating moments.

Lefebvre did not extend his conception of the production of space to the production of time, but we can imagine that conceiving of social time as a social product would mean thinking the relationship between perceived time, conceived time, and lived time. Rhythmanalysis is presented as a way to study 'concrete modalities of social time' (Lefebvre 2004: 73). Thus Bachelard helps Lefebvre think lived time, allying topo-philia with tempophilia as The poetics of space (Bachelard, 1957) through the consideration of the space of representation, the space we live in, and even 'happy' space.

Each society produces their own space and their own time. The question 'How can appropriate time accompany appropriate space' becomes 'How can time be inhabited by a collective lifestyle?' and 'How can rhythmanalysis complete spatio-analysis in the quest for this appropriate space-time?'

Rhythmanalysis and the quest for the appropriation of urban space-time

By placing rhythmanalysis in the framework of the production of space, Lefebvre articulates it with the appropriation and the abstraction of urban space and time. How do rhythms found the dynamics of the appropriation of space and time? We can assume that these dynamics proceed from the living body, for Lefebvre names the body as the 'constant reference' for rhythmanalysis: 'the theory of rhythms is founded on the experience and the knowledge of the body' (Lefebvre 2004: 67).

Lefebvre evokes the rhythmanalytical project in the chapter 'spatial architectonics' (Lefebvre 1974), dedicated to the organic appropriation of space and the creation of forms by means of the material dynamic of the bodily occupation of space. The body plays a crucial role in appropriation dynamics; it secretes its appropriate and qualified space. The body's energy elaborates social space in successive layers and creates the cosmologies that anthropologists study. It is a creative praxis which proceeds from the sensitive and affective relationship of the body to space. Spatial architectonics is also temporal because space and time are inseparable in the living body. Concrete time is made of rhythms that emanate from the body: breathing, heart rate, hunger, walking, sexuality… Marcel Jousse's anthropology of gesture [START_REF] Jousse | L'Anthropologie du geste[END_REF] shows that learning is nestled at the heart of a mimetic dynamic specific to human beings, and that gesture impregnates the human body with rhythm. This framework could allow for the micro-sociology of everyday practices, especially in public space, and contributes to the imagination of a spatial and temporal architectonics.

Yet another anthropologist, André Leroi-Gourhan, shows that rhythms contribute to our affective and emotional insertion in the world in Gesture and speech [START_REF] Leroi-Gourhan | Le geste et la parole. La mémoire et les rythmes[END_REF]. André Leroi-Gourhan does not think that social rhythms are imposed on individuals, but rather created by the activities of living bodies and their relationships with groups and living environments, thus constituting a fabric of aesthetic relationships. Lifestyles are both an emotional and affective insertion into the cosmos and society.

He begins with the vital rhythms central to understanding gesture and the creation of human environments, and ends with the creation of symbols of domestic time and space. Days and nights, seasons and walking distances are folded into symbols: rhythms create inhabited space-times. Leroi-Gourhan's writings find their echo in Lefebvre's conception of lifestyle and the construction of a corresponding time and space through 'textures' (Lefebvre 1974). Social praxis appropriates rhythms in the creation of social time, and according to the different modalities of specific lifestyles. Situated and acting bodies have inventive capacities that are developed in time, space and through energy.

Lefebvre analyses the modern production of space and time as the concrete production of abstractions (Lefebvre 1974). The urban revolution is the disruption of a cosmic conception of space and time. Cities are no longer inserted into symbolic space and time, they are no longer an image of the cosmos, as was the model of the ancient Greek city. The modern city can no longer be appropriated through old symbols of space and time. This form of abstraction results in a production of repetitive spaces and time that are no longer rhythmic. These modalities transform the aesthetic experience, notably through the predominance of the visual. Bodily rhythms no longer foster the rhythmic appropriation of space and its extension into the creation of a cosmos.

To counter this form of abstraction, Lefebvre proposes rhythmanalysis as the quest to create an appropriate urban space and time. This proposition is correlated to his project for the restitution of the 'total body' (Lefebvre 1974: 465), which would use the knowledge acquired by rhythmanalysis. It can, for example, be found in the therapeutic search for eurhythmia to treat pathologies: the living body presents numerous associated rhythms (and we must insist on this crucial point); hence a eurhythmia, when in the state of good health. Pathology, in a word illness, is always accompanied by a disruption of rhythms: arrythmia that goes as far as morbid and then fatal de-synchronisation. (Lefebvre, 2004: 68) This rhythmic diagnostic can also be used to conceive of urban environments. Because of Lefebvre's pedagogical view of rhythmanalysis as a tool for the appropriation of space (Lefebvre 1974: 237), rhythmanalysis can be thought of as a practical exercise based on listening to rhythms with each bodily sense. It is above all based on the aesthetic experience of rhythms. Furthermore, rhythmanalysis is not only a personal practice, it is a collective practice that is able to transform praxis. Lefebvre is interested in the fact that this creative praxis can create enjoyment. He develops the relation of the 'total body' to space and time through the perception of rhythms in Toward an architecture of enjoyment (Lefebvre 2014), demonstrating that the creative praxis of appropriation leads to artistic activity, notably in the construction of the urban as a work of art. As we will see, this is what Lefebvre means by poiesis.

Music and dance are 'privileged fields and experimental fields' (Lefebvre 1974: 237;[START_REF]Rhythmanalysis: Space, Time and Everyday Life[END_REF] of the creative experience of rhythms and of lived time.

Lefebvre wrote on music and society (Lefebvre 1966;[START_REF]La Fin de l'histoire épilégomènes[END_REF], and meditated on Nietzsche's conception of style as the link between music and lived time (Lefebvre 1970;[START_REF] Nicholson-Smith | The Production of Space[END_REF]. The ambivalent relationship between cyclical rhythms related to natural, cosmic, and organic forces, and linear rhythms, related to the measurement and quantification of time, prevails in Lefebvre's understanding of musical rhythms. Music appropriates the rhythmic body, as, in Lefebvre's terms: the relation between musical time and the rhythms of the body is required. Musical time resembles them but reassembles them. It makes a bouquet, a garland from a jumble. Through dance, first of all. Musical time does not cease to have a relation with the physical. (Lefebvre 2004: 64) In musical rhythm, the appropriation of time and space occurs through the body, which is why semiology is insufficient in understanding music (Lefebvre 1971). Music gives its texture to the time that is lived in.

Following this perspective, Lefebvre equates the conquest of everyday sound in concrete music and underground culture with urbanization and globalization ('mondialisation'). They provide an outlet for tensions in everyday life (Lefebvre 1981: 135). However, the aesthetic experience of the environment is not only a sonic experience. The rhythmic experience of architecture, urban space and landscape leads to an open inquiry [START_REF] Maldiney | Regard, parole[END_REF][START_REF] Revol | La rythmanalyse chez Henri Lefebvre (1901-1991): contribution à une poétique urbaine[END_REF].

The theory of moments marks another attempt on the part of Lefebvre to think appropriate space-time through the idea of repetition. 'Moment' is defined as a superior and richer form of repetition that is created from everyday forms of repetition such as gesture, behavior, instants and disruptions in stable periods of time, objects and artworks, symbols, and affective stereotypes (Lefebvre 1961: 344). Lefebvre describes different moments: love, knowledge, games… The 'moment' has temporal qualities of intensity, defined by paroxysmal fullness, and a relationship to duration that Lefebvre qualifies as 'involution' and the accomplishment of a presence (Lefebvre 1961: 345). Lefebvre mystically describes presence as a creative act in La présence et l'absence :

[Presence] supposes and implies an act: the poietic act. This also implies an adherence to being, to the fact of being and to the possibility of a fullness that is never fixed nor fully defined.

Presence, as a moment and not a substance or pure form, rewards the risk-taking act. [author's translation] (Lefebvre 1980: 226) The 'moment' is what integrates the everyday in order to transform it through the texture of space and time. And though 'moment' does not appear in Lefebvre's texts on rhythmanalysis, the figure of the poet rhythmanalyst is here described, along with the creative activity of this figure as a manner to include rhythms in daily life (Lefebvre 2004: 22-6).

This poetic activity transforms everyday life and creates lifestyles comparable with the experimental utopias developed by the avant-garde group, Situationist International.

Rhythmanalysis as experimental utopia

How can rhythmanalysis be performed as poetic practice? Though Lefebvre did not develop specific descriptions of the poet rhythmanalyst, nor define the manner in which urban time and space were to be transformed through this activity, Lefebvre did develop the concept of an 'experimental utopia' in which an understanding of this poetic practice can be found. Utopia as a literary genre proposes to show a society in a spatio-temporal elsewhere in order to criticize the existing order. Lefebvre is inspired by utopian socialists like Charles Fourier, and the conceptualization of concrete utopias by Antonio Gramsci or Ernst Bloch. He considers utopia as a means of transforming reality, and therefore does not dissociate it from critical theory, but rather explores the possibilities of imagining a society that could be created by the Revolution, and fuel the imagination of counter-spaces. It is associated with the creation of an appropriate time-space.

Lefebvre uses the term 'experimental utopia' to describe the practices of the Situationist International that go beyond fictional writings to promote 'a utopia experienced on an experimental basis' (Lefebvre 1961: 336). At the end of the 1950s, the SI defines psychogeography as 'the study of the precise laws and specific effects of the geographic environment, consciously organized or not, on the emotions and behaviours of individuals' [START_REF] Debord | Introduction à une critique de la géographie urbaine[END_REF]. Its methodology can be found in the experiment of the 'dérive', an urban exploration protocol that consists in a rapid crossing of urban space in the form of a game, thus rendering immaterial frontiers of neighbourhoods and highlighting the attractive and repulsive zones of the city. 'Dérive' is inherited from the literary tradition of the 'flâneur', recalling Balzac, Baudelaire, and the surrealists, including Louis Aragon and André Breton, who are the direct ancestors of the SI groups. Walking without purpose is a way of contesting the reduction of the street to its utilitarian and rational purposes, as well as the practice of 'détournement' (a form of hijacking, or of showing another use of an already-employed form or object). It allows for an analysis of the city by means of encounter and chance. The atmospheres of the city were seen as the possibility to construct new situations that would not define art as a specialized activity but include it in the creation of lifestyles. The city as an artwork was to announce the collapse of the society of the spectacle, as Debord would later call it [START_REF] Debord | La société du spectacle[END_REF]. The city was to be become an artwork in and of itself, an 'oeuvre'.

Lefebvre sets aside this experimental utopia to develop his critical theory in response to his dispute with Debord in the 1960s. He turns to the theorization of the production of space. Evoking psychogeography in an interview [START_REF] Ross | An interview with Henri Lefebvre[END_REF] Lefebvre imagines the possibilities of an appropriate space-time and the city as an artwork, an 'oeuvre', through the conceptualization of differential space (Lefebvre 1974). Differential space overcomes the abstract space of critical theory through the definition of new centralities, counter-spaces that are appropriated by alternative cultures. They are therefore inseparable from utopian lifestyles. Lefebvre is inspired by Fourier's utopian conception of the phalanstery, a unified, collaborative architectural space that is cohesive with human sensibilities. But unlike Fourier's insistence on harmony and lifestyle, which he sees as ascetic, Lefebvre insists on the realization of desire through enjoyment. Lefevrian utopia requires the achievement of a total body, with its excesses and spent energy, as he describes it in Toward an architecture of enjoyment written in 1973 (Lefebvre 2014). In this book, Lefebvre conceives of architectural work as the exploration of a concrete utopia that allows for the exploration of human desires. Utopian architecture here offers a key to differential space, since it imagines the possibility of overcoming the separation between product and oeuvre in a return to nature.

Evoking the rhythmanalyst as 'an enigmatic individual who strolls with his thoughts and his emotions, his impressions and his wonder, through the streets of large Mediterranean towns' (Lefebvre 2004: 87), Lefebvre recalls the practices of his old friends from the Situationist International. If Lefebvre imagines rhythmanalysis as an experimental utopia with creative ambitions, I consider it to be in line with the dérive and psychogeography in specific situations. As with psychogeography, rhythmanalysis requires a sensitive and aware experience involving body displacement or immobility.

Rhythmanalysis 'separates as little as possible the scientific from the poetic' (Lefebvre 2004: 87): it has the ambition to constitute a knowledge of concrete space and time through the form of a poetic activity. Its own practice should transform life and its effects.

Because rhythms lie at the heart of architectonics and the appropriation of space and time, rhythmanalysis is the experimental practice from which to renew their insertion into the cosmos and create an appropriate space and time in the urban world. Lefebvre seeks an experimental utopia in order to create the urban as an oeuvre.

Rhythmanalysis and Lefebvrian urban poetics

It is necessary to return to the conceptual framework that Lefebvre developed on modern time to understand how critical theory relates to a poetics. Lefebvre explicit his 'revolutionary romanticism' (Lefebvre 1957;[START_REF]Introduction à la modernité préludes[END_REF] at the same period in which he builds up his framework for critical theory and produces his first texts on rhythmanalysis. Revolutionary romanticism is anchored in the young Lefebvre's intellectual background, and is the basis from which Lefebvre constructs his personal critique of modern life as he gradually frees himself from the communist party (PCF).

The idea of modernity as an abstract process is a romantic one (Lefebvre 1962). The romantic characteristics of this thought lie in its anti-systemic construction, its critique of quantification, mechanisation, and his concern for the dissolution of communities [START_REF] Löwy | Révolte et mélancolie: le romantisme à contre-courant de la modernité[END_REF]. To counter modernity's abstraction, Lefebvre defines revolutionary romanticism as a lifestyle and develops his theory of the city as an oeuvre, or artwork of a community. He exchanges with the members of the SI on this set of ideas and elaborates the elements for a poetics of the city.

The result is the definition of the city as an oeuvre in The proclamation of the Paris Commune (Lefebvre 1965a) and The right to the city [START_REF] Lefebvre | Nietzsche[END_REF]). The implications of these theories are developed in other chapters in This conceptualisation of poiesis is completed by the anthropological point of view Lefevre develops in Metaphilosophie (Lefebvre 1965b), where he theorizes more generally the relationship between humanity and its oeuvres.

This opens the possibility for the poetic creation of the urban in terms of human artwork (Lefebvre 1965b: 117-8) and the creation of a lifestyle that transforms everyday life. How is rhythmanalysis related to this general program? I assume that rhythmanalysis, by placing lived experience at the basis of experimentation, is the outline for this poetic practice. But it has to be developed as an experimental device rather than an observation methodology.

Lefebvre did not expose rhythmanalysis as a fully elaborated program in his Elements of rhythmanalysis: each practitioner would probably have to find his own way to practice it. But as we have seen, rhythms are essential to the appropriation of space and time, so Lefebvre's rhythmanalysis is engaged to globally rethink the human environment. His aims are related to the objective of building a differential space, in other words to establish an alternative praxis as poiesis. This poiesis is not only focused on the built environment as an architectural project but could encompass the creation of new institutions, new rituals, new ways of living, and especially other temporalities…alternatives to neo-liberal urbanization.

Conclusions

By placing the texts Lefebvre wrote on rhythmanalysis in the general framework of his theory, we have shown that the production of spatial theory is completed by the question of time in the urban era. The rhythmanalytical project thus adds a temporal dimension to the spatial one in its aim to consolidate our quest for the appropriation of time and space. It takes the form of an experimental utopia in which practice is not the application of a theory; it is elaborated exclusively from thinking and acting.

This "creative practice", arising from praxis is what we have called poiesis.

Thus the rhythmanalytical project invites us to consider the poetic aspects of Lefebvre's thought, and through creative practice, imagine devices to explore the urban as the human oeuvre. and the Production of Theory, Minneapolis: University of Minnesota Press.

  , Lefebvre considers it as evidence of the fragmentation of the city, meanwhile insisting on the necessity of a broader understanding of the urban phenomenon and urban practices. Moreover, he concedes that psychogeography has been unable to demonstrate any results, and few examples have contributed to the science of atmospheres. Lefebvre is sceptical of the revolutionary potential of the construction of situations, understood as punctual interventions, because the transformation of praxis takes time. The transition from experimental utopia and alternative practices to the right to the city brings forth a far broader program.

  this book (see part five and six). It enlightens us on the importance of a certain modality of praxis that Lefebvre call poiesis; the creation of lifestyles as artworks is a central concern among them. Thus Lefebvre's critical theory combines with poetics to open new possibilities for urban society. Theory cannot produce only a critical knowledge of the production of space and time, it must open new horizons for human poiesis.