M D König

S Battiston

M Napoletano

F Schweitzer

The Efficiency and Evolution of R&D Networks

Keywords: R&D networks, technology spillovers, network efficiency, network formation JEL classification: D85, L24, O33

This work introduces a new model to investigate the efficiency and evolution of networks of firms exchanging knowledge in R&D partnerships. We first examine the efficiency of a given network structure from the point of view of maximizing total profits in the industry. We show that the efficient network structure depends on the marginal cost of collaboration. When the marginal cost is low, the complete graph is efficient. However, a high marginal cost implies that the efficient network is sparser and has a core-periphery structure. Next, we examine the evolution of the network structure when the decision on collaborating partners is decentralized. We show the existence of multiple equilibrium structures which are in general inefficient. This is due to (i) the path dependent character of the partner selection process, (ii) the presence of knowledge externalities and (iii) the presence of severance costs involved in link deletion. Finally, we study the properties of the emerging equilibrium networks and we show that they are coherent with the stylized facts on R&D networks.

Introduction

R&D partnerships have become a widespread phenomenon characterizing technological dynamics, especially in industries [START_REF] Hagedoorn | Inter-firm R&D partnerships: an overview of major trends and patterns since 1960[END_REF], with rapid technological development such as, for instance, the pharmaceutical, chemical and computer industries (see 2; 29; 45; 47). In those industries, firms have become more specialized on specific domains of a technology and they tend to rely on knowledge transfers from other firms, which are specialized in different domains, in order to combine complementary domains of knowledge for production (2; 46).

