[0pt] Complex network approach to evolving manifolds and … · 2018-10-25 · Complex network...

Complex network approach to evolvingmanifolds and simplicial complexes

S. N. Dorogovtsev

Departamento de Fısica da Universidade de Aveiro & I3N,Ioffe Institute, St. Petersburg

G. Timar, A. V. Goltsev, SND, J. F. F. Mendes, Mapping the structure ofdirected networks: Beyond the “Bow-tie” diagram,

Phys. Rev. Lett. 118, 078301 (2017).

D. C. da Silva, G. Bianconi, R.A. da Costa, SND, J.F.F. Mendes,Complex network view of evolving manifolds,

Phys. Rev. E 97, 032316 (2018).

N. A. M. Araujo, R. A. da Costa, SND, J. F. F. Mendes,Finding the optimal nets for self-folding Kirigami,

Phys. Rev. Lett. 120, 188001 (2018).

The bow-tie organization of the Web:

A. Broder, R. Kumar, F. Maghoul, P. Raghavan, S. Rajagopalan,

R. Stata, A. Tomkins, J. Wiener (2000)

2 / 36

SND, J. F. F. Mendes, A. N. Samukhin (2001)

3 / 36

4 / 36

5 / 36

(a) directed ER (N = 10000, 〈qtot〉 = 5),(b) the Gnutella P2P (N = 62586, 〈qtot〉 = 4.726),

(c) C. elegans (N = 495, 〈qtot〉 = 32.073).6 / 36

Mean number of tendril layers LT :

(Dashed lines correspond to pc .)7 / 36

Relative size of tendrils in layers:

(a) directed ER (N = 106, 〈qtot〉 = 5),(b) the WWW (N = 875713, 〈qtot〉 = 11.659).

8 / 36

Manifolds & simplicial complexes:Manifolds ≡ topological spaces locally homeomorphic toEuclidean spaces(e.g., surfaces)

d-simplex ≡ d + 1-clique[d + 1 vertex and (d + 1)d/2 edges]

d-simplicial complex ≡ constructed only of d-simplexes

Simplicial complexes are the discrete versions ofmanifolds,e.g., triangulation networks (sets of triangular faces) arethe discrete versions of surfaces.

Closed manifolds vs. manifolds with a boundary

9 / 36

Triangulations are everywhere:

Triangulations are in the heart of modern civilization asthe main method of treatment of surfaces in topography,engineering, hydrodynamics and aerodynamics,visualization techniques, and everywhere.

Particular planar graphs, strong constraint (!)

10 / 36

Manifolds with boundaries:

Wu, Menichetti, Rahmede, and Bianconi (2015)

11 / 36

Modelling closed manifolds using evolvingsimplicial complexes:

• local structure — ???(degree distribution, degree–degreecorrelations)

• space dimension — ???(Hausdorff and spectral dimensions)

• topology — ???

12 / 36

Topology:

Topology is about the properties of space that arepreserved under continuous deformations.

13 / 36

Triangular mesh operations—1:

Pachner moves:

1−move

2−move

0−move

P1

P2

14 / 36

Triangular mesh operations—2:

S

15 / 36

Triangulations of closed surfaces:

Euler’s formula for general polyhedra

χ = F + N − E ,

χ = 2(1− h),

If there are no boundaries, then

3F = 2E ,

χ = N − 1

3E = N − 1

2F .

16 / 36

Local curvature:

Ri = 1− 1

6qi ,

assuming that all edges are equal.

17 / 36

Organization of models:

At each time step,(i) an element or neighboring elements of the simplicialcomplex under consideration are chosen with somepreference or, in the simplest particular case, withoutpreference, i.e., uniformly at random. For triangulations,such elements are vertices, edges, and triangles.Then,(ii) a specific transformation from the set of operationsthat keep the simplicial complex intact is applied to thiselement.

18 / 36

Zoo:

19 / 36

Be careful:

The elements of triangulations are faces and not edgesand vertices.

20 / 36

Hausdorff dimension:

100101102103104105106107108109

100 101 102 103 104

V

r

G1G2

GGaGbGc

0 1 2 3 4 5 6 7 8 9

10

100 101 102 103 104

d ln

(V) /

d ln

(r)

r

G1G2

GGaGbGc

21 / 36

Spectral dimension:

ϕ0(t) ∼ t−dS/2, ρ(λ) ∼ λdS/2−1

dS ≤ dH

100

101

102

103

104

10-4 10-3 10-2 10-1 100

N<(

λ)

λ

G1G2

GGaGbGc

GW∼x

100

101

102

103

104

105

10-5 10-4 10-3 10-2 10-1 100

N<(

λ)

λ

E1E2E3∼x

22 / 36

Evolving topology—generation of wormholes:at each step, perform G2 (creates a new face);in addition, at each θ-th step merge two faces andeliminate them

10-810-710-610-510-410-310-210-1100

100 101 102 103 104

P(k)

k

102050

100200500

10002000∞

23 / 36

Results:

24 / 36

E1 vs. equilibrium random trees

Model E1:random addition and addition vertices of degree 3 withequal rates.

dH ∼ 2(?), dS = 1.4(2).

Equilibrium random trees:

dH = 2, dS = 4/3.

25 / 36

Self-assembling systems:

26 / 36

Optimal nets for self-folding systems:Self-assembling

3D shells are synthesized from the self-folding of 2Dtemplates of interconnected panels, called nets.

The yield is maximized following sequentially two designrules:(i) maximum number of vertices with a single-edge cutand, e.g.,(ii) minimum radius of gyration of the net.

A vertex with a single-edge cut is one whose thenumber of adjacent faces is the same in the net and inthe shell.

Step (i) is NP hard27 / 36

Shells and nets:

28 / 36

Difficult:

Previously:a random search, scanning only a small subset of possiblenets and thus missing the global optimum.

(a dodecahedron, E=30 edges, has more than 5 millionpossible cuts).

Our deterministic algorithm:finds exactly the global minimum for solids with E up to150 (desktop).Its stochastic version:approaches the global minimum for higher E .

29 / 36

Idea:

Definition:A shell graph consists of the vertices and edges of theshell.

Design rule (i) corresponds to finding the set of

maximum leaf spanning trees of the shell graph.

30 / 36

Fraction of spanning trees, NST, that are maximum leafspanning trees, NMLST, as a function of the number ofshell edges, E

31 / 36

Number of leaves, L, in a MLST as a function of thenumber of shell edges, E

32 / 36

Soccer ball-1:

33 / 36

Soccer ball-2:

Truncated icosahedron (soccer ball): (a) spectrum of theradii of gyration for all the 4114 non-isomorphic MLSTs,ordered by increasing radius of gyration; the MLST withthe (b) optimal (rank 1); (c) intermediate (rank 2057:RG = RGmin ≈ 1.23); and (d) largest (rank 4114:RG = RGmin ≈ 1.40) radius of gyration.

34 / 36

Conclusion:

∼∼∼

35 / 36

36 / 36