M Lakestani

M Razzaghi

M Dehghan

Numerical solution of the controlled Duffing oscillator by semi-orthogonal spline wavelets

Keywords: numbers: 02, 30, Vv, 02, 60, Pu

This paper presents a numerical method for solving the controlled Duffing oscillator. The method can be extended to nonlinear calculus of variations and optimal control problems. The method is based upon compactly supported linear semiorthogonal B-spline wavelets. The differential and integral expressions which arise in the system dynamics, the performance index and the boundary conditions are converted into some algebraic equations which can be solved for the unknown coefficients. Illustrative examples are included to demonstrate the validity and applicability of the technique.

Introduction

The classical Duffing's equation was first introduced to study electronics and was published by Duffing in 1918 [START_REF] Stokes | Nonlinear Vibrations[END_REF]. It is the simplest oscillator displaying catastrophic jumps of amplitude and phase when the frequency of the forcing term is taken as a gradually changing parameter. The Duffing equation in one form or another has wide applications in signal processing [START_REF] Wang | Estimation of amplitude and phase of a weak signal by using the property of sensitive dependence on initial conditions of a nonlinear oscillator Signal Process[END_REF], propagation of extremely short electromagnetic pulses in a nonlinear medium [START_REF] Maimistov | Some models of propagation of extremely short electromagnetic pulses in a nonlinear medium Quantum Electron[END_REF][START_REF] Maimistov | Propagation of an ultimately short electromagnetic pulse in a nonlinear medium described by the fifth-order Duffing model[END_REF], brain modelling [START_REF] Zeeman | Duffing equation in brain modelling Bull[END_REF], fuzzy modelling and adaptive control of uncertain chaotic systems [START_REF] Feki | Observer-based exact synchronization of ideal and mismatched chaotic systems[END_REF][START_REF] Ravindra | Dissipative control of chaos in non-linear vibrating systems[END_REF].

Vlassenbroeck and Van Dooren [START_REF] Vlassenbroeck | Chebyshev series solution of the controlled Duffing oscillator[END_REF] introduced a direct method for the controlled Duffing oscillator. The method in [START_REF] Vlassenbroeck | Chebyshev series solution of the controlled Duffing oscillator[END_REF] requires that the state and the control variables, the system dynamics, and the boundary conditions be expanded in Chebyshev series of order m with unknown coefficients. For the approximation of the integral in the performance index, a summation of order m 1 was used, and for the computation of the integrand in the performance index, a summation of order N > m 1 was employed. As a result, a rather complicated system of nonlinear equations have to be solved, for the unknowns, by some kind of iterative method. El-kady and Elbarbary [START_REF] El-Kady M And Elbarbary | A Chebyshev expansion method for solving nonlinear optimal control problems[END_REF] used Chebyshev polynomials for solving controlled Duffing oscillator. In [START_REF] El-Kady M And Elbarbary | A Chebyshev expansion method for solving nonlinear optimal control problems[END_REF], the control and state variables are approximated by Chebyshev series of different orders. The system dynamics, boundary conditions and performance index are approximated by using an explicit formula for the Chebyshev polynomials in terms of arbitrary order of their derivatives and a large system of nonlinear equations have to be solved.

Wavelets theory is a relatively new and emerging area in mathematical research. It has been applied in a wide range of engineering disciplines; in particular, wavelets are very successfully used in signal analysis for waveform representation and segmentations, time-frequency analysis and fast algorithms for easy implementation [START_REF] Chui | Wavelets: A Mathematical Tool for Signal Analysis[END_REF]. Wavelets permit the accurate representation of a variety of functions and operators. Moreover wavelets establish a connection with fast numerical algorithms [START_REF] Beylkin | Fast wavelet transforms and numerical algorithms I[END_REF]. Wavelets can be separated into two distinct types, orthogonal and semi-orthogonal (SO) [START_REF] Chui | An Introduction to Wavelets[END_REF]. Publications on integral equation methods have shown a marked preference for orthogonal wavelets [START_REF] Nevels | Semi-orthogonal versus orthogonal wavelet basis sets for solving integral equations[END_REF]. This is probably because the original wavelets, which were widely used for signal processing, were primarily orthogonal. In signal processing applications, unlike integral equation methods, the wavelet itself is never constructed since only its scaling function and coefficients are needed. However, orthogonal wavelets either have infinite support or a nonsymmetric and in some cases, fractal nature. These properties can make them a poor choice for characterization of a function. In contrast, the SO wavelets have finite support, both even and odd symmetry and simple analytical expressions, ideal attributes of a basis function [START_REF] Nevels | Semi-orthogonal versus orthogonal wavelet basis sets for solving integral equations[END_REF].

In this paper, we introduce an alternative computational method for solving the controlled Duffing oscillator. This method consists of reducing the controlled Duffing oscillator problem to a set of algebraic equations by using compactly supported linear SO B-spline wavelets, specially constructed for the bounded interval. The use of these wavelets is justified by their interesting properties. Among them the following can be explicitly cited [START_REF] Ala | An advanced numerical model in solving thin-wire integral equations by using semi-orthogonal compactly supported spline wavelet[END_REF]: they satisfy all the properties on a bounded interval that are verified by the usual wavelets on the real line, but they do not determine the difficulty related to enforce boundary conditions explicitly, when applying such wavelets to problems in finite bounded domain; unlike most of the continuous orthogonal wavelets, the SO compactly supported spline wavelets have closed form expressions.

The paper is organized as follows: in section 2, we describe the basic formulation of the B-spline scaling functions and wavelets on [0, 1] required for our subsequent development. Section 3 is devoted to the formulation of the controlled linear oscillator whose exact solution can be obtained by using Pontryagin's maximum principle [START_REF] Pontryagin | The Mathematical Theory of Optimal Processes[END_REF]. Section 4 summarizes the application of this method to the controlled linear oscillator. In section 5, we apply the proposed method to the controlled Duffing oscillator, and in section 6, we report our numerical findings and demonstrate the accuracy of the proposed method.

B-spline scaling functions and wavelets on [0, 1]

When SO wavelets are constructed from B-splines of order m, the lowest octave level j = j 0 is determined by [START_REF] Goswami | On solving first-kind integral equations using wavelets on a bounded interval[END_REF] 2 j 0 2m -1

(1) so as to give a minimum of one complete wavelet on the interval [0, 1]. In this paper, we will use a wavelet generated by a linear spline-the second-order cardinal B-spline basis function. From equation ( 1), the second-order B-spline of lowest level, which must be an integer, is determined to be j 0 = 2. This constrains all octave levels to j 2. As is the case with all SO wavelets, the second-order B-splines also serve as scaling functions. The second-order Bsplines/scaling functions are given by

φ j,k (x) =    x j -k, k x j k + 1, 2 -(x j -k), k + 1 x j k + 2, 0, otherwise, (2)
k = 0, . . . , 2 j -2,
with the respective left-and right-hand side boundary scaling functions

φ j,k (x) = 2 -(x j -k), 0 x j 1, 0, otherwise, (3)
k = -1, and
φ j,k (x) = x j -k, k x j k + 1, 0, otherwise. ( 4
) k = 2 j -1,
The actual coordinate position x is related to x j , according to x j = 2 j x. The second-order B-spline wavelets are given by

ψ j,k (x) = 1 6                    x j -k, k x j k + 1/2, 4 -7(x j -k), k + 1/2 x j k + 1, -19 + 16(x j -k), k + 1 x j k + 3/2, 29 -16(x j -k), k + 3/2 x j k + 2, -17 + 7(x j -k), k + 2 x j k + 5/2, 3 -(x j -k), k + 5/2 x j k + 3, 0, otherwise, k = 0, . . . , 2 j -3, (5)
with the respective left-and right-hand side boundary wavelets

ψ j,k (x) = 1 6            -6 + 23x j , 0 x j 1/2, 14 -17x j , 1/2 x j 1, -10 + 7x j , 1 x j 3/2, k = -1, 2 -x j , 3/2 x j 2, 0, otherwise, (6)
and

ψ j,k (x) = 1 6            2 -(k + 2 -x j ), k x j k + 1/2, -10 + 7(k + 2 -x j ), k + 1/2 x j k + 1, 14 -17(k + 2 -x j ), k + 1 x j k + 3/2, -6 + 23(k + 2 -x j ), k + 3/2 x j k + 2, 0, otherwise. k = 2 j -2 (7)
For example, for j = 2 the inner scaling functions are obtained by putting k = 0, 1, 2 in equation (4) as

φ 2,0 (x) =    4x, 0 x < 1/4, 2 -4x, 1/4 x < 1/2, 0, otherwise, (8)
φ 2,1 (x) =    4x -1, 1/4 x 1/2, 1 -4x, 1/2 x 3/4, 0, otherwise, (9)
and

φ 2,2 (x) =    4x -2, 1/2 x 3/4, -4x, 3/4 x 1, 0, otherwise. (10)
Also, for j = 2 the left-and right-hand side boundary scaling functions are obtained by putting j = 2, k = -1 and k = 3 in equations ( 3) and ( 4) respectively as

φ 2,-1 (x) = 1 -4x, 0 x 1/4, 0, otherwise, (11)
and

φ 2,3 (x) = 4x -3, 3/4 x 1, 0, otherwise. (12)
Similarly, for j = 2 the inner wavelet functions are obtained by putting j = 2, k = 0 and k = 1 in equation ( 5) and the leftand right-hand side boundary wavelets are obtained by putting j = 2, k = -1 and k = 2 in equations ( 6) and ( 7) respectively.

Function approximation

A function f (x) defined over [0, 1] may be represented by B-spline wavelets as

f (x) = 3 k=-1 c k φ 2,k + ∞ i=2 2 (i-1)
j=-1

d i, j ψ i, j , (13)
where φ 2,k and ψ i, j are scaling and wavelets functions respectively. If the infinite series in equation ( 13) is truncated, then equation ( 13) can be written as

f (x) = 3 k=-1 c k φ 2,k + M i=2 2 (i-1)
j=-1

d i, j ψ i, j = α T , (14)
where α and are (2 (M+1) + 1) × 1 vectors given by

α = [c -1 , c 0 , . . . , c 3 , d 2,-1 , . . . , d 2,2 , d 3,-1 , . . . , d 3,6 , . . . , d M,-1 , . . . , d M,2 (M-1) ] T , (15)
= [φ 2,-1 , φ 2,0 , . . . , φ 2,3 , ψ 2,-1 , . . . , ψ 2,2 , ψ 3,-1 , . . . , ψ 3,6 , . . . , ψ M,-1 , . . . , ψ M,2 (M-1) ] T . ( 16
) Let = [φ 2,-1 (x), φ 2,0 (x), φ 2,1 (x), φ 2,2 (x), φ 2,3 (x)] T , (17)
= [ψ 2,-1 , . . . , ψ 2,2 , ψ 3,-1 , . . . , ψ 3,6 , . . . , ψ M,-1 , . . . , ψ M,2 (M-1) ] T .

Using equations ( 8)- [START_REF] Chui | An Introduction to Wavelets[END_REF] and equation (17) we get 1 0

T dx = P 1 =         1
        , (19)
