Diego F Silva

Hélène Papadopoulos

Gustavo E A P A Batista

Daniel P W Ellis

A VIDEO COMPRESSION-BASED APPROACH TO MEASURE MUSIC STRUCTURE SIMILARITY

The choice of the distance measure between time-series representations can be decisive to achieve good classification results in many content-based information retrieval applications. In the field of Music Information Retrieval, two-dimensional representations of the music signal are ubiquitous. Such representations are useful to display patterns of evidence that are not clearly revealed directly in the time domain. Among these representations, self-similarity matrices have become common representations for visualizing the time structure of an audio signal. In the context of organizing recordings, recent work has shown that, given a collection of recordings, it is possible to to group performances of the same musical work based on the pairwise similarity between structural representations of the audio signal. In this work, we introduce the use of the Campana-Keogh distance, a video compression-based measure, to compare musical items based on their structure. Through extensive experiments, we show that the use of this distance measure outperforms the results of previous work using similar approaches but other distance measures. Along with quantitative results, detailed examples are provided to to illustrate the benefits of using the newly proposed distance measure.

INTRODUCTION

Within the last few years, time-series methods and algorithms have attracted the interest of many research communities such as Data Mining and Information Retrieval. Indeed, processes of interest generally change over time, and the study of how these changes occur is a central issue to fully understand such processes.

The choice of the distance measure between time-series representations can be decisive to achieve good classification results in many content-based information retrieval applications. Two distance measures commonly used in time-series analysis are the Euclidean distance (ED) and the Dynamic Time Warping distance (DTW). The DTW Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. c 2013 International Society for Music Information Retrieval. can be understood as an extension of the ED, able to provide nonlinear time scaling invariance, popularly known as warping [START_REF] Batista | A complexity-invariant distance measure for time series[END_REF]. Those simple and well-known distances have been successfully applied to various kinds of problems and have proven to be very hard to beat [START_REF] Ding | Querying and mining of time series data: experimental comparison of representations and distance measures[END_REF]. Some time-series features are not evident in the time domain. There is a large number of research papers that propose methods to explore alternative representations of time-series, such as autocorrelation [START_REF] Bagnall | Transformation based ensembles for time series classification[END_REF] and shapelets [START_REF] Lines | A shapelet transform for time series classification[END_REF], in order to clarify specific features.

In the hot context of organization and retrieval of large collections of music, the notion of similarity between music recordings is of great importance for many applications such as music summarization [START_REF] Cooper | Automatic music summarization via similarity analysis[END_REF] or cover song retrieval [START_REF] Ellis | Identifying "cover songs" with chroma features and dynamic programming beat tracking[END_REF]. In general, the similarity between two recordings is measured by comparing their respective time-series.

Music audio signals are highly structured at different time-scales (bar, phrase-level, sections, etc.) and exhibit repetitive segments, e.g. the so-called ABA sonata form (exposition -development -recapitulation) in classical music. Since their introduction in the domain of audio in 1999 [START_REF] Foote | Visualizing music and audio using self-similarity[END_REF], self-similarity matrices (SSMs) have become common representations for visualizing the time structure of an audio signal in terms of self-similarity and repetitions. Such two-dimensional representations are obtained by computing the pairwise similarity of an audio feature sequence (such as mel-frequency cepstral coefficients [START_REF] Logan | A music similarity function based on signal analysis[END_REF] or chromas [START_REF] Bartsch | Audio thumbnailing of popular music using chroma-based representations[END_REF]), and allow putting in evidence patterns that are not clearly revealed directly in the time domain. For instance, repeated patterns in the audio will appear as diagonal stripes in the SSM. For more details and a review about music structure, we refer the reader to [START_REF] Paulus | Audio-based music structure analysis[END_REF].

Among the various applications based on cross-retrieval tasks, we are interested in this work in the problem of, given a piece of music as a query, to automatically retrieve from a given collection all performances (various interpretations) of the query. We focus on classical music. Two interpretations of the same piece will have a similar musical content, but they may differ in many ways. Besides articulation, phrasing and ornamentation, the global tempo may be different from one performance to another. Local tempo variations such as ritardandi may also exist. Moreover, other factors such as the recording conditions, the loudness or the instrumentation may result in huge dynamical and spectral deviations between the two interpretations. Despite these variations, recent work has shown that it is possible to accurately measure the structural similarity between two recordings by computing the pairwise similarity between their self-similarity matrices, without extracting explicitly the underlying audio structure. In [START_REF] Izumitani | A robust musical audio search method based on diagonal dynamic programming matching of self-similarity matrices[END_REF], this approach is applied to the cover song detection problem. In [START_REF] Martin | Musical structure retrieval by aligning self-similarity matrices[END_REF], this approach is used to build a retrieval system that searches a database for the musical piece that best matches a given symbolic structural query. Of particular interest to the present article are two closely related previous work that show that it is possible robustly group audio performances of the same musical work by using a distance that measures the pairwise similarity between their respective structural representations [START_REF] Bello | Measuring structural similarity in music[END_REF][START_REF] Grosche | Structure-based audio fingerprinting for music retrieval[END_REF].

In order to compare two-dimensional objects directly, it is appropriate to use a distance measure specific to this purpose. An example of that is the Campana-Keogh (CK-1) distance [START_REF] Campana | A compression based distance measure for texture[END_REF], which uses the video compression as the basis for estimating the dissimilarity between two images.

In this paper, we introduce the use of CK-1 to retrieve music recordings based on its structural similarity to an audio query. We show that the use of this distance measure outperforms the results of previous work using similar approaches but other measures.

STRUCTURAL SIMILARITY

As mentioned above, there are at least two studies that have successfully explored the possibility to retrieve music recordings according to their structural similarity to an audio query. In this work, we introduce the use of the CK-1 measure as an efficient distance that can be used to accomplish this task using self-similarity arrays.

This section describes each step of the proposed approach. We consider the following retrieval scenario. Given a query recording and a collection of music recordings that contains various performances of the same piece as the query, along with recordings of different compositions, we aim at retrieving all the performances of the query music piece. To this end, we define the training and retrieve steps by the Algorithm 1 and Algorithm 2, respectively.

Algorithm 1 Training phase

Require: v = A collection of music recordings for i = 1 → length(v) do s ← SSM (v[i])
Stores s as image (bitmap) end for Algorithm 2 Retrieve phase Require: q = A query recording S = The collection of SSM extracted in the training phase

s ← SSM (q) D ← [] for i = 1 → length(S) do d ← d ck1 (s, S[i]) D ← concatenation(D, d) end for L ← sort(D) return L

Feature Extraction

