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].

@ __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