×

zbMATH — the first resource for mathematics

Nestedness in networks: A theoretical model and some applications. (English) Zbl 1395.90044
Summary: We develop a dynamic network formation model that can explain the observed nestedness in real-world networks. Links are formed on the basis of agents’ centrality and have an exponentially distributed lifetime. We use stochastic stability to identify the networks to which the network formation process converges and find that they are nested split graphs. We completely determine the topological properties of the stochastically stable networks and show that they match features exhibited by real-world networks. Using four different network data sets, we empirically test our model and show that it fits well the observed networks.

MSC:
90B10 Deterministic network models in operations research
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Adams, Robert M., Lars‐Hendrik Röller, and Robin C. Sickles (2002), “Market power in outputs and inputs: An empirical application to banking.” Finance and Economics Discussion Series 2002-52, U.S. Board of Governors of the Federal Reserve System.
[2] Åkerman, Anders and Anna Larsson (forthcoming), “The global arms trade network 1950-2007.” Journal of Comparative Economics.
[3] Bala, Venkatesh and Sanjeev Goyal (2000), “A noncooperative model of network formation.” Econometrica, 68, 1181-1229. 10.1111/1468‐0262.00155 · Zbl 1022.91047
[4] Ballester, Coralio, Antoni Calvó‐Armengol, and Yves Zenou (2006), “Who’s who in networks. Wanted: The key player.” Econometrica, 74, 1403-1417. 10.1111/j.1468‐0262.2006.00709.x · Zbl 1138.91590
[5] Barabási, Albert‐László and Réka Albert (1999), “Emergence of scaling in random networks.” Science, 286, 509-512. 10.1126/science.286.5439.509
[6] Bonacich, Phillip (1987), “Power and centrality: A family of measures.” American Journal of Sociology, 92, 1170-1182. 10.1086/228631
[7] Boss, Michael, Helmut Elsinger, Martin Summer, and Stefan Thurner (2004), “Network topology of the interbank market.” Quantitative Finance, 4, 677-684. 10.1080/14697680400020325
[8] Bramoullé, Yann and Rachel Kranton (2007), “Public goods in networks.” Journal of Economic Theory, 135, 478-494. 10.1016/j.jet.2006.06.006 · Zbl 1186.91099
[9] Bramoullé, Yann, Rachel Kranton, and Martin D’Amours (2014), “Strategic interaction and networks.” American Economic Review, 104, 898-930. 10.1257/aer.104.3.898
[10] Bramoullé, Yann, Dunia López, Sanjeev Goyal, and Fernando Vega‐Redondo (2004), “Network formation and anti‐coordination games.” International Journal of Game Theory, 33, 1-19. 10.1007/s001820400178 · Zbl 1080.91015
[11] Brooks, Stephen P. and Gareth O. Roberts (1998), “Assessing convergence of Markov chain Monte Carlo algorithms.” Statistics and Computing, 8, 319-335. 10.1023/A:1008820505350
[12] Brualdi, Richard A. and Alan J. Hoffman (1985), “On the spectral radius of (0,1)‐matrices.” Linear Algebra and Its Applications, 65, 133-146. 10.1016/0024‐3795(85)90092‐8
[13] Cabrales, Antonio, Antoni Calvó‐Armengol, and Yves Zenou (2011), “Social interactions and spillovers.” Games and Economic Behavior, 72, 339-360. 10.1016/j.geb.2010.10.010 · Zbl 1229.91248
[14] Calvó‐Armengol, Antoni and Yves Zenou (2004), “Social networks and crime decisions: The role of social structure in facilitating delinquent behavior.” International Economic Review, 45, 939-958. 10.1111/j.0020‐6598.2004.00292.x
[15] Chib, Siddhartha (2001), “Markov chain Monte Carlo methods: Computation and inference.” In Handbook of Econometrics, Vol. 5 (J. J. Heckman and E. Leamer, eds.), 3569-3649, Elsevier Science, Amsterdam. 10.1016/S1573‐4412(01)05010‐3
[16] Coe, David T. and Elhanan Helpman (1995), “International R&D spillovers.” European Economic Review, 39, 859-887. 10.1016/0014‐2921(94)00100‐E
[17] Cohen‐Cole, Ethan, Eleonora Patacchini, and Yves Zenou (2011), “Systemic risk and network formation in the interbank market.” Discussion Paper 8332, CEPR.
[18] Cvetković, Dragoš and Peter Rowlinson (1990), “The largest eigenvalue of a graph: A survey.” Linear and Multilinear Algebra, 28, 3-33. 10.1080/03081089008818026
[19] De Benedictis, Luca and Lucia Tajoli (2011), “The world trade network.” World Economy, 34, 1417-1454.
[20] Dutta, Bhaskar, Sayantan Ghosal, and Debraj Ray (2005), “Farsighted network formation.” Journal of Economic Theory, 122, 143-164. 10.1016/j.jet.2004.05.001 · Zbl 1112.91013
[21] Ellison, Glenn (2000), “Basins of attraction, long‐run stochastic stability, and the speed of step‐by‐step by evolution.” Review of Economic Studies, 67, 17-45. 10.1111/1467‐937X.00119 · Zbl 0956.91027
[22] Ethier, Stewart N. and Thomas G. Kurtz (1986), Markov Processes. Wiley, New York. 10.1002/9780470316658 · Zbl 0592.60049
[23] Freeman, Linton C. (1977), “A set of measures of centrality based on betweenness.” Sociometry, 40, 35-41. 10.2307/3033543
[24] Freeman, Linton C. (1979), “Centrality in social networks: Conceptual clarification.” Social Networks, 1, 215-239. 10.1016/0378‐8733(78)90021‐7
[25] Galeotti, Andrea and Sanjeev Goyal (2010), “The law of the few.” American Economic Review, 100, 1468-1492. 10.1257/aer.100.4.1468
[26] Galeotti, Andrea, Sanjeev Goyal, Matthew O. Jackson, Fernando Vega‐Redondo, and Leat Yariv (2010), “Network games.” Review of Economic Studies, 77, 218-244. 10.1111/j.1467‐937X.2009.00570.x · Zbl 1197.91168
[27] Gallager, Robert G. (1996), Discrete Stochastic Processes. Springer, Berlin. 10.1007/978‐1‐4615‐2329‐1 · Zbl 0925.60005
[28] Goyal, Sanjeev and Sumit Joshi (2003), “Networks of collaboration in oligopoly.” Games and Economic Behavior, 43, 57-85. 10.1016/S0899‐8256(02)00562‐6 · Zbl 1040.91043
[29] Goyal, Sanjeev, Marco van der Leij, and José Luis Moraga‐González (2006), “Economics: An emerging small world.” Journal of Political Economy, 114, 403-412. 10.1086/500990
[30] Goyal, Sanjeev and Fernando Vega‐Redondo (2005), “Network formation and social coordination.” Games and Economic Behavior, 50, 178-207. 10.1016/j.geb.2004.01.005 · Zbl 1109.91323
[31] Grassi, Rosanna, Silvana Stefani, and Anna Torriero (2007), “Some new results on the eigenvector centrality.” Journal of Mathematical Sociology, 31, 237-248. 10.1080/00222500701373251 · Zbl 1124.05063
[32] Grimmett, Geoffrey and David Stirzaker (2001), Probability and Random Processes. Oxford University Press, Oxford. · Zbl 1015.60002
[33] Grossman, Gene M. and Elhanan Helpman (1991), Innovation and Growth in the Global Economy. MIT Press, Cambridge. · Zbl 1112.91045
[34] Hagberg, Aric, Pieter Swart, and Daniel Schult (2006), “Designing threshold networks with given structural and dynamical properties.” Physical Review E, 74, 056116. 10.1103/PhysRevE.74.056116
[35] Hagedoorn, John (2002), “Inter‐firm R&D partnerships: An overview of major trends and patterns since 1960.” Research Policy, 31, 477-492. 10.1016/S0048‐7333(01)00120‐2
[36] Harrigan, Katherine R. (1988), “Strategic alliances and partner asymmetries.” Management International Review, 28, 53-72.
[37] 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. 10.1257/aer.97.3.890
[38] Jackson, Matthew O. and Alison Watts (2002a), “On the formation of interaction networks in social coordination games.” Games and Economic Behavior, 41, 265-291. 10.1016/S0899‐8256(02)00504‐3 · Zbl 1037.91017
[39] Jackson, Matthew O. and Alison Watts (2002b), “The evolution of social and economic networks.” Journal of Economic Theory, 106, 265-295. 10.1006/jeth.2001.2903 · Zbl 1099.91543
[40] Jackson, Matthew O. and Asher Wolinsky (1996), “A strategic model of social and economic networks.” Journal of Economic Theory, 71, 44-74. 10.1006/jeth.1996.0108 · Zbl 0871.90144
[41] Jackson, Matthew O. and Yves Zenou (2014), “Games on networks.” In Handbook of Game Theory, Vol. 4 (H. Peyton Young and Shmuel Zamir, eds.), 91-157, Elsevier Science, Amsterdam.
[42] Kandori, Michihiro, George J. Mailath, and Rafael Rob (1993), “Learning, mutation, and long run equilibria in games.” Econometrica, 61, 29-56. 10.2307/2951777 · Zbl 0776.90095
[43] Kemeny, John G. and Laurie J. Snell (1960), Finite Markov Chains. Van Nostrand, New York. · Zbl 0089.13704
[44] Kogut, Bruce, Pietro Urso, and Gordon Walker (2007), “Emergent properties of a new financial market: American venture capital syndication, 1960-2005.” Management Science, 53, 1181-1198. 10.1287/mnsc.1060.0620
[45] König, Michael D., Claudio J. Tessone, and Yves Zenou (2009), “A dynamic model of network formation with strategic interactions.” Discussion Paper 09‐006, CCSS.
[46] König, Michael D., Claudio J. Tessone, and Yves Zenou (2010), “From assortative to dissortative networks: The role of capacity constraints.” Advances in Complex Systems, 13, 483-499. 10.1142/S0219525910002700
[47] König, Michael D. and Claudio J. Tessone (2011), “Network evolution based on centrality.” Physical Review E, 84, 056108. 10.1103/PhysRevE.84.056108
[48] Liggett, Thomas M. (2010), Continuous Time Markov Processes: An Introduction. American Mathematical Society, New York. · Zbl 1205.60002
[49] Liu, Xiaodong, Eleonora Patacchini, Yves Zenou, and Lung‐Fei Lee (2012), “Criminal networks: Who is the key player?” Discussion Paper 8772, CEPR.
[50] Mahadev, Nadimpalli V. R. and Uri N. Peled (1995), Threshold Graphs and Related Topics. North‐Holland, Amsterdam.
[51] Marjoram, Paul, John Molitor, Vincent Plagnol, and Simon Tavaré (2003), “Markov chain Monte Carlo without likelihoods.” Proceedings of the National Academy of Sciences of the USA, 100, 15324-15328. 10.1073/pnas.0306899100
[52] Mele, Angelo (2010), “Segregation in social networks: Theory, estimation and policy.” Working Paper 10‐16, NET Institute.
[53] Minoiu, Camelia and Javier A. Reyes (2011), “A network analysis of global banking: 1978-2009.” Working paper, IMF.
[54] Newman, Mark E. J. (2002), “Assortative mixing in networks.” Physical Review Letters, 89, 208701. 10.1103/PhysRevLett.89.208701
[55] Park, Seung H. and Michael V. Russo (1996), “When competition eclipses cooperation: An event history analysis of joint venture failure.” Management Science, 42, 875-890. 10.1287/mnsc.42.6.875 · Zbl 0884.90109
[56] Pastor‐Satorras, Romualdo, Alexei Vàzquez, and Alessandro Vespignani (2001), “Dynamical and correlation properties of the Internet.” Physical Review Letters, 87, 258701. 10.1103/PhysRevLett.87.258701 · Zbl 1087.68509
[57] Rodríguez‐Gironés, Miguel A. and Luis Santamaría (2006), “A new algorithm to calculate the nestedness temperature of presence-absence matrices.” Journal of Biogeography, 33, 924-935. 10.1111/j.1365‐2699.2006.01444.x
[58] Sandholm, William H. (2010), Population Games and Evolutionary Dynamics. MIT Press, Cambridge. · Zbl 1208.91003
[59] Snijders, Tom A. B. (2001), “The statistical evaluation of social network dynamics.” Sociological Methodology, 31, 361-395. 10.1111/0081‐1750.00099
[60] 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. 10.1214/09‐AOAS313 · Zbl 1194.62132
[61] Sokal, Alan D. (1996), “Monte Carlo methods in statistical mechanics: Foundations and new algorithms.” In Functional Integration: Basics and Applications (C. DeWitt‐Morette, P. Cartier, and A. Folacci, eds.), 131-192, Plenum, New York. · Zbl 0890.65006
[62] Soramaki, Kimmo, Morten Bech, Jeffrey Arnold, Robert Glass, and Walter Beyeler (2007), “The topology of interbank payment flows.” Physica A: Statistical Mechanics and Its Applications, 379, 317-333. 10.1016/j.physa.2006.11.093
[63] Staudigl, Mathias (2011), “Potential games in volatile environments.” Games and Economic Behavior, 72, 271-287. 10.1016/j.geb.2010.08.004 · Zbl 1236.91118
[64] Uzzi, Brian (1996), “The sources and consequences of embeddedness for the economic performance of organizations: The network effect.” American Sociological Review, 61, 674-698. 10.2307/2096399
[65] Vega‐Redondo, Fernando (2007), Complex Social Networks. Cambridge University Press, Cambridge. 10.1017/CBO9780511804052 · Zbl 1145.91004
[66] Wasserman, Stanley and Katherine Faust (1994), Social Network Analysis: Methods and Applications. Cambridge University Press, Cambridge. 10.1017/CBO9780511815478 · Zbl 0926.91066
[67] Watts, Alison (2001), “A dynamic model of network formation.” Games and Economic Behavior, 34, 331-341. 10.1006/game.2000.0803
[68] Watts, Duncan J. and Steven H. Strogatz (1998), “Collective dynamics of ‘small‐world’ networks.” Nature, 393, 440-442. 10.1038/30918 · Zbl 1368.05139
[69] Young, Peyton H. (2001), Individual Strategy and Social Structure: An Evolutionary Theory of Institutions. Princeton University Press, Princeton.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.