and from equations ( 5)-( 7) and equation (18), we have 1 0

T dx = P 2 =      N 4×4 1 2 N 8×8 . . . 1 2 M-2 N 2 M ×2 M      , ( 20
)
where N is a five diagonal matrix given by

N =             
1 96 0 • • • 0 0 -1 864 1 96 2 27              .

The controlled linear oscillator

Consider the optimal control problem of a linear oscillator given in [START_REF] El-Kady M And Elbarbary | A Chebyshev expansion method for solving nonlinear optimal control problems[END_REF] as

J = 1 2 0 -T u 2 (t) dt, (21) subject to ẍ(t) + ω 2 x(t) = u(t), ( 22
) with x(-T ) = x 1 , x(0) = 0, ẋ(-T ) = x 2 , ẋ(0) = 0, (23)
where -T t 0 and T is known. Equations ( 22) and ( 23) are equivalent to

ẋ1 (t) = x 2 (t), ẋ2 (t) = -ω 2 x 1 (t) + u(t), ( 24
)
x 1 (-T ) = x 1 , x 2 (-T ) = x 2 , ( 25
)
x 1 (0) = 0, x 2 (0) = 0. ( 26
)
The problem is to find the control vector u(t) which minimizes equation ( 21) subject to equations ( 24)-( 26). The exact solution of the controlled linear oscillator can be obtained by applying Ponteryagin's maximum principle [START_REF] Pontryagin | The Mathematical Theory of Optimal Processes[END_REF] x

1 (t) = 1 2ω 2 [A 1 ωt sin ωt + A 2 (sin ωt -ωt cos ωt)], x 2 (t) = 1 2ω [A 1 (sin ωt + ωt cos ωt) + A 2 ωt sin ωt], u(t) = A 1 cos ωt + A 2 sin ωt, J = 1 8ω [2ωT (A 2 1 + A 2 2 ) + (A 2 1 -A 2 2 ) sin 2ωT -4A 1 A 2 sin 2 ωT ],
where

A 1 = 2ω[x 1 ω 2 T sin ωT -x 2 (ωT cos ωT -sin ωT )] ω 2 T 2 -sin 2 ωT , A 2 = 2ω 2 [x 2 T sin ωT + x 1 (sin ωT + ωT + ωT cos ωT )] ω 2 T 2 -sin 2 ωT .

Approximation of the controlled linear oscillator

In order to use the linear B-spline wavelets, we introduce the transformation t = T (τ -1). The optimal control problem can be restated as follows

J = T 2 1 0 u 2 (τ ) dτ, ( 27
) subject to ẍ(τ ) = T 2 [-ω 2 x(τ ) + u(τ )], 0 τ 1, ( 28
) with x(0) = x 1 , x(1) = 0, ( 29
) ẋ(0) = T x 2 , ẋ(1) = 0. ( 30
)
In view of equations ( 14)-( 16), ẍ(τ ) and u(τ ) may be represented by

ẍ(τ ) = D T (τ ), (31)
u(τ ) = E T (τ ), (32)
where D and E are unknown (2 M+1 + 1) × 1 vectors. By integrating equation (31) and using equations ( 29) and (30), we get

ẋ(τ ) = D T H (τ ) + T x 2 , ( 33
)
x(τ ) = D T G(τ ) + τ T x 2 + x 1 , (34)
where

H (τ ) = τ 0 (θ) dθ, G(τ ) = τ 0 H (θ) dθ.
By substituting equations ( 31), ( 32) and (34) in equation ( 28), we get

D T (τ ) = T 2 [-ω 2 (D T G(τ ) + τ T x 2 + x 1 ) + E T (τ )], 0 τ 1, (35)
A collocation scheme is defined in equation ( 35) by evaluating the result at the points

τ i = i -1/2 M+1 , i = 1, 2, . . . , 2 M+1 + 1,
that generate a set of 2 (M+1) + 1 algebraic equations as

A * i = D T (τ i ) -T 2 [-ω 2 (D T G(τ i ) + τ i T x 2 + x 1 ) + E T (τ i )] = 0, i = 1, . . . , 2 M+1 + 1. (36)
From equations (29), (30), (33) and (34), we get

x(1) = D T G(1) + T x 2 + x 1 = 0, (37) ẋ
(1) = D T H (1) + T x 2 = 0. (38)
Substituting equation (32) in equation ( 27), and using equations ( 19) and (20), we get

J = T 2 1 0 [E T (τ )][ T (τ )E] dτ = T 2 E T 1 0 [ (τ ) T (τ )] dτ E = T 2 E T P E, ( 39
)
where

P = P 1 P 2 .
The minimization problem of equation ( 27) subject to equations (28)-(30) reduces to a parameter optimization problem which can be stated as follows. Find D and E so that equation ( 39) is minimized subject to the constrains in equations ( 36)-(38). Let

J * (D, E, λ 1 , . . . , λ 2 M+1 +1 , µ 1 .µ 2 ) = J + 2 M+1 +1 i=1 λ i A * i + µ 1 x(1) + µ 2 ẋ(1),
where the scalars λ i , i = 1, . . . , 2 M+1 + 1, µ 1 and µ 2 represent the unknown Lagrange multipliers. The necessary conditions for a minimum are

∂ J * ∂ D = 0, ∂ J * ∂ E = 0. (40)
Equation ( 40) together with equations (36)-(38) are linear algebraic equations which can be solved for unknowns D, E, λ i , i = 1, . . . , 2 M+1 + 1, µ 1 and µ 2 .

The controlled Duffing oscillator

The optimal control of Duffing oscillator is described by the nonlinear differential equation [START_REF] El-Kady M And Elbarbary | A Chebyshev expansion method for solving nonlinear optimal control problems[END_REF],

ẍ(t) + ω 2 x(t) + x 3 (t) = u(t), -T t 0, (41)
subject to same boundary condition as in linear case with the same performance index. The exact solution in this case is not known. By using the transformation t = T (τ -1) and equations ( 31)-(34), we obtain the following approximation for equation (41).

D T (τ ) = T 2 [-ω 2 (D T G(τ ) + τ T x 2 + x 1 ) + (D T G(τ ) + τ T x 2 + x 1 ) 3 + E T (τ )], 0 τ 1. (42)
A collocation scheme is defined in equation ( 42) by evaluating the result at the points τ i = i -1/2 M+1 , i =1, 2, . . . , 2 M+1 + 1, that generate a set of 2 (M+1) + 1 algebraic equations as

D T (τ i ) -T 2 [-ω 2 (D T G(τ i ) + τ i T x 2 + x 1 ) + E T (τ i )] = 0, i = 1, . . . , 2 M+1 + 1, (43)
Equation ( 43) is a nonlinear equation, and hence the determining equations similar to equation (40) are also nonlinear equations which can be solved by Newton's iterative method. The starting values required to start Newton's iterative method can be chosen from the controlled linear oscillator i.e., = 0, see [START_REF] Vlassenbroeck | Chebyshev series solution of the controlled Duffing oscillator[END_REF].

The numerical results

We applied the present method to a controlled linear oscillator for various values of M with the following choice of the numerical values of the parameters in the standard case

ω = 1, T = 2,
x(-1) = 0.5, ẋ(-1) = -0.5

In table 1, we report the errors e x = x(τ ) -x * (τ ) 2 and e u = u(τ ) -u * (τ ) 2 , where x(τ ) and u(τ ) are obtained from the present method, and x * (τ ) and u * (τ ) are exact solutions of the problem. The symbol • 2 denotes the L 2 norm. In table 2, a comparison is made between the present method for M = 4, 6, 8 and 10 together with the solution obtained by [START_REF] Vlassenbroeck | Chebyshev series solution of the controlled Duffing oscillator[END_REF] for the controlled linear oscillator and the exact solution. Table 3 presents, for various values of the parameters w, T , x 1 and x 2 , the maximum error using the present method for M = 8 on the performance index in comparison with the results obtained from the exact solution, together with the results obtained by the method of [START_REF] Vlassenbroeck | Chebyshev series solution of the controlled Duffing oscillator[END_REF] with m = 10, m 1 = 15 and N = 30. Unlike the method in [START_REF] Vlassenbroeck | Chebyshev series solution of the controlled Duffing oscillator[END_REF], using the present method, by increasing the value of some of the above parameters, and holding the other parameters fixed, the accuracy is not relatively lower than the accuracy obtained using the standard case.

(m = 10, m 1 = 15, N = 30) w = 2 9.7 × 10 -11 T = 3 6.6 × 10 -14 x 1 = 1, x 2 = -1 1.1 × 10 -14 Present method Standard case 1.0 × 10 -16 M = 8 w = 2 5.2 × 10 -16 T = 3 1.1 × 10 -16 x 1 = 1, x 2 = -1 1.0 × 10 -16
In table 4, the approximation for the controlled Duffing oscillator using the present method for M = 6, 8 and 10 and the solutions obtained by the Chebyshev approximation [START_REF] Vlassenbroeck | Chebyshev series solution of the controlled Duffing oscillator[END_REF] for the same numerical values of the parameters w, T , x 1 and x 2 as given in the standard case and where, in addition, the coefficient ε of the nonlinearity has been taken as ε = 0.15.

Conclusion

In the present work, a technique has been developed for obtaining the optimal solution of the controlled Duffing oscillator. The method is based upon compactly supported linear SO B-spline wavelets. The simplicity of these bases which simplifies the process of reducing nonlinear system dynamics to algebraic equations and the structure of the P matrix given in equation (39) makes this approach computationally very attractive.

4 × 8 Table 2 .

 482 10 -5 1.2 × 10 -6 M = 8 4.4 × 10 -6 1.0 × 10 -7 M = 10 5.5 × 10 -7 1.0 × 10 -Estimated and exact values of J . Methods J Method of [8] m = 4, m 1 = 6, N = 12 0.184917 m = 7, m 1 = 10, N = 20 0.18485854 m = 10, m 1 = 15, N = 30 0

Table 4 .

 4 A comparison for the controlled Duffing oscillator J . Methods J Method of [8] m = 4, m 1 = 6, N = 12 0.187531 m = 7, m 1 = 10, N = 20 0.18744484 m = 10, m 1 = 15, N = 30 0

Table 1 .

 1 Error's norm of estimated control and state functions.

Table 3 .

 3 Error on J versus parameters.

	Methods	Parameter	Error on J
	Method of [8]	Standard case	2.7 × 10 -16


David Vallat
email: david.vallat@univ-lyon1.fr

Paul Valéry

A Platform Economy? A Sharing Economy? A Gig Economy? The Changing Nature of Work, Employment, and Market Competition An Alternative to State-Market Dualism: The Sharing Economy. Practical and Epistemological Questions

, as well as that of changing values (related to the rise of Generation Y in the workforce -Dagnaud, 2013).

. The undertaking is tricky but necessary, as the subject generates much confusion. In examining the matter, we will first underscore two major dimensions of this economic form. Second, after having performed this initial categorization, we will venture to give it more depth by emphasizing the originality of the epistemological approach inherent in certain sharing economies that lead to a profound questioning of our models of (economic) rationality.

I. The Paradoxes of the Sharing Economy

