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.
@ Applications, network science:
Barabási 16,
Menczer et al 20 [II/III].
@ 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
(and author page);
Mocnik sRep(18)
[polynomial volume law and properties of Euclidean space].
@ 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];
Miller SPIE(18)-a1812,
Aslmarand et al a1902
[entangled, and information geometry];
DiAdamo et al a2003 [QuNetSim software framework];
Miguel-Ramiro et al a2005 [genuine quantum networks].
@ 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];
Cinardi et al a1902 [Network Geometry with Flavor].
@ 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
> s.a. complexity; Machine Learning.
* Idea: Computing systems
that learn to perform tasks (machine learning) by considering examples and
recognizing patterns and relationships in sets of data, generally without
being programmed with task-specific rules.
* Applications:
Classification of galaxies and other astronomical objects
(> see astronomy); > s.a.
gravitational-wave
interferometers; quantum mechanics.
@ General references: Amit 89;
Beale & Jackson 90;
Biehl & Schwarze JPA(93);
Dotsenko 95;
Altaisky qp/01 [quantum];
Deng et al a1701 [entanglement].
@ And physics:
Sellier a1902
[and the problem of finding the ground state of a quantum system];
Schuld et al Phy(19) [and open quantum systems];
D'Agnolo & Wulzer PRD(19),
Carleo et al RMP(19)-a1903,
Iten et al PRL(20)-a1807 [physics insight];
Kohli a2001
[Bianchi type A models, as continuous-time recurrent neural networks];
Krippendorf & Syvaeri a2003 [detecting symmetries];
Halverson et al a2008 [and effective field theory];
Katsnelson & Vanchurin a2012 [emergent quantum behavior];
Ban et al a2105 [quantum].
> Online resources: see Wikipedia
page.
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 AMP(18)-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;
correlations; 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 28 may 2021