The first step consists in extracting a set of features that provides relevant information about the musical structure. Among the various clues that humans use to determine the structure of a music piece, the harmonic progression is very important [START_REF] Bruderer | The perception of structural boundaries in melody lines of western popular music[END_REF]. Since their introduction in 1999, the Pitch Class Profiles [START_REF] Fujishima | Real-time chord recognition of musical sound: a system using common lisp music[END_REF] or chroma features [START_REF] Wakefield | Mathematical representation of joint time-chroma distribution[END_REF] became common features for describing the harmonic content of music. The chroma features are, in general, 12dimensional vectors that represent the spectral energy of the pitch classes of the chromatic scale. They have been successfully used for various content-based retrieval tasks, especially in previous work on music similarity [START_REF] Bello | Measuring structural similarity in music[END_REF][START_REF] Grosche | Structure-based audio fingerprinting for music retrieval[END_REF].

Following these approaches, we extract a sequence of chroma features, as well as two variants of chroma-like features: the Chroma Energy Normalized Statistics (CENS) and the Chroma DCT-Reduced log Pitch (CRP). CENS features involve an additional temporal smoothing and downsampling step, leading to an increased robustness of the features to local tempo changes. CRP features boost the degree of timbre-invariance. We refer the reader to [START_REF] Müller | Chroma Toolbox: MATLAB implementations for extracting variants of chroma-based audio features[END_REF] for more details. For chromagram computation, we used the Matlab chroma toolbox 1 . All feature vectors are normalized to have unit norm.

Self-Similarity Matrix and Recurrence Plots

In order to analyze the music structure, we used a selfsimilarity matrix (SSM), defined by Equation 1.

S(i, j) = d( x(i), x(j)), i, j ∈ 1 • • • N (1)
where N is the length of the signal, x(i) and x(j) are the feature vectors at positions i and j of the signal, respectively, and d(•, •) is a similarity measure. In this work, we used the cosine distance defined by Equation 2.

d( x(i), x(j)) = < x(i), x(j) > || x(i)|| • || x(j)|| (2)
A well-known variation of the SSM is called Recurrence Plot (RP) [START_REF] Eckmann | Recurrence plots of dynamical systems[END_REF], that introduces three parameters to the SSM: an embedding dimension m, a time delay τ and a closeness threshold ǫ. The general idea is that each vector x is augmented by m observations evenly spaced in τ units of time. Therefore, we end up with a matrix X(i) ∈ ℜ m×k , composed by x(i), x(i + τ ), . . . , x(i + (m -1)τ ). A RP can be formally defined according to Equation 3.

Ri,j = Θ(ǫ -d(X(i) -X(j))), X(i) ∈ ℜ m×k , i, j = 1..N -m (3)
where ǫ is a closeness threshold and Θ is the Heaviside function (i.e. Θ(z) = 0 if z < 0 and Θ(z) = 1 otherwise). For a better understanding of these parameters and the use of closeness threshold, we recommend the reading of [START_REF] Iwanski | Recurrence plots of experimental data: To embed or not to embed?[END_REF]. In short, RP is a thresholded version of the SSM, so that the SSM is transformed into a binary matrix. The general idea of using the parameter ǫ is to discard spurious differences among observations that may hinder the visualization of relevant events. However, we note that setting such a parameter is not an intuitive task, and one frequently has to rely on adhoc techniques to do so. As we will discuss in Section 5, our experiments show that the use of SSM and CK-1 distance can outperform the results obtained in the literature with RP and Normalized Compression Distance.

Compression Distances

The CK-1 distance [START_REF] Campana | A compression based distance measure for texture[END_REF] is based on the concept of Kolmogorov complexity, proposed to quantify the randomness of discrete sequences. The Kolmogorov complexity K(x) of an object x is given by the size of the smallest program capable to output x on a universal computer, such as a Turing machine [START_REF] Li | An introduction to Kolmogorov complexity and its applications[END_REF]. Intuitively, K(x) is the minimal quantity of information required to generate a string x with a program. Similarly, the Kolmogorov conditional complexity K(x|y) is the size of the smallest program to generate the sequence x, given a sequence y as auxiliary input.

These concepts are the basis to a metric called Information Distance, that is universal, in the sense that it subsumes other measures [START_REF] Bennett | Information distance[END_REF]. Although Information Distance has attractive theoretical properties, it is uncomputable in the general case. Therefore, several research papers have proposed approximations to this distance using compression algorithms [START_REF] Keogh | Compression-based data mining of sequential data[END_REF][START_REF] Li | The similarity metric[END_REF].

A widely used distance based on Kolmogorov complexity is the Normalized Compression Distance (NCD) [START_REF] Li | The similarity metric[END_REF], that uses standard compression algorithms to estimate the Kolmogorov complexity. Let C(x) and C(y) be the sizes of sequences x and y after they have been compressed, and C(xy) the compression size of the concatenation of both sequences. The NCD is defined by Equation 4.

N CD(x, y) = C(xy) -min{C(x), C(y)} max{C(x), C(y)} (4)
NCD has shown to provide good similarity estimates for various applications in discrete domain, such as strings of DNA and natural language. NCD typically uses lossless compression algorithms, which are well-suited for discrete data. In short, lossless compression relies in finding exact recurring sequences in data. However, images are composed by real-valued pixels and exact repeating patterns are rare. Another relevant issue is that generally the used compression algorithms work over data sequences and are not able to make use of spatial patterns present in images.

To overcome these limitations, the CK-1 distance makes use of video compression algorithms. More specifically, it uses the MPEG-1 compressor. Such an algorithm explores recurring patterns within a frame and/or between consecutive frames to compress the video. When two consecutive frames are composed of similar images, the inter frame compression step should be able to exploit this structure to produce a smaller file size, which is therefore interpreted as significant similarity. As digital video is an important commercial application, many efforts have been made to achieve high compression rates in video encoding, mak-ing it a good approximation of the Kolmogorov conditional complexity.

In order to calculate a distance between two images, x and y, we can create a fictional video with one frame for each image. Thus, CK-1 is defined by Equation 5.

d ck1 (x, y) = C(x|y) + C(y|x) C(x|x) + C(y|y) -1 (5)
where C(x|y) is the size of a two-frame MPEG-1 video composed by images y and x, in this order.

RELATED WORK

In [START_REF] Bello | Measuring structural similarity in music[END_REF], the author proposes an approach to retrieve music using an intermediate representation of musical structure, without any explicit determination of such structure. The approach uses RP as representation of music structure and NCD as similarity measure between two plots. The paper performs a large-scale evaluation of the proposed approach, including an exploration carried out to find the best parameter configuration, a comparison of front-end features, embedding and recurrence analysis strategies. Supported by such a large experimental evaluation, the author provides evidence of the effectiveness of the approach. Subsequently, a similar method was proposed in [START_REF] Grosche | Structure-based audio fingerprinting for music retrieval[END_REF], using the Euclidean distance. Due to the simplicity of such distance, the proposed method resulted in a more efficient approach. However, temporal variations may cause recurrence shifts and the Euclidean distance is very sensitive to patterns translations. To overcome this limitation, the authors used a technique to smooth the resulting plot. The results, obtained on a dataset slightly different from [START_REF] Bello | Measuring structural similarity in music[END_REF] (with a smaller number of recordings) also proved effective.

