Network formation is an aspect of network science that seeks to model how a network evolves by identifying which factors affect its structure and how these mechanisms operate. Network formation hypotheses are tested by using either a dynamic model with an increasing network size or by making an agent-based model to determine which network structure is the equilibrium in a fixed-size network.
A dynamic model, often used by physicists and biologists, begins as a small network or even a single node. The modeler then uses a (usually randomized) rule on how newly arrived nodes form links in order to increase the size of the network. The aim is to determine what the properties the network will be when it grows in size. In this way, researchers try to reproduce properties common in most real networks, such as the small world network property or the scale-free network property. These properties are common in almost every real network including the World Wide Web, the metabolic network or the network of international air routes.
The oldest model of this type is the Erdős-Rényi model, in which new nodes randomly choose other nodes to connect to. A second well-known model is the Watts and Strogatz model, which starts from a standard two-dimensional lattice and evolves by replacing links randomly. These models display some realistic network properties, but fail to account for others.
One of the most influential models of network formation is the Barabási-Albert model. Here, the network also starts from a small system, and incoming nodes choose their links randomly, but the randomization is not uniform. Instead, nodes which already possess a greater number of links will have a higher likelihood of becoming connected to incoming nodes. This mechanism is known as preferential attachment. In comparison to previous models, the Barabbas-Albert model seems to more accurately reflect phenomena observed in real-world networks.
Agent-based modelsedit
The second approach to model network formation is agent- or game theory-based modelling. In these models, a network with fixed number of nodes or agents is created. Every agent is given utility function, a representation of its linking preferences, and directed to form links with other nodes based upon it. Usually, forming or maintaining a link will have a cost, but having connections to other nodes will have benefits. The method tests the hypothesis that, given some initial setting and parameter values, a certain network structure will emerge as an equilibrium of this game. Since the number of nodes usually fixed, they can very rarely explain the properties of huge real-world networks; however, they are very useful to examine the network formation in smaller groups.
Jackson and Wolinsky pioneered these types of models in a 1996 paper, which has since inspired several game-theoretic models.[1] These models were further developed by Jackson and Watts, who put this approach to a dynamic setting to see how the network structure evolve over time.[2]
Usually, games with known network structure are widely applicable; however, there are various settings when players interact without fully knowing who their neighbors are and what the network structure is. These games can be modeled using incomplete information network games.
Growing networks in agent-based settingedit
There are very few models that try to combine the two approaches. However, in 2007, Jackson and Rogers modeled a growing network in which new nodes chose their connections partly based on random choices and partly based on maximizing their utility function.[3] With this general framework, modelers can reproduce almost every stylized trait of real-life networks.
Referencesedit
^Jackson and Wolinsky (1996). "A Strategic Model of Social and Economic Networks" (PDF). Journal of Economic Theory. 71: 44–74. doi:10.1006/jeth.1996.0108. hdl:10419/221454.
^Jackson and Watts (2002). (PDF). Journal of Economic Theory. 106 (2): 265–295. doi:10.1006/jeth.2001.2903. Archived from the original (PDF) on 2012-07-11.
^Jackson and Rogers (2007). "Meeting Strangers and Friends of Friends: How Random are Social Networks" (PDF). American Economic Review. 97 (3): 890–915. doi:10.1257/aer.97.3.890.
Further readingedit
Barabási and Albert (2002). (PDF). Reviews of Modern Physics. 74 (1): 47–97. arXiv:cond-mat/0106096. Bibcode:2002RvMP...74...47A. CiteSeerX10.1.1.242.4753. doi:10.1103/revmodphys.74.47. Archived from the original (PDF) on 2015-08-24.
April 15, 2024
network, formation, aspect, network, science, that, seeks, model, network, evolves, identifying, which, factors, affect, structure, these, mechanisms, operate, hypotheses, tested, using, either, dynamic, model, with, increasing, network, size, making, agent, b. Network formation is an aspect of network science that seeks to model how a network evolves by identifying which factors affect its structure and how these mechanisms operate Network formation hypotheses are tested by using either a dynamic model with an increasing network size or by making an agent based model to determine which network structure is the equilibrium in a fixed size network Contents 1 Dynamic models 2 Agent based models 3 Growing networks in agent based setting 4 References 5 Further readingDynamic models editA dynamic model often used by physicists and biologists begins as a small network or even a single node The modeler then uses a usually randomized rule on how newly arrived nodes form links in order to increase the size of the network The aim is to determine what the properties the network will be when it grows in size In this way researchers try to reproduce properties common in most real networks such as the small world network property or the scale free network property These properties are common in almost every real network including the World Wide Web the metabolic network or the network of international air routes The oldest model of this type is the Erdos Renyi model in which new nodes randomly choose other nodes to connect to A second well known model is the Watts and Strogatz model which starts from a standard two dimensional lattice and evolves by replacing links randomly These models display some realistic network properties but fail to account for others One of the most influential models of network formation is the Barabasi Albert model Here the network also starts from a small system and incoming nodes choose their links randomly but the randomization is not uniform Instead nodes which already possess a greater number of links will have a higher likelihood of becoming connected to incoming nodes This mechanism is known as preferential attachment In comparison to previous models the Barabbas Albert model seems to more accurately reflect phenomena observed in real world networks Agent based models editThe second approach to model network formation is agent or game theory based modelling In these models a network with fixed number of nodes or agents is created Every agent is given utility function a representation of its linking preferences and directed to form links with other nodes based upon it Usually forming or maintaining a link will have a cost but having connections to other nodes will have benefits The method tests the hypothesis that given some initial setting and parameter values a certain network structure will emerge as an equilibrium of this game Since the number of nodes usually fixed they can very rarely explain the properties of huge real world networks however they are very useful to examine the network formation in smaller groups Jackson and Wolinsky pioneered these types of models in a 1996 paper which has since inspired several game theoretic models 1 These models were further developed by Jackson and Watts who put this approach to a dynamic setting to see how the network structure evolve over time 2 Usually games with known network structure are widely applicable however there are various settings when players interact without fully knowing who their neighbors are and what the network structure is These games can be modeled using incomplete information network games Growing networks in agent based setting editThere are very few models that try to combine the two approaches However in 2007 Jackson and Rogers modeled a growing network in which new nodes chose their connections partly based on random choices and partly based on maximizing their utility function 3 With this general framework modelers can reproduce almost every stylized trait of real life networks References edit Jackson and Wolinsky 1996 A Strategic Model of Social and Economic Networks PDF Journal of Economic Theory 71 44 74 doi 10 1006 jeth 1996 0108 hdl 10419 221454 Jackson and Watts 2002 The Evolution of Social and Economic Networks PDF Journal of Economic Theory 106 2 265 295 doi 10 1006 jeth 2001 2903 Archived from the original PDF on 2012 07 11 Jackson and Rogers 2007 Meeting Strangers and Friends of Friends How Random are Social Networks PDF American Economic Review 97 3 890 915 doi 10 1257 aer 97 3 890 Further reading editBarabasi and Albert 2002 Statistical mechanics of complex networks PDF Reviews of Modern Physics 74 1 47 97 arXiv cond mat 0106096 Bibcode 2002RvMP 74 47A CiteSeerX 10 1 1 242 4753 doi 10 1103 revmodphys 74 47 Archived from the original PDF on 2015 08 24 Retrieved from https en wikipedia org w index php title Network formation amp oldid 1169881962, wikipedia, wiki, book, books, library,
