text: 5 4 No Breaking for Gen−Whitham Gen−Whitham equation 3 Hyperbolic 2 1 0 −4 −2 0 2 4 Ω 4.5 4 3.5 3 No Breaking for Gen− 2.5 Whitham equation 2 Gen−Whitham Hyperbolic 1.5 1 0.5 0 −4 −2 0 2 4 Ω Figure 13: Breaking time as a function of the vorticity within the framework of the generalised Whitham equation with a symmetric initial condition (a = 0.20, ϕ = 0) (top) and an asymmetric initial condition (a = 0.20, ϕ = 3π/2) (bottom). The solid line corresponds to the hyperbolic case. 25 t t B B ##LTFigure## ##LTFigure## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: No

text: Breaking

text: for

text: Gen−Whitham

text: Gen−Whitham

text: equation

text: Hyperbolic

text: −4

text: −2

text: Ω

text: No

text: Breaking

text: for

text: Gen−

text: Whitham

text: equation

text: Gen−Whitham

text: Hyperbolic

text: −4

text: −2

text: Ω

text: Figure

text: Breaking

text: time

text: as

text: a

text: function

text: of

text: the

text: vorticity

text: within

text: the

text: framework

text: of

text: the

text: generalised

text: Whitham

text: equation

text: with

text: a

text: symmetric

text: initial

text: condition

