Complex network
Part of a series on | ||||
Network science | ||||
---|---|---|---|---|
Network types | ||||
|
||||
Graphs | ||||
|
||||
Models | ||||
|
||||
| ||||
In the context of
Definition
Most
Two well-known and much studied classes of complex networks are
The field continues to develop at a brisk pace, and has brought together researchers from many areas including mathematics, physics, electric power systems,[10] biology, climate, computer science, sociology, epidemiology, and others.[11] Ideas and tools from network science and engineering have been applied to the analysis of metabolic and genetic regulatory networks; the study of ecosystem stability and robustness;[12] clinical science;[13] the modeling and design of scalable communication networks such as the generation and visualization of complex wireless networks;[14] and a broad range of other practical issues. Network science is the topic of many conferences in a variety of different fields, and has been the subject of numerous books both for the lay person and for the expert.
Scale-free networks
A network is called scale-free[7][15] if its degree distribution, i.e., the probability that a node selected uniformly at random has a certain number of links (degree), follows a mathematical function called a power law. The power law implies that the degree distribution of these networks has no characteristic scale. In contrast, networks with a single well-defined scale are somewhat similar to a lattice in that every node has (roughly) the same degree. Examples of networks with a single scale include the Erdős–Rényi (ER) random graph, random regular graphs, regular lattices, and hypercubes. Some models of growing networks that produce scale-invariant degree distributions are the Barabási–Albert model and the fitness model. In a network with a scale-free degree distribution, some vertices have a degree that is orders of magnitude larger than the average - these vertices are often called "hubs", although this language is misleading as, by definition, there is no inherent threshold above which a node can be viewed as a hub. If there were such a threshold, the network would not be scale-free.
Interest in scale-free networks began in the late 1990s with the reporting of discoveries of power-law degree distributions in real world networks such as the
Some networks with a power-law degree distribution (and specific other types of structure) can be highly resistant to the random deletion of vertices—i.e., the vast majority of vertices remain connected together in a giant component. Such networks can also be quite sensitive to targeted attacks aimed at fracturing the network quickly. When the graph is uniformly random except for the degree distribution, these critical vertices are the ones with the highest degree, and have thus been implicated in the spread of disease (natural and artificial) in social and communication networks, and in the spread of fads (both of which are modeled by a percolation or branching process). While random graphs (ER) have an average distance of order log N[8] between nodes, where N is the number of nodes, scale free graph can have a distance of log log N.
Small-world networks
A network is called a small-world network
In the scientific literature on networks, there is some ambiguity associated with the term "small world". In addition to referring to the size of the diameter of the network, it can also refer to the co-occurrence of a small diameter and a high clustering coefficient. The clustering coefficient is a metric that represents the density of triangles in the network. For instance, sparse random graphs have a vanishingly small clustering coefficient while real world networks often have a coefficient significantly larger. Scientists point to this difference as suggesting that edges are correlated in real world networks. Approaches have been developed to generate network models that exhibit high correlations, while preserving the desired degree distribution and small-world properties. These approaches can be used to generate analytically solvable toy models for research into these systems.[16]
Spatial networks
Many real networks are embedded in space. Examples include, transportation and other infrastructure networks, brain networks.[3][4] Several models for spatial networks have been developed.[17]
See also
- Community structure
- Complex adaptive system
- Complex systems
- Dual-phase evolution
- Dynamic network analysis
- Interdependent networks
- Network theory
- Network science
- Percolation theory
- Random graph
- Random graph theory of gelation
- Scale-free networks
- Small world networks
- Spatial network
- Trophic coherence
Books
- B. S. Manoj, Abhishek Chakraborty, and Rahul Singh, Complex Networks: A Networking and Signal Processing Perspective, Pearson, New York, USA, February 2018. ISBN 978-0-13-478699-5
- S.N. Dorogovtsev and J.F.F. Mendes, Evolution of Networks: From biological networks to the Internet and WWW, Oxford University Press, 2003, ISBN 0-19-851590-1
- Duncan J. Watts, Six Degrees: The Science of a Connected Age, W. W. Norton & Company, 2003, ISBN 0-393-04142-5
- Duncan J. Watts, Small Worlds: The Dynamics of Networks between Order and Randomness, Princeton University Press, 2003, ISBN 0-691-11704-7
- Albert-László Barabási, Linked: How Everything is Connected to Everything Else, 2004, ISBN 0-452-28439-2
- Alain Barrat, Marc Barthelemy, Alessandro Vespignani, Dynamical processes on complex networks, Cambridge University Press, 2008, ISBN 978-0-521-87950-7
- Stefan Bornholdt (editor) and Heinz Georg Schuster (editor), Handbook of Graphs and Networks: From the Genome to the Internet, 2003, ISBN 3-527-40336-1
- Guido Caldarelli, Scale-Free Networks, Oxford University Press, 2007, ISBN 978-0-19-921151-7
- Guido Caldarelli, Michele Catanzaro, Networks: A Very Short Introduction Oxford University Press, 2012, ISBN 978-0-19-958807-7
- E. Estrada, "The Structure of Complex Networks: Theory and Applications", Oxford University Press, 2011, ISBN 978-0-199-59175-6
- Mark Newman, Networks: An Introduction, Oxford University Press, 2010, ISBN 978-0-19-920665-0
- Mark Newman, Albert-László Barabási, and Duncan J. Watts, The Structure and Dynamics of Networks, Princeton University Press, Princeton, 2006, ISBN 978-0-691-11357-9
- R. Pastor-Satorras and A. Vespignani, Evolution and Structure of the Internet: A statistical physics approach, Cambridge University Press, 2004, ISBN 0-521-82698-5
- T. Lewis, Network Science, Wiley 2009,
- Niloy Ganguly (editor), Andreas Deutsch (editor) and Animesh Mukherjee (editor), Dynamics On and Of Complex Networks Applications to Biology, Computer Science, and the Social Sciences, 2009, ISBN 978-0-8176-4750-6
- Vito Latora, Vincenzo Nicosia, Giovanni Russo, Complex Networks: Principles, Methods and Applications, Cambridge University Press, 2017, ISBN 978-1-107-10318-4
References
This article includes a list of general references, but it lacks sufficient corresponding inline citations. (August 2008) |
- S2CID 60545.
- ISBN 978-0-19-920665-0.
- ^ PMID 28230844.
- ^ a b Alex Fornito. "An Introduction to Network Neuroscience: How to build, model, and analyse connectomes - 0800-10:00 | OHBM". pathlms.com. Retrieved 2020-03-11.
- PMID 33500525.
- .
- ^ PMID 12701331.
- ^ S2CID 4429113.
- PMID 11005838.
- .
- S2CID 12823922. Archived from the originalon 2012-09-06.
- PMID 25468963.
- PMID 29931701.
- ^ Mouhamed Abdulla (2012-09-22). On the Fundamentals of Stochastic Spatial Modeling and Analysis of Wireless Networks and its Impact to Channel Losses. Ph.D. Dissertation, Dept. Of Electrical and Computer Engineering, Concordia Univ., Montréal, Québec, Canada, Sep. 2012. (phd). Concordia University. pp. (Ch.4 develops algorithms for complex network generation and visualization). Archived from the original on 2016-10-09. Retrieved 2013-10-11.
- S2CID 60545.
- ^ A Ramezanpour, V Karimipour, A Mashaghi, Generating correlated networks from uncorrelated ones. Physical Review E 67(4 Pt 2):046107 (2003) doi: 10.1103/PhysRevE.67.046107
- doi:10.1109/49.12889.
- D. J. Watts and S. H. Strogatz (1998). "Collective dynamics of 'small-world' networks". Nature. 393 (6684): 440–442. S2CID 4429113.
- PMID 11258382.
- R. Albert and A.-L. Barabási (2002). "Statistical mechanics of complex networks". Reviews of Modern Physics. 74 (1): 47–97. S2CID 60545.
- S. N. Dorogovtsev and J.F.F. Mendes (2002). "Evolution of Networks". Adv. Phys. 51 (4): 1079–1187. S2CID 429546.
- M. E. J. Newman, The structure and function of complex networks, SIAM Review 45, 167-256 (2003)
- S. N. Dorogovtsev, A. V. Goltsev, and J. F. F. Mendes, Critical phenomena in complex networks, Rev. Mod. Phys. 80, 1275, (2008)
- G. Caldarelli, R. Marchetti, L. Pietronero, The Fractals Properties of Internet, Europhysics Letters 52, 386 (2000). https://arxiv.org/abs/cond-mat/0009178. DOI: 10.1209/epl/i2000-00450-8
- A. E. Motter (2004). "Cascade control and defense in complex networks". Phys. Rev. Lett. 93 (9): 098701. S2CID 4856492.
- J. Lehnert, Controlling Synchronization Patterns in Complex Networks, springer 2016
- Dolev, Shlomi; Elovici, Yuval; Puzis, Rami (2010), "Routing betweenness centrality", J. ACM, 57 (4): 25:1–25:27, S2CID 15662473