EXPERIMENTAL SETUP

We conducted a broad experimental evaluation to assess the effectiveness of the proposed method for music retrieval. In order to evaluate and fairly compare our method to previous work, we used the same data sets, and the same feature extraction parameter variation used in [START_REF] Bello | Measuring structural similarity in music[END_REF]. In addition, we conducted experiments with a technique similar to that presented in [START_REF] Grosche | Structure-based audio fingerprinting for music retrieval[END_REF], applying the binarization and blur methods over the SSM.

Data Sets

In our evaluation phase, we used two datasets of the classical repertoire, kindly provided by the author of [START_REF] Bello | Measuring structural similarity in music[END_REF]:

• The first dataset, referred in this paper as 123tracks, is composed by 123 recordings of 19 different works from the classical and romantic period. Among these tracks, 56 are played on piano and the remaining 67 are symphonic movements. In total there are 59 different conductors in this dataset;

• The second dataset, referred in this paper as Mazurkas, consists in 29192 recordings of 49 Chopin's mazurkas for piano. These were recorded by 135 different pianists.

Parameter Configuration

The CK-1 distance measure is parameter-free, as well as the procedure to create the SSMs. However, CK-1 has a small caveat, it requires that all images must have the same dimensions. Since the dimensions of the SSM are proportional to the recordings durations, which are variable, it is necessary to resize the feature sequences to a fixed dimension d before extracting the SSM. In our experiments, this is achieved by a resampling procedure, resulting in five different feature dimensions, d ∈ {300, 500, 700, 900, 1100}.

For each chroma-based feature, Chroma, CENS and CRP, we used seven different analysis window lengths, resulting in seven feature rates, f ∈ {0.333, 0.5, 1, 1.25, 2.5, 5, 10} features/second.

To facilitate the reading and writing of parameter configurations, we adopted the notation F eat f =F ;d=D , where F eat ∈ {Chroma, CEN S, CRP } and F and D are the values of feature frequency (f ) and the feature vector dimension (d), respectively.

Evaluation

All the experiments in this work were evaluated using mean average precision (MAP). Consider a collection C consisting of M items, and a subset Q ⊂ C containing n different performances of the same music piece. Given a query q i ∈ Q, we build a ranked list by arranging the results in ascending order according to the calculated distance between all the pieces in the collection and the query q i . The Average Precision (AP) is defined by Equation 6.

AP (qi) = 1 n M r=1 P (r)Ω(r) ( 6
)
where r is the rank in the ordered list, and

P (r) = 1 r r i=1 Ω(i) (7)
and Ω(r) is 0 if the work r is relevant and 1 otherwise. Finally, the MAP is defined by the mean of all AP values.

RESULTS

Results on the 123tracks dataset

We start presenting the results obtained with SSM and CK-1 distance on the 123tracks dataset. Tables 1, 2 and 3 report MAP results obtained by the proposed method, varying parameters to calculate the SSMs using Chroma, CENS and CRP, respectively. Non-parametric paired Friedman and Dunnet post-hoc tests were applied to compare the statistical difference between the results. Yellow-shaded cells are statistically equivalent to the best result in each table. Since the parameter settings used in these experiments are the same as those used in [START_REF] Bello | Measuring structural similarity in music[END_REF], the results can be directly compared. The results obtained with the proposed method outperformed the results of [START_REF] Bello | Measuring structural similarity in music[END_REF] for all parameter settings. For instance, the best MAP result obtained with CK-1 and SSM is 0.946 (CEN S f =0.5;d=300 ). The competing method best result is 0.863 (CRP f =10;d=700 ), a significant difference of almost 9%. We must note that CK-1 and SSM have no internal parameters to be searched for. Meanwhile, the recurrence plots used in [START_REF] Bello | Measuring structural similarity in music[END_REF] have three parameters that need to be set. According to the author, after a computational intensive search in the parameters space varying the closeness threshold, the time delay and the embedding dimension, the best result obtained was 0.921. We note that such result is still outperformed by our parameterfree method.

Although the performance difference is too small in order to claim a statistically significant difference with high confidence, there are other aspects that should be considered. The lack of internal parameters makes our method much simpler to use and having its results replicated by the research community. Another relevant issue is that our method is very robust to changes of external parameters. A poor parameter choice in the feature extraction step does not affect the performance significantly. For instance, the worst result obtained by the proposed method is found a total of 2914 recordings. This condition also applies to previous work, therefore does not affect the comparison of results. 0.885, using Chroma f =2.5;d=1100 , while in [START_REF] Bello | Measuring structural similarity in music[END_REF], the worst result is 0.225. Such invariability to the parameter setting is verified by the lack of statistically significant differences among our best result and our remaining results when we vary the external parameters. We also obtained an excellent mean performance of 0.926 over all parameter values.

Further Experiments

We mentioned the fact that the NCD may not be appropriate to compare real value matrices. To prove this fact, we applied the NCD on the SSMs obtained with the best parameter configuration for Chroma, CENS and CRP, using the CK-1 distance. We also applied the NCD on the matrices obtained by setting CRP f =10;d=700 , the configuration that achieved the best result in [START_REF] Bello | Measuring structural similarity in music[END_REF]. The results of this experiment are shown in Table 4, as well as the results obtained using ED in the same configurations. With this simple experiment, it is possible to note that ED and NCD are not appropriate to compare SSM directly. However, in [START_REF] Grosche | Structure-based audio fingerprinting for music retrieval[END_REF], it was shown that the ED can be effectively used to retrieve songs by preprocessing the SSM. We take advantage of such idea to evaluate the use of CK-1 distance in this context.

As we did not have access to the code used in [START_REF] Grosche | Structure-based audio fingerprinting for music retrieval[END_REF], we just simulated similar experiments by applying threshold and blur procedures. In other words, we did not apply path enhancement technique before applying the threshold. Our goal is not to directly compare the results, because we do not even have the same dataset. However, we can compare the use of ED and CK-1 when some preprocessing operations are applied on the SSMs.

