Networks |

**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];
van der Hofstad 16.

@ __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* ~ *n*^{1/2} and
order 4 when *m* ~ *n*^{2/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 page
– abbreviations
– journals – comments
– other sites – acknowledgements

send feedback and suggestions to bombelli at olemiss.edu – modified 10 apr 2017