text: (a

text: ϕ

text: (top)

text: and

text: an

text: asymmetric

text: initial

text: condition

text: (a

text: ϕ

text: (bottom).

text: The

text: solid

text: line

text: corresponds

text: to

text: the

text: hyperbolic

text: case.

text: t

text: t

text: B

text: B

text: ##LTFigure##

text: ##LTFigure##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: [] Choi, W., 2003. Strongly nonlinear long gravity waves in uniformshear ﬂows. Phys. Rev. E 68, 026305. [] Favre, H., 1935. Etude th´eorique et exp´erimentale des ondes de transla- tion dans les canaux d´ecouverts. Dunod, Paris. [] Freeman, N. C., Johnson, R. S., 1970. Shallow water waves on shear ﬂows. J. Fluid Mech. 42 (2), 401–409. [] Holloway, P. E., Pelinovsky, E., Talipova, T., Barnes, B., 1997. A non- linear model of internal tide transformation on the australian north west shelf. J. Phys. Oceanogr. 27, 871–896. [] Hur, V., 2017. Shallow water wave models with constant vorticity. Eur. J. Mech./B Fluids, doi: 10.1016. [] Johnson, R. S., 2012. A problem in the classical theory of water waves: weakly nonlinear waves in the presence of vorticity. J. Nonl. Math. Phys. 19, 1240012. [] Kharif, C., Abid, M., Touboul, J., 2017. Rogue waves in shallow water in the presence of a vertically sheared current. J. Ocean Eng. and Mar. Energy 3(4), 301–308. [] Lannes, D., Bonneton, P., 2009. Derivation of asymptotic two- dimensional time-dependent equations for surface water wave propa- gation. Phys. Fluids 21, 016601. [] Richard, G. L., Gavrilyuk, S., 2015. Modelling turbulence generation in solitary waves on shear shallow water ﬂows. J. Fluid Mech. 773, 49–74. [] Sulem, C., Sulem, P., Frisch, H., 1983. Tracing complex singularities with spectral methods. Journal of computational physics 50, 138–161. [] Teles da Silva, A. F., Peregrine, D. H., 1990. Nonsteady computations of undular and breaking bores. Proc. Coastal Eng. 77, 1019–1032. [] Touboul, J., Kharif, C., 2016. Eﬀect of vorticity on the genera- tion of rogue waves due to dispersive focusing. Nat. Hazards, DOI 10.1007/s11069–016–2419–5. [] Whitham, G., 1974. Linear and nonlinear waves. John Wiley & Sons. 29

label: paragraph

text: Choi,

text: W.,

text: Strongly

text: nonlinear

text: long

text: gravity

text: waves

text: in

text: uniformshear

text: ﬂows.

text: Phys.

text: Rev.

text: E

text: Favre,

text: H.,

text: Etude

text: th´eorique

text: et

text: exp´erimentale

text: des

text: ondes

text: de

text: transla-

text: tion

text: dans

text: les

text: canaux

text: d´ecouverts.

text: Dunod,

text: Paris.

text: Freeman,

text: N.

text: C.,

text: Johnson,

text: R.

text: S.,

text: Shallow

text: water

text: waves

text: on

text: shear

text: ﬂows.

text: J.

text: Fluid

text: Mech.

text: Holloway,

text: P.

text: E.,

text: Pelinovsky,

text: E.,

text: Talipova,

text: T.,

text: Barnes,

text: B.,

text: A

text: non-

text: linear

text: model

text: of

text: internal

text: tide

text: transformation

text: on

text: the

text: australian

text: north

text: west

text: shelf.

text: J.

text: Phys.

text: Oceanogr.

text: Hur,

text: V.,

text: Shallow

text: water

text: wave

text: models

text: with

text: constant

text: vorticity.

text: Eur.

text: J.

text: Mech./B

text: Fluids,

text: doi:

text: Johnson,

text: R.

text: S.,

text: A

text: problem

text: in

text: the

text: classical

text: theory

text: of

text: water

text: waves:

text: weakly

text: nonlinear

text: waves

text: in

text: the

text: presence

text: of

text: vorticity.

text: J.

text: Nonl.

text: Math.

text: Phys.

text: Kharif,

text: C.,

text: Abid,

text: M.,

text: Touboul,

text: J.,

text: Rogue

text: waves

text: in

text: shallow

text: water

text: in

text: the

text: presence

text: of

text: a

text: vertically

text: sheared

text: current.

text: J.

text: Ocean

text: Eng.

text: and

text: Mar.

text: Energy

text: Lannes,

text: D.,

text: Bonneton,

text: P.,

text: Derivation

text: of

text: asymptotic

text: two-

text: dimensional

text: time-dependent

text: equations

text: for

text: surface

text: water

text: wave

text: propa-

text: gation.

text: Phys.

text: Fluids

text: Richard,

text: G.

text: L.,

text: Gavrilyuk,

text: S.,

text: Modelling

text: turbulence

text: generation

text: in

text: solitary

text: waves

text: on

text: shear

text: shallow

text: water

text: ﬂows.

text: J.

text: Fluid

text: Mech.

text: Sulem,

text: C.,

text: Sulem,

text: P.,

text: Frisch,

text: H.,

text: Tracing

text: complex

text: singularities

text: with

text: spectral

text: methods.

text: Journal

text: of

text: computational

text: physics

text: Teles

text: da

text: Silva,

text: A.

text: F.,

text: Peregrine,

text: D.

text: H.,

text: Nonsteady

text: computations

text: of

text: undular

text: and

text: breaking

text: bores.

text: Proc.

text: Coastal

text: Eng.

text: Touboul,

text: J.,

text: Kharif,

text: C.,

text: Eﬀect

text: of

text: vorticity

text: on

text: the

text: genera-

text: tion

text: of

text: rogue

text: waves

text: due

text: to

text: dispersive

text: focusing.

text: Nat.

text: Hazards,

text: DOI

text: Whitham,

text: G.,

text: Linear

text: and

text: nonlinear

text: waves.

text: John

text: Wiley

text: Sons.


text: Phase transitions in social networks inspired by the Schelling model V. Avetisov1,2, A. Gorsky3,4, S. Maslov5, S. Nechaev6,7, and O. Valba1,2 1N.N. Semenov Institute of Chemical Physics of the Russian Academy of Sciences, 119991, Moscow, Russia, 2Department of Applied Mathematics, National Research University Higher School of Economics, 101000, Moscow, Russia, 3Institute of Information Transmission Problems of the Russian Academy of Sciences, Moscow, Russia, 4Moscow Institute of Physics and Technology, Dolgoprudny 141700, Russia 5 Department of Bioengineering and Carl R. Woese Institute for Genomic Biology, University Urbana-Champaign, Urbana, Illinois, 61801 USA 6Interdisciplinary Scientiﬁc Center Poncelet (CNRS UMI 2615), Moscow, Russia 7P.N. Lebedev Physical Institute of the Russian Academy of Sciences, 119991, Moscow, Russia A generalized Schelling social segregation model is applied for the description of evolving social networks in which the number of connections of each agent (individual) remains approximately constant in time, though may be diﬀerent for diﬀerent agents. We propose two models. The ﬁrst two- parametric model describes a ”polychromatic” society, where each ”color” designates some typical ”social category”, to which the agent belongs. One control parameter, µ, reﬂects the condition that three individuals within the same social category have some preference to form a triad. The second parameter, ν, controls the preference for two individuals from diﬀerent social categories to be connected. The polychromatic model enjoys several regimes separated by phase transitions in the (µ, ν) parameter space. The second ”colorless” model describes a society in which advantage or disadvantage of forming small fully connected communities (short cycles or cliques in a graph) is controlled by a single ”energy” parameter, γ. We analyze the topological structure of a social network in this model and demonstrate that for some critical threshold, γ+ > 0, the entire network − splits into the set of weakly connected clusters, while at another threshold, γ < 0, the network acquires a bipartite graph structure. Our results shed light on social segregation and self-organized formation of cliques in social networks. I. INTRODUCTION The famous Schelling model [1] of spontaneous segregation in a society is one of the most popular models describing collective (social) behavior in a community of individuals. It can be formulated as follows: consider a lattice partially ﬁlled with social agents (individuals) of two ”colors” (green and red). Colors represent two social categories such that for each of these colors, agents prefer to live in the surrounding of the neighbors with the same color. In the original work Shelling considered the square lattice, where the number of nearest neighbors is 8 (direct and diagonal nearest neighbors). An agent of some color (say, of red), who has fraction of nearest neighbors of the same color below a threshold f, is unhappy with its surroundings and can be moved to a randomly selected nearest empty lattice cell as long as such cell could be found. In another version of the model, unhappy agents could be moved to any unoccupied cell independent of the distance. Repeating many times these steps one arrives at a dynamic equilibrium. Note that the number of agents of each color is conserved in course of such evolution. If the number of steps tends to inﬁnity, ∗ ∗ one can speak about the phase transition, which occurs at a critical value of f , such that for f < f agents tend to ∗ form unicolored clusters with mobile boundaries. The critical threshold f = 1/2 is exactly known for the Schelling ∗ model on a 1D lattice. For a two-dimensional square lattice the value of f depends on whether the occupied lattice ∗ sites are above or below the percolation transition. As discussed in [3] the result f = 1/2 holds only below the percolation transition. The Schelling model demonstrates how even relatively weak and short-ranged homophilic preferences (preference to live with people of the same social category) combined with mixing (ability to move to an empty place) could force global (macroscopic) changes in the system [2–4]. Moreover, these global changes appear abruptly (i.e. as a phase transition), as soon as the tolerance to unhappiness, quantitatively expressed in f, falls below the critical threshold, ∗ f . The Schelling model in its canonical form was aimed to uncover statistical mechanisms of racial/religious/social segregation associated with resettlement of humans in communities (e.g. in cities). Thus, this model naturally depends on spatial proximity between agents and it needs to be updated to be catch the challenges of the modern era in which distant social connections mediated by social networks such as Facebook, Twitter, etc, may be more important than local physical neighborhood (see Ref. [2] for the ﬁrst adaptation of the Schelling model to social networks). In this study we represent the society as a collection of agents from two social categories (red and green ”colors”) connected by some social relations represented as edges in some network. Our society is dynamic, which means that

text: Phase

label: title

text: transitions

text: in

text: social

text: networks

text: inspired

text: by

text: the

text: Schelling

text: model

text: V.

label: author

text: A.

text: S.

text: S.

text: and

text: O.

text: Semenov

text: Institute

text: of

text: Chemical

text: Physics

text: of

text: the

text: Russian

text: Academy

text: of

text: Sciences,

text: Moscow,

text: Russia,

text: of

text: Applied

text: Mathematics,

text: National

text: Research

text: University

text: Higher

text: School

text: of

text: Economics,

text: Moscow,

text: Russia,

text: of

text: Information

text: Transmission

text: Problems

text: of

text: the

text: Russian

text: Academy

text: of

text: Sciences,

text: Moscow,

text: Russia,

text: Institute

text: of

text: Physics

text: and

text: Technology,

text: Dolgoprudny

text: Russia

text: Department

text: of

text: Bioengineering

text: and

text: Carl

text: R.

text: Woese

text: Institute

text: for

text: Genomic

text: Biology,

text: University

text: Urbana-Champaign,

text: Urbana,

text: Illinois,

text: USA

text: Scientiﬁc

text: Center

text: Poncelet

text: (CNRS

text: UMI

text: Moscow,

text: Russia

text: Lebedev

text: Physical

text: Institute

text: of

text: the

text: Russian

text: Academy

text: of

text: Sciences,

text: Moscow,

text: Russia

text: A

text: generalized

text: Schelling

text: social

text: segregation

text: model

text: is

text: applied

text: for

text: the

text: description

text: of

text: evolving

text: social

text: networks

text: in

text: which

text: the

text: number

text: of

text: connections

text: of

text: each

text: agent

text: (individual)

text: remains

text: approximately

text: constant

text: in

text: time,

text: though

text: may

text: be

text: diﬀerent

text: for

text: diﬀerent

text: agents.

text: We

text: propose

text: two

text: models.

text: The

text: ﬁrst

text: two-

text: parametric

text: model

text: describes

text: a

text: ”polychromatic”

text: society,

text: where

text: each

text: ”color”

text: designates

text: some

text: typical

text: ”social

text: category”,

text: to

text: which

text: the

text: agent

text: belongs.

text: One

text: control

text: parameter,

text: µ,

text: reﬂects

text: the

text: condition

text: that

text: three

text: individuals

text: within

text: the

text: same

text: social

text: category

text: have

text: some

text: preference

text: to

text: form

text: a

text: triad.

text: The

text: second

text: parameter,

text: ν,

text: controls

text: the

text: preference

text: for

text: two

text: individuals

text: from

text: diﬀerent

text: social

text: categories

text: to

text: be

text: connected.

text: The

text: polychromatic

text: model

text: enjoys

text: several

text: regimes

text: separated

text: by

text: phase

text: transitions

text: in

text: the

text: (µ,

text: ν)

text: parameter

text: space.

text: The

text: second

text: ”colorless”

text: model

text: describes

text: a

text: society

text: in

text: which

text: advantage

text: or

text: disadvantage

text: of

text: forming

text: small

text: fully

text: connected

text: communities

text: (short

text: cycles

text: or

text: cliques

text: in

text: a

text: graph)

text: is

text: controlled

text: by

text: a

text: single

text: ”energy”

text: parameter,

text: γ.

text: We

text: analyze

text: the

text: topological

text: structure

text: of

text: a

text: social

text: network

text: in

text: this

text: model

text: and

text: demonstrate

text: that

text: for

text: some

text: critical

text: threshold,

text: γ+

text: the

text: entire

text: network

text: splits

text: into

text: the

text: set

text: of

text: weakly

text: connected

text: clusters,

text: while

text: at

text: another

text: threshold,

text: γ

text: the

text: network

text: acquires

text: a

text: bipartite

text: graph

text: structure.

text: Our

text: results

text: shed

text: light

text: on

text: social

text: segregation

text: and

text: self-organized

text: formation

text: of

text: cliques

text: in

text: social

text: networks.

text: I.

text: INTRODUCTION

text: The

text: famous

text: Schelling

text: model

text: of

text: spontaneous

text: segregation

text: in

text: a

text: society

text: is

text: one

text: of

text: the

text: most

text: popular

text: models

text: describing

text: collective

text: (social)

text: behavior

text: in

text: a

text: community

text: of

text: individuals.

text: It

text: can

text: be

text: formulated

text: as

text: follows:

text: consider

text: a

text: lattice

text: partially

text: ﬁlled

text: with

text: social

text: agents

text: (individuals)

text: of

text: two

text: ”colors”

text: (green

text: and

text: red).

text: Colors

text: represent

text: two

text: social

text: categories

text: such

text: that

text: for

text: each

text: of

text: these

text: colors,

text: agents

text: prefer

text: to

text: live

text: in

text: the

text: surrounding

text: of

text: the

text: neighbors

text: with

text: the

text: same

text: color.

text: In

text: the

text: original

text: work

text: Shelling

text: considered

text: the

text: square

text: lattice,

text: where

text: the

text: number

text: of

text: nearest

text: neighbors

text: is

text: (direct

text: and

text: diagonal

text: nearest

text: neighbors).

text: An

text: agent

text: of

text: some

text: color

text: (say,

text: of

text: red),

text: who

text: has

text: fraction

text: of

text: nearest

text: neighbors

text: of

text: the

text: same

text: color

text: below

text: a

text: threshold

text: f,

text: is

text: unhappy

text: with

text: its

text: surroundings

text: and

text: can

text: be

text: moved

text: to

text: a

text: randomly

text: selected

text: nearest

text: empty

text: lattice

text: cell

text: as

text: long

text: as

text: such

text: cell

text: could

text: be

text: found.

text: In

text: another

text: version

text: of

text: the

text: model,

text: unhappy

text: agents

text: could

text: be

text: moved

text: to

text: any

text: unoccupied

text: cell

text: independent

text: of

text: the

text: distance.

text: Repeating

text: many

text: times

text: these

text: steps

text: one

text: arrives

text: at

text: a

text: dynamic

text: equilibrium.

text: Note

text: that

text: the

text: number

text: of

text: agents

text: of

text: each

text: color

text: is

text: conserved

text: in

text: course

text: of

text: such

text: evolution.

text: If

text: the

text: number

text: of

text: steps

text: tends

text: to

text: inﬁnity,

text: one

text: can

text: speak

text: about

text: the

text: phase

text: transition,

text: which

text: occurs

text: at

text: a

text: critical

text: value

text: of

text: f

text: such

text: that

text: for

text: f

text: f

text: agents

text: tend

text: to

text: form

text: unicolored

text: clusters

text: with

text: mobile

text: boundaries.

text: The

text: critical

text: threshold

text: f

text: is

text: exactly

text: known

text: for

text: the

text: Schelling

text: model

text: on

text: a

text: lattice.

text: For

text: a

text: two-dimensional

text: square

text: lattice

text: the

text: value

text: of

text: f

text: depends

text: on

text: whether

text: the

text: occupied

text: lattice

text: sites

text: are

text: above

text: or

text: below

text: the

text: percolation

text: transition.

text: As

text: discussed

text: in

text: the

text: result

text: f

text: holds

text: only

text: below

text: the

text: percolation

text: transition.

text: The

text: Schelling

text: model

text: demonstrates

text: how

text: even

text: relatively

text: weak

text: and

text: short-ranged

text: homophilic

text: preferences

text: (preference

text: to

text: live

text: with

text: people

text: of

text: the

text: same

text: social

text: category)

text: combined

text: with

text: mixing

text: (ability

text: to

text: move

text: to

text: an

text: empty

text: place)

text: could

text: force

text: global

text: (macroscopic)

text: changes

text: in

text: the

text: system

text: Moreover,

text: these

text: global

text: changes

text: appear

text: abruptly

text: (i.e.

text: as

text: a

text: phase

text: transition),

text: as

text: soon

text: as

text: the

text: tolerance

text: to

text: unhappiness,

text: quantitatively

text: expressed

text: in

text: f,

text: falls

text: below

text: the

text: critical

text: threshold,

text: f

text: The

text: Schelling

text: model

text: in

text: its

text: canonical

text: form

text: was

text: aimed

text: to

text: uncover

text: statistical

text: mechanisms

text: of

text: racial/religious/social

text: segregation

text: associated

text: with

text: resettlement

text: of

text: humans

text: in

text: communities

text: (e.g.

text: in

text: cities).

text: Thus,

text: this

text: model

text: naturally

text: depends

text: on

text: spatial

text: proximity

text: between

text: agents

text: and

text: it

text: needs

text: to

text: be

text: updated

text: to

text: be

text: catch

text: the

text: challenges

text: of

text: the

text: modern

text: era

text: in

text: which

text: distant

text: social

text: connections

text: mediated

text: by

text: social

text: networks

text: such

text: as

text: Facebook,

text: Twitter,

text: etc,

text: may

text: be

text: more

text: important

text: than

text: local

text: physical

text: neighborhood

text: (see

text: Ref.

text: for

text: the

text: ﬁrst

text: adaptation

text: of

text: the

text: Schelling

text: model

text: to

text: social

text: networks).

text: In

text: this

text: study

text: we

text: represent

text: the

text: society

text: as

text: a

text: collection

text: of

text: agents

text: from

text: two

text: social

text: categories

text: (red

text: and

text: green

text: ”colors”)

text: connected

text: by

text: some

text: social

text: relations

text: represented

text: as

text: edges

text: in

text: some

text: network.

text: Our

text: society

text: is

text: dynamic,

text: which

text: means

text: that


text: 5 FIG. 2: N as a function of µ at ν = 0.1 and the behavior of the second eigenvalue of Laplacian matrix. RG FIG. 3: N as a function of ν at µ = 0.1 and the behavior of the second eigenvalue of Laplacian matrix. RG Let us mention a few possible outcomes of our study for the statistical aspects of international relations: 1) The ﬁnite plateau in the regime (ii) seems to be of importance for the international relations. This is the manifestation of the statistical physics phenomena, where we have the stable global energy-entropic balance between the intra-state and inter-state connections. This plateau exists in some ﬁnite region in the (µ, ν) parameter plane. 2) The plateau exit from the balanced regime happens critically. Let us understand under the co-identity of unicolor triples the ”nationalism”, quantitatively characterized by µ, and identify the cross-color preference with the ”international tolerance”, quantitatively characterized by ν. We argue that transition between the ”nationalism- dominated phase” (ii) and the ”tolerance-dominated phase” (iii) occurs very sharply in the regime of phase transition. ##LTFigure## ##LTFigure## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: FIG.

text: N

label: caption

text: as

text: a

text: function

text: of

text: µ

text: at

text: ν

text: and

text: the

text: behavior

text: of

text: the

text: second

text: eigenvalue

text: of

text: Laplacian

text: matrix.

text: RG

text: FIG.

text: N

text: as

text: a

text: function

text: of

text: ν

text: at

text: µ

text: and

text: the

text: behavior

text: of

text: the

text: second

text: eigenvalue

text: of

text: Laplacian

text: matrix.

text: RG

text: Let

text: us

text: mention

text: a

text: few

text: possible

text: outcomes

text: of

text: our

text: study

text: for

text: the

text: statistical

text: aspects

text: of

text: international

text: relations:

text: The

text: ﬁnite

text: plateau

text: in

text: the

text: regime

text: (ii)

text: seems

text: to

text: be

text: of

text: importance

text: for

text: the

text: international

text: relations.

text: This

text: is

text: the

text: manifestation

text: of

text: the

text: statistical

text: physics

text: phenomena,

text: where

text: we

text: have

text: the

text: stable

text: global

text: energy-entropic

text: balance

text: between

text: the

text: intra-state

text: and

text: inter-state

text: connections.

text: This

text: plateau

text: exists

text: in

text: some

text: ﬁnite

text: region

text: in

text: the

text: (µ,

text: ν)

text: parameter

text: plane.

text: The

text: plateau

text: exit

text: from

text: the

text: balanced

text: regime

text: happens

text: critically.

text: Let

text: us

text: understand

text: under

text: the

text: co-identity

text: of

text: unicolor

text: triples

text: the

text: ”nationalism”,

text: quantitatively

text: characterized

text: by

text: µ,

text: and

text: identify

text: the

text: cross-color

text: preference

text: with

text: the

text: ”international

text: tolerance”,

text: quantitatively

text: characterized

text: by

text: ν.

text: We

text: argue

text: that

text: transition

text: between

text: the

text: ”nationalism-

text: dominated

text: phase”

text: (ii)

text: and

text: the

text: ”tolerance-dominated

text: phase”

text: (iii)

text: occurs

text: very

text: sharply

text: in

text: the

text: regime

text: of

text: phase

text: transition.

text: ##LTFigure##

text: ##LTFigure##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 9 (a) (b) FIG. 5: Few typical samples of intermediate stages of network evolution: (a) Networks with strictly conserved vertex degree (our model); (b) Networks with non-conserved vertex degree (”Strauss model”). of revealing hidden layers which we interpret as social groups in a society. We see that triadic interactions in only one social group are capable of inducing the eﬀective interactions in others. In the opposite limit in the two-parameter space, when the formation of the cross-color links dominates, the network develops the bipartite structure. We have discovered the new critical behavior between two regimes at particular values of chemical potentials µ and µ. At small number of intercolor links each color cluster selects the ”ambassador” of the society, to whom the cross-society connection is delegated. In the second model we describe how in a degree-constrained (unicolor) network occurs several qualitatively diﬀerent topologies separated by phase transitions. The driving force behind these transitions is the advantage or disadvantage of forming small closed and connected groups of individuals (3-cycles of graphs nodes). Above some critical value γ+ > 0, associated to 3-cycle graph motifs, the society gets spontaneously defragmented into a set of weakly interacting − communities. Contrary, the suppression of 3-cycles, leads to a critical (below γ < 0) formation of a polarized two- community (bipartite) or multi-community (multipartite)structure with loose connections within each community. Acknowledgments We are grateful for A. Andreev, D. Grebenkov and M. Tamm for useful discussions. The work of A.G. was performed at the Institute for Information Transmission Problems with the ﬁnancial support of the Russian Science Foundation (Grant No.14-50-00150); A.G. and O.V. acknowledge the support of Basis Foundation Fellowship; S.N. acknowledges the support of the EU-Horizon 2020 IRSES project DIONICOS (612707), and of the RFBR grant No. 16-02-00252. [1] T. Schelling, Dynamic Models of Segregation, J. Math. Sociology, 1 143 (1971) [2] D. Vincovic and A. Kirman, A physical analogue of the Schelling model, PNAS 103 19261 (2006) [3] L. Dall’Asta, C. Castellano, and M. Marsili, Statistical physics of the Schelling model of segregation, J. Stat. Mech. L07002 (2008) [4] E. Hatna and I. Benenson, Combining segregation and integration: Schelling model dynamics for heterogeneous population, J. Artiﬁcial Societies and Social Simulation 18 15 (2015) [5] A. Andreev, V. Avetisov, A. Gorsky, S. Maslov, S. Nechaev, and O. Valba, in preparation ##LTFigure## ##LTFigure## ##LTFigure## ##LTLine## ##LTLine## ##LTLine##

text: (a)

font: default

text: (b)

text: FIG.

text: Few

text: typical

text: samples

text: of

text: intermediate

text: stages

text: of

text: network

text: evolution:

text: (a)

text: Networks

text: with

text: strictly

text: conserved

text: vertex

text: degree

text: (our

text: model);

text: (b)

text: Networks

text: with

text: non-conserved

text: vertex

text: degree

text: (”Strauss

text: model”).

text: of

text: revealing

text: hidden

text: layers

text: which

text: we

text: interpret

text: as

text: social

text: groups

text: in

text: a

text: society.

text: We

text: see

text: that

text: triadic

text: interactions

text: in

text: only

text: one

text: social

text: group

text: are

text: capable

text: of

text: inducing

text: the

text: eﬀective

text: interactions

text: in

text: others.

text: In

text: the

text: opposite

text: limit

text: in

text: the

text: two-parameter

text: space,

text: when

text: the

text: formation

text: of

text: the

text: cross-color

text: links

text: dominates,

text: the

text: network

text: develops

text: the

text: bipartite

text: structure.

text: We

text: have

text: discovered

text: the

text: new

text: critical

text: behavior

text: between

text: two

text: regimes

text: at

text: particular

text: values

text: of

text: chemical

text: potentials

text: µ

text: and

text: µ.

text: At

text: small

text: number

text: of

text: intercolor

text: links

text: each

text: color

text: cluster

text: selects

text: the

text: ”ambassador”

text: of

text: the

text: society,

text: to

text: whom

text: the

text: cross-society

text: connection

text: is

text: delegated.

text: In

text: the

text: second

text: model

text: we

text: describe

text: how

text: in

text: a

text: degree-constrained

text: (unicolor)

text: network

text: occurs

text: several

text: qualitatively

text: diﬀerent

text: topologies

text: separated

text: by

text: phase

text: transitions.

text: The

text: driving

text: force

text: behind

text: these

text: transitions

text: is

text: the

text: advantage

text: or

text: disadvantage

text: of

text: forming

text: small

text: closed

text: and

text: connected

text: groups

text: of

text: individuals

text: of

text: graphs

text: nodes).