In the binarization step (application of a threshold), we used the strategy to consider that k% of the closest points in the SSM represent recurrence. Thus, these points are transformed into black (0) pixels in the resulting RP. The remaining become white [START_REF] Bagnall | Transformation based ensembles for time series classification[END_REF]. To evaluate different scenarios, we used three different values for the threshold: k ∈ {10, 25, 50}. Furthermore, we used a two-dimensional circular averaging filter (Pillbox) to blur the image, using five different filter sizes: l ∈ {1, 5, 10, 20, 30}. For the sake of space, we do not present all the results of our experiments. Briefly, the best results obtained by the use of distance ED in this context were better than those obtained in [START_REF] Bello | Measuring structural similarity in music[END_REF], which used the RP-NCD, in most scenarios. However, the results obtained by CK-1 distance in the same context were better than ED in all scenarios. The best results obtained for each distance and each feature are presented in Table 5.

Results on Mazurkas Dataset

We performed experiments on the Mazurkas dataset to validate the results obtained in the previous experiments. We first chose the parameter configuration CEN S f =0.5;d=300 since it obtained the best classification performance in the 123tracks dataset. However, our method achieved a MAP of 0.611, which we considered unsatisfactory. A more detailed analysis of the SSMs showed that in many cases the matrices were not able to clearly represent the recording structure. This was due to the fact that the cosine distance, used to extract matrices, resulted in short distances in many cases. Thus, the figure generated by such distances contains very dark colors when applied to a color scale between 0 and 1.

After analyzing the recordings, we can conclude that the distances with small values can be directly related to the frequency in which the features were extracted. A low feature rate corresponds to a large analysis window, resulting in mixing several structurally distinct segments of music. Since many pieces in the dataset have a short duration and numerous structural variations of short duration, their structure can only be accurately analyzed with higher frequencies of feature extraction. To prove this fact, we performed the same experiment using CEN S f =1;d=300 , achieving M AP = 0.760, without the need of normalizing the SSM, similar to the best result achieved in [START_REF] Bello | Measuring structural similarity in music[END_REF], M AP = 0.767. The Figure 2 shows an example of the difference between different feature extraction rates. Finally, we used the same dataset to test the configuration CRP f =1.25;d=500 after the application of a threshold (k = 25) and a blur filter (l = 30). This test was performed since this configuration had the best result on the 123tracks dataset. The effectiveness of the proposed method on this setting was proved in this experiment. When analyzing the structural similarity in this configuration using ED, we reach the result of M AP = 0.652. However, when we used the CK-1 measure, we obtained M AP = 0.795. This result is statistically superior to the results obtained by competing methods in the same dataset.

CONCLUSION

This paper proposes a simple and parameter-free approach to recover music by its structural similarity. The only parameters involved in our method are those required in the feature extraction step. We also show that our method is robust to a poor choice of these parameters, provided the parameter choices achieve meaningful SSM.

Through a wide experimental evaluation, we show that our method is superior to the techniques presented in previous work. Furthermore, CK-1 outperforms other distances regardless of pre-processing steps are performed in the signal or structural representation.

We believe that the contribution of this paper is not limited to the presentation of a new method for retrieving music by structural similarity. We hope this work will encourage the scientific community to analyze signals from various domains using visual representations and imagefriendly distance measures.

  Figure 1 shows different representations of the same recording of the Chopin's Prelude Op.28 No.4. Plot (a) represents the SSM, plot (b) represents the RP (using 25% of the points) and plots (c & d) the result of applying a blur filter on the RP with four different sizes.

Figure 1 .

 1 Figure 1. Four different representations of the same recording: (a) self-similarity matrix; (b) recurrence plot; (c) RP after application of a blur filter with size l = 30.

Figure 2 .

 2 Figure 2. Self-similarity matrices of the same piece, but different feature rates: (a) 0.5f /s; (b) 1f /s;

Table 1 .

 1 MAP results obtained with Chroma features

	Feature		Feature dimension (d)
	rate (f)	300	500	700	900	1100
	10	0.914	0.915	0.904	0.900 0.897
	5	0.918	0.910	0.902	0.894 0.896
	2.5	0.930	0.922	0.898 0.890 0.885
	1.25	0.927	0.923	0.903 0.893 0.887
	1	0.929	0.928	0.913 0.903 0.889
	0.5	0.930	0.928	0.917 0.907 0.890
	0.33	0.930	0.927	0.918	0.907 0.888

Table 2 .

 2 MAP results obtained with CENS features

	Feature		Feature dimension (d)
	rate (f)	300	500	700	900	1100
	10	0.926	0.920	0.914	0.911	0.908
	5	0.943	0.929	0.923	0.917	0.915
	2.5	0.946	0.945	0.941	0.935	0.930
	1.25	0.943	0.943	0.937	0.933	0.930
	1	0.944	0.944	0.941	0.938	0.936
	0.5	0.946	0.944	0.940	0.940	0.942
	0.33	0.942	0.940	0.934 0.932 0.932

Table 3 .

 3 MAP results obtained with CRP features

	Feature		Feature dimension (d)
	rate (f)	300	500	700	900	1100
	10	0.930	0.936	0.937	0.932	0.935
	5	0.933	0.933	0.937	0.934	0.935
	2.5	0.933	0.940	0.936	0.935	0.934
	1.25	0.935	0.941	0.935	0.936	0.936
	1	0.933	0.936	0.932	0.934	0.937
	0.5	0.930	0.937	0.929	0.933	0.932
	0.33	0.929	0.937	0.929	0,932	0.931

Table 4 .

 4 Results obtained by applying NCD and ED on the SSM in some configurations.

	Configuration	NCD	ED
	Chroma f =2.5;d=300	0.322 0.279
	CEN S f =0.5;d=300	0.382 0.313
	CRP f =1.25;d=500	0.276 0.257
	CRP f =10;d=700	0.271 0.262

Table 5 .

 5 Results obtained after applying a threshold and a blurring effect in the recurrence plots. The value k is the percentage of black points and l is the size of the blur filter. The symbol * indicates where CK-1 is statistically outperformed ED in the same parameter configuration.

		k (%) l	Distance	MAP
	Chroma f =2.5;d=300	50 10	CK-1 ED 20 CK-1 1 ED	0.941 * 0.816 0.905 0.872
	CEN S f =0.5;d=300	25 25	5 1	CK-1 ED CK-1 ED	0.924 * 0.829 0.919 0.910
	CRP f =1.25;d=500	25 10	30 CK-1 ED 30 CK-1 ED	0.958 * 0.893 0.953 0.941

http://www.mpi-inf.mpg.de/resources/MIR/chromatoolbox/

This is the number of recordings presented in the official description of the dataset. However, there are pieces that are not available, and we

ACKNOWLEDGMENTS

This work was supported by grant #2012/18985-0, São Paulo Research Foundation (FAPESP), and grant IIS-1117015, National Science Foundation (NSF).