The sharing economy contains a certain contradiction in terms, accompanied by strong structural characteristics.

The "sharing economy" and it's contradictions

The sharing economy covers a multitude of activities focused on production, consumption, finance, and trade. One might ask just what the commonalities are between Airbnb, Uber,

2

Wikipedia, Ulule, Blablacar, La Ruche qui dit Oui!, Leboncoin, Linux, fab labs, LETS (local exchange trading systems), accorderies, and worker cooperatives. It is rather difficult to answer this question, as the sharing economy concerns more than just a few specific economic activities -it spreads into all spheres of economic activity 1 (exchange, consumption, production, finance): from second-hand markets (Ebay, Leboncoin), ridesharing (Blablacar) to transportation (Uber) to lodging rentals (Airbnb), consumption of local agriculture (La Ruche qui dit Oui!, Les Paniers de Martin), crowdfunding (Kickstarter, Ulule, KissKissBankBank), complementary currencies (Brixton pound), knowledge pooling (Wikipedia, Wikia, reciprocal knowledge exchange networks, Linux), production (fab lab, hackerspace, SCOP worker cooperatives), exchange of goods and services (accorderies, local exchange trading systems), and so on. Rachel Botsman's work claims that the sharing economy originated in the context of economic and ecological crisis with the desire to privilege the use of goods over their ownership (Botsman & Roger, 2011) 2 . While collaborative consumption is indeed relevant and extensive (isn't it more important to have access to a drill rather than to own it if you only need it once or twice a year?), the sharing economy is vaster yet. Jeremy Rifkin (2014, p. 326ff.) sheds light on the subject from a logistical angle. The sharing of information and resources (warehouses, unoccupied car seats, free rooms in an apartment, parking spaces, drills, etc.) enables an optimization of their use and thus the avoidance of colossal waste. Some companies are redefining their objectives so as to privilege use over property in the aim of sustainable development. As such, they fall under the category of the functionoriented economy (or the product-service system) 3 . Here is a first possible segmentation: between a sharing economy whose starting point is the horizontalization of interpersonal relationships mediated by digital platforms used as "weapons of mass collaboration" [START_REF] Tapscott | Wikinomics: How Mass Collaboration Changes Everything[END_REF] and another sharing economy whose starting point is a more vertical, traditional organization (companies as we know them now) that redefines its values and business model so as to integrate cooperation/collaboration into its strategic objectives and/or its organizational mode. The former refers to sharing economy and collaborative consumption initiatives; the latter concerns the function-oriented economy, circular economy 4 , production cooperatives, or more broadly the field of social economy (Laville, 1994(Laville, , 1999;;[START_REF] Demoustier | L'économie sociale et solidaire[END_REF][START_REF] Draperi | L'économie sociale et solidaire : une réponse à la crise[END_REF].

We find, then, that the borders of the sharing economy are not easily defined insofar as these initiatives may originate in a strict commercial logic just as they may emerge from an aspiration for solidarity (and sometimes with a savvy blend of both). The French think tank OuiShare (ouishare.net), an important medium in the sharing economy both in France and throughout the world, founded in 2011, groups the following five phenomena under the term "sharing economy": collaborative consumption; It is therefore necessary to deepen our understanding of the sharing economy by underscoring some of its distinguishing characteristics.

Horizontal culture and the return of the "invisible hand"

The sharing economy's actors have embraced the "horizontal" culture of the internet [START_REF] Castells | The Rise of the Network Society, The Information Age: Economy, Society and Culture[END_REF][START_REF] Castells | La galaxie Internet[END_REF], where power, responsibilities, information, and knowledge are distributed and shared, and the lines between producer and consumer blur [START_REF] Rifkin | La nouvelle société du coût marginal zéro, Les liens qui libèrent[END_REF], speaks of the "prosumer" to refer to a reality where individuals can simultaneously be both producers and consumers). Networks form around shared values in digital and physical communities to provide personalized answers to specific problems and to thereby pave the way for a new economic model: the "long tail" (the sale/offer of a large variety of products, each in small quantity - [START_REF] Anderson | The Long Tail[END_REF].

Digital auctioneers (Uber's, Airbnb's, and Kickstarter's algorithms play this role) that mediate peer-to-peer (P2P) exchanges act like so many "invisible hands". Could this be the return of Smith? Or Hayek? The question deserves to be asked when the founder of Wikipedia, Jimmy Wales, affirms that "Hayek's work on price theory is central to my own thinking about how to manage the Wikipedia project" (Mangu-Ward, 2007). Indeed, "prosumers" can get what they want directly from other "prosumers" with minimal or even no transaction cost (in the "zero marginal cost society" described by [START_REF] Rifkin | La nouvelle société du coût marginal zéro, Les liens qui libèrent[END_REF]. According to Rifkin, this collaborative model will progressively push capitalism aside. Take for example the fact that Airbnb has a larger market capitalization than the Hyatt group without owning a single hotel5 . The accumulation of capital (the basis of capitalism) is therefore no longer the guarantee of economic hegemony.

The sharing economy facilitates the transformation of private goods (car, apartment, drill, etc.) into productive goods. This originates, in part, from an economy of frugality found at the intersection of ecological motivations and economic crisis. All of these little invisible hands are acting within a regulatory framework ill-suited to the sharing economy6 . This new model is accompanied by a marked increase in independent workers in both France and the United States7 -a sort resurgence of the putting-out system or an acceleration of the Second Industrial Divide [START_REF] Piore | The Second Industrial Divide[END_REF] between mass production and artisanal production. A corollary to this movement has been qualified as the "Uberization of work", in reference to the company Uber, whose UberPop service puts people seeking supplemental income (or a full income) to work under very precarious conditions.

4

In any event, it is difficult to pretend that the sharing economy doesn't exist when we know that the wealth created by this sector could reach up to 335 billion USD by 2025 from its 15 billion in 20148 . Apparently frugality isn't a concern for all of the sharing economy's actors. But what about Uber or Airbnb has to do with sharing or collaboration? The notion of collaboration is ambiguous [START_REF] Servet | De nouvelles formes de partage : la solidarité au delà de l'économie collaborative[END_REF]. And on what level is it situated? Is sharing or collaboration a better term? The algorithms that manage the connection of individuals on these digital platforms are not open access, nor are the client databases.

For some, Uber and Airbnb should not be considered a part of the sharing economy9 , which refers more to the formation of self-organized communities of interest and peer-to-peer relationships as well as with the construction and management of common goods [START_REF] Servet | De nouvelles formes de partage : la solidarité au delà de l'économie collaborative[END_REF][START_REF] Bauwens | Sauver le monde. Vers une économie post-capitaliste avec le peer-to-peer[END_REF]. How then should we make a distinction between a sharing economy based in a capitalism founded on the massive use of digital tools thanks to the Internet (a "netarchical capitalism" as Bauwens puts it, 2015) and another sharing economy, to be defined, based on a communal project?

II. Characterizing the Sharing Economy

Of course, the sharing economy promotes a distributed view of the economy (Rifkin, 2012, p. 155) in which the consumer becomes involved in production by making their goods available to a third party. The pooling of goods, facilitated by the mediation of digital platforms10 , aims to save money, to use fewer resources, to reduce consumption and pollution, and to redefine consumer necessities (to shift away from goods and toward relationships). Peer-to-peer exchanges enable collaborative arrangements of production and exchange without being weighed down by institutions or organizations -it is an economy based on demand, where the consumer acts in the field of production [START_REF] Bauwens | Sauver le monde. Vers une économie post-capitaliste avec le peer-to-peer[END_REF]. The peer-to-peer approach proposes a view of the economy's place in society that was first envisioned by the economic sociologist Karl Polanyi in the mid-20 th century. This vision is based on the desire to change economic relationships and to organize their cooperative management.

The sharing economy -an economy re-embedded in society?

The sharing economy produces social innovation [START_REF] Klein | L'innovation sociale[END_REF] by mobilizing economic behaviors that reinforce social cohesion whereas mercantile exchange is a behavior that tends to depersonalize exchanges. Karl Polanyi discussed this phenomenon at length (Maucourant et al., 1998), beginning with his identification of the two meanings of "economy". The polysemy of this word is the source of many imprecisions in the dominant discourse (Polanyi, 1977, p. 19). In its formal sense, the economy connects means to endsit is a question of maximizing interest (profit) by avoiding waste -that is, by saving (through efficiency). As such, the economy is the prerogative of a select few firms, namely those organized by the principles of economic liberalism. The substantive meaning of the economy is altogether different, concerning a much larger number of companies. In the 5 substantive sense, the economy is the process that enables the livelihood of humankind (through efficiency). This livelihood circulates through interactions with other people and with their natural environment, and interactions with other people fit into a social framework, as humans cannot survive outside of society. Economics is thus immersedembedded -in the social.

Polanyi identified four principles of economic behavior: three in the substantive sense and the last in the formal sense. These principles are associated with institutional models operative in a given society, which are in turn intended to facilitate the implementation of economic principles of behavior.

The first principle is reciprocity, which consists of giving when one has received. Reciprocity can take many forms, but it's essential characteristic is that it concerns individuals that identify with one another in some respect. "Reciprocity is enormously facilitated by the institutional pattern of symmetry, a frequent feature of social organization among nonliterate peoples" (Polanyi, 1944, p. 78). Redistribution, the second principle of economic behavior, can be sketched as an initial movement of products toward a central authority which then disseminates them. "The institutional pattern of centricity […] provides a track for the collection, storage, and redistribution of goods and services" (ibid.). Finally, the principal of domestic administration, which roughly consists of consuming what one produces oneself, is based on the model of the closed group (ibid., p. 83). These three principles of economic behavior, which are not mutually exclusive, represent forms of integration into a group. They rely on institutional models generated by the collective. Respecting and adhering to these principles allows the individual to fit into their community (ibid., p. 86).

The fourth principle is mercantile exchange based on the institutional model of the market. In this case, society does not determine the individual's place according to "custom and law, magic and religion". It is rather the market's function to establish the individual's place in society in a purely mechanical manner by intersecting the individual's offers/demands with those of other buyers/sellers on the market in question. In such cases, the market risks becoming the sole "social" link due to its tendency to depersonalize exchanges [START_REF] Durkheim | De la division du travail social[END_REF].

Different forms of sharing economy mobilize these principles to various degrees. One can already see that Uber, Airbnb, and Ebay fall within the category of mercantile exchange based on the institutional model of the market despite the fact that the exchanges are peerto-peer (P2P). Wikipedia [START_REF] Rifkin | La nouvelle société du coût marginal zéro, Les liens qui libèrent[END_REF], fab labs [START_REF] Lallement | L'âge du faire. Hacking, travail, anarchie[END_REF], and LETS (Ferraton, Vallat, 2012), however, primarily function according to the principle of reciprocity based on the institutional model of symmetry. This principle of reciprocity characterizes the "concern for others" [START_REF] Servet | Le principe de réciprocité chez Karl Polanyi, contribution à une définition de l'économie solidaire[END_REF] found in groups where the pursuit of the common good takes precedence over the pursuit of individual interests. The sharing economy, in a Polanyian framework, refers to a substantive conception of the economy (the economy is embedded in and works in the service of society). Economic action is thus oriented toward the production of social utility, as is the case with solidarity economy projects [START_REF] Ferraton | Economie sociale et solidaire, création d'activité et utilité sociale[END_REF][START_REF] Gadrey | L'utilité sociale en question, à la recherche de conventions, de critères de méthodes d'évaluation[END_REF].

6

With these points in mind, we can enrich our description of the sharing economy to begin distinguishing several forms of sharing economy according to the Polanyian framework. For example, it is possible to act within a mercantile structure while having a substantive conception of the economy (this is the case in circular economies, product-service systems, and worker cooperatives). Likewise, it is possible for several principles of economic behavior to coexist within the same organization: a fab lab or a neighborhood development committee partially subsidized by public funds can function according to the principles of reciprocity or redistribution [START_REF] Demoustier | Economie sociale et solidaire, développement économique local et politique de la ville[END_REF].

Economic behavior does not seem a sufficient criterion to make distinctions between actors in the sharing economy, thus we will explore a second criterion, pertaining to the cooperative management of the economy.

A cooperatively managed economy?

The sharing economy seems to offer a third way, between the State and the market -that of the Collaborative Commons [START_REF] Rifkin | La nouvelle société du coût marginal zéro, Les liens qui libèrent[END_REF], which, aiming to produce, innovate, and manage cooperatively [START_REF] Ostrom | Governing the Commons: The Evolution of Institutions for Collective Action[END_REF]Hess & Ostrom, 2007), is based on the community's interests (economy in the substantive sense) rather than on the satisfaction of individual desires alone (economy in the formal sense). This perspective is in line with open access culture [START_REF] Suber | Open Access[END_REF], a prominent part of Internet culture [START_REF] Benkler | Coase's penguin, or Linux and the nature of the firm[END_REF]. The collaborative culture associated with the Internet draws from its academic beginnings (Castells, 2002, p. 18-49), and more generally from open source culture (while this cultural trait has not been the only one to create Internet culture, it does constitute a major foundation according to Castells -2002, p. 50-82). Thus the collective/collaborative production of content (of which Wikipedia is emblematic) has been seeping into organizations, if only by way of generational effect (generation Y11 ), and is said to contribute to the construction of an adaptive, creative, collective intelligence (Williams Woolley et al., 2010).

Collaborative practices create value for the group/society, and the free software movement is at the forefront of this idea of producing value cooperatively to the benefit of all [START_REF] Mangolte | Le logiciel libre comme commun créateur de richesses[END_REF]. In this context, knowledge is the good being collaboratively managed. The Linux operating system, the Firefox web browser, and the Arduino boards are examples of the innovative fruits of distributed, democratized development [START_REF] Hippel | Democratizing Innovation[END_REF]. As the world economy is largely based on the production and distribution of knowledge12 , this means there is great temptation to appropriate collaboratively produced knowledge for profit. Economist Elinor Ostrom's work on the commons establishes a framework for thinking about the management of these goods.

The notion of the commons was first used to speak of common-pool resources requiring communal management [START_REF] Ostrom | Governing the Commons: The Evolution of Institutions for Collective Action[END_REF]) in order to avoid the "tragedy of the commons" [START_REF] Hardin | The Tragedy of the Commons[END_REF]) -which is to say, the excessive exploitation of a common limited resource to private ends (e.g., fish stocks). After initial work on the commons was published near the end of the 1970s, with its focus on the management of rare resources (Ostrom & Ostrom, 7 1977), the commons was reimagined with a particular focus on culture (Bertacchini et al., 2012), the Internet [START_REF] Benkler | Overcoming Agoraphobia: Building the Commons of the Digitally Networked Environment[END_REF], and knowledge (Ostrom & Hess, 2011). It is thus possible to give a general definition of commons:

Commons is a general term that refers to a resource shared by a group of people. In a commons, the resource can be small and serve a tiny group (the family refrigerator), it can be a community-level (sidewalks, playgrounds, libraries, and so on), or it can extend to international and global levels (deep seas, the atmosphere, the internet, and scientific knowledge). The commons can be well bounded (a community park or library); transboundary (the Danube River, migrating wildlife, the Internet); or without clear boundaries (knowledge, the ozone layer). (Ostrom & Hess, 2011, p. 4-5) 13 Knowledge is a particular kind of commons -it grows as it is shared. The more this resource is called upon, the more it develops; and this development has been made much easier as information and communications technology bring the cost of sharing down to nearly nothing [START_REF] Rifkin | La nouvelle société du coût marginal zéro, Les liens qui libèrent[END_REF]. Within our Polanyian framework, we would say that the production of knowledge relies upon the economic behavior model of reciprocity, based on the institutional model of symmetry -the symmetry of all knowledge producers whose creativity is recognized by all14 . This is the model that allows for the democratization of innovation [START_REF] Hippel | Democratizing Innovation[END_REF].

Knowledge is, of course, a non-rivalrous good, but it can be improperly appropriated and thus calls into question the establishment of property rights [START_REF] Orsi | Revisiter la propriété pour construire les communs[END_REF]. Privatization is a constant threat to common resources (Polanyi gives the example of the creation of enclosures in the 18 th century as "a revolution of the rich against the poor" - [START_REF] Polanyi | La Grande Transformation. Aux origines politiques et économiques de notre temps[END_REF], which explains the resistance movements against privatization in the domain of knowledge [START_REF] Latrive | Du bon usage de la piraterie : culture libre, sciences ouvertes[END_REF] that advocate for open access [START_REF] Suber | Open Access[END_REF] and free culture protected by Creative Commons licenses (Lessig, 2004).

We may further characterize the different forms of sharing economy by adding a discriminating criterion based on the communal management of resources (especially the resource of knowledge, but not exclusive of financial resources, i.e., the sharing of findings related to a given activity). The representatives of "netarchical capitalism" do not share their algorithms for putting peers into contact nor do they share their profits or client databases (which are furnished by the clients themselves).

The sharing economy is not a political movement; while it sustains what may be considered a utopian project (Michel Bauwens' book is titled "To Save the World" -2015, and Jeremy Rifkin speaks of "eclipsing capitalism" -2014), it is based in a diagnosis of the actual that leads one to think: "the structure of our society is profoundly out of sync with the principles of contribution, participation, and cooperation on which the digital and the sharing economy rely" (Filippova, back cover). This conclusion is widely shared (Castelles, 1996;[START_REF] Anderson | Makers[END_REF][START_REF] Tapscott | Wikinomics: How Mass Collaboration Changes Everything[END_REF][START_REF] Botsman | What's Mine Is Yours: The Rise of Collaborative Consumption[END_REF]. Beyond this diagnosis, the supporters of the sharing economy advocate action -participation in the 8 creation of this new world by being an agent of change. Action becomes the means of testing ideas and overcoming the movement's internal contradictions 15 .

III. The Sharing Economy Is Conceived through Action

Sharing economies are united in action. Certain initiatives are managed collectively, based on reciprocity, and remain nonprofit. Others -victims of their success -shift to the side of "netarchical capitalism". No matter where they end up, they appear to share an original impetus -to act, to make, which contributes to the transformation of our worldview.

The sharing economy encourages us to bricoler

What does it mean to "make" [START_REF] Lallement | L'âge du faire. Hacking, travail, anarchie[END_REF][START_REF] Anderson | Makers[END_REF]? It is more than a political agenda, it is a way of life: to no longer be a passive consumer -to join the ranks of the producers. Production liberates, as Proudhon emphasized (in hackerspaces we approach the Prouhonian notion of mutualism that was opposed to the Marxist vision of communal ownership of the means of production) -production in places where space, tools, experiences and knowledge (fab labs and hackerspaces) are shared, production to affirm one's identity, in collaboration and for collaboration's sake. To make is to learn by doing -it is a practice of production/personal liberation that fosters empowerment16 ; it is the union of art and technique (which encourages disciplinary decompartmentalization). One might ask if the sharing economy announces the triumph of pragmatism over ideology, of the maker over the professional.

The 3d printers, laser cutters, and other digital machining tools that one finds in fab labs give access to a new form of making that is no longer simply individual, but interconnected [START_REF] Anderson | La longue traine[END_REF]2012). The Internet hasn't only made possible the implementation of more horizontalized relationships that facilitate collaboration, it has revealed and promoted the image of the maker that each of us can be (in the digital and/or the analog world) [START_REF] Castells | The Rise of the Network Society, The Information Age: Economy, Society and Culture[END_REF][START_REF] Rifkin | La nouvelle société du coût marginal zéro, Les liens qui libèrent[END_REF]. These transformations obviously call for us to question the way in which we think about society and organizations [START_REF] Castells | La galaxie Internet[END_REF]. Indeed, the idea of bricolage [DIY, tinkering] can shed light on the process of innovation (Gundry et al., 2003;[START_REF] Garud | Bricolage Versus Breakthrough: Distributed and Embedded Agency in Technology Entrepreneurship[END_REF], on the choices of entrepreneurs, and on the understanding of organizations (Duymedian and Rüling, 2010). We will show that, by way of its pragmatism, bricolage also calls into question the way we understand the construction of knowledge.

In his book The Savage Mind (published in 1962 17 ), Claude Lévi-Strauss developed the concept of bricolage to characterize a mode of understanding the world based on experimentation -a "science of the concrete" (Lévi-Strauss, 2014, p. 30) that he defines as follows:

In its old sense the verb 'bricoler' applied to ball games and billiards, to hunting, shooting and riding. It was however always used with reference to some extraneous movement: a ball rebounding, a dog straying or a horse swerving from its direct course to avoid an obstacle. And in our own time the 'bricoleur' is still someone who works with his hands and uses devious means compared to those of a craftsman. (ibid.)

By using the analogy of DIY making, Lévi-Strauss attempts to escape what he calls the "Neolithic paradox" (ibid., p. 26). The Neolithic period saw the advent of pottery, weaving, agriculture, animal husbandry, metallurgy, and more technologies that do not come into existence by simple chance, but neither did these discoveries appear as the results of a "modern" (analytical) scientific approach as that formalized by Descartes several centuries later. Thus two scientific approaches coexist in history -one incarnated by the bricoleur and the other by the engineer:

The 'bricoleur' is adept at performing a large number of diverse tasks; but, unlike the engineer, he does not subordinate each of them to the availability of raw materials and tools conceived and procured for the purpose of the project. His universe of instruments is closed and the rules of his game are always to make do with 'whatever is at hand' […].The set of the 'bricoleur's' means cannot therefore be defined in terms of a project (which would presuppose besides, that, as in the case of the engineer, there were, at least in theory, as many sets of tools and materials or 'instrumental sets', as there are different kinds of projects). It is to be defined only by its potential use or, putting this another way and in the language of the 'bricoleur' himself, because the elements are collected or retained on the principle that 'they may always come in handy'. (ibid., p. 31)

Cobbling together a construction of the world

Science seeks to understand, whereas the bricoleur seeks to build, which is anything but a barrier to understanding. On the contrary, it reminds us that the construction of knowledge is inconceivable without action: "all doing is knowing, all knowing is doing" [START_REF] Maturana | The Tree of Knowledge: The Biological Roots of Human Understanding[END_REF]. This construction of knowledge is created in dialogue with the world. The scientist observes, whereas the bricoleur dialogues; the bricoleur is in the world -he is the world. This is why the bricoleur accepts "[…] the incorporation of a certain amount of human culture into reality" (Lévi-Strauss, 2014, p. 34). Hence the term bricolage qualifies (teleologically) both the mode of production and its result.

Finally, the maker movement and its DIY approach encourage us to be/make the world, challenging our relationship to knowledge as well as calling into question the place of the engineer and the bricoleur more broadly. The figure of the bricoleur leads us to consider a profound ontological hypothesis: the real does not exist in and of itself -the project contributes to its creation. This hypothesis has already been discussed at length in the sciences in its relationship to pragmatic epistemological (Bazzoli & Dutraive, 2015) and constructivist approaches (Le Moigne, 2012) 18 . It certainly deserves to be discussed much more in the context of organizational management and political action 19 . Doing goes beyond ideological discourse by implementing concrete shared solutions (Wikipedia, OpenstreetMap, Linux, etc.) based on togetherness (or an economy in the substantive 18 "Radical constructivism, thus, is radical because it breaks with convention and develops a theory of knowledge in which knowledge does not reflect an 'objective' ontological reality, but exclusively an ordering and organization of a world constituted by our experience. The radical constructivist has relinquished 'metaphysical realism' once and for all, and finds himself in full agreement with Piaget, who says: 'Intelligence organizes the world by organizing itself'" (von [START_REF] Glasersfeld | An Introduction to Radical Constructivism[END_REF]. 19 We might inquire into the capacity of a given sharing economy to correspond to a return to political engagement by way of community involvement [START_REF] Putnam | Bowling Alone: America's Declining Social Capital[END_REF][START_REF] Putnam | Bowling Alone: The Collapse and Revival of American Community[END_REF]. 10 sense).

A Provisional Conclusion

On the one hand, we have open access culture [START_REF] Suber | Open Access[END_REF], where peers join together in support of a socially useful project and produce collectively; on the other hand are gigantic commercial enterprises that profit from the opportunities made available by the Internet and seek to establish a "netarchical capitalism"20 . The sharing economy concentrates contradictions of which the field's actors are clearly aware and which are simply the reflection of the complexity of our societies. This is why we distinguish different forms of sharing economy. Certain of them may appear as the culmination of the new spirit of capitalism [START_REF] Boltanski | Le nouvel esprit du capitalisme[END_REF] and others as its reassessment. Some of these initiatives, "victims" of worldwide success (Airbnb), succumb to institutional isomorphism [START_REF] Dimaggio | The Iron Cage Revisited: Institutional Isomorphism and Collective Rationality in Organizational Fields[END_REF], reproducing organizational forms of the past as they blend into a new capitalism supported by digital networks. Others take part in the desire to make in order to affirm one's existence in the world (to re-affiliate oneself [START_REF] Castel | Les Métamorphoses de la question sociale[END_REF], or even to transform the world and to cobble together a concrete utopia.

Makers shake up the orderly arrangement of the scientific organization of work [START_REF] Anderson | La longue traine[END_REF][START_REF] Anderson | Makers[END_REF] 21 , prosumers throw into question the workings of capitalism [START_REF] Rifkin | La nouvelle société du coût marginal zéro, Les liens qui libèrent[END_REF], and hackers challenge ownership [START_REF] Latrive | Du bon usage de la piraterie : culture libre, sciences ouvertes[END_REF]): all of them open new horizons for researchers to explore, as the established knowledge does not exhaust this new context.

The way is open to cobble together new knowledge.

  crowdfunding (peer-to-peer financing); open knowledge (open data, open education, open governance); the maker 1 For a couple of taxonomic essays on the sharing economy, see Bauwens (2012) and Servet (2014).

	movement (open design and manufacturing, DIY); and open and horizontal governance
	(participatory budgeting, cooperatives, do-ocracy, holacracy).
	Office 2004 Test Drive User 7/2/y 15:09
	Commentaire [1]: platform?
	2 Also called collaborative consumption.
	3 http://www.club-economie-fonctionnalite.fr
	4 http://www.institut-economie-circulaire.fr
	3

http://www.lefigaro.fr/secteur/high-tech/2014/03/21/32001-20140321ARTFIG00367-la-start-up-airbnbvaut-aussi-cher-que-les-grandes-chaines-d-hotellerie.php

6 http://www.lemonde.fr/entreprises/article/2015/03/14/uber-bouscule-la-loi-thevenoud_4593581_1656994.

html 7 http://telos-eu.com/fr/politique-economique/economie-collaborative-un-programme-politique-pour.html. In America, this is referred to as the Gig Economy: http://www.wired.com/insights/2013/09/the-gigeconomy-the-force-that-could-save-the-american-worker/

http://www.paristechreview.com/2014/12/31/economie-partage-reglementation/).

http://www.lemonde.fr/entreprises/article/2015/06/25/michel-bauwens-uber-et-airbnb-n-ont-rien-avoir-avec-l-economie-de-partage_4661680_1656994.html

10 http://www.brie.berkeley.edu/wp-content/uploads/2015/02/PlatformEconomy2DistributeJune21.pdf

See Dagnaud, 2013 and Palfrey & Gasser, 2008.

See OECD (2012a), OECD (2012b), European Commission (2010).

For a more in-depth definition, see[START_REF] Coriat | Le retour des communs. La crise de l'idéologie propriétaire, Les Liens qui Libèrent Dagnaud[END_REF].

The Internet makes all production available (especially knowledge) and thereby democratizes creativity[START_REF] Anderson | La longue traine[END_REF][START_REF] Anderson | Makers[END_REF][START_REF] Serres | Petite Poucette[END_REF].

http://telos-eu.com/fr/politique-economique/economie-collaborative-un-programme-politique-pour.html

See Ferraton & Vallat, 2004.

The references given here correspond to the 2014 edition.

http://www.liberation.fr/economie/2015/03/20/le-peer-to-peer-induit-que-la-production-emane-de-lasociete-civile_1225002

 21 Worker cooperatives have been able to play this role, but on a smaller scale.

Abstract:

The values of the collaborative economy (openness, cooperation, equality, empowerment, reciprocity) allow it to propose an alternative to capitalism. We attempt to characterize this form of economy by inquiring into its intentions (with a Polanyian framework), its mode of governance (collective), and its relationship to act of production.


Ciaran Mccreesh

Samba Ndojh Ndiaye

Patrick Prosser

Samba Ndojh

Ndiaye †2

Christine Solnon

Clique and Constraint Models for Maximum Common (Connected) Subgraph Problems

  L'archive ouverte pluridisciplinaire

Introduction

Maximum common subgraph problems arise in biology and chemistry [START_REF] Ehrlich | Maximum common subgraph isomorphism algorithms and their applications in molecular science: a review[END_REF][START_REF] Gay | On the subgraph epimorphism problem[END_REF][START_REF] Raymond | Maximum common subgraph isomorphism algorithms for the matching of chemical structures[END_REF], in computer vision [START_REF] Combier | Map edit distance vs. graph edit distance for matching images[END_REF][START_REF] Cook | Substructure discovery using minimum description length and background knowledge[END_REF], in the analysis of source code [START_REF] Djoko | An empirical study of domain knowledge and its benefits to substructure discovery[END_REF], binary programs [START_REF] Gao | Binhunt: Automatically finding semantic differences in binary programs[END_REF], and circuit designs [START_REF] Cook | Substructure discovery using minimum description length and background knowledge[END_REF], in character recognition problems [START_REF] Lu | Hierarchical attributed graph representation and recognition of handwritten chinese characters[END_REF], and in many other domains [START_REF] Shasha | Algorithmics and applications of tree and graph searching[END_REF], both directly and as a way of measuring the similarity or difference between two graphs [START_REF] Bunke | On a relation between graph edit distance and maximum common subgraph[END_REF][START_REF] Fernández | A graph distance metric combining maximum common subgraph and minimum common supergraph[END_REF][START_REF] Kriege | Comparing graphs[END_REF]. We illustrate two variants of this problem in Fig. 1-in both cases we are finding an induced subgraph and maximising the number of vertices selected, but in the second variant the common subgraph must be connected. Fig. 1. A maximum common induced subgraph of the first two graphs has eight vertices, shaded. However, if we require the common subgraph to be connected, only seven vertices may be selected-one way to do this is shown in the third and fourth graphs.

Definitions and Notation

We introduce definitions and algorithms on undirected and unlabelled graphs; the extension to general graphs is straightforward and is discussed in section 2.3. An undirected graph G is defined by a finite set of vertices V(G) and a set of undirected edges E(G) ⊆ V(G) × V(G), where (u, v) ∈ E(G) ⇒ (v, u) ∈ E(G). The neighbourhood of a vertex v, written N(G, v), is the set of vertices to which it is adjacent, so N(G, v) = {u ∈ V(G) : (u, v) ∈ E(G)}. Given a graph G, two vertices v s , v e ∈ V(G) are connected by a path in G if there exists a sequence of vertices (v 0 , v 1 , . . . , v k ) such that v 0 = v s , v k = v e , and each pair of successive vertices is connected by an edge, i.e. ∀i ∈ {1 . . . k}, (v i-1 , v i ) ∈ E(G). A graph G is connected if every distinct pair of vertices is connected by a path.

The subgraph of a graph G induced by a set H ⊆ V(G), written G[H], is the graph with vertex set H, and with every edge in G which has both endpoints in G, i.e. E(G[H]) = E(G) ∩ (V(H) × V(H)). We will consider only subgraphs which are induced by some set. It is also possible to permit removing edges which are not incident to removed vertices, thus leading to partial subgraphs-we do not consider this possibility in this paper, although everything we discuss may be extended to the partial case [START_REF] Ndiaye | CP models for maximum common subgraph problems[END_REF][START_REF] Vismara | Finding maximum common connected subgraphs using clique detection or constraint satisfaction algorithms[END_REF].

A graph G is isomorphic to another graph H if there exists a bijective function f : V(G) → V(H) which preserves edges and non-edges, i.e. ∀(u, v) ∈ V(G) × V(G), (u, v) ∈ E(G) ⇔ (f (u), f (v)) ∈ E(H). A common subgraph of two graphs G and H is a graph isomorphic to subgraphs of both G and H. A common connected subgraph is a common subgraph which is connected. A Maximum Common Subgraph, or MCS (resp. Maximum Common Connected Subgraph, or MCCS) is a common subgraph (resp. common connected subgraph) which has a maximum number of vertices.

Overview

In section 2, we review existing approaches for solving the MCS problem, with a specific focus on Constraint Programming (CP)-based techniques, and on reductions of the problem to finding a maximum clique in an association graph.

Previous experimental evaluations have used simple maximum clique algorithms, or even enumeration algorithms-for example, Vismara and Valery [START_REF] Vismara | Finding maximum common connected subgraphs using clique detection or constraint satisfaction algorithms[END_REF] compare a modified form of the Bron-Kerbosch maximal clique enumeration algorithm [START_REF] Bron | Algorithm 457: Finding all cliques of an undirected graph[END_REF] with a CP optimisation approach. Our experience suggests that a modern maximum clique algorithm could give many orders of magnitude improvement, due to a strong bound function which prunes the search space. Therefore, in section 3, we re-evaluate the clique-based approach using a modern algorithm, and we show that it outperforms CP on labelled graphs, and that it is competitive with CP on unlabelled graphs, contradicting earlier conclusions.

Then, in section 4, we consider the MCCS problem. For the CP approach, we may add a global connectedness constraint to the model. Alternatively, we may use a special branching rule [START_REF] Vismara | Finding maximum common connected subgraphs using clique detection or constraint satisfaction algorithms[END_REF] to grow connected subgraphs only. These two techniques may be combined, and we experimentally show that the best results are in fact obtained when combining them. When solving the MCCS problem with a clique-based approach, neither technique seems directly viable with an association graph encoding. However, we show that it is possible to adapt the combined branching and bounding rule used by modern clique algorithms to maintain connectedness during search. We compare the clique-based approach with the best CP variant for MCCS, and we show that it outperforms CP on labelled graphs, whereas it is outperformed by CP on unlabelled graphs.

Existing Complete Approaches for MCS

There are two main approaches for solving MCS. The first approach (described in section 2.1) is based on CP, whilst the second (described in section 2.2) is based on a reformulation of MCS into a maximum clique problem. Both approaches are described for undirected, unlabelled graphs; their extension to richer graphs is discussed in section 2.3. Other approaches have been tried, mixed integer programming [START_REF] Piva | Polyhedral study of the maximum common induced subgraph problem[END_REF] and heuristics [START_REF] Englert | Efficient heuristics for maximum common substructure search[END_REF]; SAT encodings seem to struggle even for subgraph isomorphism [START_REF] Mccreesh | Heuristics and really hard instances for subgraph isomorphism problems[END_REF].

Constraint Programming Models for MCS

McGregor [START_REF] Mcgregor | Backtrack search algorithms and the maximal common subgraph problem[END_REF] proposed a branch and bound algorithm: each branch of the search tree corresponds to the matching of two vertices, and a bounding function evaluates the number of vertices that still may be matched so that the current branch is pruned as soon as this bound becomes lower than the size of the largest known common subgraph. CP approaches may be viewed as enhancements of this branch and bound algorithm.

Vismara and Valery [START_REF] Vismara | Finding maximum common connected subgraphs using clique detection or constraint satisfaction algorithms[END_REF] introduced the first explicit CP model. Given two graphs G and H, this model associates a variable x v with every vertex v of G, and the domain of this variable contains all vertices of H, plus an additional value ⊥: variable x v is assigned to ⊥ if vertex v is not matched to any vertex of H; otherwise x v is assigned to the vertex of H to which it is matched. Edge constraints are introduced in order to ensure that variable assignments preserve edges and non-edges between matched vertices, i.e. ∀u, v ∈ V(G), (

x u = ⊥)∨(x v = ⊥) ∨ ((u, v) ∈ E(G) ⇔ (x u , x v ) ∈ E(H)). Difference constraints are introduced in order to ensure that each vertex of H is assigned to at most one variable, i.e. ∀u, v ∈ V(G) distinct, (x u = ⊥) ∨ (x v = ⊥) ∨ (x u = x v ).
This CP model was improved by Ndiaye and Solnon [START_REF] Ndiaye | CP models for maximum common subgraph problems[END_REF] by replacing binary difference constraints with a soft global allDifferent constraint which maximizes the number of x u variables that are assigned to values different from ⊥, while ensuring they are all different when they are not assigned to ⊥. They find that the combination "MAC+Bound" (resp. "FC+Bound") obtains the best results on labelled (resp. unlabelled) graphs and outperforms the two previous approaches. The combination "MAC+Bound" maintains arc consistency [START_REF] Sabin | Contradicting conventional wisdom in constraint satisfaction[END_REF] of edge constraints, whereas the combination "FC+Bound" simply performs forwardchecking on these constraints. In both combinations, the "Bound" filtering checks Fig. 2. A maximum common induced subgraph between the two graphs on the left has three vertices-one solution is highlighted. On the right, the association graph encoding: the highlighted clique of size three shows the same solution. The "missing" vertices correspond to assignments which are impossible due to the presence or absence of loops.

whether it is possible to assign distinct values to enough x u variables to surpass the best cost found so far-it is a weaker version of GAC(softAllDiff ) [START_REF] Petit | Specific filtering algorithms for over-constrained problems[END_REF] which computes the maximum number of variables that can be assigned distinct values.

Reformulation of MCS to a Maximum Clique Problem

An alternative approach to MCS is to reduce the problem to finding a maximum clique in an association graph [START_REF] Balas | Finding a maximum clique in an arbitrary graph[END_REF][START_REF] Durand | An efficient algorithm for similarity analysis of molecules[END_REF][START_REF] Levi | A note on the derivation of maximal common subgraphs of two directed or undirected graphs[END_REF][START_REF] Raymond | Maximum common subgraph isomorphism algorithms for the matching of chemical structures[END_REF]]. An association graph (or compatibility graph, or weak modular product) of two graphs G and H is an undirected graph

G H with vertex set V(G H) = {(v, v ) ∈ V(G) × V(H) : (v, v) ∈ E(G) ⇔ (v , v
) ∈ E(H)}-to avoid confusing vertices of G H with vertices of the two original graphs, we call vertices of G H matching nodes, as each vertex (u, u ) of G H denotes the matching of u with u . The edges of G H connect matching nodes which denote compatible assignments, so two matching nodes (u, u ) and (v, v ) are adjacent if u = v and u = v , and if they preserve both edges and non-edges, so (u, v) ∈ E(G) ⇔ (u , v ) ∈ E(H). We illustrate this in Fig. 2.

A clique is a subgraph whose vertices are all pairwise adjacent. A clique is maximal if it is not strictly included in any other clique, and it is maximum if it is a largest clique of a given graph, with respect to the number of vertices. A clique in an association graph corresponds to a set of compatible matchings. Therefore, such a clique corresponds to a common subgraph, and a maximum clique of G H is an MCS of G and H. It follows that any method able to find a maximum clique in a graph can be used to solve the MCS problem.

Note that the association graph is a partial subgraph of the microstructure [START_REF] Jégou | Decomposition of domains based on the micro-structure of finite constraint-satisfaction problems[END_REF] associated with the CP model of Vismara and Valery [START_REF] Vismara | Finding maximum common connected subgraphs using clique detection or constraint satisfaction algorithms[END_REF]: the microstructure has more matching nodes than the association graph because it has a matching node (u, ⊥) for each vertex u of G. Each clique of size |V(G)| in the microstructure corresponds to a common subgraph, the size of which is defined by the number of matching nodes that do not contain ⊥.

Extension to Labelled or Directed Graphs

In some applications, labels may be associated with vertices or edges. We denote λ(u) and λ((u, v)) the label of a vertex u and an edge (u, v), respectively. Where graphs are labelled, any isomorphism f must additionally preserve labels, so we require λ(f (v)) = λ(v) for any vertex v, and λ((f (u), f (v))) = λ((u, v)) for any edge (u, v). This kind of label compatibility constraint is handled in a straightforward way in both CP and clique-based approaches to MCS. For CP, we restrict the domain of every variable x u to vertices with compatible labels, and ensure that edge labels are preserved in edge constraints. For cliquebased approaches, label compatibility is handled through the definition of the association graph, by restricting the set of matching nodes to pairs of vertices with compatible labels, and the set of matching edges to pairs of edges with compatible labels.

The extension of MCS algorithms to directed graphs, where isomorphisms must preserve directed edges, is similarly straightforward.

Labels and directed edges usually simplify the solution process, both for CP and clique-based approaches: vertex labels reduce domain sizes for CP, and the number of matching nodes in association graphs; edge labels tighten edge constraints for CP, and make the association graph sparser for clique-based approaches. It is worth noting that edge constraints do not help CP approaches to do more filtering so long as ⊥ remains in variable domains: every pair of variables (x i , x j ) having ⊥ ∈ D(x j ) is arc consistent, since ⊥ is a support for any value u ∈ D(x i ). However, as soon as ⊥ is removed from domains (i.e. when the number of variables assigned to ⊥ has reached the best known bound on the size of the MCS), maintaining arc consistency may filter values, and then tighter constraints increase the opportunities for filtering.

Re-Evaluating the Clique Model for MCS

Previous experimental evaluations of the association graph model have used either maximal clique enumeration algorithms [START_REF] Koch | Enumerating all connected maximal common subgraphs in two graphs[END_REF][START_REF] Vismara | Finding maximum common connected subgraphs using clique detection or constraint satisfaction algorithms[END_REF] (even when the maximisation problem was being considered), or very simple maximum clique algorithms [START_REF] Bunke | A comparison of algorithms for maximum common subgraph on randomly connected graphs[END_REF][START_REF] Conte | Challenging complexity of maximum common subgraph detection algorithms: A performance analysis of three algorithms on a wide database of graphs[END_REF], and so their conclusions may now be overly pessimistic. Thus we re-evaluate the approach using a modern maximum clique algorithm. Association graphs are dense, even if the input is sparse, so we will using (the single-threaded, bit-parallel version of) the maximum clique solver by McCreesh and Prosser [START_REF] Mccreesh | The shape of the search tree for the maximum clique problem and the implications for parallel branch and bound[END_REF], which implements Prosser's [START_REF] Prosser | Exact algorithms for maximum clique: A computational study[END_REF] "MCSa1" variant of a series of algorithms due to Tomita et al. [START_REF] Tomita | An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments[END_REF][START_REF] Tomita | An efficient branch-and-bound algorithm for finding a maximum clique[END_REF][START_REF] Tomita | A simple and faster branch-and-bound algorithm for finding a maximum clique[END_REF], using a bitset encoding due to San Segundo et al. [START_REF] Segundo | An improved bit parallel exact maximum clique algorithm[END_REF][START_REF] Segundo | An exact bit-parallel algorithm for the maximum clique problem[END_REF]. We compare this to the "FC+Bound" and "MAC+Bound" (simply referred to as FC and MAC) CP implementations of Ndiaye and Solnon [START_REF] Ndiaye | CP models for maximum common subgraph problems[END_REF], using smallest domain first for variable ordering, and a value ordering which prefers vertices of most similar degree. We perform our experiments on machines with Intel Xeon E5-2640 v2 CPUs and 64GBytes RAM; software was compiled using GCC 4.9, and a timeout of one hour was used. We consider a randomly generated database [START_REF] Conte | Challenging complexity of maximum common subgraph detection algorithms: A performance analysis of three algorithms on a wide database of graphs[END_REF][START_REF] Santo | A large database of graphs and its use for benchmarking graph isomorphism algorithms[END_REF] commonly used for benchmarking maximum common subgraph problems. The dataset contains different classes of graphs: randomly connected graphs with different densities; 2D, 3D, and 4D regular and irregular meshes; regular bounded valence graphs, and irregular bounded valence graphs. For each pair of graphs, there are 3 different labellings such that the number of different labels is equal to 33%, 50% or 75% of the number of vertices. In this paper, we report experiments with unlabelled graphs (labels are ignored), and with 33% labellings (the problem becomes very easy with larger numbers of labels). For unlabelled graphs, we select the 27,500 graph pairs where the number of vertices in each graph is no more than 35; for labelled graphs, which we find less computationally challenging, we select all 81,400 graph pairs, to include graphs with up to 100 vertices.

The two plots on the top of Fig. 3 display the cumulative number of instances solved with respect to time. When graphs are labelled, the clique-based approach clearly outperforms either CP model, and MAC has a slight advantage over FC. (Recall that edge labels decrease the density of the association graph, which is typically very beneficial for clique algorithms, but do not help CP until ⊥ is removed from domains.) For unlabelled graphs, the three approaches are broadly comparable, and ultimately FC beats MAC, which beats the clique approach. The bottom row gives a per-instance comparison of the best CP approach with the clique approach: the heatmaps are similar to scatter plots, but due to the large number of instances, we colour each point according to the density of solutions around that point. For labelled graphs, the clique approach comes close to dominating MAC on non-trivial instances (which suggests that there is unlikely to be scope for per-instance algorithm selection here). For unlabelled graphs, there is still a broad correlation between the runtimes; the clique approach rarely wins by more than one order of magnitude, but is sometimes much worse.

A closer inspection of the data suggests that the different randomness models used to generate instances have little effect on the runtimes for either approach. However, the relative size of the solution matters, particularly for the clique algorithm: if the solution is large (i.e. the two input graphs are very similar), the clique approach finds nearly every labelled instance trivial.

Finding Maximum Common Connected Subgraphs

In many applications, the common subgraph must satisfy some additional constraints. This is usually handled in a straightforward way in CP, by branching rules and/or constraint propagation. In clique-based approaches, some constraints may be handled by modifying the definition of the association graph-for example, constraints on pairs of vertices that may be matched are handled by removing inconsistent pairs from V(G H). However, more global constraints cannot be handled by modifying the definition of the association graph.

In this paper, we focus on the connectedness constraint, which occurs in many applications [START_REF] Ehrlich | Maximum common subgraph isomorphism algorithms and their applications in molecular science: a review[END_REF][START_REF] Koch | Enumerating all connected maximal common subgraphs in two graphs[END_REF][START_REF] Raymond | Maximum common subgraph isomorphism algorithms for the matching of chemical structures[END_REF][START_REF] Vismara | Finding maximum common connected subgraphs using clique detection or constraint satisfaction algorithms[END_REF]. Adding the connectedness requirement makes certain special cases solvable in polynomial time, including outerplanar graphs of bounded degree [START_REF] Akutsu | A polynomial-time algorithm for computing the maximum common connected edge subgraph of outerplanar graphs of bounded degree[END_REF] and trees [START_REF] Droschinsky | Faster algorithms for the maximum common subtree isomorphism problem[END_REF], but the general case remains NP-hard. As illustrated in Fig. 1, the MCCS cannot be deduced from the MCS: we need to ensure connectedness during search. In section 4.1, we show that in CP this may be done in two different ways that may be combined, and we show in section 4.2 that the best results are obtained when combining them. In section 4.3, we introduce a new way for ensuring connectedness in a clique-based approach. Finally, we compare CP and our clique-based approach in section 4.4.

For MCCS we consider only undirected graphs (and so we treat directed edges in the inputs as being undirected). For directed graphs, there is more than one notion of connectivity, and it is not clear which should be selected-the approaches we consider extend easily to weakly connected directed graphs, but not to the strongly connected case (for which we know of no applications). We may now only branch on d, and we try d → 4. Now the only remaining variable is unbranchable, and so e = ⊥ is forced, even though 5 remains in its domain and does not violate any constraints.

Ensuring Connectedness in CP

Vismara and Valery [START_REF] Vismara | Finding maximum common connected subgraphs using clique detection or constraint satisfaction algorithms[END_REF] implement the connectedness constraint by using a branching rule which selects the next variable to be assigned. Let A be the set of variables already assigned to values different from ⊥. The next variable to be assigned is chosen within the set of unassigned variables which are the neighbour of at least one vertex of A. When this set is empty, all remaining unassigned variables are assigned to ⊥. We illustrate this in Fig. 4.

A more traditional CP approach would be to express connectedness as a conventional constraint. For example, CP(Graph) [START_REF] Dooms | CP(Graph): Introducing a graph computation domain in constraint programming[END_REF] introduces graph domain variables and enforces connectivity via the reachable constraint, ensuring that there is a path from a specified vertex to a specified set of vertices. One such constraint could be posted for each of the vertices in the graph, encoding the transitive closure of the graph. Brown et al. [START_REF] Brown | Exploring the use of constraint programming for enforcing connectivity during graph generation[END_REF] explored the use of constraint programming in the generation of connected graphs with specified degree sequences. Two constraints were combined: the graphical constraint (a backtrackable implementation of the Havel-Hakimi algorithm), and a connectivity constraint implemented using sets of vertices, where vertex sets A and B are combined when there exists a pair of vertices v ∈ A and w ∈ B and an edge (v, w) ∈ E. Residual degree counts are maintained on components and vertices to enforce graphicality and connectivity. Prosser and Unsworth [START_REF] Prosser | A connectivity constraint using bridges[END_REF] proposed a connectivity constraint for connected graph generation where decision variables are edges (the search process accepts and rejects edges). The constraint employed depth first search to maintain the set of tree edges and back edges, associating path counters on these edges. The counters were then used to detect the existence of cut-edges and protects these by forcing edges.

In all these previous works, the goal was to ensure that a given set of vertices is connected. For MCCS, the problem is slightly different: we have to ensure that the number of connected vertices that may be matched (in both graphs) is greater than the size of the largest common subgraph previously found. Therefore, we introduce a new filtering algorithm to ensure connectedness consistency for MCCS. Let us consider two graphs G and H, and let D be the current domains (we suppose that D(x u ) is a singleton when x u is assigned). Let S and T be the sets of vertices of G and H respectively which may belong to the common subgraph, i.e. S = {u ∈ V(G) : D(x u ) = {⊥}}, and T = ∪ u∈V(G) D(x u ) \ {⊥}. Connectedness consistency ensures that both G[S] and H[T ] are connected graphs.

Connectedness consistency is ensured only once a first variable has been assigned, rather than at the root of search. Let x u be the first assigned variable, and v the value assigned to x u . To ensure connectedness consistency, we perform a traversal of G (resp. H), starting from u (resp. v), and we initialize S (resp. T ) with all visited vertices. Then, for each vertex v ∈ V(G) \ S, we set x v to ⊥, and for each w ∈ V(H) \ T , we remove w from all domains to which it belongs.

During search, each time a variable is assigned to ⊥, we remove the corresponding vertex from S and perform a new traversal of G[S] starting from the initial vertex u. For each vertex w ∈ S that is not visited by the traversal, we remove w from S and assign x w to ⊥. Also, each time a value is removed from a domain so that this value no longer belongs to any domain, we remove it from T , and perform a new traversal of H[T ] starting from the initial vertex v. For each vertex w that is not visited by the traversal, we remove w from T , and remove w from all domains to which it belongs.

Finally, the two approaches for ensuring connectedness (branching and filtering) are complementary and may be combined: at each step of the search, we select the next variable to be assigned within the neighbors of A, and each time a vertex of H is removed from a domain we filter domains to ensure connectedness consistency. In the example in Fig. 4, after the first assignment, filtering alone would remove 5 from every domain but would allow branching on any remaining variable, whilst branching alone would force the next variable to be either b or c but would not immediately eliminate 5 from the domains of d and e.

Experimental Comparison of CP Connectedness Techniques

Fig. 5 compares the three approaches for ensuring connectedness in CP: by branching (Branch), by filtering (Filter), or by combining branching and filtering (Both). We show only results using the best variant for each class-that is, MAC for labelled graphs, and FC for unlabelled graphs (the other results are very similar). On labelled graphs, we see many instances which are solved very quickly by branching but not at all by filtering, and vice versa. However, combining both is rarely much worse than just doing one or the other, and is often much better, even if on average it is slightly slower. On unlabelled graphs, the three variants have rather similar performance.

Ensuring Connectedness in a Clique-Based Approach

It is not possible to determine connectedness from a raw association graph. However, we can take a maximum clique algorithm and mimic the CP branching strategy if we have access to the underlying graphs and can determine the "meaning" of the association graph vertices. Most modern maximum clique algorithms for dense graphs use some variation of greedy graph colouring as a bound-the underlying observation is that each vertex in a clique must be given a different colour in a colouring, so if we can colour a subset of vertices using k colours then a maximum clique in this subset has at most k vertices. However, the colouring is also used as a branching heuristic: vertices are selected in reverse order from their colour classes in turn, starting with the last colour class created. Because of this coupling of branching and the Algorithm 1: An algorithm for a maximum common connected induced subgraph isomorphism via an association graph. return a greedy colouring of the vertices in uncoloured , using the procedure of San Segundo et al. [START_REF] Segundo | An exact bit-parallel algorithm for the maximum clique problem[END_REF] with a static degree order from G and kmin = 0.

1 associationMCCIS :: (Graph G1, Graph G2) → Map 2 begin 3 global incumbent ← ∅ 4 G ← G1 G2 5 search(G, ∅, ∅, V(G))
15 if |solution | > |incumbent| then incumbent ← solution 16 connected ← connected ∪ {w ∈ G : first(w) ∈ N(G, first(v))} 17 remaining ← remaining ∩ N(G, v) 18 if remaining = ∅ then search(G, solution , connected , remaining ) 19 removeLast(colourClasses)
bound (which is important in practice because it mimics a "smallest domain first" branching heuristic if colour classes are viewed as variables, without requiring a new bound to be calculated for every iteration [START_REF] Mccreesh | Reducing the branching in a branch and bound algorithm for the maximum clique problem[END_REF]), if we were to select only a subset of vertices for branching at each stage inside a clique algorithm, we would lose completeness. Thus we must adapt the bound in a non-trivial way to take into account restricted branching.

In Algorithm 1 we present a novel clique-inspired algorithm which finds a maximum common connected induced subgraph via an association graph. If the additional branching restrictions are removed, the core of the algorithm is the same as the "MCSa1" clique algorithm used in the previous section (and we refer the reader to the previously cited works for implementation details on how to use bitsets and other data structures to implement the colouring stage with very low constant factors). The way we extend this algorithm for connectedness differs considerably from that of Koch [START_REF] Koch | Enumerating all connected maximal common subgraphs in two graphs[END_REF] and Vismara and Valery [START_REF] Vismara | Finding maximum common connected subgraphs using clique detection or constraint satisfaction algorithms[END_REF]: these earlier approaches worked by classifying labels in the association graph based upon whether a common vertex is shared, and then constructing cliques with particular edge properties-this is harder to integrate with a strong bound function.

Our algorithm begins by building the association graph (line 4). The main part of the algorithm then works by building up candidate cliques in the solution variable, by recursive calls to the search procedure-starting from the empty set (line 5), each recursive subcall adds one vertex to solution (line 14) in such a way that solution is always a clique which corresponds to a connected common subgraph. The remaining set contains the set of vertices which are adjacent to every vertex in solution, and which have not yet been accepted or rejected (and so initially it contains every vertex). The main loops in the search procedure (lines 10 and 11) have the effect of iterating over each vertex in this set in a particular order-each vertex v is selected in turn, and then a recursive call is made to consider the effects of including v in solution (line 18), followed by the next iteration where v is instead rejected. When v is accepted, we add it to the new solution (line 14), and create a new remaining containing only the vertices in remaining which are adjacent to v (line 17).

The connected set contains the set of matching nodes which correspond to vertices adjacent to an already-accepted vertex in the first input graph-in constraint programming terms, it is the set of assignments which could be made next which maintain connectedness. (Using only one of the two input graphs is sufficient for correctness, and has the advantage that the connectedness set may be determined by a simple lookup into a precomputed array which maps each vertex in the first input graph to a bitset.) At the top of search, this set is empty, and is not used (our first vertex selection is special, and does not care about connectedness). At subsequent depths, we may only accept vertices which are in this set, and if no such vertices remain then we return immediately (line 13). When recursing, we extend connected with the new vertices permitted by our acceptance of the branching v (line 16). Note that we are assuming that inside the main loops, we encounter every vertex in remaining ∩ connected before any vertex in remaining \ connected .

As we proceed, we keep track of the best solution we have found so far-this is stored in the incumbent variable (lines 3 and 15). We use the incumbent, together with a colour bound, to prune portions of the search space which cannot contain a better solution. The colour bound operates as follows: at each entry to the search procedure, we produce a greedy colouring of the vertices in remaining (line 9, discussed further below). This greedy colouring gives us a list of colour classes, each of which is a list of pairwise non-adjacent vertices. The two loops (lines 10 and 11) then iterate over each colour class, from last to first, and then over each vertex in that colour class, again from last to first. (Rather than actually using a list of lists and removing items, this process should be implemented using a pair of immutable flat arrays. This technique is described elsewhere [START_REF] Mccreesh | Reducing the branching in a branch and bound algorithm for the maximum clique problem[END_REF], so we do not discuss it here.) Finally, if at any point the number of remaining colour classes plus the number of vertices currently present in solution is not strictly greater than the size of the incumbent, then we may backtrack immediately (line 12).

Finally, we describe the colouring process-an example is shown in Fig. 6. In conventional clique algorithms, a simple greedy sequential colouring is used (possibly with the help of previous colourings to reduce the computational cost [START_REF] Nikolaev | Reusing the same coloring in the child nodes of the search tree for the maximum clique problem[END_REF], v) The resulting colourClasses variable.

Fig. 6. Solving a maximum common connected problem using an association graph. Suppose we have already mapped vertex a to vertex 1, giving the assignments on the right. Now we have two subgraphs to colour. We need two colours for remaining \ connected , and we place these two colour classes first in the colourClasses variable. We can also colour remaining ∩ connected using two colours, since we cannot simultaneously map c to 2 and d to 3, or vice-versa. Thus colourClasses becomes a list of four colour classes. This tells us that if we hope to extend the current common subgraph by another four vertices, we must pick one assignment from each of the four colour classes (which is not actually possible, so the bound here gives an overestimate). The algorithm thus guesses d → 3 as its next assignment, and if that fails, d → 2, and so on; once b → 3 is reached, the bound decreases by one, and if f → 5 were reached we would stop due to a lack of remaining connected association nodes.

and possibly with shortcuts taken for certain vertices [START_REF] Segundo | Relaxed approximate coloring in exact maximum clique search[END_REF], and possibly followed by a repair step to improve the colouring [START_REF] Tomita | A simple and faster branch-and-bound algorithm for finding a maximum clique[END_REF], or stronger bounding rules based upon MaxSAT inference [START_REF] Li | Combining MaxSAT reasoning and incremental upper bound for the maximum clique problem[END_REF][START_REF] Li | Incremental MaxSAT reasoning to reduce branches in a branch-and-bound algorithm for MaxClique[END_REF][START_REF] Segundo | Infra-chromatic bound for exact maximum clique search[END_REF]). Such colourings will not give us the required property that vertices in remaining ∩ connected come last (so they are selected first by the reverse branching order). Thus we produce two greedy sequential colourings, first considering the non-branching vertices in remaining \ connected , followed by the branching vertices, and concatenate them (line 9). This produces a valid colouring, since we do not merge any colour classes between the two stages, although it may use more colours than a single colouring would.

(What if we did not guarantee that vertices in remaining ∩ connected came last, and just used a conventional colouring with the branching rule? Suppose we had four vertices in remaining, and produced a colouring

[[v 1 , v 2 ], [v 3 ], [v 4 ]],
and suppose that extending solution with {v 1 , v 3 , v 4 } gives an optimal solution. If v 4 was not connected yet, we would not branch on that subtree, and the bound could eliminate branching on v 3 and v 1 , so we would miss the solution. Thus we cannot simply add the branching rule without also adapting the combined bound and ordering heuristic.)

Our colour procedure is a simple greedy sequential colouring. We use the bit-parallel algorithm introduced by San Segundo et al. [START_REF] Segundo | An exact bit-parallel algorithm for the maximum clique problem[END_REF], with the k min parameter set to 0, so we do not describe it here. We use a simple static degree ordering; other initial vertex orderings have been considered on general clique problems [START_REF] Prosser | Exact algorithms for maximum clique: A computational study[END_REF][START_REF] Segundo | Initial sorting of vertices in the maximum clique problem reviewed[END_REF], and it is possible that special properties of the association graph could be exploited in this step (for example, it is always possible to colour the initial association graph using min(|V(G 1 )| , |V(G 2 )|) colours, but with certain vertex orderings, a greedy sequential colouring will sometimes use many more colours).

Experimental Comparison of the CP and Clique Approaches

In Fig. 7 we compare the clique-based approach to the connected problem with the two CP Both approaches. The trend is broadly similar to the unconnected problem: for labelled graphs, the clique-based approach is the clear winner, but for unlabelled graphs the clique approach lags somewhat.

The heatmaps show a more detailed picture. As before, in the unlabelled case, the association approach is almost never more than an order of magnitude better, and is often much worse. In the labelled case, however, there are now many instances where the CP approach does much better than the association approach, despite the association approach remaining much better overall.

Conclusion

Contradicting earlier claims in the literature, we have seen that a modern clique algorithm can perform competitively for maximum common subgraph problems, particularly when edge labels are involved. However, the best approaches for these problems is still far behind the state-of-the-art for subgraph isomorphism, where we can often scale to unlabelled graphs with thousands of vertices.

To start tackling this gap, we believe there is further scope for tailoring clique algorithms for association graphs, including specialised inference, a bound function which is aware that it is working on an association graph, and better initial vertex orderings. Treating the first branch specially may also be beneficial, since the first branch has an unusually large effect on the search space with association graphs [START_REF] Suters | A new approach and faster exact methods for the maximum common subgraph problem[END_REF].

For CP models, using a branching rule for connectedness, rather than simply as an ordering heuristic, is unconventional and does not cleanly fit into the abstractions used by toolkits. However, we saw that combining conventional filtering and the special branching rule was beneficial.

We looked only at single-threaded versions of these algorithms. Maximum clique algorithms have been extended for thread-parallel search [START_REF] Depolli | Exact parallel maximum clique algorithm for general and protein graphs[END_REF][START_REF] Mccreesh | Multi-threading a state-of-the-art maximum clique algorithm[END_REF][START_REF] Segundo | A new exact maximum clique algorithm for large and massive sparse graphs[END_REF] in particular, work stealing strategies designed to eliminate exceptionally hard instances by forcing diversity at the top of search [START_REF] Mccreesh | The shape of the search tree for the maximum clique problem and the implications for parallel branch and bound[END_REF] could be beneficial in eliminating some of the rare cases where the clique algorithm is many orders of magnitude worse than the CP models. On the CP side, the focus for parallelism has been on decomposition [START_REF] Minot | A comparison of decomposition methods for the maximum common subgraph problem[END_REF], rather than fully dynamic work stealing-it would be interesting to compare these approaches.

Finally, we intend to investigate larger and more diverse sets of instances, and other variants of the problem. We have yet to investigate partial or weighted graphs. Nor have we considered strongly connected common subgraphs-this would make the branching approach impossible, and filtering would be much more complicated. From the datasets we selected, there appears to be little scope for per-instance algorithm selection, but other families of input data could lead to a different conclusion.

Fig. 3 .

 3 Fig. 3. The cumulative number of MCS instances solved in under a certain time: on the top, 33% labelled graphs, and then unlabelled and undirected graphs. On the bottom, an instance-by-instance comparison of the clique model with the best CP model, with 33% labelled graphs (with MAC) on the left, and unlabelled and undirected graphs (with FC) on the right.

Fig. 4 .

 4 Fig.4. Suppose we are looking for a connected common subgraph, using the graph on the left for variables and the graph on the right (which has an isolated vertex) for values. We initially consider a → 1. Our restricted branching rule requires us to select either variable b or variable c subsequently, not d or e. We try b → 2, which adds d to the branchable variables, and forces c → ⊥. We may now only branch on d, and we try d → 4. Now the only remaining variable is unbranchable, and so e = ⊥ is forced, even though 5 remains in its domain and does not violate any constraints.

Fig. 5 .

 5 Fig. 5. On top, the cumulative number of MCCS instances solved in under a certain time using different CP techniques, for 33% labelled (left) and unlabelled undirected (right) graphs. Below, instance-by-instance comparisons.

6 return incumbent 7 9 colourClasses

 679 search :: (Graph G, Set solution, Set connected , Set remaining) 8 begin ← concatenate( colour(G, remaining \ connected ), colour(G, remaining ∩ connected )) 10 while length(colourClasses) > 0 do 11 foreach v ∈ last(colourClasses) in reverse order do 12 if |solution| + length(colourClasses) ≤ |incumbent| then return 13 if v / ∈ connected and solution = ∅ then return 14 solution ← solution ∪ {v}

  20 colour :: (Graph G, Set uncoloured ) → List of List of Vertex 21 begin 22

1 (

 1 {b, c, d} × {1 . . . 5} ({b, c, d} × {2, 3}) ∪ ({e, f } × {4, 5}) i) Initial problem ii) Search variables after guessing a → 2) (c, 3) (d, 2) (d, 3) iii) remaining \ connected iv) remaining ∩ connected [[(e, 4), (e, 5)], [(f, 4), (f, 5)], [(b, 2),(b, 3)], [(c, 2), (c, 3), (d, 2), (d, 3)]]

Fig. 7 .

 7 Fig. 7. The cumulative number of connected instances solved in under a certain time: on the top, 33% labelled undirected graphs with up to 100 vertices, and then unlabelled and undirected graphs with up to 35 vertices. On the bottom, an instance-by-instance comparison of the association and CP Both approaches, with 33% labelled graphs on the left, and unlabelled and undirected graphs on the right.

* This work was supported by the Engineering and Physical Sciences Research Council [grant number EP/K503058/1] † This work was supported by the ANR project SoLStiCe (ANR-13-BS02-0002-01)