text: Above

text: some

text: critical

text: value

text: γ+

text: associated

text: to

text: graph

text: motifs,

text: the

text: society

text: gets

text: spontaneously

text: defragmented

text: into

text: a

text: set

text: of

text: weakly

text: interacting

text: communities.

text: Contrary,

text: the

text: suppression

text: of

text: leads

text: to

text: a

text: critical

text: (below

text: γ

text: formation

text: of

text: a

text: polarized

text: two-

text: community

text: (bipartite)

text: or

text: multi-community

text: (multipartite)structure

text: with

text: loose

text: connections

text: within

text: each

text: community.

text: Acknowledgments

text: We

text: are

text: grateful

text: for

text: A.

text: Andreev,

text: D.

text: Grebenkov

text: and

text: M.

text: Tamm

text: for

text: useful

text: discussions.

text: The

text: work

text: of

text: A.G.

text: was

text: performed

text: at

text: the

text: Institute

text: for

text: Information

text: Transmission

text: Problems

text: with

text: the

text: ﬁnancial

text: support

text: of

text: the

text: Russian

text: Science

text: Foundation

text: (Grant

text: A.G.

text: and

text: O.V.

text: acknowledge

text: the

text: support

text: of

text: Basis

text: Foundation

text: Fellowship;

text: S.N.

text: acknowledges

text: the

text: support

text: of

text: the

text: EU-Horizon

text: IRSES

text: project

text: DIONICOS

text: and

text: of

text: the

text: RFBR

text: grant

text: No.

text: T.

text: Schelling,

text: Dynamic

text: Models

text: of

text: Segregation,

text: J.

text: Math.

text: Sociology,

text: D.

text: Vincovic

text: and

text: A.

text: Kirman,

text: A

text: physical

text: analogue

text: of

text: the

text: Schelling

text: model,

text: PNAS

text: L.

text: Dall’Asta,

text: C.

text: Castellano,

text: and

text: M.

text: Marsili,

text: Statistical

text: physics

text: of

text: the

text: Schelling

text: model

text: of

text: segregation,

text: J.

text: Stat.

text: Mech.

text: E.

text: Hatna

text: and

text: I.

text: Benenson,

text: Combining

text: segregation

text: and

text: integration:

text: Schelling

text: model

text: dynamics

text: for

text: heterogeneous

text: population,

text: J.

text: Artiﬁcial

text: Societies

text: and

text: Social

text: Simulation

text: A.

text: Andreev,

text: V.

text: Avetisov,

text: A.

text: Gorsky,

text: S.

text: Maslov,

text: S.

text: Nechaev,

text: and

text: O.

text: Valba,

text: in

text: preparation

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: [23] H. Li. A statistical framework for snp calling, mutation discovery, association mapping and population genetical parameter estimation from sequencing data. Bioinformatics, 27(21):2987–2993, 2011. [24] C. S. Liew, M. P. Atkinson, R. Ostrowski, M. Cole, J. I. van Hemert, and L. Han. Performance database: capturing data for optimizing distributed streaming workﬂows. Philosophical transactions. Series A, Mathematical, physical, and engineering sciences, 369(1949):3268–84, 8 2011. [25] M. Massie, F. Nothaft, C. Hartl, C. Kozanitis, A. Schumacher, A. D. Joseph, and D. A. Patterson. Adam: Genomics formats and processing patterns for cloud scale computing. University of California, Berkeley Technical Report, No. UCB/EECS-2013, 207, 2013. [26] A. McKenna, M. Hanna, E. Banks, A. Sivachenko, K. Cibulskis, A. Kernytsky, K. Garimella, D. Altshuler, S. Gabriel, M. Daly, et al. The genome analysis toolkit: a mapreduce framework for analyzing next- generation dna sequencing data. Genome research, 20(9):1297–1303, 2010. [27] M. L. Mondelli, M. T. de Souza, K. Ocaña, A. T. R. de Vasconcelos, and L. M. R. Gadelha Jr. HPSW- Prof: A Provenance-Based Framework for Proﬁling High Performance Scientiﬁc Workﬂows. In Proc. of Satellite Events of the 31st Brazilian Symposium on Databases, pages 117–122. SBC, 2016. [28] F. Nadeem, F. Nerieri, S. Podlipnig, J. Qin, M. Siddiqui, H.-l. Truong, and A. Villazon. Askalon : A development and grid workﬂows. In Workﬂows for e-Science, pages 450–471. Springer, 2007. [29] K. A. Ocaña, D. d. Oliveira, E. Ogasawara, A. M. Davila, A. A. Lima, and M. Mattoso. Sciphy: A cloud-based workﬂow for phylogenetic analysis of drug targets in protozoan genomes. In Advances in Bioinformatics and Computational Biology - 6th Brazilian Symposium on Bioinformatics. Proceedings, pages 66–70. 2011. [30] W. Oliveira, L. M. Ambrósio, R. Braga, V. Ströele, J. M. David, and F. Campos. A framework for provenance analysis and visualization. Procedia Computer Science, 108:1592 – 1601, 2017. [31] T. C. Sharma and M. Jain. Weka approach for comparative study of classiﬁcation algorithm. Inter- national Journal of Advanced Research in Computer and Communication Engineering, 2(4):1925–1931, 2013. [32] V. Silva, L. Neves, R. Souza, A. Coutinho, D. de Oliveira, and M. Mattoso. Integrating domain-data steering with code-proﬁling tools to debug data-intensive workﬂows. In Proc. of the 11th Workshop on Workﬂows in Support of Large-Scale Science, pages 59–63, 2016. [33] V. Silva, D. Oliveira, and M. Mattoso. Scicumulus 2.0: Um sistema de gerência de workﬂows cientíﬁcos para nuvens orientado a ﬂuxo de dados. Sessão de Demos do XXIX Simpósio Brasileiro de Banco de Dados, 2014. [34] A. Stamatakis. Raxml-vi-hpc: maximum likelihood-based phylogenetic analyses with thousands of taxa and mixed models. Bioinformatics, 22(21):2688–2690, 2006. [35] O. Torreno and O. Trelles. Breaking the computational barriers of pairwise genome comparison. BMC bioinformatics, 16(1):250, 1 2015. [36] M. Wilde, I. Foster, K. Iskra, P. Beckman, Z. Zhang, A. Espinosa, M. Hategan, B. Clifford, and I. Raicu. Parallel scripting for applications at the petascale and beyond. Computer, 42(11), 2009. [37] M. Wilde, M. Hategan, J. M. Wozniak, B. Clifford, D. S. Katz, and I. Foster. Swift: A language for distributed parallel scripting. Parallel Computing, 37(9):633–652, 9 2011. [38] K. Wolstencroft, R. Haines, D. Fellows, A. Williams, D. Withers, S. Owen, S. Soiland-Reyes, I. Dunlop, A. Nenadic, P. Fisher, J. Bhagat, K. Belhajjame, F. Bacall, A. Hardisty, A. Nieva de la Hidalga, M. P. Balcazar Vargas, S. Suﬁ, and C. Goble. The taverna workﬂow suite: designing and executing workﬂows of web services on the desktop, web or in the cloud. Nucleic acids research, 41(Web Server issue):557– 61, 7 2013. 19

label: reference

font: UBFMHI+CharterBT-Roman

text: H.

text: Li.

text: A

text: statistical

text: framework

text: for

text: snp

text: calling,

text: mutation

text: discovery,

text: association

text: mapping

text: and

text: population

text: genetical

text: parameter

text: estimation

text: from

text: sequencing

text: data.

text: Bioinformatics,

font: KCNRXB+CharterBT-Italic

text: C.

text: S.

text: Liew,

text: M.

text: P.

text: Atkinson,

text: R.

text: Ostrowski,

text: M.

text: Cole,

text: J.

text: I.

text: van

text: Hemert,

text: and

text: L.

text: Han.

text: Performance

text: database:

text: capturing

text: data

text: for

text: optimizing

text: distributed

text: streaming

text: workﬂows.

text: Philosophical

text: transactions.

text: Series

text: A,

text: Mathematical,

text: physical,

text: and

text: engineering

text: sciences,

text: M.

text: Massie,

text: F.

text: Nothaft,

text: C.

text: Hartl,

text: C.

text: Kozanitis,

text: A.

text: Schumacher,

text: A.

text: D.

text: Joseph,

text: and

text: D.

text: A.

text: Patterson.

text: Adam:

text: Genomics

text: formats

text: and

text: processing

text: patterns

text: for

text: cloud

text: scale

text: computing.

text: University

text: of

text: California,

text: Berkeley

text: Technical

text: Report,

text: No.

text: A.

text: McKenna,

text: M.

text: Hanna,

text: E.

text: Banks,

text: A.

text: Sivachenko,

text: K.

text: Cibulskis,

text: A.

text: Kernytsky,

text: K.

text: Garimella,

text: D.

text: Altshuler,

text: S.

text: Gabriel,

text: M.

text: Daly,

text: et

text: al.

text: The

text: genome

text: analysis

text: toolkit:

text: a

text: mapreduce

text: framework

text: for

text: analyzing

text: next-

text: generation

text: dna

text: sequencing

text: data.

text: Genome

text: research,

text: M.

text: L.

text: Mondelli,

text: M.

text: T.

text: de

text: Souza,

text: K.

text: Ocaña,

text: A.

text: T.

text: R.

text: de

text: Vasconcelos,

text: and

text: L.

text: M.

text: R.

text: Gadelha

text: Jr.

text: HPSW-

text: Prof:

text: A

text: Provenance-Based

text: Framework

text: for

text: Proﬁling

text: High

text: Performance

text: Scientiﬁc

text: Workﬂows.

text: In

text: Proc.

text: of

text: Satellite

text: Events

text: of

text: the

text: Brazilian

text: Symposium

text: on

text: Databases,

text: pages

text: SBC,

text: F.

text: Nadeem,

text: F.

text: Nerieri,

text: S.

text: Podlipnig,

text: J.

text: Qin,

text: M.

text: Siddiqui,

text: H.-l.

text: Truong,

text: and

text: A.

text: Villazon.

text: Askalon

text: A

text: development

text: and

text: grid

text: workﬂows.

text: In

text: Workﬂows

text: for

text: e-Science,

text: pages

text: Springer,

text: K.

text: A.

text: Ocaña,

text: D.

text: d.

text: Oliveira,

text: E.

text: Ogasawara,

text: A.

text: M.

text: Davila,

text: A.

text: A.

text: Lima,

text: and

text: M.

text: Mattoso.

text: Sciphy:

text: A

text: cloud-based

text: workﬂow

text: for

text: phylogenetic

text: analysis

text: of

text: drug

text: targets

text: in

text: protozoan

text: genomes.

text: In

text: Advances

text: in

text: Bioinformatics

text: and

text: Computational

text: Biology

text: Brazilian

text: Symposium

text: on

text: Bioinformatics.

text: Proceedings,

text: pages

text: W.

text: Oliveira,

text: L.

text: M.

text: Ambrósio,

text: R.

text: Braga,

text: V.

text: Ströele,

text: J.

text: M.

text: David,

text: and

text: F.

text: Campos.

text: A

text: framework

text: for

text: provenance

text: analysis

text: and

text: visualization.

text: Procedia

text: Computer

text: Science,

text: T.

text: C.

text: Sharma

text: and

text: M.

text: Jain.

text: Weka

text: approach

text: for

text: comparative

text: study

text: of

text: classiﬁcation

text: algorithm.

text: Inter-

text: national

text: Journal

text: of

text: Advanced

text: Research

text: in

text: Computer

text: and

text: Communication

text: Engineering,

text: V.

text: Silva,

text: L.

text: Neves,

text: R.

text: Souza,

text: A.

text: Coutinho,

text: D.

text: de

text: Oliveira,

text: and

text: M.

text: Mattoso.

text: Integrating

text: domain-data

text: steering

text: with

text: code-proﬁling

text: tools

text: to

text: debug

text: data-intensive

text: workﬂows.

text: In

text: Proc.

text: of

text: the

text: Workshop

text: on

text: Workﬂows

text: in

text: Support

text: of

text: Large-Scale

text: Science,

text: pages

text: V.

text: Silva,

text: D.

text: Oliveira,

text: and

text: M.

text: Mattoso.

text: Scicumulus

text: Um

text: sistema

text: de

text: gerência

text: de

text: workﬂows

text: cientíﬁcos

text: para

text: nuvens

text: orientado

text: a

text: ﬂuxo

text: de

text: dados.

text: Sessão

text: de

text: Demos

text: do

text: XXIX

text: Simpósio

text: Brasileiro

text: de

text: Banco

text: de

text: Dados,

text: A.

text: Stamatakis.

text: Raxml-vi-hpc:

text: maximum

text: likelihood-based

text: phylogenetic

text: analyses

text: with

text: thousands

text: of

text: taxa

text: and

text: mixed

text: models.

text: Bioinformatics,

text: O.

text: Torreno

text: and

text: O.

text: Trelles.

text: Breaking

text: the

text: computational

text: barriers

text: of

text: pairwise

text: genome

text: comparison.

text: BMC

text: bioinformatics,

text: M.

text: Wilde,

text: I.

text: Foster,

text: K.

text: Iskra,

text: P.

text: Beckman,

text: Z.

text: Zhang,

text: A.

text: Espinosa,

text: M.

text: Hategan,

text: B.

text: Clifford,

text: and

text: I.

text: Raicu.

text: Parallel

text: scripting

text: for

text: applications

text: at

text: the

text: petascale

text: and

text: beyond.

text: Computer,

text: M.

text: Wilde,

text: M.

text: Hategan,

text: J.

text: M.

text: Wozniak,

text: B.

text: Clifford,

text: D.

text: S.

text: Katz,

text: and

text: I.

text: Foster.

text: Swift:

text: A

text: language

text: for

text: distributed

text: parallel

text: scripting.

text: Parallel

text: Computing,

text: K.

text: Wolstencroft,

text: R.

text: Haines,

text: D.

text: Fellows,

text: A.

text: Williams,

text: D.

text: Withers,

text: S.

text: Owen,

text: S.

text: Soiland-Reyes,

text: I.

text: Dunlop,

text: A.

text: Nenadic,

text: P.

text: Fisher,

text: J.

text: Bhagat,

text: K.

text: Belhajjame,

text: F.

text: Bacall,

text: A.

text: Hardisty,

text: A.

text: Nieva

text: de

text: la

text: Hidalga,

text: M.

text: P.

text: Balcazar

text: Vargas,

text: S.

text: Suﬁ,

text: and

text: C.

text: Goble.

text: The

text: taverna

text: workﬂow

text: suite:

text: designing

text: and

text: executing

text: workﬂows

text: of

text: web

text: services

text: on

text: the

text: desktop,

text: web

text: or

text: in

text: the

text: cloud.

text: Nucleic

text: acids

text: research,

text: Server


text: ∗ Black Holes as Brains: Neural Networks with Area Law Entropy Gia Dvali † ‡ and 11 (Dated: May 30, 2020) Motivated by the potential similarities between the underlying mechanisms of the enhanced mem- ory storage capacity in black holes and in brain networks, we construct an artiﬁcial quantum neural network based on gravity-like synaptic connections and a symmetry structure that allows to describe the network in terms of geometry of a d-dimensional space. We show that the network possesses a − critical state in which the gapless neurons emerge that appear to inhabit a d 1-dimensional surface, with their number given by the surface area. In the excitations of these neurons, the network can store and retrieve an exponentially large number of patterns within an arbitrarily narrow energy gap. The corresponding micro-state entropy of the brain network exhibits an area law. The neural network can be described in terms of a quantum ﬁeld, via identifying the diﬀerent neurons with the diﬀerent momentum modes of the ﬁeld, while identifying the synaptic connections among the neurons with the interactions among the corresponding momentum modes. Such a mapping allows to attribute a well-deﬁned sense of geometry to an intrinsically non-local system, such as the neural network, and vice versa, it allows to represent the quantum ﬁeld model as a neural network. I. INTRODUCTION The general message is that for gravity-like synaptic connections in a quantum neural network the informa- Given that black holes and human brains exhibit ex- tion storage mechanisms can become potentially richer traordinary memory storage capacities, it is natural to than in more conventional approaches. Instead of storing ask whether these systems share some very basic mecha- patterns in the local minima of the energy function, as, nism of the enhanced capacity of the information storage for example, in usual treatments of the Hopﬁeld model [1]. Needless to say, a potential identiﬁcation of such [4], the enhanced memory points can be identiﬁed among similarities, would be mutually beneﬁcial for both ﬁelds the highly excited critical states, where set of neurons of research. Obviously, the ﬁnal answer requires the becomes gapless. involvement of biology, which is beyond our expertise. However, we can attempt to do a physicist part of the In this paper we shall attempt to take one more step job. A step in this direction was undertaken in [1], where and try to see if a neural network can possess some a general mechanism [2] - originally proposed for the additional informational characteristics that are usually explanation of an enhanced memory capacity in black considered to be the deﬁning properties of black holes, holes - was applied to the framework [3] of quantum such as the Bekenstein’s area law entropy [5]. neural networks and was shown that it leads to an expo- nential enhancement of pattern storage and recognition In constructing such a network, we shall use the syn- capacities. The idea is that by allowing the excitatory ergy of the ideas displayed in [1] and [6]. In the latter synaptic connections among the set of neurons to be work it was shown that a theory of a quantum ﬁeld gravity-like - in the sense of a negative interaction en- inhabiting a d-dimensional sphere and experiencing an ergy - the network gives rise to a critical state with an angular-momentum-dependent attractive interaction ex- exponentially enhanced memory storage capacity. This hibits a sharp enhancement of memory storage capacity state is achieved due to the following eﬀect. A high in a critical state in which the lowest angular momentum excitation level of some neurons - due to their negative mode is macroscopically excited. This excitation lowers synaptic connections with others - lowers to zero the ex- the energy thresholds of the higher angular momentum citation threshold energies for the latter neurons, thereby modes, so that the theory delivers a set of the gap−less making is possible to store an exponentially large num- modes with their number scaling as the area of a d 1- ber of patterns within an inﬁnitesimally narrow energy dimensional sphere. The micro-states of these modes gap. Moreover, the patterns stored in such states can house an exponentially large number of patterns, with be redialed under an inﬂuence of arbitrarily soft external th−e corresponding entropy given by the area of the same stimuli. d 1-dimensional sphere. The quantum brain network that we shall construct in the present paper is nothing but a neural network ∗ implementation of the same model. This is achieved by † means of identiﬁcation of the neuron-describing degrees ‡ of freedom with the number operators of the angular ##LTLine##

text: Black

text: Holes

text: as

text: Brains:

text: Neural

text: Networks

text: with

text: Area

text: Law

text: Entropy

text: Gia

text: Dvali

text: and

text: (Dated:

text: May

label: date

text: Motivated

label: abstract

text: by

text: the

text: potential

text: similarities

text: between

text: the

text: underlying

text: mechanisms

text: of

text: the

text: enhanced

text: mem-

text: ory

text: storage

text: capacity

text: in

text: black

text: holes

text: and

text: in

text: brain

text: networks,

text: we

text: construct

text: an

text: artiﬁcial

text: quantum

text: neural

text: network

text: based

text: on

text: gravity-like

text: synaptic

text: connections

text: and

text: a

text: symmetry

text: structure

text: that

text: allows

text: to

text: describe

text: the

text: network

text: in

text: terms

text: of

text: geometry

text: of

text: a

text: d-dimensional

text: space.

text: We

text: show

text: that

text: the

text: network

text: possesses

text: a

text: critical

text: state

text: in

text: which

text: the

text: gapless

text: neurons

text: emerge

text: that

text: appear

text: to

text: inhabit

text: a

text: d

text: surface,

text: with

text: their

text: number

text: given

text: by

text: the

text: surface

text: area.

text: In

text: the

text: excitations

text: of

text: these

text: neurons,

text: the

text: network

text: can

text: store

text: and

text: retrieve

text: an

text: exponentially

text: large

text: number

text: of

text: patterns

text: within

text: an

text: arbitrarily

text: narrow

text: energy

text: gap.

text: The

text: corresponding

text: micro-state

text: entropy

text: of

text: the

text: brain

text: network

text: exhibits

text: an

text: area

text: law.

text: The

text: neural

text: network

text: can

text: be

text: described

text: in

text: terms

text: of

text: a

text: quantum

text: ﬁeld,

text: via

text: identifying

text: the

text: diﬀerent

text: neurons

text: with

text: the

text: diﬀerent

text: momentum

text: modes

text: of

text: the

text: ﬁeld,

text: while

text: identifying

text: the

text: synaptic

text: connections

text: among

text: the

text: neurons

text: with

text: the

text: interactions

text: among

text: the

text: corresponding

text: momentum

text: modes.

text: Such

text: a

text: mapping

text: allows

text: to

text: attribute

text: a

text: well-deﬁned

text: sense

text: of

text: geometry

text: to

text: an

text: intrinsically

text: non-local

text: system,

text: such

text: as

text: the

text: neural

text: network,

text: and

text: vice

text: versa,

text: it

text: allows

text: to

text: represent

text: the

text: quantum

text: ﬁeld

text: model

text: as

text: a

text: neural

text: network.

text: I.

text: INTRODUCTION

text: The

text: general

text: message

text: is

text: that

text: for

text: gravity-like

text: synaptic

text: connections

text: in

text: a

text: quantum

text: neural

text: network

text: the

text: informa-

text: Given

text: that

text: black

text: holes

text: and

text: human

text: brains

text: exhibit

text: ex-

text: tion

text: storage

text: mechanisms

text: can

text: become

text: potentially

text: richer

text: traordinary

text: memory

text: storage

text: capacities,

text: it

text: is

text: natural

text: to

text: than

text: in

text: more

text: conventional

text: approaches.

text: Instead

text: of

text: storing

text: ask

text: whether

text: these

text: systems

text: share

text: some

text: very

text: basic

text: mecha-

text: patterns

text: in

text: the

text: local

text: minima

text: of

text: the

text: energy

text: function,

text: as,

text: nism

text: of

text: the

text: enhanced

text: capacity

text: of

text: the

text: information

text: storage

text: for

text: example,

text: in

text: usual

text: treatments

text: of

text: the

text: Hopﬁeld

text: model

text: Needless

text: to

text: say,

text: a

text: potential

text: identiﬁcation

text: of

text: such

text: the

text: enhanced

text: memory

text: points

text: can

text: be

text: identiﬁed

text: among

text: similarities,

text: would

text: be

text: mutually

text: beneﬁcial

text: for

text: both

text: ﬁelds

text: the

text: highly

text: excited

text: critical

text: states,

text: where

text: set

text: of

text: neurons

text: of

text: research.

text: Obviously,

text: the

text: ﬁnal

text: answer

text: requires

text: the

text: becomes

text: gapless.

text: involvement

text: of

text: biology,

text: which

text: is

text: beyond

text: our

text: expertise.

text: However,

text: we

text: can

text: attempt

text: to

text: do

text: a

text: physicist

text: part

text: of

text: the

text: In

text: this

text: paper

text: we

text: shall

text: attempt

text: to

text: take

text: one

text: more

text: step

text: job.

text: A

text: step

text: in

text: this

text: direction

text: was

text: undertaken

text: in

text: where

text: and

text: try

text: to

text: see

text: if

text: a

text: neural

text: network

text: can

text: possess

text: some

text: a

text: general

text: mechanism

text: originally

text: proposed

text: for

text: the

text: additional

text: informational

text: characteristics

text: that

text: are

text: usually

text: explanation

text: of

text: an

text: enhanced

text: memory

text: capacity

text: in

text: black

text: considered

text: to

text: be

text: the

text: deﬁning

text: properties

text: of

text: black

text: holes,

text: holes

text: was

text: applied

text: to

text: the

text: framework

text: of

text: quantum

text: such

text: as

text: the

text: Bekenstein’s

text: area

text: law

text: entropy

text: neural

text: networks

text: and

text: was

text: shown

text: that

text: it

text: leads

text: to

text: an

text: expo-

text: nential

text: enhancement

text: of

text: pattern

text: storage

text: and

text: recognition

text: In

text: constructing

text: such

text: a

text: network,

text: we

text: shall

text: use

text: the

text: syn-

text: capacities.

text: The

text: idea

text: is

text: that

text: by

text: allowing

text: the

text: excitatory

text: ergy

text: of

text: the

text: ideas

text: displayed

text: in

text: and

text: In

text: the

text: latter

text: synaptic

text: connections

text: among

text: the

text: set

text: of

text: neurons

text: to

text: be

text: work

text: it

text: was

text: shown

text: that

text: a

text: theory

text: of

text: a

text: quantum

text: ﬁeld

text: gravity-like

text: in

text: the

text: sense

text: of

text: a

text: negative

text: interaction

text: en-

text: inhabiting

text: a

text: d-dimensional

text: sphere

text: and

text: experiencing

text: an

text: ergy

text: the

text: network

text: gives

text: rise

text: to

text: a

text: critical

text: state

text: with

text: an

text: angular-momentum-dependent

text: attractive

text: interaction

text: ex-

text: exponentially

text: enhanced

text: memory

text: storage

text: capacity.

text: This

text: hibits

text: a

text: sharp

text: enhancement

text: of

text: memory

text: storage

text: capacity

text: state

text: is

text: achieved

text: due

text: to

text: the

text: following

text: eﬀect.

text: A

text: high

text: in

text: a

text: critical

text: state

text: in

text: which

text: the

text: lowest

text: angular

text: momentum

text: excitation

text: level

text: of

text: some

text: neurons

text: due

text: to

text: their

text: negative

text: mode

text: is

text: macroscopically

text: excited.

text: This

text: excitation

text: lowers

text: synaptic

text: connections

text: with

text: others

text: lowers

text: to

text: zero

text: the

text: ex-

text: the

text: energy

text: thresholds

text: of

text: the

text: higher

text: angular

text: momentum

text: citation

text: threshold

text: energies

text: for

text: the

text: latter

text: neurons,

text: thereby

text: modes,

text: so

text: that

text: the

text: theory

text: delivers

text: a

text: set

text: of

text: the

text: gap−less

text: making

text: is

text: possible

text: to

text: store

text: an

text: exponentially

text: large

text: num-

text: modes

text: with

text: their

text: number

text: scaling

text: as

text: the

text: area

text: of

text: a

text: d

text: ber

text: of

text: patterns

text: within

text: an

text: inﬁnitesimally

text: narrow

text: energy

text: dimensional

text: sphere.

text: The

text: micro-states

text: of

text: these

text: modes

text: gap.

text: Moreover,

text: the

text: patterns

text: stored

text: in

text: such

text: states

text: can

text: house

text: an

text: exponentially

text: large

text: number

text: of

text: patterns,

text: with

text: be

text: redialed

text: under

text: an

text: inﬂuence

text: of

text: arbitrarily

text: soft

text: external

text: th−e

text: corresponding

text: entropy

text: given

text: by

text: the

text: area

text: of

text: the

text: same

text: stimuli.

text: d

text: sphere.

text: The

text: quantum

text: brain

text: network

text: that

text: we

text: shall

text: construct

text: in

text: the

text: present

text: paper

text: is

text: nothing

text: but

text: a

text: neural

text: network

text: implementation

text: of

text: the

text: same

text: model.

text: This

text: is

text: achieved

text: by

text: means

text: of

text: identiﬁcation

text: of

text: the

text: neuron-describing

text: degrees

text: of

text: freedom

text: with

text: the

text: number

text: operators

text: of

text: the

text: angular

text: ##LTLine##


text: 10 sible that satisﬁes this constraint. The mapping from performing the double Legendre transform on ρ (t, c) (cid:80) G hard constraints on the extreme value to a constraint on w.r.t. ν(t, c) (equivalently Hamiltonian minimization its mean is analogous to that from the microcan(cid:12)onical to [25]), and replacing ν(t, c) by its self-averaged value the canonical ensemble in the thermodynamic li(cid:12)mit [12]. N (cid:104)ν(t, c )(cid:105), Eq. (A.5) factorizes into Eq. (8) of the The marginal distribution of amino acid ti at posi- maii=n1 text, iwhere γ (given by Eq. (9)) is the conjugate tmioany−bi eofobptoasint-esdelef(cid:80)rcotmionEqT.C(RA.5s)eqbuy(cid:80)e→ntcaek∞si,ngPa(tisupmosto,vce)r, vνa(tri,acb)l,e(cid:104)ρtoG(νt(,tc,)c(cid:105)).beAcfotmeresthEeqL. e(g1e1n).drHeotwraβns∗foisrmfosuwnd.r.itn. 20N 1 terms. However, in the N limit, ν(t, c) practice is described after Eq. (11) of the main text. → (cid:104) (cid:105) self-averages, i.e. N ν(t , c ) N ν(t, c ) ; thus, i=1 i i i=1 i ∗ [13] S. Miyazawa and R. L. Jernigan, J. Mol. Biol. 256, 623 (1996). [1] S. M. Alam, P. J. Travers, J. L. Wung, W. Nasholds, S. Red[1p4a]thB,.SL..CA.kJeanmeetsoanl.,, NauncdleNic. ARc.idJs. GRaess.co4i5g,neD,6N35at(u2r0e137)8.1, 616 (1996). [15] H. Li, C. Tang, and N. S. Wingreen, Phys. Rev. Lett. 79, 765 (1997). [2] M. Krogsgaard and M. M. Davis, Nat. Immunol. 6, 239 (200[51)6.] M. A. Daniels, E. Teixeiro, J. Gill, B. Hausmann, D. Roubaty, K. Holmberg, G. Werlen, G. A. Holländer, N. R. J. [3] A. Murugan, T. Mora, A. M. Walczak, and C. G. Callan, Jr., PrGoca.scNoaigtln.eA, caandd. SEc.i.PUa.lSm.Aer., 1N0a9t,ur1e6146414(,2702142)(.2006). [4] E. S. Huseby, J. White, F. Crawford, T. Vass, D. Becker, C. P[1in7i]llKa,.PC..MGaarrrcaicak,anadndE.JJ. .WA.dKamapsp, lCere,llC1e2ll21,2323,32(42700(250).05). [5] Y. Elhanati, A. Murugan, C. G. Callan, Jr., T. Mora, and A.[1M8]. WB.aMlcz.aBk,akPerro,cD. N. Rat.l.SAcoctatd,.SS.cJi.. UB.lSev.Ain.s1, 1a1n,d98W75. (F2.0H14a)w. se, Immunol. Rev. 250, 10 (2012). [6] Z. Sethna, Y. Elhanati, C. R. Dudgeon, C. G. Callan, Jr., A.[1J9.]LLe.vAin.e,CTol.f,MAo.raJ,. BaanndkAov.icMh., WN.aAlc.zaHka,nPicrko,c.NN. aAt.l.BAocwaedr.man, L. L. Jones, D. M. Kranz, and K. C. Garcia, Cell 129, 135 Sci. U.S.A. 114, 2253 (2017). (2007). [7] B. D. Stadinski, K. Shekhar, I. Gómez-Touriño, J. Jung, K. [S2a0s]aXki., YAs.eKrn.,SHe.wLelil,, Man.dPRea.kAm.aMn,arAiu.zKza.,CNhaatk.rSatbrourctty., Baionld. 5, 412 (1998). E. S. Huseby, Nat. Immunol. 17, 946 (2016). [21] D. Housset and B. Malissen, Trends Immunol. 24, 429 (2003). [8] A. J. Yates, Front. Immunol. 5, 13 (2014). [22] P. Dash, A. J. Fiore-Gartland, T. Hertz, G. C. Wang, S. Sharma, A. Souquette, J. C. Crawford, E. B. Clemens, T. H. O. [9] V. Detours, R. Mehr, and A. S. Perelson, J. Theor. Biol. 200, 38N9g(u1y9e9n9,).K. Kedzierska, N. L. La Gruta, P. Bradley, and P. G. Thomas, Nature 547, 89 (2017). [10] V. Detours and A. S. Perelson, Proc. Natl. Acad. Sci. U.S.A.[2936],J5.1G53la(n1v9i9ll9e),.H. Huang, A. Nau, O. Hatton, L. E. Wagar, F. Rubelt, X. Ji, A. Han, S. M. Krams, C. Pettus, N. Haas, C. [11] A. Košmrlj, A. K. Jha, E. S. Huseby, M. Kardar, and A. K. ChakrSa.bLoirntyd,ePstraomc.ANraltelh.aAmcnad, .AS.cSi.eUtt.eS,.AS..D10. 5B,o1y6d6,7T1.(J20. 0S8c)r.iba, O. M. Martinez, and M. M. Davis, Nature 547, 94 (2017). [12] A. Košmrlj, A. K. Chakraborty, M. Kardar, and E. I. Shakh[n2o4v] iJch. ,TP. hGyeso.rRgee,v.DL.eAtt..K1e0s3s,le0r6, 8a1n03d (H2.00L9e)v.ine, Proc. Natl. Acad. Sci. U.S.A. 114, E7875 (2017). [25] M. Kardar, Phys. Rev. Lett. 51, 523 (1983). ##LTLine## ##LTLine## ##LTLine##

text: sible

text: that

text: satisﬁes

text: this

text: constraint.

text: The

text: mapping

text: from

text: performing

text: the

text: double

text: Legendre

text: transform

text: on

text: ρ

text: (t,

text: c)

text: G

text: hard

text: constraints

text: on

text: the

text: extreme

text: value

text: to

text: a

text: constraint

text: on

text: w.r.t.

text: ν(t,

text: c)

text: (equivalently

text: Hamiltonian

text: minimization

text: its

text: mean

text: is

text: analogous

text: to

text: that

text: from

text: the

text: to

text: and

text: replacing

text: ν(t,

text: c)

text: by

text: its

text: self-averaged

text: value

text: the

text: canonical

text: ensemble

text: in

text: the

text: thermodynamic

text: N

text: c

text: Eq.

text: factorizes

text: into

text: Eq.

text: of

text: the

text: The

text: marginal

text: distribution

text: of

text: amino

text: acid

text: ti

text: at

text: posi-

text: text,

text: iwhere

text: γ

text: (given

text: by

text: Eq.

text: is

text: the

text: conjugate

text: tmioany−bi

text: terms.

text: However,

text: in

text: the

text: N

text: limit,

text: ν(t,

text: c)

text: practice

text: is

text: described

text: after

text: Eq.

text: of

text: the

text: main

text: text.

text: self-averages,

text: i.e.

text: N

text: ν(t

text: c

text: N

text: ν(t,

text: c

text: thus,

text: i

text: i

text: i

text: S.

text: Miyazawa

text: and

text: R.

text: L.

text: Jernigan,

text: J.

text: Mol.

text: Biol.

text: S.

text: M.

text: Alam,

text: P.

text: J.

text: Travers,

text: J.

text: L.

text: Wung,

text: W.

text: Nasholds,

text: S.

text: NauncdleNic.

text: ARc.idJs.

text: H.

text: Li,

text: C.

text: Tang,

text: and

text: N.

text: S.

text: Wingreen,

text: Phys.

text: Rev.

text: Lett.

text: M.

text: Krogsgaard

text: and

text: M.

text: M.

text: Davis,

text: Nat.

text: Immunol.

text: M.

text: A.

text: Daniels,

text: E.

text: Teixeiro,

text: J.

text: Gill,

text: B.

text: Hausmann,

text: D.

text: Roubaty,

text: K.

text: Holmberg,

text: G.

text: Werlen,

text: G.

text: A.

text: Holländer,

text: N.

text: R.

text: J.

text: A.

text: Murugan,

text: T.

text: Mora,

text: A.

text: M.

text: Walczak,

text: and

text: C.

text: G.

text: Callan,

text: Jr.,

text: PrGoca.scNoaigtln.eA,

text: caandd.

text: SEc.i.PUa.lSm.Aer.,

text: E.

text: S.

text: Huseby,

text: J.

text: White,

text: F.

text: Crawford,

text: T.

text: Vass,

text: D.

text: Becker,

text: C.

text: .WA.dKamapsp,

text: Y.

text: Elhanati,

text: A.

text: Murugan,

text: C.

text: G.

text: Callan,

text: Jr.,

text: T.

text: Mora,

text: and

text: WB.aMlcz.aBk,akPerro,cD.

text: N.

text: Rat.l.SAcoctatd,.SS.cJi..

text: se,

text: Immunol.

text: Rev.

text: Z.

text: Sethna,

text: Y.

text: Elhanati,

text: C.

text: R.

text: Dudgeon,

text: C.

text: G.

text: Callan,

text: Jr.,

text: BaanndkAov.icMh.,

text: WN.aAlc.zaHka,nPicrko,c.NN.

text: aAt.l.BAocwaedr.man,

text: L.

text: L.

text: Jones,

text: D.

text: M.

text: Kranz,

text: and

text: K.

text: C.

text: Garcia,

text: Cell

text: Sci.

text: U.S.A.

text: B.

text: D.

text: Stadinski,

text: K.

text: Shekhar,

text: I.

text: Gómez-Touriño,

text: J.

text: Jung,

text: K.

text: YAs.eKrn.,SHe.wLelil,,

text: Baionld.

text: E.

text: S.

text: Huseby,

text: Nat.

text: Immunol.

text: D.

text: Housset

text: and

text: B.

text: Malissen,

text: Trends

text: Immunol.

text: A.

text: J.

text: Yates,

text: Front.

text: Immunol.

text: P.

text: Dash,

text: A.

text: J.

text: Fiore-Gartland,

text: T.

text: Hertz,

text: G.

text: C.

text: Wang,

text: S.

text: Sharma,

text: A.

text: Souquette,

text: J.

text: C.

text: Crawford,

text: E.

text: B.

text: Clemens,

text: T.

text: H.

text: O.

text: V.

text: Detours,

text: R.

text: Mehr,

text: and

text: A.

text: S.

text: Perelson,

text: J.

text: Theor.

text: Biol.

text: Kedzierska,

text: N.

text: L.

text: La

text: Gruta,

text: P.

text: Bradley,

text: and

text: P.

text: G.

text: Thomas,

text: Nature

text: V.

text: Detours

text: and

text: A.

text: S.

text: Perelson,

text: Proc.

text: Natl.

text: Acad.

text: Sci.

text: Huang,

text: A.

text: Nau,

text: O.

text: Hatton,

text: L.

text: E.

text: Wagar,

text: F.

text: Rubelt,

text: X.

text: Ji,

text: A.

text: Han,

text: S.

text: M.

text: Krams,

text: C.

text: Pettus,

text: N.

text: Haas,

text: C.

text: A.

text: Košmrlj,

text: A.

text: K.

text: Jha,

text: E.

text: S.

text: Huseby,

text: M.

text: Kardar,

text: and

text: A.

text: K.

text: O.

text: M.

text: Martinez,

text: and

text: M.

text: M.

text: Davis,

text: Nature

text: A.

text: Košmrlj,

text: A.

text: K.

text: Chakraborty,

text: M.

text: Kardar,

text: and

text: E.

text: I.

text: iJch.

text: ,TP.

text: Proc.

text: Natl.

text: Acad.

text: Sci.

text: U.S.A.

text: M.

text: Kardar,

text: Phys.

text: Rev.

text: Lett.

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 18 Application to fermions is straightforward since Hamiltonian terms always have fermion parity even. If one represents a fermionic Hamiltonian by the Jordan-Wigner transformation (the repre- sentation of Cliﬀord algebra), any local operator of odd fermion parity has large support over the qubits, but every local term of the Hamiltonian has local support over the qubits. If we use quantum signal processing based algorithms [4, 5] to implement the blocks of size O O ((cid:96)D), then we need (log (cid:96)) ancilla qubits for a block. Thus, if we do not mind implementing O them all in serial, then it follows that the number of ancillas needed is (log log(T L/(cid:15))), which is much smaller than what would be needed if the quantum signal processing algorithm was directly used to simulate the full system. The decomposition based on Lieb-Robinson bounds looks very similar to higher order Lie- Trotter-Suzuki formulas. The diﬀerence is in the fact that the overlap is chosen to be larger and larger (though very slowly) as the simulated spacetime volume increases. This might guide us to understand why Lie-Trotter-Suzuki formulas work well empirically. Appendix A: Lieb-Robinson Bounds with Bounded Commutators 1. Introduction and Assumptions One advantage of the method described in this paper is that if the Lieb-Robinson velocity is small, then the method becomes more accurate. One case in which this occurs is if the terms in the Hamiltonian have a small commutator with each other. This section considers the Lieb-Robinson velocity under such a small commutator assumption. Note that Trotter-Suzuki methods also improve in accuracy if the Hamiltonian terms have a small commutator, but many other time-simulation (cid:80) methods do not. Consider a Hamiltonian H = h , where each X represents some set of sites and the sum is X X over all possible subsets of the lattice. h is a Hermitian operator obeying a commutator condition X (cid:107) (cid:107) ≤ (cid:107) (cid:107) (cid:107) (cid:107) [h , h ] η h h (A1) X Y X Y ≤ ≤ for all X, Y for some 0 η 2. We will additionally impose some locality assumption on H. A convenient one is exponential decay in the following form. Introduce a metric dist(x, y) between pairs of sites x, y. Assume that there are constants ζ, µ > 0 such that for any site x,

text: Application

text: to

text: fermions

text: is

text: straightforward

text: since

text: Hamiltonian

text: terms

text: always

text: have

text: fermion

text: parity

text: even.

text: If

text: one

text: represents

text: a

text: fermionic

text: Hamiltonian

text: by

text: the

text: Jordan-Wigner

text: transformation

text: (the

text: repre-

text: sentation

text: of

text: Cliﬀord

text: algebra),

text: any

text: local

text: operator

text: of

text: odd

text: fermion

text: parity

text: has

text: large

text: support

text: over

text: the

text: qubits,

text: but

text: every

text: local

text: term

text: of

text: the

text: Hamiltonian

text: has

text: local

text: support

text: over

text: the

text: qubits.

text: If

text: we

text: use

text: quantum

text: signal

text: processing

text: based

text: algorithms

text: to

text: implement

text: the

text: blocks

text: of

text: size

text: O

text: O

text: then

text: we

text: need

text: (log

text: ancilla

text: qubits

text: for

text: a

text: block.

text: Thus,

text: if

text: we

text: do

text: not

text: mind

text: implementing

text: O

text: them

text: all

text: in

text: serial,

text: then

text: it

text: follows

text: that

text: the

text: number

text: of

text: ancillas

text: needed

text: is

text: (log

text: log(T

text: which

text: is

text: much

text: smaller

text: than

text: what

text: would

text: be

text: needed

text: if

text: the

text: quantum

text: signal

text: processing

text: algorithm

text: was

text: directly

text: used

text: to

text: simulate

text: the

text: full

text: system.

text: The

text: decomposition

text: based

text: on

text: Lieb-Robinson

text: bounds

text: looks

text: very

text: similar

text: to

text: higher

text: order

text: Lie-

text: Trotter-Suzuki

text: formulas.

text: The

text: diﬀerence

text: is

text: in

text: the

text: fact

text: that

text: the

text: overlap

text: is

text: chosen

text: to

text: be

text: larger

text: and

text: larger

text: (though

text: very

text: slowly)

text: as

text: the

text: simulated

text: spacetime

text: volume

text: increases.

text: This

text: might

text: guide

text: us

text: to

text: understand

text: why

text: Lie-Trotter-Suzuki

text: formulas

text: work

text: well

text: empirically.

text: Appendix

text: A:

text: Lieb-Robinson

text: Bounds

text: with

text: Bounded

text: Commutators

text: Introduction

text: and

text: Assumptions

text: One

text: advantage

text: of

text: the

text: method

text: described

text: in

text: this

text: paper

text: is

text: that

text: if

text: the

text: Lieb-Robinson

text: velocity

text: is

text: small,

text: then

text: the

text: method

text: becomes

text: more

text: accurate.

text: One

text: case

text: in

text: which

text: this

text: occurs

text: is

text: if

text: the

text: terms

text: in

text: the

text: Hamiltonian

text: have

text: a

text: small

text: commutator

text: with

text: each

text: other.

text: This

text: section

text: considers

text: the

text: Lieb-Robinson

text: velocity

text: under

text: such

text: a

text: small

text: commutator

text: assumption.

text: Note

text: that

text: Trotter-Suzuki

text: methods

text: also

text: improve

text: in

text: accuracy

text: if

text: the

text: Hamiltonian

text: terms

text: have

text: a

text: small

text: commutator,

text: but

text: many

text: other

text: time-simulation

text: methods

text: do

text: not.

text: Consider

text: a

text: Hamiltonian

text: H

text: h

text: where

text: each

text: X

text: represents

text: some

text: set

text: of

text: sites

text: and

text: the

text: sum

text: is

text: X

text: X

text: over

text: all

text: possible

text: subsets

text: of

text: the

text: lattice.

text: h

text: is

text: a

text: Hermitian

text: operator

text: obeying

text: a

text: commutator

text: condition

text: X

text: [h

text: h

text: η

text: h

text: h

text: X

text: Y

text: X

text: Y

text: for

text: all

text: X,

text: Y

text: for

text: some

text: η

text: We

text: will

text: additionally

text: impose

text: some

text: locality

text: assumption

text: on

text: H.

text: A

text: convenient

text: one

text: is

text: exponential

text: decay

text: in

text: the

text: following

text: form.

text: Introduce

text: a

text: metric

text: dist(x,

text: y)

text: between

text: pairs

text: of

text: sites

text: x,

text: y.

text: Assume

text: that

text: there

text: are

text: constants

text: ζ,

text: µ

text: such

text: that

text: for

text: any

text: site

text: x,


text: 30 | (cid:105) | (cid:105) where Hd is the Hadamard gate. For every eigenstate W ν = eiφν ν , the controlled as as | (cid:105) operator V acting on ν introduces a phase kickback φ on the ancilla register b. This phase is φ(cid:126) as ν transformed by the similarity operation − − − eiφ/2e iϕZ/2 Hd e iφZ/2 Hd eiϕZ/2 = eiφ/2e iφPϕ/2, P = cos (ϕ)X + sin (ϕ)Y. (C7) ϕ Thus by multiplying out the single qubit-rotations, (cid:104) | (cid:104) | | (cid:105) | (cid:105) (cid:104) | − − · · · − | (cid:105) ( + b ν as)Vϕ(cid:126)( + b ν as) = + b e(cid:88)iφνPϕN /2e iφνPϕN−1/2 e iφνPϕ1/2 + b (C8) N/2 (cid:104) | | (cid:105) = + (a I + ib Z) cos (kφ ) + i(c X + d Y ) sin (kφ ) + , (cid:88)b k k ν k k ν b k=0 N/2 = a cos (kφ ) + ic sin (kφ ), k ν k ν k=0 { } where the a, b, c, d are real coeﬃcients. ∓ ± → − The desired phase transformation e iφλ e iαtsin(φλ) may then be approximated by choosing { } the coeﬃcients a, c to be the Bessel function coeﬃcients J (αt) of the Jacobi-Anger expansion up k to k = N/2. (cid:32) (cid:33) (cid:32) (cid:33) (cid:88) (cid:88) ∞ ∞ − − e iαtsin(φ) = J (αt) + 2 J (αt) cos (kφ) i 2 J (αt) sin (kφ) (C9) 0 k k k even >0 odd >0 (cid:80) ≤ ∞ | | Note that truncation error of this approximation is (cid:15) 2 J (αt) . In principle, Trunc k=q k { } the angles ϕ(cid:126) that approximate the desired coeﬃcients a, c may be precomputed by a classical − polynomial-time algorithm [23]. This ultimately leads to an approximation of e iαtsin(φ) with error (cid:88) ∞ (cid:107) (cid:104) | (cid:104) | ⊗ | (cid:105) | (cid:105) ⊗ − − (cid:107) ≤ | | ≤ 32(αt)q (cid:15)(cid:3) = ( + G 1 )V ( + G 1 ) e itH 16 J (αt) , q = N/2 + 1. b a s ϕ(cid:126) b a s k 2qq! k=q (C10) ##LTLine##

text: where

text: Hd

text: is

text: the

text: Hadamard

text: gate.

text: For

text: every

text: eigenstate

text: W

text: ν

text: eiφν

text: ν

text: the

text: controlled

text: as

text: as

text: operator

text: V

text: acting

text: on

text: ν

text: introduces

text: a

text: phase

text: kickback

text: φ

text: on

text: the

text: ancilla

text: register

text: b.

text: This

text: phase

text: is

text: as

text: ν

text: transformed

text: by

text: the

text: similarity

text: operation

label: equation

text: Hd

text: e

text: Hd

text: P

text: cos

text: (ϕ)X

text: sin

text: (ϕ)Y.

text: ϕ

text: Thus

text: by

text: multiplying

text: out

text: the

text: single

text: qubit-rotations,

text: b

text: ν

text: b

text: ν

text: as)

text: b

text: e

text: b

text: (a

text: I

text: ib

text: Z)

text: cos

text: (kφ

text: i(c

text: X

text: d

text: Y

text: sin

text: (kφ

text: k

text: k

text: ν

text: k

text: k

text: ν

text: b

text: a

text: cos

text: (kφ

text: ic

text: sin

text: (kφ

text: k

text: ν

text: k

text: ν

text: where

text: the

text: a,

text: b,

text: c,

text: d

text: are

text: real

text: coeﬃcients.

text: The

text: desired

text: phase

text: transformation

text: e

text: iφλ

text: e

text: iαtsin(φλ)

text: may

text: then

text: be

text: approximated

text: by

text: choosing

text: the

text: coeﬃcients

text: a,

text: c

text: to

text: be

text: the

text: Bessel

text: function

text: coeﬃcients

text: J

text: (αt)

text: of

text: the

text: Jacobi-Anger

text: expansion

text: up

text: k

text: to

text: k

text: e

text: iαtsin(φ)

text: J

text: (αt)

text: J

text: (αt)

text: cos

text: (kφ)

text: i

text: J

text: (αt)

text: sin

text: (kφ)

text: k

text: k

text: k

text: even

text: odd

text: Note

text: that

text: truncation

text: error

text: of

text: this

text: approximation

text: is

text: J

text: (αt)

text: In

text: principle,

text: Trunc

text: k=q

text: k

text: the

text: angles

text: that

text: approximate

text: the

text: desired

text: coeﬃcients

text: a,

text: c

text: may

text: be

text: precomputed

text: by

text: a

text: classical

text: polynomial-time

text: algorithm

text: This

text: ultimately

text: leads

text: to

text: an

text: approximation

text: of

text: e

text: iαtsin(φ)

text: with

text: error

text: G

text: )V

text: G

text: e

text: itH

text: J

text: (αt)

text: q

text: b

text: a

text: s

text: b

text: a

text: s

text: k

text: k=q

text: ##LTLine##