In this paper, we build a model in which firms innovate by recombining their knowledge with that of other firms in the industry, via a network of costly R&D collaborations. Within this framework, we first study the efficiency of a given network structure in terms of maximization of total profits in the industry. We characterize the topology of the efficient structure for any level of the marginal cost of collaborations in the relevant range. Next, we study the emergence of pairwise stable structures by employing the notion of improving path (cf. [START_REF] Jackson | The evolution of social and economic networks[END_REF], and assuming that link deletion is subject to severance costs. We show that if the cost of a collaboration is positive, there exist multiple stable structures for any given level of link severance costs. In addition, we study the relation between network stability and efficiency. Finally, we investigate equilibrium selection under a two-sided myopic link dynamics and we show that the model is able to generate stable structures that match the properties of empirically observed R&D networks.

Our research is motivated by two different, albeit related, streams of literature on R&D networks. On the one hand, the increasing importance of R&D partnerships has spurred research, both theoretical and empirical, on the consequences of a given structure of the R&D network for technology innovation and diffusion (see among many others 2; 13; 14; 40). To this regard, an important and still unsettled debate concerns the relation between the position of a firm in the network and its performance, and, in particular, whether a densely interconnected network is more conducive to knowledge diffusion and innovation than a network with structural holes (i.e. displaying the presence of hubs indirectly connecting many firms which have no direct link across them). Indeed, clusters of densely and directly connected firms might be seen as fostering collaboration efforts among participants by generating trust and punishment of opportunistic behaviors, and a common language and problem solving heuristics (see e.g. 2; 11; 14; Walker et al.). Conversely, by creating a structural hole in the network firms may have access to different sources of knowledge spillovers at the same time economizing on the costs of direct collaborations (cf. 9; 23; 51).

On the other hand, another body of contributions has investigated the salient features of empirically observed R&D networks (see e.g. 2; 21; 29; 32; 47; 50). These empirical studies have identified three main structural properties of innovation networks that look invariant across the different industries examined: (i) Networks are sparse, that is, from all possible connections between firms, only a small subset is realized. (ii) Networks are highly clustered, that is, they are locally dense. In clusters firms are closely interconnected but between different clusters there exist only a few connections. (iii) The distribution of links over the firms tends to be highly heterogeneous with only few firms being connected to many others. Following this wave of empirical research, theoretical models have explored the emergence of R&D networks in a framework with firms being allowed to form any arbitrary pattern of bilateral R&D agreements (see 24; 25, for an equilibrium approach, and Cowan et al., 2006, for an agent-based approach) . However, these models lead to network structures that are too simple to account for the stylized facts listed above.

Our paper contributes to the foregoing literature along several dimensions. First, we show that the network structure maximizing industry welfare (measured as the sum of firms' profits) is a function of the marginal cost of collaborations. In particular, when the marginal cost is low the complete graph -i.e. the one maximizing the number of direct ties -is the most efficient. As the marginal costs increase, it is efficient for the industry to organize into networks (the class of nested-split graphs, see Definition 2 and Proposition 3) having a core-periphery structure. More precisely, such networks display the presence of hubs, indirectly linking cliques of firms to otherwise disconnected nodes in the network. Second, and relatedly, we show that if collaboration costs and the size of the industry are large enough, the efficient structure for the industry is characterized by significant inequality in profits across firms. In particular, firms having less (more) direct connections are also the ones displaying higher (lower) profits. In addition, profits inequality increases both in the number of firms and in the marginal cost of collaboration.

Third, we study the relation between efficiency and equilibrium networks in our model. We show that multiple equilibrium structures for the same level of collaboration costs do arise in our model. In particular, we demonstrate that, for the same level of collaboration cost, both the spanning star (i.e. the star encompassing all nodes in the network), as well as the graph composed by disconnected cliques of the same size are possible equilibrium networks. The existence of multiple equilibria implies that efficiency is not necessarily met by equilibrium structures in our model. In addition, we identify the conditions on industry size and collaboration costs under which the efficient network never belongs to the set of possible equilibria. Finally, we study the properties of equilibrium structures in our model and we compare them with those of empirical R&D networks. More precisely we investigate equilibrium selection under a two-sided link formation/deletion (see [START_REF] Vega-Redondo | Complex Social Networks[END_REF] in which agents are stochastically selected to revise their collaboration strategies. In this dynamics, firms decide to form a link if the link did not exist before and the link is beneficial to both of them, and decide to delete a link if the link existed before and deletion is beneficial to at least one of the agents selected. We show that under this dynamics the model is able to select equilibrium structures matching the stylized facts of empirical R&D networks. As we mentioned above, the possibility of recombining different knowledge stocks to introduce innovations in the industry is the rationale for R&D collaborations in our model (see 2; 38; 46; 58). We formalize this idea by assuming that the arrival rate of innovations is proportional to the growth rate in the knowledge stock of the firm, and that firm's knowledge growth is a linear combination of the idiosyncratic knowledge stocks of the firm and the knowledge of its R&D partners. In the model, firm's expected profits are a linear function of the expected number of innovations per period and of the costs of R&D collaborations. Each R&D collaboration requires a fixed investment over each period. Total costs of collaboration are thus proportional to the number of collaborations (the degree) of the firm. Moreover, if the period over which collaborations are evaluated is long enough, the expected number of innovations per period turns out to be proportional to the largest eigenvalue of the matrix associated with the connected component to which the firm belongs. This has several implications. First, as the largest eigenvalue is the same for all firms in the same component, the formation/deletion of a collaboration by a firm has a strong non-rival external effect on all its direct and indirect neighbors. Second, the magnitude of the change in eigenvalue, resulting from creating/severing a collaboration, varies with the topology of the network and the position of the two firms involved in the collaboration, thus implying a strong path-dependent character of partner's choice decisions. Finally, it can be shown that the largest eigenvalue is related to the number of all walks connecting firms in a given component.

Our model can be related to the models in the network formation literature in which agents face a trade-off between the benefit they get from accessing the network and the cost of forming links with other agents (see e.g. 4; 10; 31; 37; 56). To this regard, our model shares many similarities and differences with the "Connections" model introduced in [START_REF] Jackson | A strategic model of social and economic networks[END_REF] and with the linear "Two-Way Flow" model without decay introduced in (4). For instance, similar to both models, the benefit an agent receives from the network derives also from indirect connections. In addition, such a benefit is non-rival1 (see in particular Eq. [START_REF] Carayol | A strategic model of complex networks formation[END_REF] and discussion thereafter). However, differently from both models, link deletion involves severance costs. Furthermore, differently from the Jackson and Wolinsky's model the benefit the agent receives from the network does not depends only on the shortest path existing between the agent and its direct and indirect neighbours but it accounts for all possible walks existing among them. Next, differently from the Bala and Goyal's linear model, link-formation is two-sided . Another difference is that, the utility of the agent does not depend only on the number of direct and indirect neighbours that can be reached by the agent with its existing connections, but also on how each neighbour can be reached. Incorporating all walks and severance costs in the network formation process has several implications also for the results obtained. First, as efficiency is concerned, similar to the Jackson and Wolinsky's model (and differently from the Bala and Goyal's model) we obtain that the complete graph and the empty graph are efficient for, respectively, low and high values of the marginal cost of link formation. By contrast, differently from both models, first, the efficient graph for intermediate levels of the marginal cost of collaboration (i.e. the nested-split graph), is in general not minimally connected (i.e. more than one path exists between any two agents in the efficient graph). Second, stable graphs are not necessarily connected as it can consists of several disconnected components. Similar to both models, we obtain the spanning star as possible equilibrium network for intermediate levels of the marginal cost of collaboration. However, differently from both models, this equilibrium coexists with the equilibrium consisting of the class of graphs composed of disconnected cliques of the same size.

The paper is organized as follows. Section 2 contains the description of the model, starting with the definition of the network of R&D collaborations across firms, and then moving to explain how firms profit from R&D collaborations, and the relations between our model and the others proposed in the literature. Section 3 is devoted to the analysis of the efficiency of R&D network structures and to the relation between efficiency and firms' profits inequality. Network dynamics, the emergence of equilibrium networks and their properties are analyzed in Section 4. Finally, Section 5 concludes. All proofs can be found in the Appendix.

The Model

We consider an industry in which firms engage in pairwise R&D collaborations with other firms. Collaborations allows the growth of knowledge within the firm and an increase in the probability to introduce innovations that yield profits to the firm. We first define the network of R&D collaborations. Next, we characterize how the R&D network influences knowledge growth, innovation and the profits of the firms. Finally, we briefly discuss the relations between our model and the relevant literature.

The Network

Consider an industry populated by N firms. The network2 G is the pair (N, E) consisting of the set of nodes N (G) = {1, ..., n}, n > 1, representing the firms and a set of edges E(G), representing the R&D collaborations among the firms3 (for simplicity we may just write N and E where it is obvious to which network G the sets refer). An edge ij ∈ E, represents the existence of an R&D collaboration between firm i and j. A

subgraph of G is a pair G = (N , E ) such that N ⊆ N , E ⊆ E.
The number of nodes is |N | = n and the number of edges |E| = m. A complete graph K n is a graph in which all n nodes are pairwise adjacent. The graph in which no pair of nodes is adjacent is the empty graph Kn . A clique K n , n ≤ n, is a complete subgraph of the network G. An independent set Kn is a clique in which all n nodes are not pairwise adjacent.

The neighborhood of i is the set

N i = {j ∈ N : ij ∈ E}.
The degree of a node i in G, written by d i , is the number of edges incident to i. Clearly,

d i = |N i |.
The maximum degree is ∆(G) and the minimum degree is δ(G). The clustering coefficient C i for firm i is the proportion of links between the firms within its neighborhood N i divided by the number of links that could possibly exist between them, i.e.

C i = 2|{jk : j, k ∈ N i ∧ jk ∈ E}| d i (d i -1) . (1)
The total clustering coefficient is the sum of the clustering coefficients for each firm, A connected component in G is a maximal set of firms such that there exists a path between any two of them. We will say that two components are disconnected if there is no path between them. A connected graph is a graph consisting of only one connected component.

C = n i=1 C i . A walk W k of length k connecting firm i 1 and i k is a sequence of firms (i 1 , i 2 , ..., i k ) such that i 1 i 2 , i 2 i 3 , ..., i k-1 i k ∈ E. A
Let A(G) be the symmetric n × n adjacency matrix of the R&D network G. The element a ij ∈ {0, 1} indicates if there exists a link between firm i and j such that

a ij = 1 if ij ∈ E and a ij = 0 if ij / ∈ E.
The eigenvalues of the adjacency matrix A are the numbers λ such that Ax = λx has a nonzero solution vector, which is an eigenvector associated with λ. The term λ PF denotes the largest real eigenvalue of A (the Perron-Frobenius eigenvalue, cf. 34; 52), i.e. all eigenvalues λ of A(G) satisfy |λ| ≤ λ PF and there exists an associated nonnegative eigenvector v ≥ 0 such that Av = λ PF v. For a connected graph G the adjacency matrix A(G) has a unique largest real eigenvalue λ PF and a positive associated eigenvector v > 0.

Let A(G) be the symmetric n × n adjacency matrix of the R&D network G. The element a ij ∈ {0, 1} indicates if there exists a link between agent i and j such that

a ij = 1 if ij ∈ E and a ij = 0 if ij / ∈ E.
The eigenvalues of the adjacency matrix A are the numbers λ such that Ax = λx has a nonzero solution vector, which is an eigenvector associated with λ. The term λ PF denotes the largest real eigenvalue of A (the Perron-Frobenius eigenvalue, cf. 34; 52), i.e. all eigenvalues λ of A(G) satisfy |λ| ≤ λ PF and there exists an associated nonnegative eigenvector v ≥ 0 such that Av = λ PF v. For a connected graph G the adjacency matrix A(G) has a unique largest real eigenvalue λ PF and a positive associated eigenvector v > 0.

Finally, for a graph with n nodes there are n 2 possible links. We denote with G(n, p) the random graph with n nodes, in which each of the possible links occurs independently with probability p. Similarly, G(n, m) is the random graph with n nodes and m edges.

Innovation and Profits from R&D Collaborations

Firms exploit R&D collaborations to introduce innovations in the industry. Decisions over R&D partners are taken at discrete times t = T, 2T, 3T, ... where the length of a period is given by T > 0. Innovations are introduced during each period (t, t + T ]. The rewards from each innovation are assumed to be appropriable so that an innovation returns a value equal to the constant V > 0. Following the theoretical literature on innovation and endogenous technical change (see e.g. 1; 41; 48; 49; 60), we assume that the introduction of innovations is governed by a non-homogeneous Poisson process with arrival rate equal to h i (τ ), where τ ≥ 0 indicates the time variable within a period. Thus, the probability that an innovation is introduced by firm i in the interval dτ , is equal to h i (τ )dτ . Moreover we assume that, for any firm i, the arrival rate of innovations is proportional to the growth rate ρ i (τ ) of knowledge4

h i (τ ) = bρ i (τ ), b > 0. ( 2
)
In other words, the higher the growth rate of new ideas, the more likely it is that the firm will be able to innovate. This assumption is tantamount to say that it is the growth (flow) of knowledge of a firm that makes it more innovative, rather than the stock of knowledge accumulated by the firm over time. Expected revenues of firm i in a period (t, t + T ] are given by the value V of each innovation times the expected number of innovations in the period. Note that in Equation ( 2) the innovation process starts anew at the beginning of every period (t, t + T ], taking as initial condition the stock of knowledge at the end of the previous period (t -1, t -1 + T ]. In addition, let us set τ ∈ (0, T ]. From Equation (2) the expected number of innovations accumulated in a period (t, t + T ] can be written as:

T 0 h i (τ )dτ = b T 0 ρ i (τ )dτ. (3)
In turn, the growth rate of knowledge is affected by the network of collaborations as follows. In each period (t, t + T ], new knowledge is generated by recombining the existing knowledge stocks of firms in the economy via the existing network of R&D collaborations (see 38; 43; 58). More precisely, let us denote by x i (τ ) the stock of knowledge of firm i at time τ ∈ (t, t + T ]. Then new knowledge within firm i is generated according to:

ẋi (τ ) = n j=1 a ij (t)x j (τ ), (4)
where a ij (t) are the elements of the adjacency matrix A(G(t)) (defined in Section 2.1) corresponding to the network of R&D collaborations 5 . In vector-matrix notation Equation (4) reads ẋ(τ ) = A(G(t))x(τ ). Note also that in Equation ( 4) for non-negative initial values of x(0) ≥ 0, we have that ẋ(τ ) ≥ 0 as well as x(τ ) ≥ 0. The growth rate of knowledge of firm i, ρ i (τ ) = ẋi (τ )/x i (τ ), is directly affected by the growth rate of knowledge of its neighbors, whose growth rate is affected by the growth rate of their neighbors, and so on. Therefore, Equation 4 implies that the topology of the whole network of R&D collaborations (including all direct and indirect paths along which knowledge can flow between the firms), influences the innovation process within the firm.

Collaborations also imply a cost for the firms. Within a period (t, t + T ] each collaboration involves a cost per unit of time equal to c. Moreover, we assume that firms are risk-neutral. Finally, if we denote by G i (t) the connected component to which firm i belongs in the period, then expected profits for the firm at the beginning of the period can be written as:

πi (G i (t), c, t) = bV T 0 ρ i (τ )dτ -cT d i (t), (5)
where d i (t) is the degree of the firm at time t and during the period. The timing of events in each period (t, t + T ] runs as follows: at the beginning t of the period the network of R&D collaborations is determined (only one link is added or removed at time t), based on the expected profits and remains fixed throughout the period (t, t + T ]. During the period (t, t + T ], firms recombine their knowledge stocks through the network while they also bear the costs of their collaborations. As a result, innovations are introduced and the rents accrue to the firm.

The expression for expected profits in Eq. ( 5) can be directly related to the structure of the network of collaborations. For this purpose, the next Proposition establishes a relation between, on one hand, the asymptotic growth rate of ideas, the asymptotic relative stock of knowledge and the rate of convergence, and, on the other hand, the eigenvalues and eigenvectors of the adjacency matrix A(G i (t)) of the connected component of firm i. Proposition 1 Consider the eigenvalues λ PF = λ 1 ≥ λ 2 ≥ ... ≥ λ n associated with the adjacency matrix A(G i (t)) of the connected component G i (t) of firm i ∈ N (G i (t)). Then the following results hold:

(i) The asymptotic knowledge growth rate of a firm i is constant and equal to the largest real eigenvalue (Perron-Frobenius eigenvalue) of the adjacency matrix

A(G i (t)) lim τ →∞ ρ i (τ ) = λ PF (G i (t)). ( 6
)
The rate of convergence is O e -[λPF(Gi(t))-λ2(Gi(t))]τ as τ → ∞.

(ii) The asymptotic value of a firm i's relative knowledge stock equals the element v i of the eigenvector associated with λ PF (G i (t))

lim τ →∞ x i (τ ) n j=1 x j (τ ) = v i . (7)
Point (i) of the above Proposition states that the knowledge dynamics defined in Equation (4) converges, for a given R&D network, to a steady state characterized by a constant growth rate of ideas. In addition, such constant growth rate depends on the topology of the connected component which the firm belongs to (through the largest eigenvalue λ P F (G i (t))). This implies that, in the steady state, the arrival rate of an innovation is constant and equal to bλ P F . Moreover, point (ii) implies that the topology of the connected component G i (t) determines the distribution of relative values of the knowledge stocks of firms in the same component. Finally, the rate of convergence to the steady state is determined by the eigenvalues of 6 of A(G i ).

An important assumption of our model is that the growth of knowledge is much faster than the formation of R&D collaborations. This is equivalent to saying that τ is measured in time units much smaller than those used to measure t. In other words, t = kτ , with k large. Under this assumption, the expected number of innovations per unit of time can be approximated (taking the limit k → ∞) with the largest real eigenvalue of a firm's connected component. Corollary 1 The expected number of innovations of firm i per unit of time in a period (t, t + T ] tends to the largest real eigenvalue of firm i's connected component G i .

lim k→∞ 1 kT kT 0 ρ i (τ )dτ = λ PF (G i (t)). (8)
Expected profits of the firm at beginning of the period (t, t + T ] can now be written as

πi (G i (t), c, t) = bλ PF (G i (t))V T -cd i (t)T. (9)
Applying an affine transformation to the above equation, we finally obtain expected profits per unit of time in the period between t and t + T ,

π i (G i (t), c, t) = λ PF (G i (t)) -cd i (t), (10)
where c = c bV is the marginal cost of link formation (rescaled by the factor 1/bV ) 7 . Since in Equation [START_REF] Carayol | A strategic model of complex networks formation[END_REF] the largest eigenvalue λ PF (G i (t)) is the same for all firms in the same connected component, the expected revenues from R&D collaborations will be the same for all the members of G i . Nonetheless, profits from R&D collaborations vary, in general, across firms, since each firm may have a different number of collaborations. The following Lemma 8 characterizes the relation between the largest eigenvalue of a connected component and the creation or removal of R&D collaborations. 6 In general, the convergence in a connected component to its largest real eigenvalue is always guaranteed. In addition, more dense networks are characterized by a faster convergence (see the proof of Proposition (1) in the Appendix). However, the convergence can be slow for sparse networks and particular network topologies. For a recent application and discussion of the convergence properties of the social network matrix see [START_REF] Jackson | Naive learning in social networks: Convergence, influence and wisdom of crowds[END_REF]. 7 The introduction of linear and homogeneous in-house R&D activities in Equation (4) for the dynamics of knowledge stocks would not alter the functional form of profits (up to a constant). 8 A proof of the foregoing Lemma can be found in [START_REF] Cvetkovic | Spectra of Graphs: Theory and Applications[END_REF].

Lemma 1 Denote G = (N , E ) the graph obtained from the connected graph G = (N, E) by the addition or removal of an edge. Then

(i) λ PF (G ) ≥ λ PF (G) if ij / ∈ E and λ PF (G ) ≤ λ PF (G) if ij ∈ E. (ii) λ PF (G ) ≤ λ PF (K n ) = n -1. (iii) |λ PF (G ) -λ PF (G)| ≤ 1
Thus, the largest real eigenvalue in a component is a non decreasing function of the number of links. In addition, it is a bounded function, since its value can never be higher than the one associated with the complete graph K n . Finally, the change in the eigenvalue is itself a bounded function, since its value must be less than one. The preceding observations deliver two central properties of the model.

First, since the probability of innovation is the same for all the firms in a given connected component and it is affected by each link, the creation (deletion) of a collaboration by one firm has a positive (negative) non-rival external effect on all its direct and indirect neighbors in the component. As we will see in Section 4, this property is at the origin of the fact that the network can evolve into equilibria that are socially inefficient.

Second, the marginal revenue from R&D collaborations is always a positive (albeit bounded) function of the number of links. This means that the creation (deletion) of a new R&D collaboration increases (decreases) the probability of innovation and thus the expected revenue. Moreover, the revenue itself is a bounded function of the number of links. The last property does not imply that the revenue is also a concave function of the number of links 9 . However, as we will show in Section 4, it implies that, as the network grows in the number of links, the highest marginal revenue that -for a given network -can actually be obtained from the creation of a new link or from the removal of an existing link can become very small. In turns out that, when the highest marginal revenue from a collaboration that can be obtained is smaller than the marginal cost of collaboration, the network reaches an equilibrium, and this may happen well before the network has grown to a fully connected graph. .

Relation to the Literature

The profit Equation [START_REF] Carayol | A strategic model of complex networks formation[END_REF] can be compared to other similar utility functions in the literature that feature a dependence on the position of a firm in the network. For instance, the utility function proposed in the "connections model" in [START_REF] Jackson | A strategic model of social and economic networks[END_REF] is given by

u i = n j=1 δ d(i,j) -cd i , (11)
where 0 < δ < 1 and d(i, j) is the length of the shortest path from node i to node j.

The difference between the profit function in [START_REF] Carayol | A strategic model of complex networks formation[END_REF] and the utility function in (11) becomes apparent in the benefit term. While Equation [START_REF] Coleman | Social capital in the creation of human capital[END_REF] considers the shortest path between firm i and j only, our model instead takes into account all possible walks from firm i to the other firms in the connected component 10 Recall that, in our model, a walk represents a sequence of recombination of the knowledge of the firms along that walk. Not any recombination of knowledge might translate into a successful innovation. However, the more walks there are in the component, the higher is the number of possible knowledge recombinations available. It turns out that the likelihood for a successful innovation is increased. Indeed, the largest eigenvalue λ PF (G i ) of the adjacency matrix of a connected component G i , is related to the number of possible walks in that component (more precisely, the growth rate in the number of walks of length k tends to λ PF (G i ); this property has been further elaborated in König et al. (39)). Thus, the larger is λ PF (G i ), the larger is the number of possible knowledge recombinations via direct and indirect R&D collaborations. From Equation [START_REF] Carayol | A strategic model of complex networks formation[END_REF] we can conclude that profits of firm i grow with the number of walks in the connected component which firm i belongs to. On the other hand, profits decrease with the degree d i of the firm. Therefore, with our profit function it is best for a firm to be able to reach the other firms through many walks but to have not too many links to pay for. This observation becomes apparent if one considers the following simple example. The revenues of the hub in a star K 1,n-1 and a node in a complete graph K n in Equation ( 11) are identical, because the shortest paths to all the other nodes are one link long in both cases. This is not the case in our model where these two graphs generate very different revenues. A node in the complete graph can reach the other nodes through many different paths and this generates a much higher revenue than the one of the hub in a star.

In their linear "Two-Way Flow" model Bala and Goyal (4) introduce a utility function of the form:

u i = |G i | -cd i , (12)
where |G i | is the size of the connected component of firm i ∈ N (G i ). This means that the utility of firm i grows with the number of all firms in the network who can be reached by firm i across at least one path. The number of links and the number of paths between i and the other firms do not matter because the benefit flow across the network is assumed to be independent of its topology. In contrast, in our model the topological properties of the component the firm belongs to are critical for the profits of the firm. Consider the following simple examples. According to Equation [START_REF] Corbo | A study of nash equilibrium in contribution games for peer-to-peer networks[END_REF], revenues for a firm in the complete graph K n , in the clique K 1,n-1 and in the cycle C n , are identical. However, as one can see from Table [START_REF] Aghion | Endogenous Growth Theory[END_REF], in our model for the same number of collaborations the revenues a firm earns from being part of a clique K n are higher than in a star K 1,n-1 , which in turn are higher than in a cycle C n . This ranking can be understood if one considers the possible walks in these graphs. The number of walks is highest in the complete graph K n while it is smallest in the cycle C n (that contains only one walk). While all these graphs encompass the same number of firms, they differ significantly in the way the links are arranged among the firms.

Efficiency

In the model presented in the previous Section, firms face a trade-off between increasing the probability to innovate by forming R&D collaborations and the cost of sharing knowledge with other firms in the industry. In this Section we investigate how this trade-off can be managed in order to yield the best outcome from the industry point of view. First, we show that there exists an interval of the marginal cost of link formation, c ∈ [0, 1], in which the network that maximizes social welfare, that is the efficient graph, is a connected graph. We will show in Section 4 that this interval is the one of main interest since for values above this interval, c > 1, firms do not have the incentive to form any additional collaboration. Therefore, we restrict our attention to values of cost in this interval.

We then investigate the topology of the efficient graph, and we show that it belongs to a well defined class of connected graphs, the "nested split graphs". In particular, for c small enough, the efficient graph is the complete graph. On the other hand, for higher values of c and a larger number of firms, the efficient graph is sparser and characterized by degree heterogeneity. Finally, we show that at higher values of cost, the efficient graph is characterized by a significant degree of inequality in profits.

Efficient Networks

Following [START_REF] Jackson | A strategic model of social and economic networks[END_REF], we define social welfare as the sum of firms' individual profits

Π(G, c) = n i=1 π i (G i ) = n i=1 (λ PF (G i ) -cd i ) = n i=1 λ PF (G i ) -2mc. ( 13
)
We are interested in the solution of the following social planner's problem. Let G(n) denote the set of all possible graphs with n nodes. For a given value of cost c, the social planner's solution is given by

G * = argmax G∈G(n) Π(G, c). (14)
A graph G * solving the maximization problem ( 14), will be denoted as "efficient".

In order to solve this problem we begin by identifying an interval for the marginal costs c in which social welfare is increased by connecting two disconnected components of the network. The following Lemma can be stated.

Lemma 2 Consider a graph G consisting of two disconnected components G 1 and G 2 , with n 1 , n 2 nodes, m 1 , m 2 edges, eigenvalues λ PF (G 1 ), λ PF (G 2 ) and total profits Π(G 1 ) = n 1 λ PF (G 1 ) -2m 1 c, Π(G 2 ) = n 2 λ PF (G 2 ) -2m 2 c
. We further assume that c ∈ [0, 1]. Then there exists a connected graph G with n = n 1 + n 2 nodes that has higher total profits

Π(G ) ≥ Π(G) = Π(G 1 ) + Π(G 2 ).
Thus, for c ∈ [0, 1], connecting two previously disconnected components of the graph yields total profits larger than the respective total profits of the disconnected components. From this it follows immediately that the efficient network is connected. Proposition 2 Let H(n, m) denote the set of connected graphs having n nodes and m links.

If c ∈ [0, 1] then G * ∈ H(n, m).
This means that, in order to guarantee an efficient knowledge production in the economy, each firm must have (direct or indirect) access to the knowledge of all other firms in the industry. Since the efficient graph is connected, the equation for total profits [START_REF] Cowan | Network structure and the diffusion of knowledge[END_REF]

simplifies to Π(G, c) = nλ PF (G) -2mc. ( 15
) This implies that, for any given values of n and m, the efficient graph is also the one with maximal λ PF . In other words, for c ∈ [0, 1], the efficient graph G * belongs to the set of connected graphs that maximize λ PF (G), denoted by H * (n, m). As a result, the efficient graph belongs to a special class of graphs characterized by well defined topological properties 11 . In order to fully describe these properties we first need to introduce some basic definitions. [START_REF] Brualdi | On the spectral radius of connected graphs[END_REF] show that the graphs in the set H * (n, m) have a stepwise adjacency matrix A, defined as follows: Definition 1 In a stepwise matrix A, the elements a ij satisfy the following condition. If i < j and a ij = 1, then a hk = 1 whenever h < k ≤ j and h ≤ i. The above definition says that if the adjacency matrix has an element equal to one, a ij = 1, then also the element above in the matrix is one, a i,j-1 = 1, and the element to the left in the matrix is one, a i-1,j = 1. Consequently, all the preceding elements to the left and above are one. In this way, the one-elements are separated from the zero-elements in the adjacency matrix along a line which has the form of a staircase function. This fact has brought about the name stepwise matrix. An example of a stepwise matrix is shown in Figure (1, right).

The graphs associated with a stepwise adjacency matrix are called nested split graphs (3). However, before providing a formal definition, we consider an example of a connected nested split graph and describe its structure with the help of the representation in Figure (1, left). First, the nodes in a nested split graph can be partitioned in subsets of nodes with different properties. In Figure (1, left) each circle represents a subset of nodes (and not an actual node of the network). We denote the partition of the graph as P = U ∪ V , where U and V consists respectively of subsets,

U = {U 1 , U 2 , ..., U k } and V = {V 1 , V 2 , ..., V k }.
Recall the notation from Section 2.1 in which K n denotes the complete graph with n nodes and Kn the empty graph with n isolated nodes. Then, for example, in Figure (1, left) the sets are

U 1 = K 2 , U 2 = K 2 ∪ K 1 and U 3 = K 2 ∪ K 1 ∪ K 1 and V 1 = K2 , V 2 = K2 and V 3 = K2 respectively. Of course, K 2 is
simply a complete graph since it contains only two nodes, and even more so K 1 .

The subsets U i and V i differ in the fact that in U i all nodes are connected to each other while in V i there exist no links between the nodes. However, there exist also links between nodes belonging to different subsets. In Figure (1, left) a line between two subsets indicates that there exists a link between each node in one subset to each node in the other subset. E.g. the nodes in K2 at the top right of the Figure are all connected to the nodes in K 2 at the top left. Additionally, the set U as well as any union of the subsets in U form a complete subgraph or clique. Similarly, any union of the sets in V form an independent set. Notice also that all the nodes in one set have the same degree. Next to the sets in Figure (1, left) the degree of the nodes in a subset is indicated. The degree of a node in a set can be easily derived from the adjacency matrix shown in Figure (1, right) by counting the number of ones in a row corresponding to a particular node in a set. E.g. the set K 2 , top left in the Figure, corresponds to two nodes whose links are indicated in the first two rows of the adjacency matrix.

With the preceding discussion in mind, we can now give a more formal definition of a nested split graph . 1) actually show a connected nested split graph. From the stepwise property of the adjacency matrix it follows that a connected nested split graph contains at least one spanning star, that is there is at least one node that is connected to all other nodes. This property can also be seen in Figure [START_REF] Aghion | Endogenous Growth Theory[END_REF], where the first row of the adjacency matrix that is entirely filled with ones indicates the presence of a spanning star. We have shown that G * is connected and we know that G * has a stepwise adjacency matrix. From the above discussion we can further conclude that G * is a connected nested split graph and it contains at least one spanning star as a subgraph.

The determination of the exact topology of G * in the class of connected split graphs is still is still an unresolved research problem in Spectral Graph Theory (see 3) However, it turns out that the value of total profits associated with the efficient graph G * can be approximated by total profits associated with a special type of a connected nested split graph. Following Bell [START_REF] Bell | On the maximal index of connected graphs[END_REF] we denote this graph by F n,d . Definition 3 (( 6)) F n,d is the graph obtained from the complete graph K d with d nodes and a subset of nd disconnected nodes, by adding nd links connecting a given node in K d to each of the nd disconnected nodes. Notice that the complete graph and the spanning star are particular cases of connected split graph: the star is K 1,n = F n,1 and the complete graph is K n = F 0,n . Figure [START_REF] Aouchiche | Variable neighborhood search for extremal graphs, 16. some conjectures related to the largest eigenvalue of a graph[END_REF] shows several examples of this type of graph for n = 10. The number of edges in F n,d is given by m

= d 2 + (n -d). Note that d ≤ n and F n,n is just K n .
As discussed in more detail in the Proof of the next Proposition, the maximum relative discrepancy of total profits between F n,d and the efficient graph G * is considerably small and vanishes for large n. E.g. for n = 100 we get get an error below 2%, while for n = 200 the error is below 1%, as it can be seen in Figure [START_REF] Bala | A noncooperative model of network formation[END_REF]. The higher is the number n of firms, the more total profits of F n,d get close to total profits of G * . Thus, in order to determine the efficient network G * , if n is small12 one can search through all connected nested split graphs and identify the one with highest total profits, while for large n one can use F n,d as a good approximation.

Bringing the above results together, we can state the following Proposition which characterizes the topology of the efficient graph G * with n firms in the industry for any level of marginal cost c ∈ [0, 1]. Proposition 3 Let G * be the efficient graph for a given number n of firms and F n,d be the graph defined in [START_REF] Aouchiche | Variable neighborhood search for extremal graphs, 16. some conjectures related to the largest eigenvalue of a graph[END_REF].

(i) If c ∈ [0, 1] then G * is a connected nested split graph.
(ii) Denote the relative error in total profits between the the efficient graph and the graph

F n,d as = (Π(G * ) -Π(F n,d ))/Π(F n,d ). If c ∈ [0, 1]
, the relative error is bounded from above as follows

≤ 2c(2c -1)n -5c 2 n 2 + 2c(1 -2c)n + 9c 2 (16)
and vanishes for large n, i.e. lim n→∞ = 0.

(iii) If c ∈ [0, 0.5] then G * is the complete graph K n . (iv) If c > n then G * is the empty graph Kn . 0 0.5 1 c K n connected nested split graph K K K K K K ∼ n→∞ F n,d
Fig. 2. Illustration of the range of efficient graphs as a function of the cost of collaboration. For costs 0 ≤ c ≤ 0.5 the efficient graph is the complete graph Kn. In the region 0.5 < c ≤ 1 the connected graphs with stepwise matrices are efficient [START_REF] Aghion | Endogenous Growth Theory[END_REF] or equivalently the connected nested split graphs. Note that for n large, F n,d attains total profits of G * with a vanishing relative error in total profits and thus can be seen as an approximation for G * .

Figure [START_REF] Ahuja | Collaboration networks, structural holes, and innovation: A longitudinal study[END_REF] gives a graphical representation of the results on network efficiency in Proposition [START_REF] Aouchiche | Variable neighborhood search for extremal graphs, 16. some conjectures related to the largest eigenvalue of a graph[END_REF]. For the particular case of n = 10 the connected graph with maximal eigenvalue is known (3) and so is the efficient network G * . In this case, the efficient graph is F n,d itself (without any approximation). In Figure (3) the efficient graphs for values of cost c ∈ [0, 1] and n = 10 are shown. Moreover, Figure (??) shows the corresponding total profits and number of links. We observe that, with increasing marginal cost, the efficient network becomes more sparse and the degree heterogeneity is increasing. For any value of cost larger than 0.6 the efficient network consists of a densely connected cluster (clique) and one node that acts as a hub (star) and connects the remaining nodes to the cluster. From Proposition (3), point (ii), and Figure ( 4) it can be seen that the relative error between total profits of F n,d and G * is considerably small. Moreover, it is decreasing with increasing number of firms n and vanishes for n large. In this case, we can take F n,d as a sufficient approximation to the efficient network G * .

If we consider F n,d as the efficient network, we can make the following observation. From the topological structure of F n,d it follows that, when marginal cost of link formation is high, it is efficient to concentrate knowledge creation in a small and dense cluster with one firm acting as a hub that connects all the peripheral firms to the cluster. As the marginal cost of link formation decreases, knowledge recombination becomes cheaper 13and it is efficient that a larger fraction of firms takes part in the densely connected cluster. Finally, in the region of small marginal cost, 0 ≤ c ≤ 0.5, it is efficient that all firms take part in densely connected cluster, thus establishing as many collaborations as possible. In this case, the fully connected graph of all firms is the one in which knowledge production (measured by the growth rate of knowledge) in the economy attains its highest possible value.

An important final remark concerns the relation to the efficient graphs found in related models. Similar to both [START_REF] Jackson | The evolution of social and economic networks[END_REF] and ( 4), we find that the efficient graph is always connected and that it includes, depending on c, the star and the complete graph. However, differently from the former model, it is, in general, not minimally connected (removing one link does not necessarily make the graph disconnected). Moreover, differently from the latter model, F n,d includes a whole class of graphs that can be seen as intermediate graphs between the star and the complete graph, these being the two extreme cases.

Efficiency and Profits Distribution

Former works on R&D networks (see 13) have emphasized the emergence of a trade-off between efficiency (in terms of knowledge diffusion) and inequality (in terms of knowledge levels). A similar trade-off emerges also in this model, between efficiency and profits, if the marginal cost of link formation and the number of firms operating in the industry are high enough. We measure inequality in profits in terms of profit variance.

In Proposition [START_REF] Ahuja | Collaboration networks, structural holes, and innovation: A longitudinal study[END_REF] we have shown that for c ∈ [0, 1] the efficient graph is connected, G * ∈ H(n, k). Thus, the returns from collaborations in an efficient graph are identical for all firms (since they have the same largest real eigenvalue) but the cost is different and is proportional the degree of the firm. More formally, let us define by σ 2 π the variance of profits associated with the graph G. It follows for a graph G ∈ H(n, m)

σ 2 π (G) = c 2 σ 2 d (G), ( 17
)
where σ 2 d is the degree variance. Since degree is by definition homogeneous in a complete graph, from Proposition (3) it follows that for c ≤ 0.5 profits inequality is zero, and no tension between efficiency and equality arises.

For higher values of costs, we can take F n,d as a sufficient approximation to the efficient network G * , and we can conclude that the efficient network is characterized by considerable degree heterogeneity and profits inequality. More precisely, the following proposition can be stated. Proposition 4 Let F n,d be the graph defined in (3) and d = 2m/n its the average degree. Then (i) The degree variance is growing quadratically with the number of firms, i.e.

σ 2 d (F n,d ) = O(n 2 ). (18)
(ii) Let c > 0.5. The coefficient of variation of degree, c v (F n,d ) = σ d (F n,d )/ d tends, for large n, to a constant value dependent on cost

lim n→∞ c v (F n,d ) = √ 2c -1. ( 19
)
(iii) Consider the random graph G(n, m) with n nodes and m links. For large n, the variance of the graph F n,d is larger by a factor n than the variance of a random graph with equal number of nodes and links

σ 2 d (F n,d )/σ 2 d (G(n, m)) = O(n). (20)
The results of this Proposition are illustrated in Figure 4. The coefficient of variation of degree, c v , increases with increasing cost (Figure 4, top-left). It also increases with the number of firms up to the finite limit of √ 2c -1 for large n. Equation ( 17) implies that the inequality in profits increases with cost as well. Moreover, the degree variance of F n,d is many times larger than the degree variance of a random graph G(n, m) with the same density (Figure 4, bottom-left). It follows that, for higher values of marginal cost 0.5 < c ≤ 1, the industry displays an inequality in profits significantly larger than the one that could be observed if collaborations would be formed at random.

Network Evolution

The analysis contained in the previous Section assumes that the structure of the network is fixed. In this way, it is possible to study which network topologies maximize welfare. In this Section we depart from this static network perspective, and we investigate how the structure of the network evolves whenever firms are allowed to endogenously choose the partners with whom they want to collaborate.

Following Jackson and Watts [START_REF] Jackson | The evolution of social and economic networks[END_REF] we consider a network formation process in which the creation of a new link requires the bilateral agreement of the two parties involved. However, the deletion of a link requires the unilateral decision of one of the two firms only. Consistently, as network equilibrium criterion, we adopt the definition of pairwise stability, as in Jackson and Watts [START_REF] Jackson | The evolution of social and economic networks[END_REF]. Based on this definition of stability, we derive the conditions on the value of cost for which structures like the empty graph, the complete graph or the star are stable. Among the possible stable graphs, we find also a disconnected graph consisting of multiple cliques of the same size. A first important finding here is the co-existence of multiple equilibrium networks for the same values of cost.

However, these relatively simple structures are not the only stable networks emerging in our model. Since it is increasingly difficult to derive general proofs of stability for more complex structures, we follow the argument in Vega-Redondo (55, p. 208) and we perform a dynamic study of network stability. We model explicitly the evolution process in which, at the beginning of each period, a pair of firms decides whether to form or delete a link, based on the expected profits this action brings about. This investigation, performed through computer simulation, shows that there exist a multitude of complex structures which are pairwise stable. Remarkably, these networks display topological properties that are consistent with the stylized facts of R&D networks, in a region of the parameters of the model.

Improving Paths and Equilibrium Networks

We consider a process of network evolution in which firms form or delete one link at a time based on the marginal profits they expect from that action. In other words, new links are created whenever the increase in the probability of innovation, i.e. the marginal revenue of a new collaboration, is greater than the marginal cost of collaboration, with the gain being strict for at least one of the firms in the selected pair. Likewise, link deletion occurs whenever the saving in marginal cost from removing a collaboration are enough to compensate for the decrease in marginal revenue. However, given its unilateral nature, we assume that removing a collaboration involves severance costs14 so that the savings in marginal costs from removing a collaboration is reduced by a factor α.

As in Jackson and Watts [START_REF] Jackson | The evolution of social and economic networks[END_REF], we call Improving Path, the sequence of networks {G t } t∈N+ such that (i) any two adjacent networks differ only by one link, (ii) if the link is added both firms benefit, at least one of them strictly, and (iii) if a link is deleted, at least one of the two firms strictly benefit .

Improving Paths emanating from any initial network must either lead to an equilibrium network structure (where no pair of firms has an incentive to form a link, and no single firm has an incentive to remove a link) or to a cycle, in which a finite number of networks is repeatedly visited (see Lemma 1 in 36). In this Section we investigate both equilibrium networks and cycles.

Denote as G + ij (Gij) the graph obtained from G by adding (removing) the edge ij. Denote by λ i (G) the largest eigenvalue of the connected component to which the firm i belongs. Note that, although link deletion implies that the degree of i is reduced by one (and so is the cost for firm i), the firm saves only a fraction α of the cost due to the presence of the severance costs v(c) = (1αc). A network is pairwise stable whenever the following conditions are fulfilled. Fig. 5. Largest real eigenvalue λ PF of a network of n = 50 firms as a function of the number m of links, along a specific Improving Path (optimal). At every step, among all possible new links in the network, the one that gives the best possible increase in expected profits (and thus in λ PF ) is created. Moreover, the straight line depicts the average λ PF .

Definition 4 Let λ i (G) denote λ PF (G i (t)). Then the graph G is pairwise stable if (i) ∀ij ∈ E(G), π i (G) ≥ π i (G -ij) and π j (G) ≥ π j (G -ij) or, equivalently, ∀ij ∈ E(G), λ i (G) -λ i (G -ij) ≥ αc and λ j (G) -λ j (G -ij) ≥ αc (ii) ∀ij / ∈ E(G), if π i (G + ij) > π i (G) then π j (G + ij) < π j (G), and, if π j (G + ij) > π j (G) then π i (G+ij) < π i (G) or, equivalently, ∀ij / ∈ E(G), if λ i (G+ij)-λ i (G) > c then λ j (G+ij)-λ j (G) < c, and, if λ j (G+ij)-λ j (G) > c then λ i (G+ij)-λ i (G) < c
Before moving to the analysis of the stability of different graphs, we give an intuition about why in our model the network might stop evolving along an Improving Path and reach an equilibrium. Let us consider an Improving Path along which the number m of links is increasing from m 1 = 0 (the empty graph) to at most m 2 = n(n -1)/2 (the complete graph K n ). For any network in this sequence, λ PF (m) can be computed. Since the largest eigenvalue is bounded

(λ PF (G ) ≤ λ PF (K n ) = n -1, see Lemma 1), it follows the average increase of λ PF (m) is 2
n . This is represented in Figure ( 5) by the straight line with slope 2 n . The curve of the function λ PF (m) is also shown for a particular Improving Path for an industry of n = 50 firms, starting from the empty graph. At every step, among all possible new links in the network, the one that gives the best possible increase in expected profits and thus in λ PF is created (where we assume that c = 0 and no links are removed). As a matter of fact, not only in this particular Improving Path but along any Improving Path, λ PF (m) starts off above the straight line and since it has to reach the same bound as the straight line, the increment of ∆λ PF (m) has to be smaller than 2 n for some number of links m ≤ m max = n(n -1)/2. Therefore, for any value of cost, if n is large enough there will be a value of m, along the Improving Path, where the marginal revenue is smaller than the marginal cost. This is stated more precisely in the following Proposition. Proposition 5 Along any Improving Path with an increasing number m of links the marginal profit becomes negative for some value of m ≤ m max , for any given value c of cost and n large enough.

In light of the foregoing results we now proceed to investigate the stability of specific network structures. From a straightforward application of the properties of marginal revenue from collaboration (cf. item (iii) in Lemma ( 1)) it follows that, on one hand, when marginal costs are zero (c = 0) links will always be created and no existing link will be deleted. It follows that the only equilibrium is the complete graph K n . Proposition 6 If costs are zero, c = 0, then the complete graph K n is the unique stable network. On the other hand, when the difference between marginal costs c and severance costs v(c) is larger than one, it is profitable to remove any link and the only equilibrium is the Fig. 6. Two complete graphs, K 9 , connected through an edge.

empty graph Kn . Proposition 7 For cost c = αc > 1 the empty graph Kn is the unique stable network.

Besides the foregoing extreme situations, the determination of stable networks becomes quite involved. This is because, in general, the marginal revenue from a collaboration depends on the topology of the graph. In addition, for a given topology, it varies with the position of the firm which is chosen to create or delete a link. Starting from an initial graph G 0 this property implies that different network trajectories can be explored, according to the particular pair of firms that is allowed to revise its collaboration strategy at the beginning of each period. Thus, multiple equilibrium networks might be possible for the same level of marginal costs. In what follows we show that, on one hand, multiple pairwise stable networks exist for the same value of marginal cost c ∈ (0, 1) and severance costs v(c). On the other hand, we identify a region of costs in the same interval in which stable networks do not exist and a sequence of networks is repeatedly visited 15 . In the following Proposition, we show that a set of disconnected cliques of the same size can be a stable network, if their size falls within a certain interval that depends on the marginal cost of collaboration c and on the severance cost parameter α. Proposition 8 Consider costs c, c = αc and α ∈ [0, 1]. If the network G consists of a set of k equally sized, disconnected cliques K 1 n , K 2 n , ..., K k n (G having kn nodes in total) then G is stable if 161

+ c(1 -c) c ≤ n ≤ 2 -c (1 -c ) c . ( 21
)
An example of stable graph formed by disconnected cliques of the same size is shown in Figure 6. From Proposition (16) it follows immediately that for a given value of cost c there exist multiple integer values n (the size of the clique) that fit into the interval spanned by the above mentioned upper and lower bounds. Thus, multiple equilibrium networks exist for a given value of marginal cost c and severance cost v(c). Note that the homogeneous size of the clique is only a sufficient condition for stability but it is not necessary. Indeed, the equilibrium networks obtained with computer simulations show clearly that there exist equilibria with disconnected cliques of different sizes (see e.g. limiting but allows for a more simple analytical investigation of the existence of stable networks.

Equally sized disconnected cliques are not the only possible stable networks structures in the interval c ∈ (0, 1) ∩ α ∈ [0, 1]. The next Proposition shows that the spanning star, i.e. the star encompassing all nodes, can be pairwise stable as well, if the size of the star (and therewith the number of firms in the industry) falls within a certain region that depends on the cost c and on the severance cost parameter α.

Proposition 9 Consider costs c, c = αc, α ∈ [0, 1]. The network G consisting of a spanning star K 1,n-1 with 1 + 2-c 2c ≤ n ≤ 1+c 2 (6+c 2 ) 4c 2
is stable. The foregoing results have two important implications in relation to the literature. First, the stable graphs are not necessarily connected. Second, in general they are not minimally connected. Indeed, the multiple clique equilibrium is a disconnected graph in which each component is complete and thus not minimally connected. This is an important feature that for instance distinguishes our model from the "connections" model in Jackson and Watts [START_REF] Jackson | The evolution of social and economic networks[END_REF] and from the linear "two-way flow" model Bala and Goyal [START_REF] Bala | A noncooperative model of network formation[END_REF]. In both such models, the equilibrium networks are always connected, while in the latter they are also minimally connected. Furthermore, both models find that the spanning star is stable for intermediate values of the cost of collaboration. However, differently from both models, in our model the spanning star is never the unique stable network. Indeed, the next Proposition combines together the results of the previous two propositions, the conditions under which the link formation dynamics defined in (5) may lead to two different pairwise stable network topologies for the same level of marginal cost c and severance cost parameter α, namely (i) the set of disconnected equally sized cliques or (ii) the spanning star. Proposition 10 Consider costs c, c = αc, α ∈ [0, 1] and the network G with n nodes such that 1+

2-c 2c ≤ n ≤ 1+c 2 (6+c 2 ) 4c 2 . If there exists an integer k ≤ n, mod (n, k) = 0 such that 1+c(1-c) c ≤ k ≤ 2-c (1-c ) c then G can be stable for at least two cases. (i) G consists of disconnected cliques K 1 k , ..., K d k , n = kd or (ii) G consists of a spanning star K 1,n-1 .
There are at least two stable networks for the same level of marginal cost c (degenerate cost region).

Not all values of marginal cost c and severance cost parameter α lead to pairwise stable networks. Consistently with the concept of Improving Path (cf. 36, , Lemma 1) the next Proposition shows that in the interval (0.586, 0.618), there exists a cycle of repeatedly visited networks, . The Proposition provides explicitly the network structures visited in the cycle. Proposition 11 If we have values of cost 2 -√ 2 = 0.586 < c < 1 2 √ 5 -1 = 0.618 and α ∈ [0.707, 1] then the Improving Path leads to a cycle of networks. In this cycle, a sequence of paths (P 2 , {P 2 , P 2 }, P 4 , P 3 , P 2 ) is repeatedly visited. The graphs which are repeatedly visited are illustrated in Figure [START_REF] Brualdi | On the spectral radius of connected graphs[END_REF]. The fact that for some values of the parameters of the model no network is stable is found also by [START_REF] Jackson | The evolution of social and economic networks[END_REF] and by (30; 31).

Stability vs Efficiency

The existence, for the same level of marginal cost, of multiple equilibrium structures associated with different values of total profits, implies that stable networks can, in general, be inefficient. In particular, we have shown that in the marginal cost interval i ¸n(0, 1), graphs that are not connected can be stable (cf. Propositions 16 and 10), while in that cost region the efficient graph is always connected (cf. Proposition 2). The possible inefficiency of network evolution process stems from externalities inherent in the process of knowledge recombination, described in Section 2.2. Indeed, when a firm decides to create or delete a link it takes into account its private marginal revenue from collaboration (given by the change in the largest eigenvalue of its connected component), but neglects social marginal revenues inherent to that decision. The latter is equal to the sum of changes in the largest eigenvalue of all firms belonging to the same connected component. Thus, it may well be that creating a link is not profitable for the individual firm although it would be profitable from the industry point of view.

Furthermore, the efficient network may not even belong to the set of equilibria, as shown by the next proposition. Proposition 12 Consider a network of size n ≥ 2 c . For cost c < 1 2 the equilibrium network is not efficient. This result can be explained in the following way. Proposition (3) states that, when the marginal cost of link formation is less or equal to 1/2, the complete graph is the efficient graph. However, if the number n of firms in the industry is large enough, the individual marginal revenue of a collaboration is bounded from above by a value decreasing with n (see proof of the proposition). In particular, for n ≥ 2 c the upper bound is always smaller than the marginal cost c. Therefore the complete graph is not stable 17 .

A complete discussion of efficiency and stability would require the determination of total and firm's profits of all possible graphs. Both require the computation of the largest eigenvalue. Unfortunately, there is no closed form solution available for any graph. However, one can provide general results for some special classes of graphs. Table [START_REF] Aghion | Endogenous Growth Theory[END_REF] summarizes the results on efficiency and stability discussed so far and compare them with results for other quite well known classes of graphs in the literature.

Three graphs in the table deserve a special attention. The first is the empty graph, which is never stable nor efficient in the interval [0, 1]. The second one is the complete graph, which is efficient in [0, 0.5], but is never stable for c > 0. As we saw earlier, this is due to the fact that, when the graph becomes very dense, the marginal revenue of an additional link becomes smaller and smaller. The third graph is the star, which can be stable but is never efficient in [0, 1]. In other words, both the star and the complete graph are never stable and efficient at the same time. This is a first important difference with respect to the models in ( 36) and ( 4), where, at least in an interval of the parameters, the star (or, respectively, the complete graph) can be efficient and stable. In our model the tension between efficiency and stability is more pronounced. We were not able to find any efficient graph which is also stable, except from the trivial case of c = 0 in which, due the absence of collaboration cost the complete graph is both stable and efficient.

Moreover, it is interesting to review the properties of the other graphs listed in the table and their mutual relations. A k-regular graph, i.e. a graph in which all nodes have the same degree, yields a revenue proportional to the degree of the nodes, regardless what is the size of the graph. This means that when the degree is small the performance of this graph is rather poor. However, the complete graph is a particular case of regular graph in which all nodes have degree n -1. In this case, the regular graph can be efficient.

The set of cliques of the same size, is stable for particular values of the size n, depending on the level of costs. It can also be efficient, in the particular case of a set consisting of one clique, i.e. the complete graph. In this case however, it is never stable, as noted above. The set of identical cliques is also a particular case of k-regular graph, because the nodes in each clique have the same degree. In a path, the degree of the nodes is two except from the two nodes at the beginning and at the end of the path. In this sense, the graph is similar to a 2-regular graph. Indeed its eigenvalue is a little smaller than the one of 2-regular graph. When the network evolves starting from an empty graph, the first connected graph that is formed is indeed a path of length 2, possibly followed by a path of length 3 (see proof of Proposition 5). In this transition, the largest eigenvalue of the component jumps from 0 to 1 and then to 2 cos( π 4 ) > 1. Instead, when the graph is almost complete, the addition of a link yield a little change in the eigenvalue. Notice that the path of length 3 is also a star with one hub and two peripheral nodes.

A cycle is a closed path and it is in particular a 2-regular graph. In a cycle there is only one walk, which yields a revenue independent on the number of participating firms. As we already noticed in Section 2.3, this is a consequence of the payoff function in this model which differs remarkably in this respect from the one used in other models in the literature (e.g. 4). Finally we also list in the table the bipartite graph because of its relation to the notion of structural holes. Consider a network consisting of few hubs, disconnected among them, and of many peripheral nodes, connected to one or more hubs but disconnected among them. In such a network, the hubs are filling the structural holes among the the peripheral nodes. Such a network is, in particular, a bipartite graph, since the hubs and the peripheral nodes form two separate classes and links connect only nodes of one class to nodes of the other class. Notice that the star is also a particular case of a bipartite graph. The cases n 1 = 1 (or n 2 = 1) would refer to the star K 1,n2-1 (or K 1,n1-1 ).

Topological Properties of Stable Networks

The empirical research on R&D partnerships has investigated in depth the topological patterns of networks of knowledge exchange. From this literature (see e.g. 2; 21; 32; 47), three features emerge as robust stylized facts: (i) R&D networks are sparse, that is the number of actual links is much less than the number of possible links. (ii) Networks are highly clustered, where clusters consist of highly interconnected firms, but different clusters are only sparsely connected. (iii) The distribution of links over the firms is characterized by high dispersion, with few firms being connected to many others.

The analytical study of equilibrium networks in Section 4 has pointed to the existence of equilibrium networks that match some of the stylized facts mentioned above. Indeed, equally sized cliques are characterized by a high clustering, while the spanning star shows high degree heterogeneity. All these networks belong to the set of possible equilibria structures in our model.

In this Section we define an explicit process of network evolution that is a particular case of improving path and we analyze via computer simulation the structural properties of stable networks in our model. In this way, we assess whether our model is also able to generate pairwise stable structures that feature, at the same time, all the stylized facts of R&D networks.

There are several possible processes which would be consistent with the definition of improving path and the set of selected equilibria depends in general on the specific process. In this work, we investigate a stochastic process in which all pairs of firms have the same probability to be selected to revise their R&D collaboration strategy (cf. 55, p. 212). Definition 5 (Myopic Pairwise Dynamics) Let G t denote the graph at time t. We define the network formation process Γ(G) as follows. At the beginning of each period (at times t = 0, T, 2T, ...) a single pair of firms, i and j, is uniformly selected at random.

(i) If the link ij does not currently exist, ij / ∈ G t , then it is created whenever neither player is harmed by the creation and at least one of them strictly gains, i.e.

Graph Class

λ PF = 0 Π = 0 c > n c > 1 G = Kn complete graph λ PF = n -1 Π = (1 -c)n(n -1) c ≤ 1 2 c = 0 G = K n k-regular graph λ PF = k -1 Π = n(k -1)(1 -c) if a k = n see cliques see K n path λ PF = 2 cos π n+1 Π = 2 cos π n+1 -(n -1)c no no G = P n star λ PF = √ n -1 Π = n √ n -1 -2(n -1)c not in b 1 + 2-c 2c ≤ n ≤ 1+c 2 (6+c 2 ) 4c 2 G = K 1,n-1 0 < c < 1 cycle λ PF = 2 Π = 2n(1 -c) no no G = C n bipartite graph c λ PF = √ n 1 n 2 Π = (n 1 + n 2 ) √ n 1 n 2 -n 1 n 2 c no no G = K n1,n2 G = F n,d λ PF ≥ d -1 d Π = λ PF (F n,d ) -2c n 2 + (n -d)
with good no e approx. f

cliques g λ PF = d -1 Π = n(d -1)(1 -c) if h l = 1, d = n, 1+c(1-c) c ≤ n ≤ 2-c (1-c ) c G = {K 1 d , ..., K l d } see K n
Table 1. Summary of the largest real eigenvalue, total profits, efficiency and stability for different types of networks. For the bipartite graphs Kn 1 ,n 2 we assume n 1 > 1 and n 2 > 1. The cases of either n 1 = 1 or n 2 = 1 would refer to the star K 1,n 2 -1 or K 1,n 1 -1 . The path P 3 is equivalent to the star K 1,2 . If the regular graph consists of equally sized cliques and the size of the cliques is stable then obviously the regular graph is stable as well.

a In this case regular graph and complete graph coincide.

b One can show that for c < n n-1+ √ n-1 ∼ 1 for n → ∞, Kn has a higher performance than K 1,n-1 . E.g. for n = 100 we get c < 0.918. c This graph is a generalization of the star K 1,n-1 where one partite set has only one element. d An exact solution is given by the largest root of the cubic polynomial

x 3 -(d -2)x 2 -(n -1)x + (d -2)(n -d) (6).
e One can show that for a fixed value of d, limn→∞ ∆λ PF = 0 and thus it is always profitable to remove a link if n is large (however large the severance cost or small the marginal cost may be). f ∀c, and for large n, total profits of this graph tends to the one of efficient graph, limn→∞ = 0 g We have l cliques of identical size d. h In this case there is one clique and it coincides with the complete graph Kn.

π i (G t + ij, c) ≥ π i (G t , c) ∧ π j (G t + ij, c) ≥ π j (G t , c)∧ π i (G t + ij, c) > π i (G t , c) ∨ π j (G t + ij, c) > π j (G t , c). ( 22
)
or equivalently

λ i (G t + ij) -λ i (G t ) ≥ c ∧ λ j (G t + ij) -λ j (G t ) ≥ c∧ λ i (G t + ij) -λ i (G t ) > c ∨ λ j (G t + ij) -λ j (G t ) > c. (23)
(ii) If the link ij is currently in place, ij ∈ G t-1 , then it is removed whenever at least one of the players strictly gains from the change, with link deletion involving the cost

v(c) = (1 -α)c, α ∈ [0, 1]. More formally π i (G t -ij, c, v) > π i (G t , c, v) ∨ π j (G t -ij, c, v) > π j (G t , c, v), (24)
or equivalently:

λ i (G t ) -λ i (G t -ij) < αc ∨ λ j (G t ) -λ j (G t -ij) < αc (25)
Note that, in the evolution of the network defined above the only element of stochasticity is the sequence of the pairs of firms chosen to create or delete links.

We study stable network structures arising from this process in computational experiments 18 conducted in a large region of the model's parameter space. More precisely, we carried out multiple (50 repetitions for each parameter choice) computer simulations of the network dynamics defined in ( 5) with a fixed number n of firms in the industry 19(n = 50), starting each from an empty network Kn . For each simulation we selected a value for the marginal cost c in the interval (0, 1) and a value for the severance cost parameter α in the interval 20 [0, 0.5]. As the number of chosen values were respectively 12 for the marginal cost and 5 for the severance cost parameter, the total number of computer simulations summed up to 3000. The results of the aforementioned Monte-Carlo experiments are shown in the Figures from ( 9) to [START_REF] Coleman | Social capital in the creation of human capital[END_REF].

The plots in Figure [START_REF] Burt | Structural Holes: The Social Structure of Competition[END_REF] show typical equilibrium networks obtained in simulations for cost of link formation equal to 0.15 and different values of the severance cost parameter α. Recall that severance cost are equal to v = (1α)c, and thus are inversely related to the parameter α. As the plots reveal, in this region of the parameter space the dynamics in our model is able to generate equilibrium structures displaying the complex features that characterize R&D networks observed in reality. In particular, for very high severance costs the equilibrium network contains a giant component with a high degree heterogeneity. On the other hand, as the severance cost associated with link deletion fall down (increasing values of α), we observe a significant increase in the cliquishness of the network, and a reduction of degree heterogeneity.

The insights coming from the foregoing qualitative study are confirmed by a more quantitative analysis of the topological properties of equilibrium graphs. The plots in Figure [START_REF] Carayol | A strategic model of complex networks formation[END_REF] display respectively the mean and the variance of the network degree distribution as functions of the marginal cost c and severance cost parameter α. The mean degree is inversely related to the sparseness of the graph, while degree variance captures the degree heterogeneity. As the plots in the figure make clear, higher cost of R&D collaboration lead to graphs that are more sparse. On the other hand, degree heterogeneity reaches a peak for values of marginal cost close to 0.1, and then falls down as collaboration cost increase. In addition, degree heterogeneity increases with severance costs (decreasing α).

The presence of clusters of highly interconnected firms is a key feature of real world R&D networks (cf. stylized fact number (iii)). As the plots in Figure [START_REF] Coleman | Social capital in the creation of human capital[END_REF] show, this feature is also a characteristic for the equilibrium networks generated by the model. In particular, the average clustering coefficient (Figure [START_REF] Coleman | Social capital in the creation of human capital[END_REF], top-left) is close to one in a wide region of the explored parameter space (c ∈ (0, 0.5), α > 0). Moreover, it is a decreasing function of severance costs v = (1α)c. Finally, note that clustering becomes zero for values of costs greater or equal to 0.7. Further information on the topological features of R&D clusters can be gathered by looking at the average number of connected components, at their average size and the concentration of their size (Figure [START_REF] Coleman | Social capital in the creation of human capital[END_REF], topright, bottom-left and bottom-right respectively). As the plots in the Figure indicate, the the number of connected components is an increasing function of collaboration costs while the average size and its concentration variables are negatively related to collaboration costs. In addition, as the costs of link severance increase the number of components increases, while component size and its concentration decrease.

Joining together the foregoing results we can conclude that sparse equilibrium networks organized in clusters of highly interconnected firms are a distinctive feature of the network dynamics in our model. Moreover, low values of the R&D collaboration costs and high values of the costs of link severance lead to equilibrium structures characterized by a small number of large components, with a highly dispersed degree distribution. As collaboration costs increase and as link severance costs decrease, we observe that equilibrium networks tend to be more and more organized in size homogeneous cliques having only few connections among them.

Conclusions

In this paper, we have investigated the efficiency and the evolution of networks of knowledge exchange across firms. We developed a model in which firms recombine their knowledge stock with the stocks of knowledge of other firms in the industry, in order to introduce innovations in the market. Since each collaboration is costly for firms they face a trade-off between the benefits of new collaborations (in terms of an increase in the expected number of innovations per period) and the cost associated with it. Furthermore, we showed that under mild conditions on the horizon over which the performance of R&D collaborations is evaluated, the benefit the firm receives from the network depends on the growth rate of all walks existing across firms in their connected component. To this end, our model can be seen as extending other popular models in the network formation literature (cf. the "Connections" model in Jackson and Wolinsky, 1996, and the linear "Two-Way Flow" model without decay in [START_REF] Bala | A noncooperative model of network formation[END_REF].

Within the foregoing framework, we characterized the topology of the efficient graph for any level of the marginal cost of collaboration. We showed that, when the marginal cost of maintaining collaborations is low, the efficient network is the complete graph. Thus, when collaboration costs are low, a network of densely connected firms maximizes industry total profits. On the other hand, as the marginal cost of collaboration increases it is better for the industry network to display the presence of structural holes. In particular, for intermediate costs of collaboration the efficient graph belongs to the class of nested split graphs, characterized by the presence of hubs linking a clique to a set of disconnected firms. Furthermore, we showed that nested-split graphs are characterized by significant cross-firm profit inequality, increasing both in collaboration costs and size of the industry. Finally, we showed that for very large costs of collaboration the empty graph is efficient.

We then studied the existence of equilibrium graphs in the model, and the relation between equilibrium and efficiency. For this purpose, we employed the notion of "Improving Path" (cf. 36), and we assumed that the deletion of existing connections involves a severance cost. In line with the concept of Improving Path (see 36, Lemma ( 1)), we identified regions of collaboration and severance costs in which there exist either pairwise stable graphs or a closed cycles of networks. As far as pairwise stable networks are concerned, we showed that different network structures are stable for the same level of costs. In particular, we identified regions of the collaboration and severance costs in which (i) the class of (different-size) equisized disconnected cliques is stable, (ii) the spanning star (i.e. the star encompassing all firms in the network), and the class of size-homogeneous disconnected cliques are stable. In turn, the source of multiplicity of equilibria lies in (i) the strong path dependency involved in partner selection decisions, (ii) in the presence of external effects affecting marginal revenue of collaborations for firms belonging to the same connected component and (iii) the inertia arising from the presence of a severance cost associated with link deletion. The presence of multiple stable structures for the same level of collaboration costs implies that, in general, efficient structures are not attained in our model. Furthermore, we identified a region of the size of the industry and of costs in which the efficient graph is never attained.

Finally, we investigated the topological characteristics of pairwise stable graphs in our model, to see whether they are able to replicate the stylized facts on empirically observed R&D networks. To this end, we studied via computer simulations the properties of equilibria selected under a two-sided myopic pairwise dynamics (cf. 55). The results of our simulations show that the existence of a region of low marginal costs of collaboration and high costs of link deletion in which the aforementioned dynamics is able to select pairwise stable structures matching the stylized facts on R&D networks.

The present work could be extended at least in three ways. First, the model could be extended to account for industry demand, for example like in [START_REF] Goyal | R&D networks[END_REF], and then study how the efficiency and dynamics of network structure may change when firms operate markets that are interdependent. Second, one could investigate whether the foregoing results about the properties of stable networks are robust to different link updating algorithms. For example, one could study the effect of network dynamics of introducing firms pursuing different strategies, for example of the kind explored in (4). Likewise, one could depart from the strong assumptions we made about the knowledge of the network the firms have, and about their ability to forecast the stream of innovations out of a given network of collaborations, and rather pursue the way of studying the efficiency and emergence of network structures when firms follow more simple rules of behavior, for example of the kind suggested in the empirical work by [START_REF] Powell | Network dynamics and field evolution: The growth of interorganizational collaboration in the life sciences[END_REF]. Third, in the present model we assumed that the knowledge bases of firms in the industry were sufficiently homogeneous to be transferred across firms. However, the process of knowledge transfer across firms is likely to be shaped by its degree of tacitness, as well as by the existing technological complementarities across sectors and firms' knowledge bases. In addition, as argued at more length in (19; 44) technological dynamics into an industry, i.e. the evolution of the nature of problem solving strategies and learning processes, is likely to be a fundamental determinant of any industrial structure, and in particular of the network of firms of R&D collaborations. A further analysis of R&D network dynamics and efficiency should therefore embed all the foregoing ingredients related to industry technology, and try to investigate how they may affect the revenues and costs of the process of knowledge recombination.

λ PF -ẋi(t) xi(t) = λPFxi(t)-ẋi(t) xi(t) = n j=1 cj vjie λ j t (λPF-λj ) xi(t) = n j=2 cj vjie λ j t (λPF-λj ) n j=1 cjvji e λ j t . ( .2)
In the numerator of (.2) we obtain a sum of exponentials with one exponential term less than in the denominator, namely the one with the largest real eigenvalue in the exponent.

We have that the sum of exponentials converges to the exponential with the largest real eigenvalue. Consider for example ae λ1t + be λ2t = ae λ1t 1 + b a e (λ2-λ1)t ∼ ae λ1t for large t. This also holds in general. Thus we get

λ PF -lim t→∞ ẋi (t) x i (t) = lim t→∞ c 2 v 2i e λ2t (λ PF -λ 2 ) c 1 v 1i e λPFt ∝ lim t→∞ e -(λPF-λ2)t = 0. ( .3)
In what follows we compute a lower bound for the order of convergence. Consider the real eigenvalues λ PF = λ 1 ≥ λ 2 ≥ ... ≥ λ n of the adjacency matrix A. We have that n j=1 λ 2 i = tr(A 2 ) = 2m [START_REF] Bollobas | Modern Graph Theory[END_REF]. Thus, we get

λ 2 2 = 2m -λ 2 PF - n j=3 λ 2 i ≤ 2m -λ 2 PF ≤ 2m -2m n 2 = 2m(n 2 -2m) n 2 . ( .4)
Here we use the fact that λ PF ≥ 2m n [START_REF] Bollobas | Modern Graph Theory[END_REF]. Therefore we get

λ PF -λ 2 ≥= 2m -2m(n 2 -2m) n , ( .5)
which is positive and a monotonic increasing function for n 2 /4 < m ≤ n(n -1)/2.

Proof of Corollary (1)

The proof follows directly from an application of the following Lemma.

Lemma 3 Consider a continuous function f : [0, ∞) → R that converges to a finite value λ, i.e. lim t→∞ f (t) = λ < ∞. Then lim T →∞ 1 T T 0 f (t)dt = λ. ( .6
)

Proof of Lemma (3) Denote F (T ) = 1 T T 0 f (t)dt.
We can write

F (T ) = 1 T τ 0 f (t)dt ≤cτ + 1 T T τ f (t)dt. ( .7)
The first integral in the above expression is finite since any continuous function on a compact set (0, τ ) has a maximum denoted by c. Since f (t) converges to λ for any we can find a τ ( ) such that for all t ≥ τ we have |f (t) -λ| < . Thus we get

|F (T ) -λ| ≤ | 1 T cτ + T τ f (t)dt -λ| ≤ 1 T |c|τ + | T τ f (t)dt -λT | ≤ 1 T |c|τ + T τ |f (t) -λ|dt + (T -τ -T )λ ≤ 1 T (|c|τ + (T -τ ) -τ λ) = (|c|-λ)τ T + T -τ T ≤ |c|τ T + . ( .8)
We define

= |c|τ T + τ = |c|τ -. ( .9)
Since ∂ ∂T = -|c|τ T 2 < 0 we have that |F (T ) -λ| < for T > τ . For any ≥ 0 we can find an < and the corresponding τ ( ) from which we compute τ ( ) such that |F (T ) -λ| < for all T > τ ( ). This means that lim T →∞ F (T ) = λ.

Proof of Lemma (2) Since G 1 and G 2 are connected, we have that m 1 ≥ n 1 -1 and m 2 ≥ n 2 -1 [START_REF] West | Introduction to Graph Theory[END_REF]. We now consider different cases for the number of edges in the components.

(i) m 1 ≥ n 1 and m 2 ≥ n 2 : Assume that the largest eigenvalue of

G 1 is λ PF (G 1 ) ≥ λ PF (G 2
). Let G be the graph obtained as follows: for each node in G 2 we rewire one incident edge to a node in G 1 . In this way, all nodes in G 2 are connected to G 1 .

The number of rewired edges is n 2 (and there are at least that many edges since m 2 ≥ n 2 by assumption).

There exists a relationship between the largest real eigenvalue of a graph and those of its subgraphs [START_REF] Cvetkovic | Spectra of Graphs: Theory and Applications[END_REF]

: if H is a subgraph of G, H ⊆ G, then λ PF (H) ≤ λ PF (G). Therefore, λ PF (G ) ≥ λ PF (G 1 ) ≥ λ PF (G 2 )
. And total profits of G are

Π(G ) = (n 1 + n 2 )λ PF (G ) -2(m 1 + m 2 )c ≥ n 1 λ PF (G 1 ) + n 2 λ PF (G 2 ) -2(m 1 + m 2 )c = Π(G 1 ) + Π(G 2 ). ( .10)
(ii) m 1 ≥ n 1 and m 2 = n 2 -1: If m 2 = n 2 -1 then the largest real eigenvalue of G 2 is at most the one of the star K 1,n2-1 with λ PF (G 2 ) ≤ √ n 2 -1 (33)
. We construct the graph G by connecting all nodes of K 1,n2-1 to a single node in G 1 and including the remaining isolated node by adding one more edge. The graph

G has an eigenvalue λ PF (G) ≥ λ PF (K 1,n1+n2-1 ) = √ n 1 + n 2 -1.
Otherwise, the edges in G are redistributed to form a star K 1,n1+n2-1 and the remaining edges attached at random. Since λ PF is an increasing function of the number of edges in the graph the inequality follows. We obtain

Π(G) = (n 1 + n 2 )λ PF (G) -2(m + 1)c Π(G 1 ) + Π(G 2 ) = n 1 λ PF (G 1 ) + n 2 √ n 2 -1 -2 (m 1 + (n 2 -1)) m c ( .11)
Thus, we get

Π(G) -(Π(G 1 ) + Π(G 2 )) = Π(G) -(Π(G 1 ) + Π(K 1,n2-1 )) = n 1 (λ PF (G) -λ PF (G 1 )) ≥0 +n 2 (λ PF (G) - √ n 2 -1) -2c ≥ n 2 (λ PF (G) - √ n 2 -1) -2c. ( .12)
With

λ PF (G) ≥ √ n 1 + n 2 -1 ≥ √ n 2 + 1 if n 1 ≥ 2
(by assumption). If the last inequality above is large than 0, we have that

√ n 2 + 1 - √ n 2 -1 ≥ 2c n 2 . ( .13)
If 0 ≤ c ≤ 1, this inequality is true if n 2 ≥ 2 (by assumption). (iii) m 1 = n 1 -1 and m 2 = n 2 -1: If m 1 = n 1 -1 and m 2 = n 2 -1, then both components are stars, K 1,n1-1 and K 1,n2-1 with eigenvalues √ n 1 -1 and √ n 2 -1. Construct the graph G by connecting n 2 -1 nodes from K 1,n2-1 to the central node in K 1,n1-1 .
Then attach an edge to the remaining isolated node to obtain a star

G = K 1,n1+n2-1 . Π(G) = Π(K 1,n1+n2-1 ) = (n 1 + n 2 ) √ n 1 + n 2 -1 -2c(n 1 + n 2 -1) ( .14)
For the difference we get

Π(G) -(Π(K 1,n2-1 ) + Π(K 1,n2-1 )) = n 1 ( √ n 1 + n 2 -1 - √ n 1 -1) +n 2 ( √ n 1 + n 2 -1 - √ n 2 -1) -2c ≥ (n 1 + n 2 )( √ n 1 + n 2 -1 - √ n 1 -1). ( .15)
W.l.o.g. we have assumed that n 1 ≥ n 2 . The expression above is larger or equal than 0 if

(n 1 + n 2 ) ≥n1+2 ( √ n 1 + n 2 -1 - √ n 1 -1 ≥ √ n1+1- √ n1-1 ) ≥ 2 ≥ 2c, ( .16)
with n 2 ≥ 2. We get

√ n 1 + 1 - √ n 1 -1 ≥ 2 n 1 + 2 , ( .17)
and the last inequality holds for n 1 ≥ 2. (iv) n 1 ≥ 2 and n 2 = 1: We have one isolated node and a connected graph

G 1 . Total profits are Π(G) = n 1 λ PF (G 1 )-2m 1 c. Denote the graph G obtained by connecting the isolated node to G 1 . Then Π(G ) = (n 1 + 1)λ PF (G ) -2(m 1 + 1)c ≥ Π(G) + (λ PF (G ) -2c), ( .18)
We now consider three more cases:

(1) If n 1 ≥ 4, then m 1 ≥ n 1 -1 (since G 1 is connected by assumption). We can construct a star K 1,n1-1 plus additional edges from G 1 and connect the isolated node to it. Denote the resulting graph G . Then,

λ PF (G ) ≥ λ PF (K 1,n1 ) = √ n 1 ≥ 2. Thus, Π(G ) -Π(G) ≥ 0 if λ PF (G ) ≥ 2 ≥ 2c for c ∈ [0, 1].
(2) If n 1 = 3, then G 1 is either a path P 3 of length 3 or a cycle C 3 containing 3 nodes. We connect the isolated node to G 1 . In the case of G 1 = P 3 we get

Π(G ) -Π(G) = 4 √ 3 -6c Π(G ) -(3 √ 2 -4c) Π(G) = 2.69 -2c > 0, ( .19)
where the last inequality follows from c ∈ [0, 1]. In the case of

G 1 = C 3 we obtain Π(G ) -Π(G) = 42.17 -8c Π(G ) -(32 -6c) Π(G) = 2.68 -2c > 0 , ( .20)
again, using c ∈ [0, 1].

(3) For n 1 = 2 we connect the isolated node to G 1 = P 2 and again denote the resulting connected graph G . We have that

Π(G ) -Π(G) = 3 √ 2 -4c Π(G ) -(21 -2c) Π(G) = 2.24 -2c > 0 , ( .21)
with c ∈ [0, 1]. (v) n 1 = 1 and n 2 = 1: We have two isolated nodes with total profits Π(G) = 0. If we connect the nodes via an edge we have Π(G ) = 2(1c). Since 0 ≤ c ≤ 1 total profits in the connected graph G are higher. The above cases consider all possible cases of disconnected graphs and show that total profits Π can be increased by connecting them.

Proof of Proposition (2) For a contradiction assume that the efficient graph G is disconnected (and all connected graphs have smaller total profits than G). Since G is disconnected then it has at least two components. With proposition (2) each pair of components can be connected, resulting in a graph with higher total profits. Ultimately all components of G can be connected, yielding a connected graph G with at least the total profits of G. This is a contradiction to the assumption that the efficient graph is disconnected.

Proof of Proposition (3)

We prove each claim of the Proposition as follows.

(i) From Lemma (2) we know that the efficient graph is connected. Moreover, ( 8) have shown that among the connected graphs, the graphs with maximal eigenvalue have a stepwise adjacency matrix. We have mentioned already that these graphs are referred to connected nested split graphs (3). (ii) We have introduced the graph F n,d in Section 3.1. In order to prove the claim, we derive a lower bound for the total profits of F n,d , as well as an upper bound for the total profit of the efficient graph G * . We then show that, if one chooses d appropriately, the relative difference between the two bounds vanishes for large n.

Π(F n,d ) = nλ P F (F n,d ) -2m(d)c ≥ n(d -1) -2m(d)c. ( .22)
Since the inequality above is valid for any integer d, such that 1 ≤ d ≤ n, we are interested in the value of d that maximizes the right hand side of Eq. (.22), that is

d = argmax 1≤k≤n {n(k -1) -2m(k)c}, ( .23)
where m(k) = n 2 + (nk) and k ∈ N + . By computing the first and second derivative of the objective function n(k -1) -2m(k)c with respect to k, one finds that its maximum occurs for k = n+3c 2c . For simplicity, one can take d as the closest integer to this value 21 . Notice that, as a consequence, d converges to n 2c for large n.

Replacing d = n+3c 2c in Equation (.22), we obtain a general lower bound, which is independent of d, and given by

Π(F n,d , c) ≥ n 2 + n(2c -8c 2 ) + 9c 2 4c . ( .24)
We now derive an upper bound for total profits of the efficient network G * . The largest real eigenvalue of a connected graph is at most √ 2mn + 1 [START_REF] Hong | Bounds of eigenvalues of graphs[END_REF] and from this it follows immediately that total profits of G * are bounded by

Π(G * , c) ≤ n √ 2m -n + 1 -2mc. ( .25)
We have shown already that for cost c ≤ 1/2 the efficient graph is complete. Therefore, we are interested in values of cost c > 1/2. Assuming that c > 0.5, the number m of edges that maximize the right hand side of Equation (.25

) is m = n 2 +4nc 2 -4c 2 8c 2
. Replacing such value of m, we obtain an upper bound that is independent on the number m of edges,

Π(G * , c) ≤ n 2 -4nc 2 + 4c 2 4c . ( .26)
At this point, combining Equation (.24) and (.26), we obtain that the relative difference in the total profits of the graph F n,d and the graph G * is bounded from above

= Π(G * , c) -Π(F n,d , c) Π(F n,d , c) ≤ 2c(2c -1)n -5c 2 n 2 + 2c(1 -2c)n + 9c 2 . ( .27)
The expression on the right hand side of the above inequality converges to zero for n large, and therefore the relative difference in total profits vanishes for n large. (iii) Since for the complete graph it is λ PF = n -1 and m = n(n-1)

2

, its total profits are given by

Π(K n ) = n(n -1) -2 n(n -1) 2 c = n(n -1)(1 -c). ( .28)
On the other hand, the largest real eigenvalue λ PF of a graph G with m edges is bounded from above so that λ PF ≤ 1 2 ( √ 8m + 1 -1) (53) 22 . For the performance of the system we then have

Π = n i=1 λ PF (G i ) -2mc ≤ n max 1≤i≤n λ PF (G i ) -2mc ≤ n 2 ( √ 8m + 1 -1) -2cm =: b(n, m, c), ( .29)
with n ≤ m ≤ n 2 . For fixed cost c and number of nodes n, the number of edges maximizing Eq. (.29) is given by m

* = n 2 -c 2 8c 2 if n 2 -c 2 8c 2 < n 2 and m * = n(n-1)
2 if 21 The results on the relative error that we obtain later in this proof are still valid under this assumption. 22 Notice that a similar result can be obtained using an alternative bound for connected graphs, λ PF ≤ √ 2m -n + 1 due to (33)

n 2 -c 2 8c 2 > n 2 .
The graph with the latter number of edges is the complete graph K n . Inserting m * into Eq. (.29) yields

b(n, m * , c) = n 2 ( n 2 -c 2 c 2 + 1 -1) -n 2 -c 2 4c , if c > n 2n-1 , n(n -1)(1 -c) = Π(K n ), if c < n 2n-1 .
(

The bound for c ≤ n 2n-1 ∼ 1 2 coincides with the performance of the complete (i) With i d i = 2m we can write the degree variance as follows

σ 2 d = 1 n n i=1 d i -2m n 2 = 1 n n i=1 d 2 i -2m n 2 . ( .31)
Using then the fact that the graph F n,d contains one node with degree n -1 (the hub), d -1 nodes with degree d -1 (those in the clique) and nd nodes with degree 1, we get

σ 2 d (F n,d ) = 1 n (n -1) 2 + (d -1) 3 + (n -d) - 2m n 2 . ( .32)
We now replace in the equation above the value of d that maximizes total profits for the graph F n,d , d = n+3c 2c , as found from Equation (.23), as well as the corresponding value of m, given by m(d) = n 2 +8c 2 n-9c 2 8c 2 . As a result, one obtains the degree variance and this expression is of quadratic order in n, σ 2 d = O(n 2 ). (ii) The coefficient of variation of the degree is defined as c v = σ d / d. Recalling that the average degree is d = 2m/n and replacing, as above, the value of d that maximizes total profits, d = n+3c 2c , and the corresponding value of m, one obtains an expression in n and c. The limit of large n for this expression is well defined and equal to lim n→∞ c v = (2c -1).

(

(iii) [START_REF] Gutman | The variance of the vertex degrees of randomly generated graphs[END_REF] have shown that the degree variance of a random graph G(n, m) with n nodes and m links is given by

σ 2 d (G(n, m)) = 2m(n 2 -n -2m) n 3 + n 2 . ( .34)
Replacing m as in (ii), the expression above turns out to be of order O(n), and consistently, the ratio of (.32) and (.34) is of order O(n).

Proof of Proposition ( 5

However, along the Improving Path, y m starts off positive. For instance, starting from an empty network, the first link added yields a pair (i.e. a path of length 2, P 2 23 ), with an eigenvalue λ PF = 1, which yields y m = 1 -2 n > 0 for n > 2. If a second link is added to one of the nodes of the pair, a path of three nodes is formed, with eigenvalue λ PF = 2 cos(π/4) = 1.41 (see Table 1) and y m = 2 cos(π/4) -4

n . Therefore, we can always find an integer m 3 ≥ 1, such that ( 1 For any given cost, we can find n large enough so that the marginal revenue is smaller that the cost for some m * . This concludes the proof.

Proof of Proposition ( 6) If costs are zero, c = 0, then the change in eigenvalue equals the change in payoff. Since (in a connected graph G) every created link strictly increases λ PF [START_REF] Horn | Matrix Analysis[END_REF] and accordingly the payoff, the complete graph K n is reached eventually. Proof of Proposition [START_REF] Cvetkovic | Spectra of Graphs: Theory and Applications[END_REF] The structure of the Proof is as follows. We want to show that the graph G consisting of k cliques of the same size is stable, that is no link is removed or created. For the removal, we can focus on links between nodes in a same clique, since these are the only links in G. Thus, in Proposition [START_REF] Cowan | Network structure and the diffusion of knowledge[END_REF] we show that, for any pair of nodes in a same clique, the link is not removed as long as the size of the clique is smaller than a given bound b r , n ≤ b r = 2-c (1-c ) c . For the creation of links, we can focus on links between nodes in different cliques, since these are the only new links that can be added to the graph. Thus, in Proposition [START_REF] Cowan | Structural holes, innovation and the distribution of ideas[END_REF] we show that for any pair of firms belonging respectively to different cliques, a link between them is not created as long as the size of the clique is larger than another bound b This is a remarkable finding as it implies that for those values of cost, there is a multiplicity of equilibria. Indeed for a given value of cost, the stable graphs are all the configurations with cliques of the same size n, where n varies among the integers included in the interval [b c , b r ].

Proof of Proposition

c , n ≥ b c = 1+c(1-c)
This concludes the Proof of the Proposition. Propositions ( 16) and ( 13), used for this Proof, are stated and provided below.

Proposition 13 Consider a clique K n and denote by K nij the graph obtained from K n by removing an edge ij.

Then λ PF (K n ) -λ PF (K n -ij) > c if n ≤ 2-c (1-c ) c .
Proof of Proposition (13) Denote the matrix obtained from the adjacency matrix A of K nij, and subtracting the variable λ on the diagonal of A by M = A -λI. M is a block matrix of the form

M =   K B T B D   , ( .39)
with submatrices 24

K =             -λ 1 • • • • • • 1 1 -λ . . . . . . . . . . . . . . . 1 1 • • • 1 -λ             (n-2)×(n-2) , ( .40)
B =   1 1 1 1 1 1 • • • 1 1 1 1 1 1 • • •   2×n , ( .41)
D =   -λ 0 0 -λ   2×2 . ( .42)
Since M is a block-matrix [START_REF] Horn | Matrix Analysis[END_REF] we can write det(M) = det(K) det(P). (

We have the following Lemma: 24 The numbers at the bottom right of the matrix indicate the dimension of the matrix.

Lemma 4

det             a 1 • • • • • • 1 1 a . . . . . . . . . . . . . . . . . . 1 1 • • • • • • 1 a             n×n = ((n -1) + a) (a -1) n-1 . ( .44)
Proof of Lemma (4) The above determinant can be written as det (U -(1a)I), where U is a matrix consisting of all ones, u ij = 1 i, j = 1, ..., n and I is the identity matrix. Hence, the eigenvalues of the above matrix are minus 1a the eigenvalues of U. U has eigenvalues n and 0 with multiplicities 1 and n -1 respectively [START_REF] Horn | Matrix Analysis[END_REF]. Therefore, we can write for the determinant (n

-(1 -a)) (0 -(1 -a)) n-1 = ((n -1) + a) (a -1) n-1 .
Thus, we get for the determinant of

K det K = -((n -1) -λ) (1 + λ) n-1 . ( .45)
The Schur complement is P = D -BK -1 B T . Multiplying the inverse of K with B from the left and B T from the right we obtain

BK -1 B T = ||K -1 || 1   1 1 1 1   ( .46)
where ||K -1 || 1 is the sum of all elements in the matrix K -1 (the l 1 norm of the matrix K -1 (34)). By computing K -1 K = I one can verify that

K -1 =      n-4-λ (λ-(n-3))(1+λ) - 1 (λ-(n-3))(1+λ) • • • - 1 (λ-(n-3))(1+λ) . . . . . .      . ( .47)
And, by summation over the elements in K -1 , we obtain ||K -1 || 1 = n-2 (n-3)-λ . Consequently, the determinant of the Schur complement P is given by det

(P) = (1 + λ) n-3 λ λ 2 -(n -3)λ -2(n -2) . ( .48)
The largest real eigenvalue of K nij is given by the root of

λ 2 -(n -3)λ -2(n -2) = 0. ( .49)
Thus we get

λ PF = 1 2 n -3 + n 2 + 2n -7 . ( .50)
For the change in eigenvalue ∆λ

PF = λ PF (K n ) -λ PF (K n -ij) we obtain ∆λ PF = 1 2 n + 1 -n 2 + 2n -7 , ( .51)
since λ PF (K n ) = n -1. This is a decreasing function in n. Then for n ∈ N, ∆λ PF > c if n ≤ 2 -c (1 -c ) c . ( .
M =   K B B T K   , ( .53)
K =         -λ 1 • • • • • • 1 1 -λ . . . . . . . . . 1 1 • • • 1 -λ         n×n . ( .54)
Due to the symmetry of the graph we can consider a matrix of the following form, where we have put the one on the diagonal indicating the link between the cliques,

B =                   0 • • • • • • 0 . . . . . . . . . . . . . . . 0 . . . • • • 0 1 0 • • • . . . 0 . . . . . . . . . . . . . . . 0 • • • • • • 0                   n×n , ( .55)
with the Schur complement

Q = K -B T K -1 B. ( .56)
For the determinant of M we have det M = det(K) det(Q). The determinant of K is given by det

(K) = (1 + λ) n-3 (λ -n + 3). ( .57)
The inverse of K is already given in (.47) 25 . W.l.o.g. the Schur complement Q is given by

Q =            -λ 1 • • • • • • 1 1 -λ . . . . . . . . . -λ 1 1 • • • • • • 1 -λ + λ-(n-2) (λ-(n-1))(1+λ)            . ( .58)
In the next step we make use of the following Lemma:

Lemma 5 det             b 1 • • • • • • 1 1 a . . . . . . . . . . . . . . . a 1 1 • • • • • • 1 a             n×n = (1 -n + (n -2)b + ab) (a -1) n-2 . ( .59)
Proof of Lemma ( 5) We give a proof by induction. For n = 2 we get det

  b 1 1 a   2×2 = ab -1 = (b(2 -2) + ab -(2 -1))(a -1) 0 . ( .60)
For n = 3 we get det

     b 1 1 1 a 1 1 1 a      3×3 = a 2 b -2a + 2 -b = (b + ab -2)(a -1). ( .61)
For the induction step we apply a Laplace expansion of the determinant in (.59) into Minors.

b det

            a 1 • • • • • • 1 1 a . . . . . . . . . . . . . . . a 1 1 • • • • • • 1 a             (n-1)×(n-1) -(n -1) det             1 1 • • • • • • 1 1 a . . . . . . . . . . . . . . . a 1 1 • • • • • • 1 a             (n-1)×(n-1)
(.62) 25 Note that here the matrix K has dimension n × n

For the first determinant we can use Lemma (4) and for the second the induction hypothesis in order to obtain

b ((n -2) + a) (a -1) n-2 -(n -1)(a -1) n-2 . ( .63)
Now we can compute the determinant of the Schur complement

Q det Q = -(1 -n + (n -2)q -λq) (1 + λ) n-2 (.64) q := -(n -2) + λ (-(n -1) + λ)(1 + λ) -λ. ( .65)
λ PF is given by the largest root of det Q = 0. We obtain

λ PF = 1 2 (n -1 + √ n 2 -2n + 5). The change in the largest real eigenvalue is ∆λ PF = 1 2 (n -1 + √ n 2 -2n + 5) -(n -1) = 1 2 (1 -n + (n -2)n + 5), (.66) since λ PF (K n ) = n -1. Thus, ∆λ PF < c if n ≥ 1 + c(1 -c) c . ( .67)
For costs c = 0.5 we get n ≥ 2 and for c = 1 we get n ≥ 1.

Proof of Proposition ( 9) In order to proof the stability of the spanning star K 1,n-1 (connecting all nodes in the network), we have to consider two cases: (i) the creation of a link and (ii) the removal of a link. (i) We consider the creation of a link between the nodes in the star. The normalized eigenvector associated with the largest real eigenvalue λ PF is given by 1 2(n-1) (1, ..., 1, √ n -1, 1, ..., 1) T . ( 42) found an upper bound for the largest real eigenvalue λ PF and corresponding eigenvector x of an undirected graph G if an edge ij is added

λ PF (G + ij) -λ PF (G) < 1 + δ - δ(1 + δ)(2 + δ) (x i + x j ) 2 + δ(2 + δ + 2x i x j ) , ( .68)
where δ denotes the minimum degree in the graph G26 . Applying Eq. (.68) to the star K

1,n-1 gives ∆λ PF = λ PF (K 1,n-1 + ij) -λ PF (K 1,n-1 ) < 2 3-4n+2n 2 . The link ij is not created if ∆λ PF < c or equivalently n > 1 + 2 -c 2c . ( .69)
This is a decreasing function in c. For c > 2 3 this means that n ≥ 3. (ii) The change in eigenvalue by removing a link from K 1,n-1 is given by ∆λ

PF = λ PF (K 1,n-1 ) -λ PF (K 1,n-2 ) = √ n -1 - √ n -2. A link is not removed from the star if ∆λ PF > c or equivalently 2 < n < 1 + c 2 (6 + c 2 ) 4c 2 . ( .70)
Putting the bounds obtained in (i) and (ii) together we get the desired Proposition.

Proof of Proposition [START_REF] Coleman | Social capital in the creation of human capital[END_REF] A link between two disconnected firms is created if the largest real eigenvalue of the connected component of the firms after the link is created increases more then the cost, i.e. ∆λ PF > c. Similarly an existing link is removed if the largest real eigenvalue of the connected component of the firms after the link is removed does not decrease more then the cost, i.e. |∆λ PF | < c = αc. We therefore have to consider the change in eigenvalue by the creation or removal of a link and compare it to the cost. The proof of Proposition ( 11) is composed of two steps. (i) We show that in every period t in the network formation process Γ(G) = G 0 , G 1 , ... the network G t , t ≥ 1, consists only of graphs from the set S = {∅, P 2 , P 3 , P 4 }, where ∅ denotes the set of isolated nodes. (ii) We show that there exists a cycle, i.e. a sequence of repeatedly visited graphs, C = (P 2 , {P 2 , P 2 }, P 4 , P 3 ), in which each graph is an improvement over the previous graph in the sequence C [START_REF] Jackson | The evolution of social and economic networks[END_REF]. Since all the graphs in the set S can be found in the cycle C, starting from any of the graphs in S, the network formation process will proceed to the next graph in the cycle C. Therefore, for the given values of α and cost c, c respectively, we can infer that there does not exist a pairwise stable equilibrium network.

(i) We give a proof by induction on the periods t ≥ 1 of the network formation process Γ(G). The induction basis is period t = 1. The network G 1 is obtained from the empty network G 0 (initial network) by the formation of a link and thus contains only a P 2 and isolated nodes, both graphs are contained in the set S. Now we assume that the network at time t > 1 consist only of graphs in the set S (induction hypothesis). The induction step consists in showing from G t to G t+1 , no other graphs than the ones in the set S will be created. This will conclude this part of the proof. In order to prove the induction step, we observe that in the network formation process Γ(G), at time t, a pair of nodes, say i and j, is selected at random. Either i and j are already connected in G t or they are not. In any case, they both belong by assumption to one of the graphs in S. All the possible cases can be grouped as follows.

(a) Both nodes are isolated. We show that the empty graph evolves into a P 2 . The creation of a link between two isolated nodes results in ∆λ PF = 1. Since by assumption c < 1, the link is indeed created. (b) At least one of the nodes, say i, is part of a P 2 . In this case, we show that the only possible evolution step is from two P 2 to one P 4 . (i) Link creation. Figure (.3) shows all possible distinct graphs that can be obtained depending on which graph belongs the second node, j, and in which position. Each of these possible graphs is named with a number in the following way. For instance, when j is in another P 2 , the possible positions in that P 2 result both in one same graph labelled as 1. When j is in a P 3 , there are two possible distinct resulting graphs, labelled as 2.1 and 2.2. Similarly, we label the graphs resulting in the remaining case that j is in a P 4 . Table (.1) report the increase of the largest eigenvalue of the graph when the link is created in all the possible cases. For instance, consider the graph 2.1 resulting from a P 2 and a P 3 with the creation of a link. Before the creation of the link, node i is in a P 2 which has λ P F = 1 and node j is in a P 3 graph which has λ P F = √ 2. Since the link formation rule requires that both nodes will benefit after the creation of the link, we have to consider the worst case for the initial graph, which means the highest of the two values, i.e. λ P F = √ 2 = 1.414. For the resulting graph 2.1 we have λ P F = √ 3 = 1.732, and therefore an increase of eigenvalue ∆λ P F = 0.318 which is smaller than the cost c = 0.586. It follows that this link will not be created. After analyzing all the other cases, we can see that only the case 1 results in an increase in the largest real eigenvalue ∆λ PF = 0.618 that is higher than the lower bound of the cost c > 2 -√ 2 = 0.586. This implies that the only possible evolution step at this point is the formation of one P 4 starting from two P 2 . Notice that P 4 is in the set S. (ii) Link deletion. A link is deleted if this beneficial to at least one of the two firms concurrent to the link, or, equivalently, if |∆λ PF | < c = cα. In the case we are considering, by assumption at least one of the nodes is in a P 2 and we examine the deletion of a link. This implies that the two nodes form a P 2 , which has λ PF = 1. The deletion of the link implies to evolve into an empty graph which has λ PF = 0, yielding |∆λ PF | = 1. Since, by assumption we have that c > 2 -√ 2, the case of cα > 1 implies that the link is removed only if α > 1 2-√ 2 = 1.707. But we have assumed that α ∈ [0, 1] and therefore the link is not removed.

(c) At least one of the nodes is part of a P 3 . In this case, we show that if α ∈ [0.707, 1] then the only possible evolution step is from one P 3 to one P 2 and one isolated node. (i) Link creation. Figure (.4) shows all possible graphs that can be obtained by adding a link when at least one of the selected nodes is part of a P 3 . Table (.2) shows the increase in eigenvalue for all these possible graphs.

From the Table we can see that in none of the cases the increase in eigenvalue is higher than the lower bound of the cost. Thus, no link is created. the link is removed and we obtain a single connected pair P 2 and one isolated node. Both are contained in the set of graphs {∅, P 2 , P 3 , P 4 }. (d) At least one of the nodes is part of a P 4 . In this case, we show that if α ∈ [0.707, 1] then the only possible evolution step is from one P 4 to one P 3 and an isolated node. (i) Link creation. Figure (.5) shows the possible graphs that can be obtained by adding a link when at least one of the selected nodes is part of a P 4 . Table (.2) shows the corresponding increase in eigenvalue. From the Table we can see that in none of the cases the increase in eigenvalue is higher than the lower bound of the cost. Thus, no link is created. = 0.348 which is certainly true since we have assumed that α ≥ √ 2-1 2-√ 2 = 0.707. Thus, the link is removed under the above made assumptions on cost and α and we obtain a path of length three, P 3 , which is in the set of graphs {∅, P 2 , P 3 , P 4 }.

P 3 3
P 4 3
In case (B) we have that ∆λ PF = 1 -1 2 (1 + √ 5). This link is removed

for |∆λ PF | ≤ c = cα implying that α ≥ |1-1 2 (1+ √ 5)| 2- √ 2
= 1.055. Since we have assumed that α ∈ [0, 1] this cannot be true. Therefore, the link is not removed. Notice that in all the cases the graphs created belong to the set S, as we wanted to prove. (ii) From the preceding analysis we can infer two facts: First, the individual profits of the firms involved in the creation or removal of a link always increase along the closed sequence of graphs C = (P 2 , {P 2 , P 2 }, P 4 , P 3 .P 2 ), as it is illustrated in Figure [START_REF] Brualdi | On the spectral radius of connected graphs[END_REF]. Therefore, this is an Improving Path [START_REF] Jackson | The evolution of social and economic networks[END_REF] which is cyclical and never stops. Notice that, the firms responsible for the creation or deletion of the links along the sequence are different and individual profits of a given firm are not increasing at every step. Along the Improving Path, the individual profits of the firms involved in the link creation or removal increase, while the profits of the others may decrease. This highlights the effects of the externalities inherent in our model on the individual profits of the firms.

Second, since at every step of the sequence there is only one possible network evolution step and since all the non-empty graphs of the set S are also in the cycle C, we can conclude that C is the only Improving Path in the given range of parameters.

Proof of Proposition [START_REF] Corbo | A study of nash equilibrium in contribution games for peer-to-peer networks[END_REF] The change in the largest real eigenvalue, ∆λ PF of a graph G with m edges and n nodes, by adding one edge to the graph is bounded by ∆λ PF ≤ 1 2 (-1 + 1 + 8(m + 1)) -2m n .

(.71)

The above inequality can be obtained as follows. The average degree of the graph is d = 2m n . A lower bound on the largest real eigenvalue is given by λ PF ≥ d ( 17). An upper bound on the largest real eigenvalue is given by λ PF ≤ 1 2 (-1 + √ 1 + 8m) [START_REF] Stanley | A bound on the spectral radius of graphs with e edges[END_REF]. Combining the two bounds yields the inequality in (.71).

We apply the bound of Equation (.71) on the change in the largest real eigenvalue, ∆λ PF , by adding an edge to the graph G with m edges. Solving the equation ∆λ PF = c for m yields the maximal number m * of edges that can be added to a graph of n nodes when the cost is c, m * (n, c) = n 4 (-1 -2c + n + n 2 + 9 -2n(1 + 2c)). Notice that m * (n, c) decreases with increasing cost c. Imposing now this expression to be equal to one edge less than the number of edges in a complete graph K n with n nodes, n 2 -1 = n(n-1)

2

-1, we get c * = 2 n . Thus, if costs exceed this value then the increase in eigenvalue corresponding to the creation of the link that would make the graph complete, is smaller than the cost. Notice that c * decreases with n and tends to 0 for large n, as plotted in Fig. (.6), and therefore for any given c there is an n large enough such that the complete graph cannot be reached.

  walk is closed if the first and last firm in the sequence are the same, and open if they are different. A path is an open walk in which no firm is visited twice. A closed path encompassing n nodes is a cycle, denoted by C n .

Fig. 1 .

 1 Fig.1. Representation of a connected nested split graph (left) and the associated adjacency matrix (right) with n = 10 nodes. A nested split graph can be partitioned into subsets of nodes with the same degree (each subset is represented as circle, the degree d of the nodes in the subset is indicated). A line connecting two subsets indicates that there exists an edge between each node in one set and all the nodes in the other set.

F 10 , 10 = K 10 F 10 , 9 F 10 , 8 F 10 , 7 Fig. 3 .

 1010101091081073 Fig. 3. Efficient graphs for values of cost c = 0.55, 0.65, 0.75, 0.85 and n = 10. The density of the efficient graph is decreasing and the degree heterogeneity is increasing with increasing cost.

Fig. 4 .

 4 Fig. 4. Properties of the F n,d graph as a function of the cost of collaboration. Upper bound ¯ on the relative error in the approximation of the efficient graph G * (top, left); degree variance σ 2 d (F n,d ) (bottom, left); degree coefficient of variation cv(F n,d ) (top, right); ratio of degree variance of F n,d and degree variance of a random graph G(n, m) of same size and density, σ 2 d (F n,d )/σ 2 d (G(n, m)) (bottom, right) for n = 50, n = 100 and n = 200 and cost c ∈ [0.5, 1].

Figure ( 9 )Fig. 7 .

 97 Fig. 7. A star K 1,8 and (i) the creation of a link or (ii) the removal of a link.

Fig. 8 .

 8 Fig. 8. Cycle C = (P 2 , {P 2 , P 2 }, P 4 , P 3 ) of repeatedly visited graphs in which one graph is improved by the next in the sequence.

Fig. 9 . 2 dFig. 10 .

 9210 Fig. 9. Equilibrium networks for n = 50, c = 0.15, (a) α = 0.0, (b) α = 0.1, and (c) α = 1.0 starting from an empty network. Relative profits (compared to the firm with highest profits in the network) are indicated with different shades of red, meaning that nodes with higher relative profits are shown in a lighter shade. The network plots use the Fruchterman-Reingolg algorithm (22).

Fig. 11 .

 11 Fig. 11. Average clustering coefficient C (top, left), average number of components N H (top, right), average size of components |H| (bottom, right) and average Herfindal index of components size concentration h H (bottom, right) in the equilibrium network for n = 50, c ∈ [0, 1], starting from an empty network (averaged over 50 simulations).

Fig. . 1 .

 1 Fig. .1. Upper bound b(n, m * , c) of Eq. (.30) for n = 100 and varying costs c. For c ≤ n 2n-1 the upper bound corresponds with the complete graph Kn.graph, K n which is therefore the efficient graph. (iv) If c = n then the number of edges maximizing Eq. (.29) is given by m * = 0 and the efficient graph is the empty graph Kn .

)

  Along an Improving Path the number m of links can vary, in absolute value, only by one or zero. Here, we restrict ourselves to the Improving Paths with number of links increasing from m 1 = 0 to (possibly) m 2 = n(n -1)/2. Along any of these Improving Path λ PF (m) is a well defined one-valued function. Since the largest eigenvalue is bounded, λ PF (m) ≤ n -1 (Prop. 1), the average increase of λ PF (m) per link added is 2 n . The straight line in Figure 5 has slope 2 n and intersect the origin. Let us now define y m = λ PF (m) -2 n m. Since it is y m1 = 0 and y m2 = 0. It obviously holds that the sum of the increments ∆y m = y my m-1 in I = [m 1 , m 2 ] ∩ N , has to be zero, m2 m1+1 ∆y m = 0. (

2 nFig. . 2 .

 22 Fig. .2. Number of stable clique sizes when the spanning star K 1,n-1 is an equilibrium as well (for α = 0.1 and α = 0.5). If this number is positive then we have a spanning star K 1,n-1 and (at least one) set of disconnected cliques K 1 k , ..., K d k as equilibrium networks for the same level of cost c.

( 7 )

 7 There exists the following bound on the change in eigenvalue by the removal and creation of a link (16): If the graphs G, G differ in only one edge then|λ PF (G )λ PF (G)| ≤ 1. A link is created if ∆λ PF > c. Thus, no link is created if c = 1.On the other hand, a link is removed, if ∆λ PF < c . And thus, all links are removed if c > 1 and we obtain an empty graph Kn .

c.

  It turns out that the bound for the removal, b r , is larger than the bound for the creation, b c , for any value of c ∈ [0, 1], as it is shown in Figure(??). However, since the size n of the clique has to be an integer, the interval [b c , b r ] needs to contain at least one integer. This can be checked numerically. We explored the interval c ∈ [0, 1] with a resolution of 10 -3 and we counted the number of integer values that fall within [b c , b r ]. As it is shown in Figure (.2), for c < 0.35, there is always at least one integer in between the two bounds, while for c < 0.2, there are always several integers falling in between the two bounds.

52 ) 2 . 14

 52214 For c = 2 -√ 2 = 0.586 we have n ≤ 3 and for c = 1 we obtain n ≤ Proposition Denote the graph consisting of two disconnected cliques by G and the graph obtained from G by connecting the two cliques in G via an edge by G . Then for n ≥ 1+c(1-c) c 2 we have λ PF (G )λ PF (G) < c. Proof of Proposition (14) Denote the adjacency matrix of the graph obtained by connecting two complete subgraphs K n and K n via and edge, see Figure (6), by A. And denote the matrix obtained by subtracting the variable λ on the diagonal of A by M = A -λI. The eigenvalues of A are given by the roots of the determinant of M. M has the form of a block matrix with the submatrices K and B. We have

Fig. . 3 .

 3 Fig. .3. All possible graphs for link creation when at least one of the selected nodes is part of a P 2 . We have labeled all the possible cases or links respectively with numbers shown next to the dashed links.

1

 1

  Figure (.3). The maximum increase in the largest real eigenvalue is given by the creation of a link between the two pairs, indicated by 1 in Figure(.3).

2 .

 2 the possible links indicated by the same numbers in Figure (.4). The maximum increase in the largest real eigenvalue is given by the creation of a triangle, indicated by 5 in Figure (.4). However, does not exceed the minimum value of cost c ≥ 0.586 and so the corresponding firms do not form this link. (ii) Link deletion. The removal of a link from P 3 results in a change in eigenvalue of ∆λ PF = √ 2 -1 = 0.414. The lower bound for the cost is c > 2 -√ We have that |∆λ PF | ≤ c = αc if α ≥ we restrict the values of α to the interval [0.707, 1] then

Fig. . 6 .

 6 Fig. .6. Maximal value of cost c for which the complete graph Kn can be obtained as an equilibrium network.

  Let us start with the lower bound. Recall that F n,d is the graph obtained from a complete graph K d of d nodes and nd isolated nodes by connecting each isolated node to one and the same node of K d via one link. The number of links m in this graph is determined by the size d of the clique, m(d) = n 2 + (nd). Since F n,d contains K d as a subgraph, the largest real eigenvalue of F n,d is larger or equal to the one of K d , which is λ PF (K d ) = d -1. Therefore, total profits of the graph F n,d are bounded from below as follows:

1

  Change in eigenvalue for link creation when at least one of the selected nodes is part of a P 2 . The numbers in the first row in the table refer to the possible links indicated by the same numbers in

			2.1 2.2 3.1 3.2	4
	λ PF	1	1.414	1.618	1
	λ PF ' 1.618 1.732 1.848 1.802 1.932 1.414
	∆λ PF 0.618 0.318 0.434 0.184 0.314 0.414
	Table .

2

  Fig. .4. All possible cases for link creation when at least one of the selected nodes is part of a P 3 . We have labeled all the possible cases or links respectively with numbers shown next to the dashed links. Change in eigenvalue for link creation when at least one of the selected nodes is part of a P 3 . The numbers in the first row in the table refer to

	1.1	1.3	1.2	1.4	2.1	2.2	2.3		2.4	P 3
								4.2
	.1 3.2	3.3	3.4		4.1			5
				1.1 1.2 1.3 1.4		2.1 2.2 2.3 2.4
				λ PF	1.414		λ PF	1.414
				λ PF ' 1.732 1.848 1.732 1.848	λ PF ' 1.902 1.802 2 1.902
				∆λ PF 0.318 0.434 0.318 0.434	∆λ PF 0.488 0.388 0.586 0.488
					3.1 3.2 3.3 3.4		4.1 4.2	5
				λ PF		1.618			λ PF	1.414
				λ PF ' 1.848 2 1.932 2.053	λ PF ' 1.732 1.618 2
				∆λ PF 0.23 0.382 0.314 0.435	∆λ PF 0.318 0.204 0.586
	Table .

3

  Fig. .5. All possible cases for link creation when at least one of the selected nodes is part of a P 4 . Change in eigenvalue for link creation when at least one of the selected nodes is part of a P 4 .(ii) Link deletion. The change in eigenvalue is either (A) ∆λ PF = 0.204 if the first or last link in P 4 is removed or (B) it is ∆λ PF = 0.618 if the second link in the middle of P 4 is removed.In case (A) the change in eigenvalue is given by ∆λ PF = , then |∆λ PF | ≤ c = αc and the link is removed. This means that, for c > 2 -√ 2 we must have that α ≥

	1.1	1.2	2.1	2.2 2.3	2.4
							P 4
						4.2	5.1
	.1	3.2 3.3	3.4	4.1		5.2
				1.1 1.2		2.1 2.2 2.3 2.4
			λ PF	1.618	λ PF	1.618
			λ PF ' 1.802 1.932	λ PF ' 1.970 1.848 2.053 1.932
			∆λ PF 0.184 0.314	∆λ PF 0.352 0.23 0.435 0.314
			3.1 3.2 3.3 3.4			4.1 4.2	5.1 5.2
			λ PF	1.618		λ PF	1.618	λ PF	1.618
			λ PF ' 1.879 1.989 1.989 2.095	λ PF ' 1.848 1.732	λ PF ' 2.170 2
			∆λ PF 0.261 0.371 0.371 0.477	∆λ PF	∆λ PF 0.552 0.382
		Table .√ √ 5). If c = αc ≥ √ 2 -1 2 (1 + √ 5)| √ 2-1 2 (1+ √ 5)| 2-√ 2	2 -1 2 (1 +

See Vega-Redondo and Goyal[START_REF] Vega-Redondo | Structural holes in social networks[END_REF] for a model where benefits from indirect connections are non-rival.

In this paper we will use the terms graph and network interchangeably. The same holds for links and edges.

We consider undirected graphs only.

Note that b has the dimension of an inverse time.

In Equation[START_REF] Bala | A noncooperative model of network formation[END_REF] we are assuming the process of creation of ideas at the firm level is cumulative, in that larger knowledge stocks (of the firm and of its collaborators) lead to higher knowledge growth. This property of knowledge dynamics has often been emphasized in innovation studies (see e.g. 20).

Incidentally, note that λ PF is not even determined as a function of m, because, for a given m, there are many different ways to arrange the links among the nodes, resulting in different values of λ PF ).

It has been argued that in several settings paths that are not the shortest may have a big impact on the information that is transmitted from one agent to another (see e.g. 54; 57).

The efficient networks are similar to those obtained in the model of[START_REF] Ballester | Who's who in networks. wanted: The key player[END_REF]. The authors show that their model is a generalization of[START_REF] Goyal | R&D networks[END_REF], which was introduced in the context of R&D networks. More precisely, in[START_REF] Corbo | A study of nash equilibrium in contribution games for peer-to-peer networks[END_REF] it is shown that the networks that maximize aggregate outcome and welfare coincide and are given by the graphs with maximal eigenvalue.

Since the number of possible connected nested split graphs is an increasing function of the number n of nodes for small value of the cost c it is feasible to construct all the possible graphs directly and to identify the one which maximizes total profits.

Note that for c = 0 the problem in[START_REF] Cowan | Structural holes, innovation and the distribution of ideas[END_REF] can be reduced to the problem of maximizing total knowledge growth in the steady state for a given number of firms, in which case the complete graph is the solution.

These severance costs can be associated with the legal procedures needed to unilaterally bring a contract to an end, or it can have a different nature, e.g. be associated with the loss of reputation for managers breaking long-lasting collaborations.

This is a cycle in the space of network trajectories, to not confuse with the specific graph called cycle.

In the following, x , where x is a real valued number x ∈ R, denotes the smallest integer larger or equal than x (the ceiling of x). Similarly, x the largest integer smaller or equal than x (the floor of x).

Another (degenerate) region of the parameter space in which the network dynamics leads to inefficient equilibrium outcomes is the one in which marginal cost is in the open interval (0.586, 0.618). In that case (cf. Proposition[START_REF] Coleman | Social capital in the creation of human capital[END_REF]), for any number of firms in the industry the dynamics gets stuck into a cycle of networks, none of which is efficient.

When simulating the network evolution discussed in Section 4 the largest real eigenvalue of the network has to be computed many times. Since the largest real eigenvalue of a graph can be computed in polynomial time[START_REF] Hong | Bounds of eigenvalues of graphs[END_REF] our model is well suited for numerical investigations.

Choosing a different, possibly higher, number of firms would have not altered the results, as only the size (the number of firms) of the connected components, and not the total size of the system matters for the dynamics.

Preliminary simulation studies with values of α greater than 0.5 for the severance cost did not reveal the presence of any striking difference in the results.

The term path refers to a particular type of graph, see Section 2.1. The term Improving Path refers to a sequence in the space of graphs, as defined earlier.

Equation (.68) is an upper bound and the number of stable stars derived from it may actually be higher.

Acknowledgements

Thanks to Hans Haller, Koen Frenken, Luigi Marengo, Giorgio Fagiolo, Nicolas Carayol, Patrick Groeber and Hans Gersbach for their invaluable advice and support. All usual disclaimers apply.

Appendix

In the Appendix we give the proofs of the Propositions and Lemmas stated in the preceding Sections.

Proof of Proposition (1)

The adjacency matrix A(G) is diagonalizable [START_REF] Haemers | Handbook of Linear Algebra, chapter Matrices and Graphs[END_REF] and thus, the general solution of (4) can be written as ( 61)

where c i are unknown constants, that are determined by the initial values x(0) = n j=1 c j v j , λ PF = λ 1 ≥ λ 2 ≥ ...λ n are the real eigenvalues of A and v 1 , ..., v n the corresponding eigenvectors. In (.1) only those eigenvalues and corresponding eigenvectors of the adjacency matrix of the connected component G i of firm i appear. All other eigenvalues have vanishing eigenvector components and do not contribute to the trajectory. This is intuitively clear since firms in disconnected components have decoupled equations of the form (4) and their trajectories can be computed independently. We get