Matthieu Mercier

De Luzon

modéliser la marée interne

La marée interne est issue de l'interaction d'un écoulement oscillant (la marée barotrope) avec une topographie dans un fluide stratifié. Différents modèles décrivent les mécanismes mis en jeu et des outils numériques sont disponibles pour prédire les ondes internes générées et les comparer aux observations. Cependant des limitations existent lorsque l'on considère des effets tridimensionnels ou non-linéaires.

Le détroit de Luçon (The Luzon Strait), situé entre Taïwan et les Philippines, est un parfait exemple de génération d'ondes internes non linéaires par une topographie complexe. Des observations in situ et via imagerie satellite ont mis en évidence que des ondes solitaires s'étendant sur plusieurs centaines de kilomètres se propagent depuis le détroit vers la mer de Chine. Ces ondes solitaires sont les plus fortes observées jusqu'à aujourd'hui, avec des déplacements verticaux allant jusqu'à 200m et des vitesses horizontales de l'ordre du mètre par seconde. De nombreuses études (océanographiques, numériques et théoriques) cherchent à identifier l'origine de ces ondes, et l'influence des différents facteurs tels que la stratification, le forçage de la marée, etc. [2] Afin de compléter les études précédentes , nous avons réalisé une expérience à grande échelle à la plateforme Coriolis, table tournante de 13m de diamètre, la plus grande au monde. Nous avons reproduit le forçage de la marée, générant un écoulement oscillant sur une maquette réaliste du détroit, avec une stratification similaire aux observations océaniques. La mise à l'échelle du laboratoire a été réalisée tout en préservant le régime dynamique associé au problème océanique (nombre de Froude, criticalité, excursion de la marée, etc.). Je présenterai les principaux résultats obtenus en lien avec les observations existantes.

Figure 1 :

 1 Figure 1 : Gauche :Image satellite MODIS illustrant deux trains d'ondes solitaires s'éloignant du détroit de Luzon (RC Lien, cruise plan 2011). Droite :Observation expérimentale des ondes internes rayonnées


Pascal Billand
email: pascal.billand@univ-st-etienne.fr

Christophe Bravard
email: christophe.bravard@univ-st-etienne.fr

Subhadip Chakrabarti
email: s.chakrabarti@qub.ac.uk

Sudipta Sarangi
email: sarangi@lsu.edu

A Note on Networks of Collaboration in Multi-market Oligopolies

Keywords: C70, L13, L20, D85 R&D Collaborations, Network Formation, Multi-market Oligopolies

In this note, we extend the Goyal and Joshi's model of network of collaboration in oligopoly to multi-market situations. We examine the incentive of firms to form links and the architectures of the resulting equilibrium networks in this setting. We also present some results on efficient networks.

Introduction

Research collaborations among firms take a variety of forms, such as joint ventures, technology sharing or joint R&D [START_REF] Hagedoorn | Understanding the Cross-level Embeddedness of Inter-firm Partnership Formation[END_REF]. These collaborations are often bilateral and non exclusive, and form a network of collaborative links between firms.

By forming collaborative links, firms alter the competitive positions of competitors and influence market structure and performance. It is then important to develop models of network formation between firms in order to predict the architectures of the networks that should emerge and examine to what extent these networks are socially efficient. Goyal and Joshi (GJ, 2003) propose a model of network formation which addresses these questions for situations in which firms compete on a oligopoly market. Collaborative links between firms lower marginal costs. However these links are costly and the costs are fixed and uniform across links. [START_REF] Westbrock | Natural Concentration in Industrial Research Collaboration[END_REF] investigates efficient networks in this setting albeit with differentiated products. Certain architectures emerge as candidates for stable and efficient networks. In the case that has maximum relevance for us, namely quantity competition in a homogeneous oligopoly with small costs of link formation, the complete network is both stable and efficient. In more general settings, stars, interlinked stars and dominant group architectures emerges as candidates for stable and efficient networks. Now competition between firms in few markets is a prominent feature of modern economies. In a seminal paper, [START_REF] Bulow | Multimarket Oligopoly: Strategic Substitutes and Complements[END_REF] show how the introduction of multimarket competition can produce quite unexpected findings compare to standard results in industrial organization. We can then ask what happens to equilibrium and efficient networks when we introduce multimarket competition in the GJ's model of formation of collaborative networks. This paper gives a first insight at this question. We assume for purposes of simplicity heterogeneous product markets, with linear demand curves and quadratic cost functions, where multimarket competitors can form quality products enhancing collaborative links on one market. 1 Our paper is different from the two earlier papers that follows the framework introduced by Bloch (1995) in the sense that links reduce marginal costs.

We follow the line of reasoning laid down by [START_REF] Chakrabarti | An Analysis of Advertising Wars[END_REF]. In that paper, firm can make costly investments that increase its demand and reduce the demand of other firms. These investments are interpreted as negative advertising. Here, investments increase the demand of both firms making the investment and interpreted as collaborative R&D activity. These investments take the form of costly links where the link increases the demand of both firms forming the link by a fixed amount. We restrict ourselves to quantity competition and use a similar demand function to that of [START_REF] Singh | Price and Quantity Competition in a Differentiated Duopoly[END_REF], [START_REF] Westbrock | Natural Concentration in Industrial Research Collaboration[END_REF] and [START_REF] Chakrabarti | An Analysis of Advertising Wars[END_REF].

Our findings concerning equilibrium networks are quite similar to those of GJ (2003), that is equilibrium networks have still a dominant group architecture, i.e. a group of firms are linked to each other while other firms have no links at all. We show that this result follows from the fact that our collaborative multimarket game qualifies as playing the field games [START_REF] Goyal | Unequal Connections[END_REF], with payoff function satisfying convexity in own links as well as the strategic substitutes property with regard to quantities. However, using [START_REF] Bulow | Multimarket Oligopoly: Strategic Substitutes and Complements[END_REF] analysis, we show that contrary to the model of GJ (2003) there exist situations where competitors do not form collaborative links in order to increase the 1 Considering that firms can form links on one market only is admittedly restrictive. However, it allows us to deal with situations where products innovation is a strategic issue for only one market, and there is little to gain by forming collaborative links that will increase the quality of the product on the second market. Besides this restrictive assumption simplifies the analysis and allows us to give a first insight on the impact of multi-market competition on the collaborative networks.

3

quality of their products even if these links have no costs. This result follows from the fact that there are joint diseconomies across markets and goods produced by competing firms are strategic substitutes. It illustrates how the intermarket effect play a key role in the incentive of firms to collaborate.

