The formation of networks with local spillovers and limited observability

König, Michael David Article The formation of networks with local spillovers and limited observability Theoretical Economics Provided in Cooperation with: The Econometric Society Suggested Citation: König, Michael David (2016) : The formation of networks with local spillovers and limited observability, Theoretical Economics, ISSN 1555-7561, The Econometric Society, New Haven, CT, Vol. 11, Iss. 3, pp. 813-863, https://doi.org/10.3982/TE1524 This Version is available at: https://hdl.handle.net/10419/150295 Standard-Nutzungsbedingungen: Die Dokumente auf EconStor dürfen zu eigenen wissenschaftlichen Zwecken und zum Privatgebrauch gespeichert und kopiert werden. Sie dürfen die Dokumente nicht für öffentliche oder kommerzielle Zwecke vervielfältigen, öffentlich ausstellen, öffentlich zugänglich machen, vertreiben oder anderweitig nutzen. Sofern die Verfasser die Dokumente unter Open-Content-Lizenzen (insbesondere CC-Lizenzen) zur Verfügung gestellt haben sollten, gelten abweichend von diesen Nutzungsbedingungen die in der dort genannten Lizenz gewährten Nutzungsrechte. Terms of use: Documents in EconStor may be saved and copied for your personal and scholarly purposes. You are not to copy documents for public or commercial purposes, to exhibit the documents publicly, to make them publicly available on the internet, or to distribute or otherwise use the documents in public. If the documents have been made available under an Open Content Licence (especially Creative Commons Licences), you may exercise further usage rights as specified in the indicated licence. https://creativecommons.org/licenses/by-nc/3.0/ Theoretical Economics 11 (2016), 813–863 1555-7561/20160813 The formation of networks with local spillovers and limited observability Michael D. König Department of Economics, University of Zurich This paper analyzes the formation of networks in which each agent is assumed to possess some information of value to the other agents in the network. Agents derive payoff from having access to the information of others through communication or spillovers via the links between them. Linking decisions are based on network-dependent marginal payoff and a network-independent noise capturing exogenous idiosyncratic effects. Moreover, agents have a limited observation radius when deciding to whom to form a link. I find that for small noise the observation radius does not matter and strongly centralized networks emerge. However, for large noise, a smaller observation radius generates networks with a larger degree variance. These networks can also be shown to have larger aggregate payoff. I then estimate the model using a network of co-inventors and scientific collaborations in physics and economics, and find that the model can closely reproduce a variety of observed patterns. I show that local search is important in all the empirical networks conside, but that economists tend to search more broadly for new collaboration opportunities. Keywords. Diffusion, network formation, growing networks, limited observability. JEL classification. C63, D83, D85, L22. 1. Introduction Networks are important in explaining a large variety of social and economic phenomena. This insight has lead to an increasing interest in the study of networks in economics Michael D. König: [email protected] I am grateful to Matt Jackson for his guidance and support. Moreover, I thank Mathias Staudigl for the excellent research assistance in the early stages of the paper. I would like to thank Christian Zimmermann, Sanjeev Goyal, Andrea Galeotti, Brian Rogers, Yves Zenou, Ben Golub, Tomás R. Barraquer, Lee Fleming, Fabrizio Zilibotti, Kjetil Storesletten, Anton Kolotilin, and seminar participants at University of Berkeley, University of Cambridge, University of Vienna, University of Bielefeld, University of Zurich, ETH Zurich, and Stanford University for their insightful comments. I would like to thank Thomas Krichel for providing access to the data. Financial support from Swiss National Science Foundation through research Grants PBEZP1-131169 and 100018_140266 is gratefully acknowledged. Finally, I would like to thank SIEPR and the Department of Economics at Stanford University for their hospitality during 2010–2012. A previous version of this paper was circulated under the title “Centrality Based Network Formation of Boundedly Rational Agents with Limited Information.” Copyright ©2016 Michael D. König. Licensed under the Creative Commons Attribution-NonCommercial License 3.0. Available at http://econtheory.org. DOI: 10.3982/TE1524 814 Michael D. König Theoretical Economics 11 (2016) and related sciences accompanied by a growing number of publications in the field.1 Networks play a particularly important role in understanding the process of communication of information and knowledge diffusion among diverse actors, ranging from inventors to scientists. In this paper, I introduce a simple, parsimoniously parameterized and tractable model to study the emergence of networks of information and knowledge diffusion, which is able to match and explain the observed empirical patterns on an unprecedented scale. A large body of literature has emphasized the crucial effect of social networks of inventors on the productivity of innovative regions (see, e.g., Marshall 1919,Allen 1983, Singh 2005,Almeida and Kogut 1999). A prominent example is the success story of Silicon Valley, which has been attributed to its informal networks of friendship and collaboration (Saxenian 1994,Fleming et al. 2007). Similarly, the formation of collaborations in academic research is a crucial component in the process of scientific discovery and knowledge production (Newman 2001a, 2004,Fafchamps et al. 2010,Goyal et al. 2006). The networks of inventors and scientific collaborations share a number of empirical regularities. First, the distributions of degree (the number of links of a node) in these networks exhibit fat tails, typically decaying as a power law.2Similarly, the average clustering coefficient (Watts and Strogatz 1998), i.e., the fraction of connected neighbors of a node, tends to decrease with the degree and also exhibits a power-law decay (cf. Goyal et al. 2006). Moreover, the distribution of (small) connected components (in which there exists a path between every pair of nodes) decays as a power law. Finally, the networks of inventors and coauthors exhibit an increasing average neighbors’ degree with the degree of a node, referred to assortativity (Newman 2002). In this paper, I introduce a simple model that can explain all these distributions. This is a novel contribution and extends previous studies that focused primarily on the distribution of degree or some aggregate statistics (cf. Jackson and Rogers 2007). I consider a degree-based approximation (see below) to a general class of models (payoff functions) in which each agent is assumed to possess some information of value to the other agents in the network. Agents derive payoff from having access to the information of others through direct communication or spillovers along the links in the network.3Agents’ incentives to form links can be partitioned into a network-dependent part as well as a network independent exogenous random term, referred to as noise. The network-dependent part of agents’ payoffs (represented by the degree) derives from having access to the information of others. The noise term captures exogenous random 1This literature has steadily grown in the last decade. The monographs of Jackson (2008),Goyal (2007), and Vega-Redondo (2007) are excellent surveys for the economic theory of networks. See also Newman (2010) for a survey of the literature in physics, and Durrett (2007) for a concise review of the literature on networks in mathematics. 2A power-law degree distribution in patent citation networks has been documented in e.g. Valverde et al. (2007). 3For the purpose of tractability, in this paper I consider a simplified setup with myopically rational agents, and I ignore issues related to private signals, strategic communication, and inference problems with Bayesian updating (see, e.g., Hagenbach and Koessler 2010,Calvó-Armengol and De Martï 2007,for alternative setups). Theoretical Economics 11 (2016) The formation of networks 815 perturbances, shortcomings in assessing the correct value of information possessed by other agents, and exogenous matching effects.4 Moreover, it is assumed that the information transmitted through the links in the network is exposed to decay, making information that travels longer distances less valuable (cf. Bala and Goyal 2000,Jackson and Wolinsky 1996). In this paper, I focus on the case of strong decay, or weak knowledge spillover effects, where the value for an agent of being connected in a network is determined by his immediate neighbors (cf. Galeotti et al. 2010). This assumption is consistent with the empirical evidence. For example, Singh (2005) and Breschi and Lissoni (2005) find in their studies of patent networks that the existence of a tie is associated with a greater probability of knowledge flow, while the probability is decreasing as the path length increases, and the probability is becoming small or nearly null for social distance greater than 2. In turn, this implies that the marginal return from connecting to an agent is determined by his degree.5 Agents sequentially enter the network and obtain an opportunity to acquire information from the incumbent agents through forming links. Upon entry, each agent can sample a given number of existing agents in the network and observes these agents and their neighbors (cf. Friedkin 1983).6I call the number of sampled agents the observation radius. He then forms links to the observed agents in the sample based on the marginal payoff (determined by the degree) obtained from each link. With this sampling procedure I follow a common approach in the statistics and sociology literature for how individuals collect information on an existing population that is difficult to observe called snowball/star sampling (Goodman 1961,Frank 1977,Kolaczyk 2009).7 I analyze the emerging networks for different observation radii and levels of noise. I find that for small noise the observation radius does not matter and strongly centralized networks emerge. However, for large noise, a smaller observation radius generates networks with a larger degree variance. One can show that the aggregate payoff maximizing networks in the class of models considered here increases with the degree variance.8Hence, I find that when the exogenous noise is large, then a smaller observation radius leads to networks that have larger aggregate payoff. This provides an example in the context of a network-based meeting process where “knowing less can be better.” Collaboration and the formation of teams involve opportunity, time, and friction costs, and information available in the circle of acquaintances will be more easily available. Hence, collaborations are more likely the closer individuals are in the network of 4The introduction of noise also allows me to compare the current model with other papers that consider a random network formation process (i.e., strong noise), such as the landmark model by Jackson and Rogers (2007). 5Newman (2001b) finds in his empirical study of co-authorship networks that the probability of a scientist acquiring a new collaborator increases with the number of his past collaborators, that is, his degree. 6In a similar way Jackson and Rogers (2007),Galeotti et al. (2010),McBride (2006),Alós-Ferrer and Weidenholzer (2008) assume that agents have only limited information of the network. 7See von Hippel et al. (1999) for a case study where a firm uses snowball sampling to collect information from customers and their contacts. 8Similarly, Westbrock (2010) shows that in the model by Goyal and Moraga-González (2001),wherefirms are competing on the product market while they can form research and development (R&D) collaborations to reduce their production costs, welfare positively correlates with the degree variance. 816 Michael D. König Theoretical Economics 11 (2016) Figure 1. The network between co-inventors in the drugs development sector. Node colors indicate different clusters of densely connected nodes using the modularity algorithm proposed in Blondel et al. (2008); node sizes indicate their degree. The figure illustrates the existence of highly connected clusters of inventors. In this paper, I develop a model that can explain the formation of these densely connected groups through a local search process for new collaboration partners. See Section 7 for further details about the data. social ties (Fafchamps et al. 2010,Goyal et al. 2006). In the empirical application of the model in this paper I compare the tendency of inventors (see Figure 1 for an example of a network between co-inventors in the drugs development sector), and scientists in condensed matter physics and economics to select their research collaborations in their local neighborhood as compared to searching for more distant partners. I show that local search is important in all the empirical networks considered, but that economists tend to search more broadly for collaboration opportunities as the estimated observation radius tends to be higher. This might reflect the diverse backgrounds and application areas of economists, which can also be witnessed in the large number of classification codes categorizing economic sciences,9and that economists are less constrained by their institutional boundaries.10 9Comparing, for example, the number of academic disciplines and sub-disciplines listed on Wikipedia we find 50 in economics and only 27 in physics. See also http://en.wikipedia.org/wiki/List_of_academic_ disciplines_and_subdisciplines. 10Schilling and Green (2011) find that search scope, search depth, and atypical connections between different research domains significantly increase a paper’s impact in the social sciences. Similarly, Theoretical Economics 11 (2016) The formation of networks 817 The paper in the economics literature most closely related to the one presented here is the seminal work by Jackson and Rogers (2007).11 In this influential article the authors introduce a model of a growing network that combines random search protocols for potential linking partners with local network-based search protocols. By means of theoretical and empirical analysis, they are able to show that their model is very flexible in fitting real-world data. However, while in Jackson and Rogers (2007) links are formed at random, here instead I make a first attempt to start directly from a (degree-based) discrete-choice approach,12,13 with an explicit modeling of the reasons why links are formed. Further, albeit similar, the difference in the linking processes of their model and the present one allows me to measure empirically the information radius of the agents. Moreover, the results for the degree distribution and efficiency in Jackson and Rogers (2007) are based on a mean-field approximation, while such an approximation is not needed to obtain the corresponding results in the present paper. Further, Jackson and Rogers (2007) do not derive explicitly all the statistics that I do here (such as the average nearest neighbor connectivity, the clustering degree distribution,14 or the component size distribution), and do not analyze the impact of different observation radii on these statistics. Moreover, with varying levels of the noise in the payoff function of Jones et al. (2008) find that multi-university research teams produce the highest impact papers. Moreover, they observe that the growth in multi-institution collaboration was greater in the social sciences than science and engineering. For instance, as noted by Winkler et al. (2011), “...research in the biological and chemical sciences almost invariably requires a lab and thus has a strong local component. Research in economics is different: Except for experimental economics, labs are rarely part of economic research; neither is specialized equipment. But data and software can be readily shared and this encourages collaboration.” 11Besides the economics literature there also exists a large literature in computer science, physics, and mathematics, where similar models are studied. I refer to Krapivsky et al. (2000),Krapivsky and Redner (2001),Oliveira and Spencer (2005),Vázquez (2003),Kumar et al. (2000),Wang et al. (2009), and Toivonen et al. (2006), to mention only a few. However, these authors typically do not make explicit behavioral assumptions about why links are formed, do not analyze welfare implications, and do not estimate their models for empirically observed networks. 12The payoff function I introduce focuses on the case of strong decay of the knowledge transmitted along the links between agents, such that the degree of an agent determines his propensity to acquire new links (see, e.g., Singh (2005),Breschi and Lissoni (2005),Newman (2001b) for an empirical motivation), so that the degree of an agent will be a sufficient statistic to assess the agent’s marginal payoff from forming links (see Assumption 1 in Section 2.1). There is clearly much more work to be done in this area that incorporates more general payoff functions, but I believe that the model considered here provides a first step toward a better understanding of the structure of real-world networks and the incentives and information sets that are influencing the processes that generate these networks. 13The general class of models considered here (see also supplementary Appendix E) has the property that the payoff of an agent is increasing with the number of collaborations, i.e., his degree. This is a characteristic that has been found in empirical studies of co-authorship networks (see, e.g., Abbasi et al. 2011,Ductor 2015). 14Jackson and Rogers (2007, p. 900) conjecture that C(k), the clustering coefficient for a node with indegree k, is a strictly decreasing function of degree k. Here I complement their analysis by providing asymptotic expressions for C(k) showing that C(k) is not only decreasing with the degree, but actually decaying as a power law with a well defined exponent. The intuition behind the decreasing clustering coefficient with the degree is that in this growing network model older agents are connected to a larger number of younger agents, and these younger agents have not only a smaller number of links but are also less likely to be connected among each other. In contrast, the younger agents are primarily connected to older agents, who have a higher degree and are more likely to be connected among other old agents. Hence, we observe a 818 Michael D. König Theoretical Economics 11 (2016) the agents, a transition from assortative to dissortative networks can be observed in the model. As Jackson and Rogers (2007) do not provide results for the average nearest neighbor connectivity, and they do not have a payoff function governing the decision with whom to form a link, this behavior cannot be studied in their setup. Besides, a feature of the model by Jackson and Rogers (2007) is that it generates dissortative undirected networks.15 This is particularly problematic when we look at the networks in the empirical examples in Section 7 (networks of co-authors and co-inventors), which are all assortative. Also, when the marginal payoff of agents is increasing in the degree and there is no exogenous noise, then differently to the efficiency results obtained in Jackson and Rogers (2007), I show that the observation radius has no impact on aggregate payoffs and efficiency. Based on the pioneering model by Jackson and Rogers (2007) anumberofextensions and applications have been suggested. Ghiglino (2011) introduces an algorithm similar to Jackson and Rogers (2007) to study the creation and recombination of ideas from a pool of existing knowledge (more precisely, networks of citations between scientific publications). Bramoullé et al. (2012) and Vigier (2014) introduce different types of agents and study the mechanisms underlying homophily, that is, the tendency of similar types of agents being connected. Moreover, Kovᡠrík and Van der Leij (2014) introduce risk aversion in the decisions of agents to form links locally or globally. They show that risk aversion can lead to increased clustering in the network. In contrast, in Chaney (2014) a spatial extension is suggested in which the network is embedded into geographical space and agents who are closer in space are more likely to form links. Differently to these authors, I introduce a behavioral foundation (albeit simplistic) of why links are formed in the model by Jackson and Rogers (2007) in the context of knowledge diffusion in networks. Moreover, none of these works investigates all the empirical networks that I do in the present paper and estimates the model for these data. The paper is organized as follows. In Section 2, I introduce the general modeling framework. Section 2.1 defines the payoff agents derive from the network. Next, in Section 2.2, I describe the evolution of the network. In Section 3, I analyze the networks generated by the model, while Section 4 provides an efficiency analysis and shows how the level of noise and the observation radius affect aggregate payoffs. Section 5 analyzes correlations between an agent and his neighbors. Section 6 discusses several extensions of the model. Section 7 contains an application of the model to different real-world networks. Section 8 concludes. Appendix A contains a few basic definitions and notation. All proofs are relegated to Appendix B. Supplementary Appendices C and D, negative clustering degree relationship. The numerator of the clustering coefficient then grows roughly linearly and the denominator grows roughly quadratically with degree, which results in a power-law behavior of the clustering degree distribution. See Section 5.2 for a more detailed discussion. 15Assortativity in the model by Jackson and Rogers (2007) is found for the average nearest in-neighbor connectivity that is increasing with the in-degree. The intuition is that older agents are more likely to form links to other old agents with high degrees, while younger agents are more likely to form links to other young agents with smaller degrees. This gives rise to an assortative trend. However, this does not hold in the undirected closure of the network. In the undirected network the average nearest neighbor degree of the younger agents is now much higher because it includes not only the in-neighbors, but also the outneighbors, who are older agents with high degrees. This can reverse the positive trend of the average nearest neighbor connectivity and give rise to a dissortative network. See Section 5.1 for more details. Theoretical Economics 11 (2016) The formation of networks 819 available in a supplementary file on the journal website, http://econtheory.org/supp/ 1524/supplement.pdf, present some technical details of the sampling scheme. Various examples in the literature that fall into the general class of games considered here are discussed in supplementary Appendix E. A detailed explanation of the empirical method and results are given in supplementary Appendix F. Finally, supplementary Appendices G and H provide a more detailed discussion of the model extensions introduced in Section 6. 2. The model In the following sections we introduce the payoff agents derive from being connected in a network and their incentives to form links within a dynamic network formation process. The basic definitions and notation used throughout the paper can be found in Appendix A. 2.1 Payoffs For a given network G= NE∈G(n) we assign each agent i∈Napayoffπi(·δ) : G(n) →Rthat depends on the network Gand a (decay) parameter δ≥0that measures the degree of interdependency between agents’ payoffs in G.Wedefinethelink incentive function fi:G(n) ×N→Rfor an agent i∈Nas fδ i(Gj) ≡πi(G ⊕ij δ) −πi(Gδ) which measures the marginal payoff to the agent iresulting from the potential link ij /∈E. Here we focus on link incentive functions (and therefore on classes of games) that satisfy the following conditions. Assumption 1. For all i∈Nthe link incentive function fδ i(G·):N→Rhas the following properties: (LM) Link monotonicity. The incentives to link are nonnegative, i.e., fδ i(Gj) ≥0for all j= i∈N. (LD) Linear differences. With strong decay, the incentives to link to an agent are increasing with his degree, i.e., for all ij ik /∈E, there exists a constant γ≥0and a linear increasing function g:R→Rsuch that fδ i(Gj) −fδ i(Gk) δγ=g(dG(j) −dG(k)) +o(1) holds in the limit of δ→0. Let us briefly discuss the implications of these two conditions in turn. Link monotonicity (LM) requires that the incentives to link are nonnegative. Intuitively it says that no link to be formed can harm an agent (cf. Dutta et al. 2005). Condition (LD), linear 820 Michael D. König Theoretical Economics 11 (2016) differences, allows us to order the linking incentives for the entering agent across all potential linking partners. It says that the agent ihas the highest incentive to direct a link to the agent who has the current highest degree among all alternative linking partners.16 Two potential links are judged as being equally attractive for the agent if the involved agents have the same degree in the current network.17 Further, the assumption of strong decay should capture the fact that in this model an agent cares about knowledge spillovers from direct and indirect neighbors, that is, up to length-2connections but not longer.18 For our efficiency analysis, we further make the following assumption. Assumption 2. Let :G(n) ×R+→Rdenote aggregate payoff defined by (Gδ) ≡ i∈Nπi(Gδ) and let σ2 d(G) bethedegreevarianceofG∈G(n e). Then we assume that the following condition holds: (DC) Degree concentration. For n∈Nand 0≤e≤n 2, argmax G∈G(ne) (Gδ) =argmax G∈G(ne) σ2 d(G) holds in the limit of δ→0. Assumption (DC) assumes that networks with a higher degree inequality, as measured by the degree variance, generate higher welfare.19 For example, if welfare in an economy depends on the rapid diffusion of knowledge and new technologies, then a centralized structure can be optimal (cf., e.g., König et al. 2012). Assumption (DC) will be needed for our efficiency analysis in Section 4. Supplementary Appendix E provides a number of examples from the economic literature that satisfy Assumptions 1and 2. These examples illustrate how the assumptions made in this section arise naturally when knowledge diffuses in networks and the transmission of information along the links is exposed to strong decay or when there are weak knowledge spillover effects between neighboring agents (corresponding to small values of δ). 16This is consistent, for example, with the empirical evidence for co-authorship networks, where it is found that the probability of a particular scientist acquiring a new collaborator increases with the number of his past collaborators (Newman 2001b). Moreover, Ductor (2015) investigates the causal effect of coauthorship on individual productivity and provides evidence for the existence of peer effects. i.e., positive knowledge spillovers. He further shows that by simultaneously controlling for time invariant unobservable factors and for the potential endogeneity of co-authorship formation, co-authorship leads to a higher academic productivity. This result is robust and statistically significant. 17An agent iis indifferent between linking to jand kwhen jand khavethesamedegree. Itdoesnot matter with whom jand kare connected, even if jand kmightsharethesameneighbor. Inthenetwork formation process I consider the probability of overlapping neighborhoods is small when the network becomes large. The model by Jackson and Rogers (2007) has the same feature, and it has been used for their mean field analysis. Hence, Assumption (LD) is not very restrictive. 18See also the examples discussed in supplementary Appendix E. 19Such a correlation between the degree variance and welfare has also been identified in R&D collaboration networks (cf., e.g., Westbrock 2010). Further examples from the literature with this feature can be found in supplementary Appendix E. Theoretical Economics 11 (2016) The formation of networks 827 indefinite iteration of the network formation process (Gβ t)t∈Nassuming that St=Pt−1for every t>m+1. Then Pt(k) →Pβ(k), almost surely, where Pβ(k) =(1+βk)−(2+1/(mβ))1+O1 k (4) for all k≥0as t→∞. Thus, Proposition 2 shows that in the limit of large noise and a large observation radius we obtain networks with a degree distribution that decays as a power law with exponent 2+1/(mβ) for large degrees. This heavy tailed distribution indicates a highly uneven distribution of links, where old nodes typically have a larger degree as they have more time to accumulate links and thus become more likely to receive a link by the entrant. The tail flattens with increasing m, making high degree agents more likely as entering agents are forming more links. Note, however, that the power-law decay does not hold for small degrees. The degree distribution of (4) and a typical distribution obtained from a numerical simulation of the network formation process are shown in Figure 5. The smaller is the number of links mcreated by an entrant and the stronger is the exogenous noise (the smaller β), the higher is the decay in the power-law tail of the distribution, making high degree agents less likely and reducing inequality. In the extreme case that we assume “strong noise,” corresponding to the situation with β=0,wethen obtain a process of uniform attachment (cf. Bollobás et al. 2001). Corollary 1. In the network formation process (Gβ t)t∈N, assuming that St=Pt−1for every t>m+1and β=0, the agents perform a uniform attachment process whose degree distribution is given by P0(k) =1 m+1m m+1k (5) which is a geometric distribution with parameter m/(m +1)for all k≥0. When Stdoes not encompass all agents in Pt−1, then our analysis becomes more complicated. We therefore restrict our discussion to the case of strong noise when β=0. In this case we have that the attachment kernel (which gives the probability that jreceives a link from the entering agent given that jis in the sample St)is K0 t(j|StGt−1)=m |St| 1St(j) Thesamplesizeisboundedby|St|≤ns(m +1). If no agent enters the sample more than once, then equality holds. The sample Stis constructed by selecting nsnodes from Pt−1 without replacement, and forming the union of these nodes and their out-neighbors. Assuming that ns=o(t) and dGt−1(j) =op(t), the probability that a node is entering St more than once is of o(t) and thus 1 |St|=1 ns(m +1)+op1 t(6) 828 Michael D. König Theoretical Economics 11 (2016) Figure 5. Top row: Comparison of the simulation results with the theoretical predictions for T=105,St=Pt−1,andm=4with β=01under the linear approximation to the attachment kernel. Bottom row: Comparison of the simulation results for T=105and ns=m=4(β=0) with the theoretical predictions. The exact expressions for the different distributions can be found in the proofs in Appendix B. Theoretical Economics 11 (2016) The formation of networks 829 The unconditional probability that an agent j∈Pt−1receives a link by the entrant tis then given by K0 t(j|Gt−1)=(1/(ns(m+1)))P(j ∈St|Gt−1)+o(1/t). If the degree of node j is small compared to the network size t, i.e., dGt−1(j) =op(t), and the observation radius is small such that ns=o(t), then P(j ∈St|Gt−1)=ns(1+dGt−1(j))/t +o(1/t) and we obtain K0 t(j|Gt−1)=1 1+m 1+dGt−1(j) t+o1 t(7) We then can state the following result for the asymptotic degree distribution when the observation radius is small. The proof, which is based on the attachment kernel in (7), can be found in Appendix B.2. Proposition 3. Consider the sequence of degree distributions {Pt}t∈Ngenerated by an indefinite iteration of the network formation process (Gβ t)t∈Nwith a small observation radius ns=o(t). Assume that β=0and dGt−1(j) =op(t) for all j∈Pt−1. Then we have that Pt(k) →P(k), almost surely, where P(k)=k−(2+1/m)1+O1 k (8) for all k≥0as t→∞. Equation (8) is a power law decaying with an exponent 2+1/m. A comparison with numerical simulations can be found in Figure 5. Compared to the power-law behavior in (4) obtained for a large observation radius, we find that the degree distribution in the case of a small observation radius has fatter tails, making high degree agents more likely and indicating a more unequal organization of the network. This is due to the fact that agents with a high degree can be found in a larger number of neighborhoods when entrants form the sample Stand thus are more likely to receive a link. Also, when entrants form more links (by increasing m), the probability of agents with a high degree increases (which can be seen from a smaller exponent of the power-law decay). Observe that the degree distribution in (8) does not depend on the number nsof samples taken by the entering node. The reason is that two effects on the probability to receive a link of an incumbent cancel each other: On one hand, a larger value of nsmakes it more likely that an agent enters the sample Stand, hence, increases the probability that he receives a link. On the other hand, a higher value of nsalso increases the sample size |St|and thus decreases the probability that he is selected by the entrant to receive a link. The results obtained in this section show that when agents have global information, the presence of strong noise (β→0) induces networks with a smaller degree variance (following from the geometric distribution of Corollary 1) than when agents have only local information to form links (as implied by the power-law distribution of Proposition 3). However, as we have seen in part (i) of Proposition 1, in the absence of noise (as β→∞), the amount of information available to the agents when forming links does not matter, and the emerging network will be a quasi-star with a high degree variance. 830 Michael D. König Theoretical Economics 11 (2016) Figure 6. Degree variance σ2 dfor local (ns=1)andglobal(ns=t) search strategies for different values of βwith m=1,T=104nodes (averaged over 10 simulation runs). The degree variance of the star K1T −1is given by σ2 d(K1T−1)=(T −1)(T −2)2/T2. These results are indicated in Figure 3. Hence, whether a limited observation radius impacts inequality in outcome networks depends crucially on the level of exogenous noise in agents’ payoffs. The degree variance is also closely related to aggregate payoff and efficiency, and this will be discussed in more detail in the next section. 4. Efficiency Since we have computed the degree distribution in Section 3 for different values of the observation radius ns, by virtue of Assumption (DC) we can readily state the following efficiency result. Proposition 4. Consider the sequence of networks (Gβ t)t∈[T], generated with an observation radius n(1) slarge such that St=Pt−1for all t≥m+2,and(Hβ t)t∈[T]with a small observation radius n(2) s=o(t), and assume that dHt(i) =op(t) for all i∈Ptas tbecomes large. Let (Gβ Tδ) and (Hβ Tδ) be the aggregate payoff under Gβ T, respectively, Hβ T, after Titerations. Then, almost surely, the following statements hold: (i) For β→∞we have (Hβ Tδ)=(Gβ Tδ)=(m Tδ),wherem T⊂G(T) is the isomorphism class of quasi-stars of order T. (ii) In the limit of large T,wehaveforβ→0that (Hβ Tδ)>(Gβ Tδ). A comparison of the degree variance σ2 dfor different observation radii ns(local vs. global) obtained by means of numerical simulations for T=104agents with different values of βcan be seen in Figure 6. The figure shows that aggregate payoff is higher for Gβ T(global information) if βis high enough; however, the opposite holds for small values of β, where aggregate payoff is higher for Hβ T(local information). Proposition 4 and Figure 6 show a major difference between the model considered here and the one by Jackson and Rogers (2007) (apart from differences in the sampling technology). In Jackson and Rogers (2007) a higher ratio of (local) neighborhood-based Theoretical Economics 11 (2016) The formation of networks 831 nsk± nn(k) C(k) Global information k− nn(k) =O(ln(k)) C(k) =O(t−2/(1+βm) ·k2(1/(βm)−1)) k+ nn(k) =O(t(βm)/(1+βm)) Local information k− nn(k) =O(ln(k)) C(k) =O( 1 k) k+ nn(k) =O(t(m−1)/(m+1)·k1/m) Table 1. Asymptotic behavior of the average nearest neighbor connectivity, k± nn(k), and the clustering degree distribution, C(k), in the large noise limit summarizing the results of Propositions 5,6,7,and8in Section 5. linking to (global) random-based linking is always increasing average payoff as long as payoff is a convex function of the degree.33 However, here we find that this does not hold in general when exogenous effects are taken into account, where this relationship might be reversed.34 Also, when the marginal payoff of agents is increasing in the degree (and there is no exogenous noise), then differently to the welfare results obtained in Jackson and Rogers (2007), whether links are formed locally or globally has no impact on average payoffs and efficiency. Thus, the introduction of noise into decisionmaking in a network-based meeting process matters significantly for efficiency results. 5. Large noise limit and higher order statistics In the following sections I analyze correlations between an agent and his neighbors. Such correlations are not only interesting as they help us to understand the behavior of our model for different parameter values, but also to compare it with correlations observed in real-world networks. In Section 5.1 we first investigate the average in-degree of the in- and out-neighbors of a node with in-degree k, denoted by the average nearest in-neighbor connectivity k− nn(k) and the average nearest out-neighbor connectivity k+ nn(k) (Pastor-Satorras et al. 2001). Next, in Section 5.2, we analyze the fraction of connected neighbors of a node with degree k(in the closure of the network), referred to the clustering coefficient C(k) (Watts and Strogatz 1998). The results of these sections are anticipated in Table 1. Note that, so as to derive the functional forms of these statistics, I consider a continuous representation of our discrete dynamical system, the so-called continuum approximation, in which both time tand degree kare treated as continuous variables in R+.35 Using the continuum approximation, we can then apply the rate equation approach outlined in Barrat and Pastor-Satorras (2005) to compute higher order correlations in the network. 33See Corollary 1 and footnote 51 in Jackson and Rogers (2007). 34Observe, however, that a reversal of the assumption on the degree concentration (DC) would also reverse the inequality in part (ii) of Proposition 4 and this conclusion would no longer hold. 35 This is an approximation that has been shown to be accurate in various growing network models as T→∞(Dorogovtsev and Mendes 2013, p. 117). See Appendix B.4 for more discussion. 832 Michael D. König Theoretical Economics 11 (2016) 5.1 Average nearest neighbor connectivity In this section we analyze two vertex degree correlations, i.e., correlations between the degree of an agent and his neighbors’ degrees. Let P(k|k) denote the probability that a node of in-degree khas an in-neighbor with in-degree k. The average in-degree of inneighbors of nodes with in-degree kcan then be written as k− nn(k) =∞ 0kP(k|k)dk (cf. Pastor-Satorras et al. 2001). In the case that k− nn(k) is an increasing function of k, we speak of assortative mixing, while for k− nn(k) decreasing with k,wehavedissortative mixing (Newman 2002). Similarly, the average nearest out-neighbor connectivity k+ nn(k) can be defined. We now derive these quantities for different observation radii. In the case of global information (when the observation radius nsis large) and small β(large noise) we obtain the following proposition. Proposition 5. Consider the network formation process (Gβ t)t∈R+with St=Pt−1.Then under the continuum approximation in the limit β→0, the average nearest in-neighbor in-degreeofanagentwithin-degreekgrows logarithmically with kand is independent of t,k− nn(k) =O(ln(k)), and the average nearest neighbor out-degree becomes independent of kand grows with the network sizes as k+ nn(k) =O(t(βm)/(1+βm))as t→∞. Similarly, we can compute the nearest neighbor connectivities under local information (when the observation radius nsis small), assuming strong noise (β=0). Proposition 6. Consider the network formation process (Gβ t)t∈R+with nssmall. If β= 0, then under the continuum approximation the average nearest in-neighbor in-degree of an agent with in-degree kgrows logarithmically with k,thatis,k− nn(k) =O(ln(k)),and the nearest out-neighbor degree grows as k+ nn(k) =O(t(m−1)/(m+1)·k1/m)as t→∞. In Figure 5 a comparison of numerical simulations with the theoretical predictions of Propositions 5and 6are shown. In both cases—local as well as global information (corresponding to Propositions 5 and 6, respectively)—we find that networks are characterized by positive degree correlations, or assortative mixing.36 The intuition for this result derives from the observation that older agents form links to other old agents with high degrees, while younger agents are more likely to form links to agents with smaller degrees. This gives rise to an assortative trend in the average nearest out-neighbor degree k+ nn(k). This intuition carries over to the average nearest in-neighbor degree k− nn(k), but the average degree of the in-neighbors of older nodes is much smaller, because in this case the in-neighbors include also a large number of younger nodes. Consequently, we observe that the assortative trend is much weaker in the case of the average nearest in-neighbor degree k− nn(k) (growing only logarithmically with the degree k). If we compute the average nearest neighbor degree in the closure Gof G, then the average nearest neighbor degree knn(k) (the sum of in- and out-neighbors’ total degrees 36Note that in contrast to the model considered here, both the Erdös–Rényi random graph G(n p) with link density p>p c,wherepcis the critical link probability below which the graph becomes disconnected, and the Barabási–Albert power-law graph are zero assortative (Van Mieghem 2011). Theoretical Economics 11 (2016) The formation of networks 833 divided by the total degree) of older nodes is similar to the case of the average nearest inneighbor degree; however, the average nearest neighbor degree of younger nodes is now higher because the average nearest neighbor degree includes not only the in-neighbors, but also the out-neighbors which tend to have higher degrees. Therefore, we expect to see a dissortative trend in the average nearest neighbor connectivity knn(k) in the closure G. This intuition is confirmed by combining the results we have obtained for k+ nn(k) and k− nn(k).37 As we will see in the next section, the similarities between local and global observability do not carry over to the case of three vertex correlations, where networks generated under local and global information produce starkly different results. 5.2 Clustering degree correlations In this section I study three vertex degree correlations in the undirected network obtained from the closure Gβ tof the directed network (Gβ t)t∈R+. The clustering coefficient C(k) is defined as the probability that a vertex of degree kin Gβ tis connected to vertices with degrees kand k, and that these vertices are themselves connected, averaged over all kand k (Watts and Strogatz 1998).38 Note that in the case of m=1all networks will be trees, Gβ t∈T([t]), which are characterized by a vanishing clustering coefficient. Hence, we will consider only the case of m>1in this section. Similarly to the case of two vertex degree correlations in the previous section, we can derive the clustering coefficient using a rate equation approach (Barrat and Pastor- Satorras 2005). With global information (St=Pt−1)andsmallβ(strong noise) we can state the following proposition. Proposition 7. Consider the network formation process (Gβ t)t∈R+with St=Pt−1and m>1. Then under the continuum approximation in the limit β→0the clustering coefficient of an agent with degree kis given by C(k) =O(t−2/(1+mβ) ·k2(1/(mβ)−1))as t→∞. The clustering coefficient for m=4and β=01can be seen in Figure 5. It grows with kas a power law with exponent 2(1/(mβ) −1).39 Moreover, we find that the clustering coefficient is decreasing with the network size as t−2/(1+mβ). Hence, for large networks 37An increasing total nearest neighbor connectivity knn(k) can be obtained in two possible extensions of the model, considering undirected links (see Section 6.1), or heterogeneous linking opportunities (see Section 6.2). 38So as to compute the clustering coefficient as a function of the degree, in this section we proceed by first computing the clustering coefficient of a vertex s,bornattimes. The clustering coefficient of vertex s is defined as the number of links between the neighbors of sdivided by the total number of links that can exist between them (in the undirected closure of the graph), which is ks(ks−1)/2when ksisthedegreeof vertex s(Watts and Strogatz 1998). Under the continuum approximation (see also footnote 35), there exists a continuous mapping between the time of birth, s, and the degree, ks,ofavertexs. Hence, under the continuum approximation, knowing the clustering coefficient of a vertex born at time stells us the clustering coefficient of a vertex with degree ks(cf., e.g., Barrat and Pastor-Satorras 2005,Boguná and Pastor-Satorras 2003). See Appendix B.4.2 for a detailed derivation. 39We need only consider values of ksuch that C(k) does not exceed its upper bound given by 1. 834 Michael D. König Theoretical Economics 11 (2016) with a high clustering coefficient (such as the network of co-inventors; see Section 7), the assumption of global information seems to be at odds with the empirical observation. When agents have only local information and β=0(strong noise), we obtain clustering degree correlations as given in the next proposition. Proposition 8. Consider the network formation process (Gβ t)t∈R+with ns=o(t) small and assume that m>1.Ifβ=0, then under the continuum approximation the clustering coefficient C(k) of an agent with degree kis given by C(k)=O(1/k) as t→∞. The proof of Proposition 8 relies on deriving upper lower and upper bounds for the clustering coefficient that asymptotically decay as O(1/k).40 These bounds for the clustering coefficient for m=ns=4can be seen in Figure 5. The figure confirms the asymptotic decay of the clustering coefficient as a power law with exponent −1. Note that, in contrast to the results obtained in Proposition 7, the clustering coefficient in Proposition 8 does not vanish as the network becomes large. Moreover, the clustering coefficient shows a power-law decay that is a typical feature of all the empirical networks we consider (see Section 7), indicating that a limited observation radius is a general constraint in the creation of various real-world networks. Comparing the results for global and local information, we find that networks generated under global information produce relatively low clustering and a positive degree clustering correlation. This is what one would expect from a global link formation process in which the formation of cliques is very unlikely, and becomes even more unlikely the later an agent enters. Hence, we find an increasing clustering degree correlation since older agents tend to have higher degrees. However, networks formed with local information tend to produce higher clustering and a negative clustering degree correlation (see also Figure 5). Local link formation favors the creation of links between neighboring agents, making the network highly clustered. Moreover, the large number of younger agents that connect to the older ones with higher degrees are less clustered and thus gives rise to a negative clustering degree correlation (as conjectured by Jackson and Rogers 2007). Finally, while the results for different observation radii are fairly robust as long as the observation radius does not become too large, this does not hold for the average clustering coefficient, which is decreasing sharply with the observation radius ns.Asthe number of links are distributed across a larger number of agents when nsincreases, the formation of triangles becomes less likely and, hence, the clustering coefficient declines. 6. Robustness analysis and extensions 6.1 Undirected links An extension to the network formation process we have introduced in Definition 1 is to allow entering agents to observe not only the out-neighbors of incumbent agents (the ones to which these agents have formed links), but also their in-neighbors (the ones 40See (29) and (30)inAppendix B.4.2. Theoretical Economics 11 (2016) The formation of networks 835 from which they have received links). The resulting network can then be viewed as an undirected graph. One can show that the distributions of the network statistics we have considered follow a similar behavior as in the case of directed links. The degree distribution exhibits a power-law decay k−αwith exponent α=3+1/(mβ) for a large observation radius and α=3+1/m for a small observation radius. Note, however, that by introducing undirected links, the rigorous approach to derive the degree distributions for a small observation radius in Section 3.2 is no longer viable, because there is no straightforward way to compute the sample size |St|. Instead, one has to resort to an approximation as |St|≈ns(¯ d+1). The results obtained using this approximation are given in supplementary Appendix G. 6.2 Heterogeneous linking opportunities We can introduce heterogeneity in the linking opportunities of entering agents by assuming that a fixed fraction 1−p,withp∈(01), of the population of agents does not form any links and remains passive throughout the evolution of the network. Moreover, one can also allow for a varying number of links to be created by each entrant following a certain distribution function with given mean m≥1. This extension is studied in the accompanying supplementary Appendix H.41 We find degree distributions that follow a power-law decay k−αwith exponent α=2+1/(βmp) for a large observation radius and α=1+(1+m)/(mp) for a small observation radius. The main difference with respect to the basic model in Definition 1 is that this extension gives rise to a nontrivial component structure of the network, where the component size distribution exhibits a power-law decay. In the special case of β=0and ns=m=1one can show that the distribution P(s) of components of size sis identical for both large and small observation radii and decays as a power law with exponent 1+1/p. Moreover, we find an assortative trend for the nearest neighbor connectivity (in the closure of the graph) when the observation radius nsand pare small enough in the large noise limit (β→0). Note, however, that differently to Proposition 1,avalueofp<1can lead to the emergence of multiple quasi-stars in the limit of vanishing noise (β→∞) when the observation radius is small, and an analytic characterization as in Proposition 1 becomes harder to obtain. 6.3 From assortative to dissortative networks Finally, when combining the model with undirected links and heterogeneity in the number of links that entrants can form, a transition from an assortative to a dissortative network can be observed when varying the parameter β, which is related to the noise in the payoff function of the agents. Figure 7 shows two examples for the average nearest neighbor degree distribution knn(k),eitherforβ=0(left panel) or for β=5(right panel). Recall that βis a parameter related to the level of noise in the payoff function of the agents and their decisions with whom to form a link. For β=0(large noise) we 41A related, more general setup is introduced in Vigier (2014), where agents’ propensities to form a link follow a certain distribution that allows the incorporation of homophily, making more similar agents more likely to connect. 836 Michael D. König Theoretical Economics 11 (2016) Figure 7. Left panel: The average nearest neighbor degree distribution knn(k). The parameters used are T=50,000,ns=2,m=4,p=07,andβ=0. Right panel: The average nearest neighbor degree distribution knn(k) with the same parameters except for β=5. see that knn(k) is increasing with the degree k, indicating an assortative network, while for β=5(weak noise) we find that knn(k) is decreasing with the degree k, characterizing a dissortative network.42 While dissortativity does not play any role in the empirical networks we consider in Section 7, dissortativity has been found, for example, in trade networks (see the working paper version König 2011).43 7. Empirical implications To bring the model to data, I consider three different real-world collaboration networks in which knowledge diffusion and spillovers are an important source of knowledge generation and dissemination. First, I analyze a network of inventors constructed from United States Patent and Trademark Office (USPTO) patent data in the year 2009.44 I consider only patents in the drugs and medical sector with patent classification numbers 424 and 514 (see also the classification in Hall et al. (2001)). I focus on the drugs development sector due to the high collaboration intensity in this sector as well as for practical reasons, since for the size of the subsample corresponding to this sector our estimation process is feasible, while larger sample sizes would make the estimation of the model computationally difficult.45 The network of co-inventors is constructed by creating a link between any pair of inventors that has appeared together on a patent. The resulting network is undirected. I use this network as a proxy for the social network of inventors, in which local knowledge spillovers take place.46 This gives us a network with 27,492 nodes, an average degree of ¯ d=351, and a degree variance of σ2 d=3003 (with a coefficient of variation of 42Note that as Jackson and Rogers (2007) do not provide results for knn(k) and they do not have a payoff function governing the decision with whom to form a link, this transition cannot be studied or observed in their setup. 43For a classification of assortative vs. dissortative networks, see Newman (2002). 44See Lai et al. (2009) for a more detailed description of the data. 45The statistics computed for this subsample of the original data set are similar to the full sample or other subsamples for different sectors. 46As noted by Fafchamps et al. (2006), in the context of scientific co-authorship networks, the (unobserved) social network of personal acquaintances has more links than the co-inventor network. However, Theoretical Economics 11 (2016) The formation of networks 843 After sampling nsnodes uniformly at random, it must hold that [m]⊆Stwith probability 1. The reason is that either one of the agents in [m]is observed directly. Since each of them has an outgoing link to all other agents in [m], they all enter the sample St. Otherwise, if one of the agents not in [m]is observed directly, we know from the definition of the quasi-star that such an agent has outgoing links to all the agents in [m]and, therefore, they all enter the sample St.Theagentsin[m]are the ones with the highest degree in Gt−1and so they receive all the mlinks. It follows that the network Gtmust beaquasi-star. Hence,forallns≥1and T>m+1, we must have that in the limit of β→∞,Gβ T∈m+1 Talmost surely. Next, we consider part (ii) of the proposition. In the limit of strong shocks, as β→0, we obtain from (2) that lim β→0 Ptfδ t(Gt−1j)+εtj =max k∈St fδ t(Gt−1k)+εtk=1 |St| It follows that the entrant selects magents uniformly without replacement from the sample Stwith probability 1as β→0. The probability that an agent jreceives a link by the entrant is then given by lim β→0Kβ t(j|Gt−1St)=m |St| 1St(j) Let us consider the sequence (Gt)T t=m+2with ns≥1and assume that Gt−1∈m t−1.Weare interested in the probability Pt(Gt∈m t|Gt−1∈m t−1).WehavethatGt∈m tif only the magents in the set [m]receive a link by the entrant at time t.GiventhesampleSt,the probability that this happens is m |St|m−1 |St|−1···1 |St|−m+1=m!|(St|−m)! |St|! =|St| m−1 (9) Consequently, we then can write Pt(Gt∈m t|Gt−1∈m t−1)= St∈Pt−1|St| m−1 Pt(St|Gt−1∈m t−1) (10) Due to the properties of the quasi-star Gt−1∈m t−1, the sample can only be of size |St|= m+1m+2m+1+ns. The sample Sthas size m+1if all the nsdraws are from the m+1nodes in the set [m+1]that are in the initial complete graph Km+1.Itisof size m+2if ns−1draws are from the set [m+1], and one agent is drawn from the remaining agents, and so on. An illustration can be seen in Figure 9.LetX0denote the number of agents drawn from the set [m+1]and let X1be the number of agents drawn from the remaining agents in the set [t−1]\[m+1].ThenX0follows a hypergeometric distribution, and the sample size distribution is given by Pt(|St|=m+1+k|·)=Pt(X0=ns−kX1=k|·)=m+1 ns−kt−m−2 k t−1 ns 844 Michael D. König Theoretical Economics 11 (2016) |St|X0X1 m+1ns0 m+2ns−11 m+3ns−22        m+1+ns0ns Figure 9. Left panel: Illustration of the selection of agents in a quasi-star by the entrant t.The filled circles indicate the nodes present in the initial complete graph Km+1. Right panel: The variable X0denotes the number of agents drawn from the set [m+1]and X1denotes the number of agents drawn from the remaining agents in the set [t−1]\[m+1]. The table shows the possible values for |St|,X0,andX1. Theexpectedsamplesizeis Et[|St||·] = ns  k=0 (m +1+k)Pt(|St|=m+1+k|·)=(m +1+k)m+1 ns−kt−m−2 k t−1 ns =ns+m+1−ns(m +1) t−1 We thus find that the expected sample size is decreasing with ns. Moreover, we have that the sample size distribution for ns+1first-order stochastically dominates the distribution for ns.Let0≤l≤ns. Then first-order stochastic dominance is implied by l  k=0m+1 ns−kt−m−2 k t−1 ns≥ l  k=0m+1 ns+1−kt−m−2 k t−1 ns+1 which is equivalent to 0≤ l  k=0t−2−m km+1 ns−k t−1 ns−m+1 ns+1−k t−1 ns+1 =(l +1)(ns−l−m−2) t(ns−l) −m(ns+1)−2(ns+1) ×t−m−2 l+1 t−1 nst−1 ns+1t−1 nsm+1 ns−l−t−1 ns+1 m+1 ns−l−1 =(l +1)(ns−l−m−2) t(ns−l) −m(ns+1)−2(ns+1)t−m−2 l+11+t−ns−1 ns+1 ns−l ns−l−m−2m+1 ns−l t−1 ns+1 =l+1 ns+1t−m−2 l+1m+1 ns−l t−1 ns+1 Theoretical Economics 11 (2016) The formation of networks 845 The last expression is nonnegative for all admissible parameter values. If one distribution is first-order stochastically dominated by another, then the expected value of any decreasing function of a random variable governed by the first distribution is higher than the expectation under the latter (see, e.g., Mas-Colell et al. 1995). Since (9)isa decreasing function of the sample size |St|, we can apply stochastic dominance and it follows that (10) is decreasing with ns. The network Gt≤m+1is the complete graph Km+1and, therefore, is a quasi star. The probability of observing a quasi-star in period Tis given by P(GT∈m T)=T t=m+2Pt(Gt∈m t|Gt−1∈m t−1).Aswehaveshownabove, the probability Pt(Gt∈m t|Gt−1∈m t−1)is decreasing in nsfor any t≥m+2.Thus,if β→0, it follows that for a sequence (Gβ t)T t=m+2of networks generated under n(1) sand a sequence (Hβ t)T t=m+2of networks generated under n(2) swith n(1) s>n (2) s,wemusthave that limβ→0P(Gβ T∈m T)<limβ→0P(Hβ T∈m T). B.2 The degree distributions Let us review some notation we have introduced in the main part of the paper. For all t≥1we denote by Nt(k) ≡t i=01k(dGt(i)) the number of nodes in the graph Gtwith in-degree k. The relative frequency of nodes with in-degree kis accordingly defined as Pβ t(k) ≡(1/t)Nt(k) for all t≥1. The sequence {Pβ t(k)}k∈Nis the (empirical) degree distribution. In the following text, we will show almost sure convergence of the empirical degree distribution to its expected value (see Propositions 9and 10), and explicitly characterize the limiting distribution (see the proofs of Propositions 2and 3,and Corollary 1). We will now derive a recursive system that can be used to describe the time evolution of the expected degree distribution. Let Nt≡{Nt(k)}k≥0. Denoting k=d− Gt−1(j),we write the attachment kernel as Kβ t(j|Gt−1)=a(k)/(tζ(βm)) +o(1/t). The expected number of nodes with in-degree kat time tcan increase by the creation of a link to a node with in-degree k−1or it decreases by the creation of a link to a node with indegree k. It then follows that E[Nt+1(k)|Nt]=Nt(k)1−a(k) tζ(βm)+Nt(k −1)a(k −1) tζ(βm) +δ0k +o1 t(11) Taking expectations on both sides of (11), dividing by t+1, and denoting Pβ t(k) = E[Nt(k)]gives us Pβ t+1(k) =t t+1Pβ t(k)1−a(k) tζ(βm)+Pβ t(k −1)a(k −1) tζ(βm) +1 tδ0k+o1 t Some algebraic manipulations allow us to write this as Pβ t+1(k) −Pβ t(k) =bt(k)[ct(k) −Pβ t(k)]+o1 t(12) 846 Michael D. König Theoretical Economics 11 (2016) where bt(k) ≡ζ(βm) +a(k) ζ(βm) 1 t+1 ct(k) ≡Pβ t(k −1)a(k −1) ζ(βm) +a(k) +ζ(βm) ζ(βm) +a(k)δ0k The following lemma gives us a simple way to determine the asymptotic solution (i.e., as t→∞)oftherecursionin(12). Lemma 1. Let (xn),(yn),(ηn),and(rn)denote real sequences such that xn+1−xn=ηn(yn−xn)+rn and (i) limn→∞ yn=x, (ii) ηn>0,∞ n=1ηn=∞and there exists a N0such that for all n≥N0,ηn<1, and (iii) rn=o(ηn). Then limn→∞ xn=x. For the proof of Lemma 1,seeJordan (2006, p. 229). For our purposes the lemma can be applied by identifying xt=Pβ t(k),ηt=bt(k) and yt=ct(k).Wehavethatbt(k) > 0and t≥0bt(k) =∞since ζ(βm) < ∞.Under this condition it is evident that ct(k) has a well defined limit, which is determined in a recursive way. We give a proof by induction. The induction basis follows from the case of k=0,where c(0)≡lim t→∞ ct(0)=ζ(βm) ζ(βm) +a(0) To proceed with the induction proof, suppose we have already determined the lower tail of the distribution c(0)=Pβ(0),,c(k −1)=Pβ(k −1),k>0.Thenweseethat c(k) ≡lim t→∞ ct(k) =Pβ(k −1)a(k −1) ζ(βm) +a(k) and iterating this equation with respect to kgives us c(k) =Pβ(0) k  j=1 a(j −1) ζ(βm) +a(j) Hence, we get for the explicit expression for the asymptotic degree distribution Pβ(k) =ζ(βm) ζ(βm) +a(0) k  j=1 a(j −1) ζ(βm) +a(j)(13) This general scheme can be used to determine the degree distribution for the different parameters we consider, as we show now in the following proof. Proof of Proposition 2.Forβ→0the attachment kernel of (3)isgivenby Kβ t(j|Gt−1)=a(k)/(tζ(βm)) +o(1/t),wherek=dGt−1(j),a(k) =1+βk,andζ(βm) = Theoretical Economics 11 (2016) The formation of networks 847 (1+βm)/m. We then can apply (13), noting that the product on the right-hand side admits a closed-form representation in terms of Gamma functions as Pβ(k) =1+βm 1+m(1+β) 1 β+k2+1+βm βm  1 β2+1+m 1+βm +k(14) By Stirling’s formula we can approximate the Gamma function for large kas57 (k) (k +c) =k−c1+O1 k(15) For the tails of the degree distribution in (14) this implies that Pβ(k) ∼ (1+βk)−(2+1/(βm))(1+O(1/k)) for large k. Thecaseofβ=0can be treated analogously. Proof of Corollary 1. The degree distribution in (5) follows from the attachment kernel K0 t(j|Gt−1)=a(k)/(tζ(βm)) +o(1/t) =m/t +o(1/t) and inserting a(k) =1and ζ(βm) =1/m into (13).  Similarly, we can derive the asymptotic degree distribution in Proposition 3 for β=0 when the observation radius nsis small enough. The proof is given in the following text. Proof of Proposition 3. With the attachment kernel from (7)givenbyK0 t(j|Gt−1)= a(k)/(tζ(βm)) +o(1/t) =(m/(m +1))((1+k)/t) +o(1/t),wherek=dGt−1(j),a(k) = 1+k,andζ(βm) =(m +1)/m, we can apply (13)toobtain P(k)=(1+m)3+1 m(k +1) (1+2m)3+1 m+kk≥0 Using (15)wegetP(k)∼k−(2+1/m) for large k. 57By Stirling’s formula we can approximate the Gamma function for large kas (k) =2π kk ek1+O1 k Hence, (k) (k +a) =1+O1 k(1+a/k)(1+a/k)−kk k+akk+a e−a  Since (1+a/k) →1for k→∞, this term is asymptotically negligible. Additionally (1+a/k)−k→e−afor k→∞, and (k +a)−a∼k−afor k→∞. Hence, the leading order approximation of the ratio of Gamma functionsisgivenby (k) (k +a) =k−a1+O1 k 848 Michael D. König Theoretical Economics 11 (2016) Finally, we can give an upper bound on the deviations for finite tand show that the empirical degree distribution is a consistent estimator of the expected degree distribution in the limit of large t. Proposition 9. Let the empirical in-degree distribution be given by {Pt(k)}k∈N.Then for any >0we have that PtPt(k) −Et[Pt(k)]≥≤2exp−2t 8(m +1)2(16) and Pt(k) converges in probability to Et[Pt(k)]for large t. Proof. Let the number of vertices with in-degree kin network Gt=NtEtbe denoted by Nt(k) =i∈Nt1d− Gt−1(i)(k) =|Nt|Pt(k). Consider the filtration Fn=σ(G1G2 Gn),1≤n≤t, which is the smallest σ-algebra generated by G1G2Gn,with the property that Fn⊆Fn+1,andletF∞be the σ-algebra generated by the infinite union of the Fn’s. For n=1s, we denote the conditional expectation of the number of vertices with in-degree kat time s, conditional on the filtration Fn,byZn= Et[Nt(k)|Fn].First,fromthefactthatNt(k) ≤t, it follows that Et[|Zn|] = Et[Zn]= Et[Nt(k)]≤t<∞. Second, since Fn⊆Fn+1, we have that for all n≤t−1,Et[Zn+1|Fn]= Et[Et[Nt(k)|Fn+1]|Fn]=Et[Nt(k)|Fn]=Zn.Wethusfindthat(Zn)t n=1is a martingale with respect to (Fn)t n=1. Moreover, note that Z1=Et[Nt(k)|F1]=Et[Nt(k)|G1], since F1contains no more information than the initial network G1.TheZtis given by Zt=Et[Nt(k)|Ft]=Nt(k). Therefore, we have that Zt−Z1=Nt(k)−Et[Nt(k)|G1]. Next, we show that |Zn−Zn−1|≤ 2(m +1). To see this note that Zn=Et[Nt(k)|Fn]=i∈NtPt(dGt−1(i) =k|Fn)and, similarly, Zn−1=Et[Nt(k)|Fn−1]=i∈NsPt(dGt−1(i) =k|Fn−1),sothatwecanwrite Zn−Zn−1= i∈NtPt(dGt−1(i) =k|Fn)−Pt(dGt−1(i) =k|Fn−1)(17) In Fn−1we know where the edges up to time n−1have been attached. In Fnwe know in addition where the edges in the nth step are attached. These edges affect the total degree of m+1vertices, namely those receiving a link and those initiating the links. For the conditional expectation given Fn, we need to take the expectation over all possible ways of attaching the remaining edges in the periods n+1s. Only the distribution of the degrees of the vertices that have obtained or initiated an edge in period nare affected by the knowledge of Fn, compared to the knowledge of Fn−1. Neither the probability of the other vertices to receive a link nor the probability to initiate a link is affected by the creation of the edges in the nth step. Thus, also the law of their total degree is unaffected. There are at most m+1vertices that receive or initiate a link in period n. Therefore, (17) shows that the distribution of at most 2(m +1)vertices in Gt is different by conditioning on Fncompared to conditioning on Fn−1. This implies that |Zn−Zn−1|≤2(m +1). We then can apply the Azuma–Hoeffding inequality (see, e.g., Theoretical Economics 11 (2016) The formation of networks 849 Grimmett and Stirzaker 2001) to obtain, for any η>0, PtNt(k) −Et[Nt(k)|G1]≥η≤2exp−η2 8(m +1)2t and by choosing η=t,(16) follows.  With Proposition 9 we are now able to show almost sure convergence of the empirical degree distribution to its expected value. Proposition 10. For a fixed k≥0,Pt(k) as −→ Et[Pt(k)]as t→∞. Proof. The proof follows from the Borel–Cantelli lemma (see, e.g., Grimmett and Stirzaker 2001)andProposition 9 by observing that for any >0, ∞  t=1 PtPt(k) −Et[Pt(k)]≥≤2 ∞  t=1 e−(2t)/(8(m+1)2)=1 e(2)/(8(m+1)2)−1<+∞ B.3 Efficiency Proof of Proposition 4. Part (i) of the proposition is a direct consequence of part (ii) of Proposition 1. Part (ii) of the proposition follows from the fact that networks generated under (Ht)T t=m+2have a finite degree variance, while the degree variance of networks generated under (Gt)T t=m+2diverge with T, since the first has a geometric degree distribution while the latter has a power-law degree distribution in the large Tlimit. More precisely, the degree variance under HTis given by σ2 d=lim T→∞ T  k=0 1 1+mm m+1k (k −m)2=m(m +1)<+∞ while the variance under GTis σ2 d=lim T→∞ T  k=0 (m +1)3+1 m(k +1) (1+2m)3+1 m+k(k −m)2=lim T→∞ O(T1−1/m)=+∞ if m>1, while for m=1we get σ2 d=lim T→∞4HT+1−4(1+T)(5+3T) 6+5T+T2=+∞ where HTis the harmonic number, diverging as ln Tfor large T. 850 Michael D. König Theoretical Economics 11 (2016) B.4 Higher order statistics The results of this section are derived using a continuum approximation in which both time and degree are treated as continuous variables in R+(see Dorogovtsev and Mendes 2013, p. 117). In this continuum approach, the probability that a vertex shas in-degree d− Gt(s) =kat time tis given by δ(k −¯ k(st)),where ¯ k(st) =Et[d− Gt(s)]denotes the expected degree of vertex sat time t. The degree distribution can then be obtained from Pt(k) =1 tt 0 δ(k −¯ k(st))ds =−1 t∂¯ k(st) ∂s −1s=s(kt) (18) So as to compare this approximation with our previous analysis, we will derive the degree distributions in the case of a large and a small observation radius. To ease the notation we will denote by ks(t) the in-degree d− Gt(s) of a vertex sat time tfor the remainder of this section, and we will focus only on the in-degree ks(t), since it uniquely determines the total degree dGt(s) =ks(t) +mand vice versa. We first consider the expected change in the in-degree ks(t) of a vertex sreceiving a link from an entrant twhen St=Pt−1(large observation radius). In the continuum approximation, the corresponding expectation in the time interval [tt +t) is given by Et[ks(t +t)−ks(t)|Gt]≈(m/(1+βm))((1+βks(t))/t)t for large t,where(3) describes a transition rate and t =O(1/T). The evolution of the in-degree of vertex sat time tis governed by the differential equation dks(t) dt =lim t↓0 Et[ks(t +t) −ks(t)|Gt] t =m 1+βm 1+βks(t) t with the initial condition ks(s) =0for all s≥0. The solution is given by ks(t) =1 βt s(mβ)/(1+mβ) −1(19) From (18)wethenget Pβ(k) =1+βm m(1+βk)−(2+1/(βm))(20) with ∞ 0Pβ(k)dk =1. This is asymptotically equivalent to the degree distribution we obtained in (4). Similarly,inthecaseofnssmall enough (small observation radius), we have from (7)thatEt[ks(t +t) −ks(t)|Gt]≈(m/(1+m))((1+ks(t))/t)t for large t.Thetime evolution of the in-degree of a vertex scan then be written as dks(t) dt =m m+1 ks(t) +1 t with the initial condition ks(s) =0for all s≥0. The solution is given by ks(t) =t sm/(m+1) −1(21) Theoretical Economics 11 (2016) The formation of networks 851 From (18)wethenget P(k)=m+1 m(1+k)−(2+1/m)(22) with the property that ∞ 0P(k)dk =1. Comparing this distribution with the one in (8) shows that they are both asymptotically equivalent. Since the continuum approximation delivers only meaningful results in the large tlimit, we will consider only the leading order terms in O(1/t) in our derivations in the following sections. B.4.1 Average nearest neighbor degree distribution Proof of Proposition 5.LetR− s(t) denote the sum of in-degrees of the in-neighbors of a vertex sat time t,thatis,R− s(t) =j∈N− Gt(s) kj(t). In the continuum approximation, with the attachment kernel from (3), we have up to leading orders in O(1/t) that dR− s(t) dt = j∈N− Gt(s) m1+βkj(t) (1+βm)t =a tR− s(t) +a βt kj(t) =a tR− s(t) +a β2tt sa −1 wherewehavedenoteda≡(mβ)/(1+mβ). Wit the initial condition R− s(s) =0we obtain R− s(t) =1 β21+alnt s−1t sa and the average nearest neighbor in-degree is given by k− nn(ks)=R− s(t)/ks.From(19) we know that t/s =(1+βks)1/a, and we obtain k− nn(k) =1 β2k1+(ln(1+βk) −1)(1+βk)(23) Next, we turn to the analysis of the average nearest out-neighbor in-degree. Let us denote by R+ s(t) the sum of the in-degrees of the out-neighbors of vertex sat time t,thatis, R+ s(t) =j∈N+ Gt(s) kj(t). Up to leading orders in O(1/t) we can write dR+ s(t) dt = j∈N+ Gt(s) a t1 β+kj(t)=a tm β+R+ s(t) The solution is given by R+ s(t) =−m β+Csta(24) where the constant Csis determined by the initial conditions. They are given by R+ s+1= s  j=1 a s1 β+kj(s)(kj(s) +1)=a β2β(1+m(β −1)) −1+s2a−1ζ(s2a) 852 Michael D. König Theoretical Economics 11 (2016) where ζ(s2a) is the Hurwitz zeta function.58 Together with the solution (24)wethenget R+ s(t) =1 β2βm(1+p(β −1)) +a ss2aζ(s2a) t s+1a −mβ The average nearest out-neighbor in-degree is then given by k+ nn(k) =R+ s/m,thatis, k+ nn(k) =1 β2mβm(1+p(β −1)) +a ss2aζ(s2a) t s+1a −mβ Hence, we find that for large k, the average nearest in-neighbor connectivity grows logarithmically with kand is independent of t, while the average nearest out-neighbor connectivity becomes independent of kand grows with the network sizes as t(βm)/(1+βm). Proof of Proposition 6.LetR− s(t) denote the sum of in-degrees of the in-neighbors of a vertex sat time t,thatis,R− s(t) =j∈N− Gt(s) kj(t). In the continuum approximation, with the attachment kernel from (7), we have up to leading orders in O(1/t) that59 dR− s(t) dt =a t j∈N− Gt(s) (1+kj(t)) =a tks(t) +a tR− s(t) wherewehavedenoteda≡m/(1+m). In the continuum approximation we have that ks(t) =(t/s)a−1(see (21)), so that we can write dR− s(t) dt =a tt sa −1+a tR− s(t) The solution is given by R− s(t) =Csta+1+at sa lnt where the constant Csis determined by the initial conditions given by R− s(s) =0.With these initial conditions we get R− s(t) =1−t sa +at sa lnt s Further, using the fact that s(kt) =t/((k +1)1/a)we obtain R− s(t) =1+(k +1)(ln(k +1)−1) It follows that k− nn =R− s k=1 k1+(k +1)(ln(k +1)−1) 58The Hurwitz zeta function is defined by ζ(sa) ≡∞ n=01/(a +n)s. 59We ignore cases in which two or more neighbors of sare found as the neighbors of directly observed vertices (other than s), which happens with probability O(1/t2). Theoretical Economics 11 (2016) The formation of networks 859 Calvó-Armengol, Antoni and Joan De Martï (2007), “Communication networks: Knowledge and decisions.” American Economic Review, 97, 86–91. [814] Chaney, Thomas (2014), “The network structure of international trade.” American Economic Review, 104, 3600–3634. [818] Chernozhukov, Victor and Han Hong (2003), “An MCMC approach to classical estimation.” Journal of Econometrics, 115, 293–346. [839] Chib, Siddhartha (2001), “Markov chain Monte Carlo methods: Computation and inference.” In Handbook of Econometrics (James J. Heckman and Edward Leamer, eds.), 3569–3649, Elsevier Science, Amsterdam, The Netherlands. [839,840] Cooper, Colin and Alan Frieze (2003), “A general model of web graphs.” Random Structures & Algorithms, 22, 311–335. [839,841] Dorogovtsev, Sergei N. and José F. F. Mendes (2013), Evolution of Networks: From Biological Nets to the Internet and WWW. Oxford University Press, New York. [831,850] Ductor, Lorenzo (2015), “Does co-authorship lead to higher academic productivity?” Oxford Bulletin of Economics and Statistics, 77, 385–407. [817,820] Durrett, Rick (2007), Random Graph Dynamics. Cambridge University Press, New York. [814] Dutta, Bhaskar, Sayantan Ghosal, and Debraj Ray (2005), “Farsighted network formation.” Journal of Economic Theory, 122, 143–164. [819,822] Fafchamps, Marcel, Marco J. Van der Leij, and Saneev Goyal (2006), “Scientific networks and co-authorship.” Department of Economics Dicussion paper series, University of Oxford. [836] Fafchamps, Marcel, Marco J. Van der Leij, and Sanjeev Goyal (2010), “Matching and network effects.” Journal of the European Economic Association, 8, 203–231. [814,816] Fleming, Lee, Charles King III, and Adam I. Juda (2007), “Small worlds and regional innovation.” Organization Science, 18, 938–954. [814] Frank, Ove (1977), “Survey sampling in graphs.” Journal of Statistical Planning and Inference, 1, 235–264. [815,821] Friedkin, Noah E. (1983), “Horizons of observability and limits of informal control in organizations.” Social Forces, 62, 54–77. [815,822] Galeotti, Andrea and Sanjeev Goyal (2010), “The law of the few.” American Economic Review, 100, 1468–1492. [825] Galeotti, Andrea, Sanjeev Goyal, Matthew O. Jackson, Fernando Vega-Redondo, and Leeat Yariv (2010), “Network games.” Review of Economic Studies, 77, 218–244. [815,822] Geweke, John (1992), “Evaluating the accuracy of sampling-based approaches to the calculation of posterior moments.” In Bayesian Statistics 4 (José M. Bernardo and Morris H. DeGroot, eds.), 169–193, Oxford University Press, New York. [840] 860 Michael D. König Theoretical Economics 11 (2016) Ghiglino, Christian (2011), “Random walk to innovation: Why productivity follows a power law.” Journal of Economic Theory, 147, 713–737. [818] Goodman, Leo A. (1961), “Snowball sampling.” Annals of Mathematical Statistics, 32, 148–170. [815] Goyal, Sanjeev (2007), Connections: An Introduction to the Economics of Networks. Princeton University Press, Princeton, New Jersey. [814] Goyal, Sanjeev and Sumit Joshi (2006), “Unequal connections.” International Journal of Game Theory, 34, 319–349. [825] Goyal, Sanjeev and José L. Moraga-González (2001), “R&D networks.” RAND Journal of Economics, 32, 686–707. [815] Goyal, Sanjeev, Marco J. Van der Leij, and Jose Luis Moraga-González (2006), “Economics: An emerging small world.” Journal of Political Economy, 114, 403–412. [814,816] Grimmett, Geoffrey R. and David R. Stirzaker (2001), Probability and Random Processes, third edition. Oxford University Press, Oxford. [849] Hagenbach, Jeanne and Frédéric Koessler (2010), “Strategic communication networks.” Review of Economic Studies, 77, 1072–1099. [814] Hall, Bronwyn H., Adam B. Jaffe, and Manuel Trajtenberg (2001), “The NBER patent citation data file: Lessons, insights and methodological tools.” NBER Working Paper 8498. [836] Jackson, Matthew O. (2008), Social and Economic Networks. Princeton University Press, Princeton, New Jersey. [814] Jackson, Matthew O. and Brian W. Rogers (2007), “Meeting strangers and friends of friends: How random are social networks?” American Economic Review, 97, 890–915. [814,815,817,818,820,821,822,830,831,834,836] Jackson, Matthew O. and Asher Wolinsky (1996), “A strategic model of social and economic networks.” Journal of Economic Theory, 71, 44–74. [815] Jones, Benjamin F., Stefan Wuchty, and Brian Uzzi (2008), “Multi-university research teams: Shifting impact, geography, and stratification in science.” Science, 322, 1259– 1262. [817,841] Jordan, Jonathan (2006), “The degree sequences and spectra of scale-free random graphs.” Random Structures & Algorithms, 29, 226–242. [846] Kolaczyk, Eric D. (2009), Statistical Analysis of Network Data: Methods and Models. Springer-Verlag, New York. [815,821] Kolotilin, Anton (2013), “Estimation of a scale-free network formation model.” Working Paper. [839] König, Michael D. (2011), “The formation of networks with local spillovers and limited observability.” SIEPR Discussion Paper 11-004. [836] Theoretical Economics 11 (2016) The formation of networks 861 König, Michael D., Stefano Battiston, Mauro Napoletano, and Frank Schweitzer (2012), “The efficiency and stability of R&D networks.” Games and Economic Behaviors, 75, 694– 713. [820,825] König, Michael D., Claudio J. Tessone, and Yves Zenou (2009), “A dynamic model of network formation with strategic interactions.” CEPR Discussion Paper DP7521. [825] Kovᡠrík, Jaromír and Marco J. Van der Leij (2014), “Risk aversion and networks.” Review of Network Economics, 13, 121–155. [818] Krapivsky, Paul L. and Sidney Redner (2001), “Organization of growing random networks.” Physical Review E, 63, 066123. [817] Krapivsky, Paul L., Sidney Redner, and Francois Leyvraz (2000), “Connectivity of growing random networks.” Physical Review Letters, 85, 4629–4632. [817] Kumar, Ravi, Prabhakar Raghavan, Sridhar Rajagopalan, D. Sivakumar, Andrew Tomkins, and Eli Upfal (2000), “Stochastic models for the Web graph.” In Proceedings of the 41st Annual Symposium on the Foundations of Computer Science, 2000, 57–65, IEEE, Redondo Beach, California. [817] Lai, Ronald, Alexander D’Amour, and Lee Fleming (2009), “The careers and coauthorship networks of U.S. patent-holders, since 1975.” Harvard Business School, Harvard Institute for Quantitative Social Science. [836] Leskovec, Jure, Jon Kleinberg, and Christos Faloutsos (2007), “Graph evolution: Densification and shrinking diameters.” ACM Transactions on Knowledge Discovery from Data (TKDD),1,ArticleNo.2.[837] Marjoram, Paul, John Molitor, Vincent Plagnol, and Simon Tavaré (2003), “Markov chain Monte Carlo without likelihoods.” Proceedings of the National Academy of Sciences, 100, 15324–15328. [839] Marshall, Alfred (1919), Industry and Trade. McMillan, London. [814] Mas-Colell, Andreu, Michael Dennis Whinston, and Jerry R. Green (1995), Microeconomic Theory. Oxford University Press, New York. [845] McBride, Michael (2006), “Imperfect monitoring in communication networks.” Journal of Economic Theory, 126, 97–119. [815,822] McFadden, Daniel (1981), “Econometric models of probabilistic choice.” In Structural Analysis of Discrete Data With Econometric Applications (Charles F. Manski and Daniel McFadden, eds.), 198–272, The MIT Press, Cambridge, Massachusetts. [823] McFadden, Daniel (1989), “A method of simulated moments for estimation of discrete response models without numerical integration.” Econometrica, 57, 995–1026. [839] Móri, Tamás F. (2005), “The maximum degree of the Barabási–Albert random tree.” Combinatorics, Probability and Computing, 14, 339–348. [826] Newman, Mark (2001a), “The structure of scientific collaboration networks.” Proceedings of the National Academy of Sciences, 98, 404–409. [814] 862 Michael D. König Theoretical Economics 11 (2016) Newman, Mark (2001b), “Clustering and preferential attachment in growing networks.” Physical Review E, 64, 025102. [815,817,820] Newman, Mark (2002), “Assortative mixing in networks.” Physical Review Letters, 89, 208701. [814,832,836,837] Newman, Mark (2004), “Coauthorship networks and patterns of scientific collaboration.” Proceedings of the National Academy of Sciences, 101, 5200–5205. [814] Newman, Mark (2010), Networks: An Introduction. Oxford University Press, New York. [814] Oliveira, Roberto and Joel Spencer (2005), “Connectivity transitions in networks with super-linear preferential attachment.” Internet Mathematics, 2, 121–163. [817] Pakes, Ariel and David Pollard (1989), “Simulation and the asymptotics of optimization estimators.” Econometrica, 57, 1027–1057. [839] Pastor-Satorras, Romualdo, Alexei Vázquez, and Alessandro Vespignani (2001), “Dynamical and correlation properties of the Internet.” Physical Review Letters, 87, 258701. [831,832,837] Ratmann, Oliver, Ole Jørgensen, Trevor Hinkley, Michael Stumpf, Sylvia Richardson, and Carsten Wiuf (2007), “Using likelihood-free inference to compare evolutionary dynamics of the protein networks of h. pylori and p. falciparum.” PLoS Computational Biology, 3, e230. [839] Robert, Christian P. and George Casella (2004), Monte Carlo Statistical Methods. Springer-Verlag, New York. [839] Saxenian, AnnaLee (1994), Regional Advantage: Culture and Competition in Silicon Valley and Route 128. Harvard University Press, Cambridge, Massachusetts. [814] Schilling, Melissa A. and Elad Green (2011), “Recombinant search and breakthrough idea generation: An analysis of high impact papers in the social sciences.” Research Policy, 40, 1321–1331. [816,841] Singh, Jasjit (2005), “Collaborative networks as determinants of knowledge diffusion patterns.” Management Science, 51, 756–770. [814,815,817] Sisson, Scott A. and Yanan Fan (2011), “Likelihood-free MCMC.” In Handbook of Markov Chain Monte Carlo (Steve Brooks, Andrew Gelman, Galin L. Jones, and Xiao-Li Meng, eds.), Chapman & Hall/CRC, New York. [839] Snijders, Tom A. B. (2001), “The statistical evaluation of social network dynamics.” Sociological Methodology, 31, 361–395. [822] Snijders, Tom A. B., Johan Koskinen, and Michael Schweinberger (2010), “Maximum likelihood estimation for social network dynamics.” The Annals of Applied Statistics,4, 567–588. [822] Theoretical Economics 11 (2016) The formation of networks 863 Sokal, Alan D. (1996), “Monte Carlo methods in statistical mechanics: Foundations and new algorithms.” In Functional Integration: Basics and Application (Cecile DeWitt- Morette, Pierre Cartier, and Antoine Folacci, eds.), 131–192, Springer-Verlag, New York. [840] Stephan, Paula E. (2012), How Economics Shapes Science. Harvard University Press, Cambridge, Massachusetts. [841] Toivonen, Riitta, Jukka-Pekka Onnela, Jari Saramäki, Jörkki Hyvönen, and Kimmo Kaski (2006), “A model for social networks.” Physica A: Statistical Mechanics and its Applications, 371, 851–860. [817] Valverde, Sergi, Ricard V. Solé, Mark A. Bedau, and Norman Packard (2007), “Topology and evolution of technology innovation networks.” Physical Review E, 76, 056118. [814] Van Mieghem, Piet (2011), Graph Spectra for Complex Networks. Cambridge University Press, New York. [832] Vázquez, Alexei (2003), “Growing network with local rules: Preferential attachment, clustering hierarchy, and degree correlations.” Physical Review E, 67, 056104. [817] Vega-Redondo, Fernando (2007), Complex Social Networks. Cambridge University Press, New York. [814] Vigier, Adrien (2014), “Meeting friends of friends and homophily: A complementarity.” Economic Theory Bulletin, 2, 45–52. [818,823,835] von Hippel, Eric, Stefan Thomke, and Mary Sonnack (1999), “Creating breakthroughs at 3M.” Harvard Business Review, 77, 47–57. [815] Wang, Li-Na, Jin-Li Guo, Han-Xin Yang, and Tao Zhou (2009), “Local preferential attachment model for hierarchical networks.” Physica A: Statistical Mechanics and its Applications, 388, 1713–1720. [817] Watts, Duncan J. and Steven H. Strogatz (1998), “Collective dynamics of ‘small-world’ networks.” Nature, 393, 440–442. [814,831,833] West, Douglas B. (2001), Introduction to Graph Theory, second edition. Prentice-Hall, Upper Saddle River, New Jersey. [842] Westbrock, Bastian (2010), “Natural concentration in industrial research collaboration.” RAND Journal of Economics, 41, 351–371. [815,820] Winkler, Anne E., Wolfgang Glänzel, Sharon G. Levin, and Paula E. Stephan (2011), “The diffusion of information technology and the increased propensity of teams to transcend institutional and national borders.” IZA Discussion Paper 5857. [817] Co-editor Nicola Persico handled this manuscript. Submitted 2013-5-1. Final version accepted 2015-9-2. Available online 2015-9-3.