In General > s.a. cellular automaton; complexity; graph.
* Idea: Networks are finite non-empty set of objects called vertices, and a finite set of edges associated each with an unordered pair of vertices (its endpoints); A generalization of the concept of graph (they can have multiple edges).
* Embedded in a manifold: A system of segments or edges which intersect only at their endpoints, called vertices; For example, the edges of a tessellation, which are also an embedded graph.
* Applications: Cells, networks of chemicals linked by chemical reactions, the Internet or computer networks.
@ General references: Buchanan 01, 03 [I]; Barabási 03; Watts 04; Newman et al 06; Newman PT(08)nov; Barthélemy PRP(11) [spatial networks]; Newman 10; West & Grigolini 11 [r PT(11)nov]; Bianconi EPL(15)-a1509 [physics challenges]; Barabási 16.
@ Complex networks: Albert & Barabási RMP(02)cm/01 [statistical mechanics]; Evans CP(04) [rev]; Boccaletti et al PRP(06) [dynamics]; Bogacz et al PhyA(06) [homogeneous, Monte Carlo]; Costa & Silva JSP(06) [hierarchical model]; West et al PRP(08) [new concepts, information exchange]; Radicchi et al PRL(08) [renormalization]; Horak et al JSM(09)-a0811-in [persistent homology]; Dorogovtsev 10; Macedo et al PLA(14) [optimal degree distribution, from Kaniadakis statistics].
@ Quantum networks: Finkelstein et al qp/96 [of quantum points, and standard model]; Törmä PRL(98)qp [transitions]; Somma et al PRA(02) [simulating physical phenomena]; Altman et al IJTP(04)qb.NC/03 = IJTP(04) [superpositional]; Chiribella et al PRA(09)-a0904 [theoretical framework]; Novotný et al JPA(09) [random unitary dynamics]; Allati et al PS(11) [communication via entangled coherent states]; Bisio et al APS-a1601 [general framework]; Perseguers et al RPP(13)-a1210 [entanglement distribution]; Novotný et al PRA(15)-a1601 [random].
@ Quantum networks, locality and localization: Törmä et al PRA(01)qp; Cardy CMP(05); Cavalcanti et al nComm(11)-a1010.

And Dynamical Systems > s.a. graphs and physics; quantum information.
* Random network: If we start with a set of n vertices and add links between them at random, there are certain thresholds at which the resulting graph/network changes qualitatively [Erdős & Renyi]; One obtains first a disjoint union of trees of order 2, then of order 3 when m ~ n1/2 and order 4 when m ~ n2/3, trees of higher orders, cycles when m ~ n/2; Until this point, there are many small components of order ~ ln n, then at m > n/2 there is a phase transition and a giant component of order n appears; The graph becomes connected when m ~ (n ln n)/2.
@ Evolving: Krapivsky & Derrida PhyA(04) [growing, properties]; Minnhagen et al PhyA(04) [merging and creation]; Grönlund et al PS(05) [correlations and preferential growth]; Shi et al mp/05; Shi et al PhyA(07) [clustering coefficients]; Gu & Sun PLA(08) [with node addition and deletion]; Hou et al in(09)-a0808 [degree-distribution stability of growing networks], a0901 [stable degree distribution]; Britton & Lindholm JSP(10); Wang et al PLA(11) [discrete degree distribution]; Aoki & Aoyagi PRL(12) [evolution of the nodes and links, scale-free].
@ Transport, flows on networks: Jordan et al JMP(04) [fluctuations]; Stinchcombe PhyA(05) [regular and disordered networks]; Estrada et al PRP(12) [communicability]; Toyota et al a1412 [effect of network topology].
@ Critical phenomena: Goltsev et al PRE(03)cm/02 [phenomenological theory]; Giuraniuc PRL(05) + pn(05)aug [interactions vs network structure]; Dorogovtsev et al RMP(08)-a0705; > s.a. renormalization, {scale-free below}.
@ Random network: Dorogovtsev & Samukhin PRE(03)cm/02 [fluctuations], et al NPB(03)cm/02 [statistical mechanics], cm/02, cm/02 [construction], cm/02-conf [overview], NPB(03)cm/02 [path lengths]; Resendis-Antonio & Collado-Vides PhyA(04) [growth as diffusion]; Luque & Ballesteros PhyA(04) [random walk networks]; Franceschetti & Meester 07 [r JSP(09)]; Nowotny & Requardt JCA(07)cm/06 [emergent properties]; Ben-Naim & Krapivsky JPA(07) [addition-deletion]; Novotný et al a0904 [random unitary quantum dynamics]; Shang RPMP(11) [asymptotic link probabilities]; Coon et al PRE(12)-a1112 [impact of boundaries]; > s.a. non-extensive statistical mechanics [entropy]; random tilings.
@ Phase transitions: Derényi et al PhyA(04) [topological phase transition]; Li et al PhyA(04) [transition to chaos]; Kramer et al PRP(05) [and 2D quantum phase transitions]; Wu et al PhyA(13) [emergence of clustering].
@ Reaction networks: Baez a1306 [techniques from quantum field theory, master equation and coherent states].
@ Related topics: Balachandran & Ercolessi IJMPA(92) [single-particle statistics]; Golubitsky & Stewart BAMS(06) [grupoid formalism]; La Mura & Swiatczak qp/07 [Markovian Entanglement Networks]; Passerini & Severini in(11)-a0812 [entropy]; Timme & Casadiego JPA(14) [revealing interaction topology from collective dynamics]; > s.a. entanglement; spin models.