With regard to efficient networks, though we cannot arrive at a precise characterization of these networks, we can derive some interesting properties of such networks and restrict the set of networks that are efficient into a small group. More precisely, we show that efficient networks belong to the class of Nested-Split Graphs. 2 These architectures have interesting features. In particular, they consist of only one component, that is efficient networks are such that firms which have formed links are all directly or indirectly linked. Moreover the diameter of the non-singleton component is very low since firms are at most at distance 2 from each other. Besides it turns out that equilibrium and efficient networks do not coincide.

The rest of the paper proceeds as follows. Section 2 introduces the model and discusses the notation and terminology. Section 3 examines equilibrium networks, while Sections 4 deals with efficient networks. Section 5 concludes.

Framework

The Multi-market Cournot Model

Suppose there are n firms indexed by i = 1, 2, . . . , n (where n ≥ 3) that compete à la Cournot in two inter-related markets 1 and 2. The set of all firms is denoted by N .

We denote by q i and Q i the quantities sold by firm i on markets 1 and 2 respectively, and by p i and P i the prices of firm i's products on these markets. Focusing on the most interesting case, we assume that competitors' products are strategic substitutes and there are diseconomies of scope across markets. 3 . More specifically, demand in markets 1 and 2 for firm i are respectively given by

p i = α i -q i - j =i q j ; P i = β i -Q i - j =i Q j . (1)
The cost function of a firm i is given by

C i (q i , Q i ) = 1 2 (q i + Q i ) 2 . ( 2
)
Since ∂ 2 C i (q i ,Q i ) ∂q i ∂Q i = 2(q i + Q i ) > 0,
there are diseconomies of costs across markets.

The profits of each firm i ∈ N can be written as:

π i =   α i -q i - j =i q j   • q i +   β i -Q i - j =i Q j   • Q i - 1 2 (q i + Q i ) 2 . (3)

Quality Improving Links and Collaborative Networks

Assume that firms can improve the quality of their products via collaborative links in only market 1. More specifically, we suppose that for each firm i ∈ N we have

α i (g) = γ 0 + γ • η i (g) (4)
where η i (g) is the number of links formed by firm i in the network g. Link formation is costly and the cost of forming each link is given by c ≥ 0 and is incurred by both firms forming the link.

3 Formally, let πi(q1, ..., qi, ...qn, Q1, ..., Qi, ..Qn) be the profits function of firm i. Competitors' products are strategic substitutes on market 1 whenever ∂ 2 π i ∂q i ∂q j < 0. Let Ci(qi, Qi) be the cost function of a firm i. There are diseconomies (economies) of scope across markets whenever

∂ 2 C i (q i ,Q i ) ∂q i ∂Q i > (<) 0
simplicity, we denote the link between i and j (where i = j) by ij. So ij ∈ g indicates i and j are linked in the network g. A network g is a formal descriptions of the pair-wise collaborative links that exist between firms. Let G denote the set of all networks. We let g + ij denote the network formed by adding the link ij to the network g, g -ij denote the network formed by deleting the link ij from the network g.

A firm i's neighborhood N i (g) is given by {j ∈ N \{i}|ij ∈ g}. We define as L i (g) = {ij ∈ g | j ∈ N i (g)} ⊂ g the set of links in which firm i is involved. Let λ(g) = 1 2 i∈N η i (g)
be the total number of links in a network g. For any h ⊂ g, let g -h denotes the network formed by deleting the set of links h from the network g. Similarly, for h ⊂ g N \g, g + h denotes the network formed by adding the links set h to the network g. Moreover we define g -i as the resulting network once we remove all firm i's links from the network g.

A path in g connecting i and j is a set of distinct firms {i 1 , i 2 , . . . , i p } ⊂ N with p ≥ 2 such that i 1 = i, i p = j, and {i 1 i 2 , i 2 i 3 , . . . , i p-1 i p } ⊂ g. We say i and j are connected to each other if a path exists between them and they are disconnected otherwise. Given a network g, we define a component as a set C(g) ⊂ N such that for all i, j ∈ C(g) there exists a path between i and j and there does not exist a path between a player i ∈ C(g) and a player j ∈ C(g). A component C(g) is complete if for all distinct i, j ∈ C(g), ij ∈ g. Firms who are not connected in the network g are named singletons. We define three network architectures that play a role in this paper. The network g N in which all firms are linked with each other is referred to as the complete network and the network g 0 in which all firms are singletons is referred to as the empty network. The dominant group architecture g k is characterized by one complete non-singleton component with

|N k | ≥ 2 and n -|N k | singletons.
A network is a strongly pair-wise stable network4 if (a) for all i ∈ N and h ⊂ L i (g), π i (g) ≥ π i (g -h), and

(b) for all i ∈ N , j ∈ N , and ij / ∈ g, if π i (g + ij) > π i (g) then π j (g + ij) < π j (g).
For any network g, and h ⊂ g N \g, we denote the variation of benefit from links formation by ∆π i (g, h)

= π i (g + h) -π i (g).
Next, we define efficient networks. Let CS be consumers' surplus function and Π be firms' aggregate profits function. The welfare function W is given by:

W (g) = CS(g) + Π(g)
A network g is an efficient network if g maximizes the welfare function, that is W (g) ≥ W (g ) for all g = g. We say that g is efficient for firms (consumers) if it maximizes the aggregate profits of firms (surplus of consumers). For any network g, and h ⊂ g N \g,

we denote the variation in welfare and total profits resulting from link formation by ∆W (g, h) = W (g + h) -W (g) and ∆Π(g, h) = Π(g + h) -Π(g) respectively.

Characterization of Equilibrium Networks

Although the payoff functions are quite complicated, this game has features similar to the game analyzed by [START_REF] Goyal | Unequal Connections[END_REF]. Hence we will invoke their results here.

Definition 1 A network game is called playing the field game if the payoff function of firm i is a function of her degree, η i (g), and the total number of links in g -i , λ (g -i ):

π i (g) = Φ (η i (g) , λ (g -i ))
.

Definition 2

The payoff function Φ is convex in its own links if the marginal returns

Φ (k + 1, l) -Φ (k, l) is strictly increasing in k.
Definition 3 Suppose l > l. The payoff function Φ satisfies the strategic substitutes

property if Φ (k + 1, l ) -Φ (k, l ) < Φ (k + 1, l) -Φ (k, l).
It is easy to check from the equilibrium profits function, Φ(k, l), given in Appendix 6.1. that the collaborative multimarket game qualifies as playing the field game. Furthermore, we show that this function satisfies convexity in own links as well as the strategic substitutes property. Indeed, define

∆Φ(k, l) = Φ (k + 1, l) -Φ (k, l)
. The equilibrium profits function satisfies convexity in own links, since we have

∆Φ(k + 1, l) -∆Φ(k, l) = (11n 4 + 44n 3 -6n 2 -100n + 83)γ 2 9(n + 3) 2 (n + 1) 2 > 0
Likewise, the equilibrium profits function satisfies the strategic substitutes property, since we have

∆Φ(k, l + 1) -∆Φ(k, l) = -2γ 2 (11n 3 + 62n 2 + 91n + 4) (n + 3) 2 (n + 1) 2 ) < 0.
Therefore, we get from GJ (2006, p.327, Proposition 3.1) the following corollary.

Corollary 1 The strongly pair-wise stable network is either complete or empty or has a dominant group architecture.

Remark 1. We can check that the empty network can be a strongly pair-wise stable network, even when costs of forming links are null. For instance, suppose n = 6, γ 0 = 100, γ = 0.05, β i = 400 for all i ∈ N , and f = 0. We have ∆Φ(0, 0) = -0.09 < 0, so no firm has an incentive to form a link in the empty network, and the latter is a strongly pair-wise stable network. It follows that in some situations firms will not form collaborative links in order to increase the quality of their products even if these links have no costs.

The intuition behind this fact, inspired from [START_REF] Bulow | Multimarket Oligopoly: Strategic Substitutes and Complements[END_REF], is as follows: The formation of a link by firms i and j in market 1 enhances the quality of their product in this market and leads these firms to produce more for this market. Due to joint diseconomies across markets this reduces marginal profitability for firms i and j in market 2 and induces these firms to lower their quantities on this market. Because of strategic substitutability, rival firms will increase their quantities on market 2 and this induces a loss in market 2, and possibly an overall loss, for firms i and j. Note that in the one-market Cournot model of GJ ( 2003), the dominant group architecture can emerge only if there are substantial link formation costs.

Remark 2. As in GJ we find that the impact of the costs of link formation on the size of the non-singleton component is non-monotonic: for low costs, the complete network is uniquely stable, for moderate costs only networks with relatively large dominant groups are stable, for high costs, only medium size non-singleton components are stable (small and large groups are not sustainable), while for very high costs, the empty network is uniquely stable. The example below illustrates the fact that for high costs, only medium size non-singleton components are stable.

Example 1 Let n = 50, γ 0 = 749, γ = 0.45, β i = 400, for all i ∈ N . Straightforward computations show that for f = 9.7, only the empty network and dominant-group networks, g k , such that k is at least equal to 7 and at most equal to 21 can be strongly pair-wise stable.

Remark 3. In the case with Economies of scope across markets, there is no tension across the markets anymore. The formation of a link by firms i and j in market 1 enables both firms to produce larger quantities on both markets. Thus profits of both firms increase in equilibrium. Clearly, under zero link costs, the complete network is the only equilibrium network, i.e. we obtain the same result as in Goyal and Joshi model ( 2003) where firms compete only on one market.

Characterization of Efficient Networks

Efficient networks are hard to characterize and we provide a partial characterization for n ≥ 4 firms. 5 .The first lemma present a result on the consumers' surplus function which simplifies the characterization of efficient networks (the proof is in appendix).

Lemma 1 For any network g, (i) the consumers' surplus function only depends on the total number of collaborative links formed by firms, and (ii) this surplus function is convex in the total number of links formed.

Proof The proof of (i) and (ii) is straightforward since the expression of consumers' surplus function is given by

CS(g) = (n 2 + 4n + 5)( ᾱ2 + β2 ) -4(n + 2) ᾱ β (3 + 4n + n 2 ) 2 ,
where ᾱ = nγ 0 + 2γλ(g) > 0, and β = n i=1 β i > 0.

The following lemma considers a network g in which links ik and im do not exist, while firm m has formed at least as many links as firm k in g. This lemma allows us to state that if total profits of firms increase when the link ik is added to the network g, then total profits also increases when the link im is adding to the network g + ik and this increase is of a greater magnitude (the proof of this lemma is in appendix).

Lemma 2 For any network g and firms i, k, m ∈ N such that ik, im / ∈ g and η m (g) ≥ η k (g), we have ∆Π(g + ik, im) > ∆Π(g, ik)

From Lemmas 1 and 2 we obtain the following lemma (the proof is in appendix).

Lemma 3 For any network g and firm i such that ik, im / ∈ g and η m (g) ≥ η k (g), we

have ∆W (g + ik, im) > ∆W (g, ik).

The proposition that follows from lemma 3 gives an important characteristic of efficient networks.

Proposition 1 Efficient networks g belong to the class of Nested-Split Graphs (NSG).

Proof First we show that in an efficient network g, the following condition is satisfied (C1): if ij ∈ g and ik / ∈ g, then η j (g) > η k (g). Let ∆W (g, ij) be the marginal change in welfare when the link ij is added to the network g. Suppose there exists an efficient network g and ij ∈ g and ik / ∈ g. Then, ∆W (g -ij, ij) ≥ 0. Suppose, towards a contradiction, η k (g) ≥ η j (g). This implies by Lemma 3 that ∆W (g, ik) > 0 contradicting that g is efficient. Hence, for all k such that ik / ∈ g, η k (g) < η j (g).

Second, we show that if a network g satisfies the condition (C1), then g belongs to the class of NSG. Belhaj, Bervoets, and Deroïan (2013, p.9) define a NGS as a graph which satisfies the following condition (C2): if ij ∈ g and η k (g) ≥ η j (g), then ik ∈ g.

Conditions (C1) and (C2) are clearly equivalent. It follows that if g is an efficient network, then g belongs to the class of NSG.

There is an interesting effect behind Condition (C1). Let a network g and firms i, k, m ∈ N such that ik ∈ g and im / ∈ g. Suppose that we substitute the link im to the link ik in g. The total number of links is the same in network g as in network

g -ik + im. It follows from Lemma 1 (i) that the consumer surplus does not change when we substitute the link im to the link ik in the network g. Therefore consumers' surplus plays no role in the result of Proposition 1. Moreover, since the total number of links is the same in the network g as in the network g -ik + im, the total costs of forming links also plays no role in the result of Proposition 1. Therefore, the result of Proposition 1 lies only on the total profits (gross of the costs of forming links) of firms. This Proposition highlights the fact that if firms could act in a cooperative way at the links formation stage of the multi-market oligopoly game, then they would have an incentive to act toward some kind of concentration (of increase of the Gini coefficient) of links distribution among them: it would be better for firms (and for social welfare) that a firm poorly linked firm k gives up to a collaboration it has established with a firm i in network g and let firm i set up an additional collaboration with a firm m which has already set up more collaborations that firm k in g.

Remark 3. Since efficient networks belong to the class of NGS, it follows that if a network g is an efficient network, then g has two properties (i) g contains at most one component. (ii) The geodesic distance between any two connected firms in g is at most 2. This means that in an efficient network all firms which have formed links are connected, and connected firms are very close one from each other.