Neural Network
* Applications: Classification of galaxies and other astronomical objects (> see astronomy).
@ References: Amit 89; Beale & Jackson 90; Biehl & Schwarze JPA(93); Dotsenko 95; Altaisky qp/01 [quantum]; Deng et al a1701 [entanglement].

Scale-Free Networks
* Idea: Networks characterized by a power-law distribution in the number of connections (degree) each node has; The network continually grows by the addition of new nodes; A new node connects to two existing nodes in the network at time t + 1; This new node is much more likely to connect to highly connected nodes (preferential attachment); The function P(k) does not have a peak and decays as a power law at large k, so most nodes have one or two links, but a few nodes (hubs) have a large number of links, which guarantees that the system is fully connected.
$ Def: A network in which the probability that any given vertex is of degree k is Prob[d(v) = k] = kγ, where often γ ∈ [1,3].
@ References: Dorogovtsev et al PRE(02) [properties]; Barabási & Bonabeau SA(03)may; Dangalchev PhyA(04) [stochastic models]; Chen & Shi PhyA(04) [modeling]; Shiner & Davison CSF(04) [connectivity]; Rodgers et al JPA(05) [eigenvalue spectrum of adjacency matrix]; Del Genio et al PRL(11) + Sinha Phy(11) [they must be sparse].

Other Concepts and Types > s.a. cell complex; Elastic Networks; graph types; Tensor Networks; tilings.
* Network connectivity: Can be characterized by the probability P(k) that a node has k links.
* Random: (Erdős-Renyi) Each pair of nodes is connected with probability p; The function P(k) is highly peaked at some k, and decays exponentially at large k, so most nodes have approximately the same number of links; (Uniform random graph) Pick one uniformly at random; These types of random graphs do not reproduce well the observed properties of real-world networks, which are sparse, have small diameters (small-world phenomenon), become denser with time, have an inverse-power-law distribution of vertex degrees with hubs and clusters/cliques; The reason is that random graphs are too independent, and models with correlations should be used.
* May-Wigner stability theorem: Increasing the complexity of a network inevitably leads to its destabilization, such that a small perturbation will be able to disrupt the entire system.
@ Random cellular networks: Vincze et al JGP(04) [Aboav-Weaire law].
@ Small-world networks: Watts 99; Araújo et al PLA(03); Sinha PhyA(05) [complexity vs stability]; Cont & Tanimura AAP(08).
@ Causal networks: (a.k.a. Bayesian networks) Ito & Sagawa PRL(13) [non-equilibrium thermodynamics of complex information flows and the second law]; > s.a. generalized bell inequalities.
@ Other types: Holme & Saramäki PRP(12) [temporal networks]; Bartolucci & Annibale JPA(14) [associative networks, with diluted patterns]; Boguñá et al NJP(14) [cosmological networks]; Baez & Pollard a1704 [open reaction networks, as morphisms in a category].
@ Related topics: Kim PRL(04)cm [coarse-graining]; Gelenbe PRS(08) [intro to stochastic networks]; Fortunato PRP(10) [clustering]; Motoike & Takigawa-Imamura PRE(10) [branching structure growth, effect of signal propagation]; Thyagu & Mehta PhyA(11) [competitive cluster growth].
> Related topics: see Causal Model; discrete geometry [models of spacetime]; entanglement entropy; technology [internet].
> In different areas of physics: see electricity [resistor networks]; topological defects [cosmic-string networks, etc].

main pageabbreviationsjournalscommentsother sitesacknowledgements
send feedback and suggestions to bombelli at – modified 10 apr 2017