Remark 4. It is worth noting that the architectures of strongly pair-wise stable and efficient networks share some similarities. First, in both cases all firms that have formed collaborative links are directly or indirectly linked together. Moreover, in both cases too the maximal distance between these firms is very low: one for strongly pair-wise stable networks, two for efficient networks. However as illustrated by the following example, for some parameters values, architectures of strongly pair-wise stable and efficient networks are very different.

Example 2 Let n = 50, γ 0 = 749, γ = 0.45, β i = 400, for all i ∈ N . We know from Example 1 that for f = 9.7, only the empty network and dominant-group networks, g k , such that k is at least equal to 7 and at most equal to 21 can be strongly pair-wise stable.

Straightforward computations show that these architectures are less efficient than the complete network.

Conclusion

In this paper, our aim was to ask what happens to equilibrium and efficient networks when we introduce multimarket competition in the GJ's model of formation of collaborative networks. We have shown that although equilibrium architectures are of the same type as in GJ, a complete network needs not materialize in equilibrium when costs of links are null as it is the case in GJ. With regard to efficiency, we have shown that efficient networks belong to the class of NGS. Therefore, efficient networks have the interesting features of this class of graphs. In particular, they consist of only one component, that is efficient networks are such that firms which have formed links are all directly or indirectly linked. Moreover the diameter of the non-singleton component is very low since firms are at most at distance 2 from each other.

We now briefly discuss some issues that could be explored in future work. First, we need to examine the case where firms can form links on both markets. This will allow us to check the robustness of our results and to know in particular whether other types of architectures can emerge as strongly pair-wise stable networks. Second, it will be interesting to adapt the model of Goyal and Moraga-Gonzales (2001), and to introduce in our model the possibility for each firm to unilaterally choose a level of effort in R&D in order to increase the quality of its product, given the collaboration network. This will allow us to us to examine the impact of bilateral R&D collaboration on the level of R&D activities.

6 Appendix

Equilibrium profits in Multi-market equilibrium

Differentiating (3) with respect to q i and Q i for each firm i ∈ N , we obtain the equilibrium quantities of each firm i:

q * i = (2n 2 + 6n + 1)α i -(n 2 + 3n -1)β i -(2n + 5) j =i α j + (n + 4) j =i β j 3(3 + 4n + n 2 ) ; Q * i = (2n 2 + 6n + 1)β i -(n 2 + 3n -1)α i -(2n + 5) j =i β j + (n + 4) j =i α j 3(3 + 4n + n 2 )
In order to ensure that each firm produces strictly positive quantities in equilibrium, we will assume that the parameters γ 0 , γ, {β i } are such that for each firm i ∈ N we have both :

γ 0 > γ(n -1)(n -2)(2n + 5) + (n 2 + 3n -1)β i -(n + 4) i =j β j 3(n + 2) , γ 0 > -γ(n -1)(n 2 + 3n -1) + (2n 2 + 6n + 1)β i -(2n + 5) i =j β j 3 14
.

We obtain the second stage equilibrium profits by replacing q i and Q i by their equilibrium values, q * i and Q * i , in [START_REF] Bernheim | Multimarket Contact and Collusive Behavior[END_REF]. Moreover, by replacing in the equilibrium profits α i by γ 0 -γη i and j =i α j by nγ 0 + j =i η j -η i 6 , the equilibrium profits function is given by π i (g) = Φ (η i (g) , λ (g -i )).

Proof of Lemma 1, Lemma 2 and Lemma 3

Proof of Lemma 1. Consider the total consumer surplus of agents in both markets.

It is given by

CS = i (α i -p * i ) q * i + i (β i -P * i ) Q * i where p * i = α i - n i=1 q * i and P * i = β i - n i=1 Q * denotes prices in both markets at equilibrium. Let q = n i=1 q i , Q = n i=1 Q i , α = n i=1 α i , and β = n i=1 β i . We have, CS = i (α i -p * i ) q * i + i (β i -P * i ) Q * i = i (q * ) q * i + i Q * Q * i = (q * ) 2 + Q * 2 = (n + 2)α -β 3 + 4n + n 2 2 + (n + 2)β -α 3 + 4n + n 2 2 = (n 2 + 4n + 5) α 2 + β 2 -4(n + 2)αβ (3 + 4n + n 2 ) 2 .
The proof of (i) follows directly the expression of the consumers' surplus function given above. As for the proof of (ii), consider any two arbitrary links ij and kl where 6 we delete ηi in order to obtain the number of links formed in the network g-i 15 neither link belongs to the network. We have, ∆CS(g + ij, kl) -∆CS(g, ij) = 8γ 2 (n 2 + 4n + 5)

(3 + 4n + n 2 ) 2 > 0.

It follows that the consumers' surplus function is convex in the total number of links formed.

Proof of Lemma 2. Suppose a network g and firms i, k, m ∈ N such that ik, im / ∈ g and η m (g) ≥ η k (g). The aggregate profit effect of link formation between i and k is given by ∆Π(g, ik) = κ α i + α k -τ n =i,k α + Λ -2c, where τ > 0, κ > 0 and Λ are constants independent of network structure and α i and α k are the values of the demand intercept parameters before link formation commences 7 .

τ has an upper bound less than 11 (at n = 2, its value is 10.79) and is strictly decreasing in n. It has a lower bound of 2 and converges asymptotically to 2. It is important to note that at n = 4, τ = 3.5.

Hence, starting from an arbitrary network g with ik, im / ∈ g, if firms i and k form a link, the increase in aggregate profits can be written as ∆Π(g, ik) κ = 2γ 0 + γ (η i (g) + η k (g)) -τ n (n -2)γ 0 + γ =i,k,m η l (g) + γη m (g) + Λ -2c κ .

Suppose then that firms i and m form a link. The increase in aggregate profits can be written as ∆Π(g + ik, im) κ = ∆Π(g, ik) κ + γ 2 + (1 + τ n ) (η m (g) -η k (g) -1) .

Since η m (g) ≥ η k (g), we have ∆Π(g + ik, im) κ ≥ ∆Π(g, ik) κ + γ 1 -τ n .

We know that τ = 3.

We thank one of the referees for pointing out this general characteristic of efficient networks in our framework.

Our definition can be seen as a generalization of stable networks given in GJ (2003), since in GJ no firm has an incentive to delete one of its links or all its links in a stable network.

[START_REF] Goyal | Networks of Collaboration in Oligopoly[END_REF] do not provide efficiency results for the one market case stating that this is a hard problem.

Detailed calculations are available in the working paper version of this paper: http: mpra.ub.uni-muenchen.de /28188/1/M P RA-paper -28188.pdf