text: ties such as spectral properties (e. g. [Batson et al., 2013]). tivity of the network and most properties we consider. The networks of our interest are already sparse in this Our results illuminate which methods are suitable with sense. With the goal of reducing network data size respect to which properties of a network. Additionally, while keeping important properties, our research is re- we take a look at emergent properties by simulating epi- lated to a body of work that considers sampling from net- demic spreading on sparsiﬁed networks in comparison with works (on which [Ahmed et al., 2014] provides an exten- the original network. We show that our Local Degree sive overview). Sampling is concerned with the design of method is best for preserving connectivity and short dis- algorithms that select edges and/or nodes from a network. tances which results in a good preservation of the diameter Here, node and edge sampling methods must be distin- of the network, some centrality measures and the behavior guished: For node sampling, nodes and edges from the of epidemic spreading. Depending on the network, our Lo- original network are discarded, while edge sampling pre- cal Degree method can also preserve clustering coeﬃcients. serves all nodes and reduces the number of edges only. The Considering the preservation of the community structure literature on node sampling is extensive, while pure edge we show that some of the newly introduced variants with sampling and ﬁltering techniques have not been considered local ﬁltering are best for preserving the community struc- as often. A seminal paper [Leskovec and Faloutsos, 2006] ture while the variants without local ﬁltering do not pre- concludes that node sampling techniques are preferable, serve the community structure in our experiments. but considers few edge sampling techniques. The study Furthermore, we have published eﬃcient paral- presented in [Ebbes et al., 2008] looks at how well a sam- lelized implementations and a framework for such ple of 5%-20% of the original network preserves cer- methods as part of the NetworKit open-source tool tain properties, and is mainly focused on node sampling suite [Staudt et al., 2014]. While our study covers var- through graph exploration. It concludes that random ious approaches from the literature, it is by no means walk-based node sampling works best on complex net- exhaustive due to the vast amount of potential sparsiﬁ- works, but does so on the basis of experiments on syn- cation techniques. With future methods in mind, we hope thetic graphs only and compares only with very simple to contribute a framework for their implementation and edge sampling methods. evaluation. Only edge sampling techniques are directly comparable 2 Network Properties to our edge scoring and ﬁltering methods. In this work, we restrict ourselves to reducing the edge set, while keeping all nodes of the original graph. Preserving the nodes allows The structure of a complex network is usually char- us to infer properties of each node of the original graph. acterized in terms of certain key ﬁgures and statis- This is important because in network analysis, the unit of tics [Newman, 2010]. Decomposition of the network into analysis is often the individual node, e. g. when a score cohesive regions is a frequent analysis task: All nodes for each user in an online social network scenario shall be in a connected component are reachable from each other. computed. With respect to the goal of accelerating the A typical pattern in real-world complex networks is the analysis, many relevant graph algorithms scale with m so emergence of a giant connected component which contains reducing m is more relevant. the bigger part of all nodes and is usually accompanied Another related approach is the Multiscale Back- by a large number of very small components. Commu- bone [Serrano et al., 2009], which is applicable on nities are subsets of nodes that are internally dense and weighted graphs only and is therefore not included in our externally sparsely connected. The diameter of a graph study. Instead of applying a global edge weight cutoﬀ for is the maximum length of a shortest path between any edge ﬁltering, which hides important structures at diﬀer- two nodes [Newman, 2010]. The observation that the di- ent scales, this approach aims at preserving them at all ameter of social networks is often surprisingly small is re- scales. ferred to as the small world phenomenon. In case of dis- 1.2 Contribution connected graphs, we consider the diameter of the largest component. Node centrality measures quantify the rela- We contribute the ﬁrst systematic conceptual and ex- tive importance of a node within the network structure. perimental comparison of existing and novel edge scoring We consider any function which assigns to each node an and ﬁltering methods on a diverse set of network proper- attribute value of at least ordinal scale of measurement to ties. Descriptions and literature references for the related be a node centrality measure. The distribution of degrees, methods which we reimplemented are given in Section , the number of connections per node, can be seen as the for some of them we include descriptions of how we par- simplest measure that falls under this deﬁnition. It plays allelized them. In Section we also introduce our Local an important role in characterizing a network: Empirically Degree sparsiﬁcation method and Edge Forest Fire, an observed complex networks tend to show a heavy tailed de- adaption of the existing node sparsiﬁcation technique to gree distribution which follows a power-law with a charac- ∼ − edges. Furthermore, we propose a local ﬁltering step that teristic exponent: p(k) k γ. Such networks have been has been introduced by [Satuluri et al., 2011] for one spe- categorized as scale-free [Barabási and Albert, 1999], re- ciﬁc sparsiﬁcation technique as a generally applicable and ferring to the fact that it is not possible to pick a node of beneﬁcial post-processing step for preserving the connec- typical degree. Clustering coeﬃcients are key ﬁgures for 2

text: ties

text: such

text: as

text: spectral

text: properties

text: (e.

text: g.

text: [Batson

text: et

text: al.,

text: tivity

text: of

text: the

text: network

text: and

text: most

text: properties

text: we

text: consider.

text: The

text: networks

text: of

text: our

text: interest

text: are

text: already

text: sparse

text: in

text: this

text: Our

text: results

text: illuminate

text: which

text: methods

text: are

text: suitable

text: with

text: sense.

text: With

text: the

text: goal

text: of

text: reducing

text: network

text: data

text: size

text: respect

text: to

text: which

text: properties

text: of

text: a

text: network.

text: Additionally,

text: while

text: keeping

text: important

text: properties,

text: our

text: research

text: is

text: re-

text: we

text: take

text: a

text: look

text: at

text: emergent

text: properties

text: by

text: simulating

text: epi-

text: lated

text: to

text: a

text: body

text: of

text: work

text: that

text: considers

text: sampling

text: from

text: net-

text: demic

text: spreading

text: on

text: sparsiﬁed

text: networks

text: in

text: comparison

text: with

text: works

text: (on

text: which

text: [Ahmed

text: et

text: al.,

text: provides

text: an

text: exten-

text: the

text: original

text: network.

text: We

text: show

text: that

text: our

text: Local

text: Degree

text: sive

text: overview).

text: Sampling

text: is

text: concerned

text: with

text: the

text: design

text: of

text: method

text: is

text: best

text: for

text: preserving

text: connectivity

text: and

text: short

text: dis-

text: algorithms

text: that

text: select

text: edges

text: and/or

text: nodes

text: from

text: a

text: network.

text: tances

text: which

text: results

text: in

text: a

text: good

text: preservation

text: of

text: the

text: diameter

text: Here,

text: node

text: and

text: edge

text: sampling

text: methods

text: must

text: be

text: distin-

text: of

text: the

text: network,

text: some

text: centrality

text: measures

text: and

text: the

text: behavior

text: guished:

text: For

text: node

text: sampling,

text: nodes

text: and

text: edges

text: from

text: the

text: of

text: epidemic

text: spreading.

text: Depending

text: on

text: the

text: network,

text: our

text: Lo-

text: original

text: network

text: are

text: discarded,

text: while

text: edge

text: sampling

text: pre-

text: cal

text: Degree

text: method

text: can

text: also

text: preserve

text: clustering

text: coeﬃcients.

text: serves

text: all

text: nodes

text: and

text: reduces

text: the

text: number

text: of

text: edges

text: only.

text: The

text: Considering

text: the

text: preservation

text: of

text: the

text: community

text: structure

text: literature

text: on

text: node

text: sampling

text: is

text: extensive,

text: while

text: pure

text: edge

text: we

text: show

text: that

text: some

text: of

text: the

text: newly

text: introduced

text: variants

text: with

text: sampling

text: and

text: ﬁltering

text: techniques

text: have

text: not

text: been

text: considered

text: local

text: ﬁltering

text: are

text: best

text: for

text: preserving

text: the

text: community

text: struc-

text: as

text: often.

text: A

text: seminal

text: paper

text: [Leskovec

text: and

text: Faloutsos,

text: ture

text: while

text: the

text: variants

text: without

text: local

text: ﬁltering

text: do

text: not

text: pre-

text: concludes

text: that

text: node

text: sampling

text: techniques

text: are

text: preferable,

text: serve

text: the

text: community

text: structure

text: in

text: our

text: experiments.

text: but

text: considers

text: few

text: edge

text: sampling

text: techniques.

text: The

text: study

text: Furthermore,

text: we

text: have

text: published

text: eﬃcient

text: paral-

text: presented

text: in

text: [Ebbes

text: et

text: al.,

text: looks

text: at

text: how

text: well

text: a

text: sam-

text: lelized

text: implementations

text: and

text: a

text: framework

text: for

text: such

text: ple

text: of

text: of

text: the

text: original

text: network

text: preserves

text: cer-

text: methods

text: as

text: part

text: of

text: the

text: NetworKit

text: open-source

text: tool

text: tain

text: properties,

text: and

text: is

text: mainly

text: focused

text: on

text: node

text: sampling

text: suite

text: [Staudt

text: et

text: al.,

text: While

text: our

text: study

text: covers

text: var-

text: through

text: graph

text: exploration.

text: It

text: concludes

text: that

text: random

text: ious

text: approaches

text: from

text: the

text: literature,

text: it

text: is

text: by

text: no

text: means

text: walk-based

text: node

text: sampling

text: works

text: best

text: on

text: complex

text: net-

text: exhaustive

text: due

text: to

text: the

text: vast

text: amount

text: of

text: potential

text: sparsiﬁ-

text: works,

text: but

text: does

text: so

text: on

text: the

text: basis

text: of

text: experiments

text: on

text: syn-

text: cation

text: techniques.

text: With

text: future

text: methods

text: in

text: mind,

text: we

text: hope

text: thetic

text: graphs

text: only

text: and

text: compares

text: only

text: with

text: very

text: simple

text: to

text: contribute

text: a

text: framework

text: for

text: their

text: implementation

text: and

text: edge

text: sampling

text: methods.

text: evaluation.

text: Only

text: edge

text: sampling

text: techniques

text: are

text: directly

text: comparable

text: Network

text: Properties

text: to

text: our

text: edge

text: scoring

text: and

text: ﬁltering

text: methods.

text: In

text: this

text: work,

text: we

text: restrict

text: ourselves

text: to

text: reducing

text: the

text: edge

text: set,

text: while

text: keeping

text: all

text: nodes

text: of

text: the

text: original

text: graph.

text: Preserving

text: the

text: nodes

text: allows

text: The

text: structure

text: of

text: a

text: complex

text: network

text: is

text: usually

text: char-

text: us

text: to

text: infer

text: properties

text: of

text: each

text: node

text: of

text: the

text: original

text: graph.

text: acterized

text: in

text: terms

text: of

text: certain

text: key

text: ﬁgures

text: and

text: statis-

text: This

text: is

text: important

text: because

text: in

text: network

text: analysis,

text: the

text: unit

text: of

text: tics

text: [Newman,

text: Decomposition

text: of

text: the

text: network

text: into

text: analysis

text: is

text: often

text: the

text: individual

text: node,

text: e.

text: g.

text: when

text: a

text: score

text: cohesive

text: regions

text: is

text: a

text: frequent

text: analysis

text: task:

text: All

text: nodes

text: for

text: each

text: user

text: in

text: an

text: online

text: social

text: network

text: scenario

text: shall

text: be

text: in

text: a

text: connected

text: component

text: are

text: reachable

text: from

text: each

text: other.

text: computed.

text: With

text: respect

text: to

text: the

text: goal

text: of

text: accelerating

text: the

text: A

text: typical

text: pattern

text: in

text: real-world

text: complex

text: networks

text: is

text: the

text: analysis,

text: many

text: relevant

text: graph

text: algorithms

text: scale

text: with

text: m

text: so

text: emergence

text: of

text: a

text: giant

text: connected

text: component

text: which

text: contains

text: reducing

text: m

text: is

text: more

text: relevant.

text: the

text: bigger

text: part

text: of

text: all

text: nodes

text: and

text: is

text: usually

text: accompanied

text: Another

text: related

text: approach

text: is

text: the

text: Multiscale

text: Back-

text: by

text: a

text: large

text: number

text: of

text: very

text: small

text: components.

text: Commu-

text: bone

text: [Serrano

text: et

text: al.,

text: which

text: is

text: applicable

text: on

text: nities

text: are

text: subsets

text: of

text: nodes

text: that

text: are

text: internally

text: dense

text: and

text: weighted

text: graphs

text: only

text: and

text: is

text: therefore

text: not

text: included

text: in

text: our

text: externally

text: sparsely

text: connected.

text: The

text: diameter

text: of

text: a

text: graph

text: study.

text: Instead

text: of

text: applying

text: a

text: global

text: edge

text: weight

text: cutoﬀ

text: for

text: is

text: the

text: maximum

text: length

text: of

text: a

text: shortest

text: path

text: between

text: any

text: edge

text: ﬁltering,

text: which

text: hides

text: important

text: structures

text: at

text: diﬀer-

text: two

text: nodes

text: [Newman,

text: The

text: observation

text: that

text: the

text: di-

text: ent

text: scales,

text: this

text: approach

text: aims

text: at

text: preserving

text: them

text: at

text: all

text: ameter

text: of

text: social

text: networks

text: is

text: often

text: surprisingly

text: small

text: is

text: re-

text: scales.

text: ferred

text: to

text: as

text: the

text: small

text: world

text: phenomenon.

text: In

text: case

text: of

text: dis-

text: Contribution

text: connected

text: graphs,

text: we

text: consider

text: the

text: diameter

text: of

text: the

text: largest

text: component.

text: Node

text: centrality

text: measures

text: quantify

text: the

text: rela-

text: We

text: contribute

text: the

text: ﬁrst

text: systematic

text: conceptual

text: and

text: ex-

text: tive

text: importance

text: of

text: a

text: node

text: within

text: the

text: network

text: structure.

text: perimental

text: comparison

text: of

text: existing

text: and

text: novel

text: edge

text: scoring

text: We

text: consider

text: any

text: function

text: which

text: assigns

text: to

text: each

text: node

text: an

text: and

text: ﬁltering

text: methods

text: on

text: a

text: diverse

text: set

text: of

text: network

text: proper-

text: attribute

text: value

text: of

text: at

text: least

text: ordinal

text: scale

text: of

text: measurement

text: to

text: ties.

text: Descriptions

text: and

text: literature

text: references

text: for

text: the

text: related

text: be

text: a

text: node

text: centrality

text: measure.

text: The

text: distribution

text: of

text: degrees,

text: methods

text: which

text: we

text: reimplemented

text: are

text: given

text: in

text: Section

text: the

text: number

text: of

text: connections

text: per

text: node,

text: can

text: be

text: seen

text: as

text: the

text: for

text: some

text: of

text: them

text: we

text: include

text: descriptions

text: of

text: how

text: we

text: par-

text: simplest

text: measure

text: that

text: falls

text: under

text: this

text: deﬁnition.

text: It

text: plays

text: allelized

text: them.

text: In

text: Section

text: we

text: also

text: introduce

text: our

text: Local

text: an

text: important

text: role

text: in

text: characterizing

text: a

text: network:

text: Empirically

text: Degree

text: sparsiﬁcation

text: method

text: and

text: Edge

text: Forest

text: Fire,

text: an

text: observed

text: complex

text: networks

text: tend

text: to

text: show

text: a

text: heavy

text: tailed

text: de-

text: adaption

text: of

text: the

text: existing

text: node

text: sparsiﬁcation

text: technique

text: to

text: gree

text: distribution

text: which

text: follows

text: a

text: power-law

text: with

text: a

text: charac-

text: edges.

text: Furthermore,

text: we

text: propose

text: a

text: local

text: ﬁltering

text: step

text: that

text: teristic

text: exponent:

text: p(k)

text: k

text: γ.

text: Such

text: networks

text: have

text: been

text: has

text: been

text: introduced

text: by

text: [Satuluri

text: et

text: al.,

text: for

text: one

text: spe-

text: categorized

text: as

text: scale-free

text: [Barabási

text: and

text: Albert,

text: re-

text: ciﬁc

text: sparsiﬁcation

text: technique

text: as

text: a

text: generally

text: applicable

text: and

text: ferring

text: to

text: the

text: fact

text: that

text: it

text: is

text: not

text: possible

text: to

text: pick

text: a

text: node

text: of

text: beneﬁcial

text: post-processing

text: step

text: for

text: preserving

text: the

text: connec-

text: typical

text: degree.

text: Clustering

text: coeﬃcients

text: are

text: key

text: ﬁgures

text: for


text: [Ebbes et al., 2008] Ebbes, P., Huang, Z., Rangaswamy, on Advances in Social Networks Analysis and Mining, A., Thadakamalla, H. P., and Unit, O. R. G. B. (2008). ASONAM 2015, Paris, France, August 25 - 28, 2015, Sampling large-scale social networks: Insights from sim- pages 448–454. ACM. ulated networks. In 18th Annual Workshop on Informa- tion Technologies and Systems, Paris, France. Citeseer. [Newman, 2010] Newman, M. (2010). Networks: an in- troduction. Oxford University Press. [Fortunato and Barthelemy, 2007] Fortunato, S. and Barthelemy, M. (2007). Resolution limit in community [Nick et al., 2013] Nick, B., Lee, C., Cunningham, P., and detection. Proceedings of the National Academy of Brandes, U. (2013). Simmelian backbones: Amplifying Sciences, 104(1):36–41. hidden homophily in facebook networks. In Proceed- ings of the 2013 IEEE/ACM International Conference [Fortunato et al., 2008] Fortunato, S., Boguñá, M., Flam- on Advances in Social Networks Analysis and Mining, mini, A., and Menczer, F. (2008). Approximating pager- ASONAM ’13, pages 525–532, New York, NY, USA. ank from in-degree. In Algorithms and Models for the ACM. Web-Graph, pages 59–71. Springer. [Geisberger et al., 2008] Geisberger, R., Sanders, P., and [Nocaj et al., 2014] Nocaj, A., Ortmann, M., and Bran- Schultes, D. (2008). Better approximation of between- des, U. (2014). Untangling hairballs - from 3 to 14 ness centrality. In ALENEX, pages 90–100. SIAM. degrees of separation. In Duncan, C. A. and Symvonis, A., editors, Graph Drawing - 22nd International Sympo- [Gleiser and Danon, 2003] Gleiser, P. M. and Danon, L. sium, GD 2014, Würzburg, Germany, September 24-26, (2003). Community structure in jazz. Advances in Com- 2014, Revised Selected Papers, volume 8871 of Lecture plex Systems, 6(4):565–574. Notes in Computer Science, pages 101–112. Springer. [Hubert and Arabie, 1985] Hubert, L. and Arabie, P. [Ortmann and Brandes, 2014] Ortmann, M. and Bran- (1985). Comparing partitions. Journal of Classiﬁca- des, U. (2014). Triangle listing algorithms: Back from tion, 2(1):193–218. the diversion. In McGeoch, C. C. and Meyer, U., edi- tors, 2014 Proceedings of the Sixteenth Workshop on Al- [Keeling and Rohani, 2008] Keeling, M. and Rohani, P. gorithm Engineering and Experiments, ALENEX 2014, (2008). Modeling infectious diseases in humans and an- Portland, Oregon, USA, January 5, 2014, pages 1–8. imals. Princeton University Press. SIAM. [Lancichinetti and Fortunato, 2009a] Lancichinetti, A. and Fortunato, S. (2009a). Benchmarks for testing [Page et al., 1999] Page, L., Brin, S., Motwani, R., and community detection algorithms on directed and Winograd, T. (1999). The pagerank citation ranking: weighted graphs with overlapping communities. Phys. Bringing order to the web. Technical Report 1999-66, Rev. E, 80(1):016118. Stanford InfoLab. Previous number = SIDL-WP-1999- 0120. [Lancichinetti and Fortunato, 2009b] Lancichinetti, A. and Fortunato, S. (2009b). Community detection [Rosvall et al., 2009] Rosvall, M., Axelsson, D., and algorithms: A comparative analysis. Phys. Rev. E, Bergstrom, C. T. (2009). The map equation. The Eu- 80:056117. ropean Physical Journal Special Topics, 178(1):13–23. [Leskovec and Faloutsos, 2006] Leskovec, J. and Falout- [Saha et al., 2013] Saha, T., Rangwala, H., and Domeni- sos, C. (2006). Sampling from large graphs. In Proceed- coni, C. (2013). Sparsiﬁcation and sampling of net- ings of the 12th ACM SIGKDD International Confer- works for collective classiﬁcation. In Social Comput- ence on Knowledge Discovery and Data Mining, KDD ing, Behavioral-Cultural Modeling and Prediction, pages ’06, pages 631–636, New York, NY, USA. ACM. 293–302. Springer. [Leskovec and Mcauley, 2012] Leskovec, J. and Mcauley, [Salathé et al., 2010] Salathé, M., Kazandjieva, M., Lee, J. J. (2012). Learning to discover social circles in ego J. W., Levis, P., Feldman, M. W., and Jones, J. H. networks. In Pereira, F., Burges, C., Bottou, L., and (2010). A high-resolution human contact network for Weinberger, K., editors, Advances in Neural Informa- infectious disease transmission. Proceedings of the Na- tion Processing Systems 25, pages 539–547. Curran As- tional Academy of Sciences, 107(51):22020–22025. sociates, Inc. [Lindner et al., 2015] Lindner, G., Staudt, C. L., [Satuluri et al., 2011] Satuluri, V., Parthasarathy, S., and Hamann, M., Meyerhenke, H., and Wagner, D. (2015). Ruan, Y. (2011). Local graph sparsiﬁcation for scalable Structure-preserving sparsiﬁcation of social networks. clustering. In Proceedings of the 2011 ACM SIGMOD In Pei, J., Silvestri, F., and Tang, J., editors, Proceed- International Conference on Management of Data, SIG- ings of the 2015 IEEE/ACM International Conference MOD ’11, pages 721–732, New York, NY, USA. ACM. 18

text: [Ebbes

label: reference

text: et

text: al.,

text: Ebbes,

text: P.,

text: Huang,

text: Z.,

text: Rangaswamy,

text: on

text: Advances

text: in

text: Social

text: Networks

text: Analysis

text: and

text: Mining,

text: A.,

text: Thadakamalla,

text: H.

text: P.,

text: and

text: Unit,

text: O.

text: R.

text: G.

text: B.

text: ASONAM

text: Paris,

text: France,

text: August

text: Sampling

text: large-scale

text: social

text: networks:

text: Insights

text: from

text: sim-

text: pages

text: ACM.

text: ulated

text: networks.

text: In

text: Annual

text: Workshop

text: on

text: Informa-

text: tion

text: Technologies

text: and

text: Systems,

text: Paris,

text: France.

text: Citeseer.

text: [Newman,

text: Newman,

text: M.

text: Networks:

text: an

text: in-

text: troduction.

text: Oxford

text: University

text: Press.

text: [Fortunato

text: and

text: Barthelemy,

text: Fortunato,

text: S.

text: and

text: Barthelemy,

text: M.

text: Resolution

text: limit

text: in

text: community

text: [Nick

text: et

text: al.,

text: Nick,

text: B.,

text: Lee,

text: C.,

text: Cunningham,

text: P.,

text: and

text: detection.

text: Proceedings

text: of

text: the

text: National

text: Academy

text: of

text: Brandes,

text: U.

text: Simmelian

text: backbones:

text: Amplifying

text: Sciences,

text: hidden

text: homophily

text: in

text: facebook

text: networks.

text: In

text: Proceed-

text: ings

text: of

text: the

text: IEEE/ACM

text: International

text: Conference

text: [Fortunato

text: et

text: al.,

text: Fortunato,

text: S.,

text: Boguñá,

text: M.,

text: Flam-

text: on

text: Advances

text: in

text: Social

text: Networks

text: Analysis

text: and

text: Mining,

text: mini,

text: A.,

text: and

text: Menczer,

text: F.

text: Approximating

text: pager-

text: ASONAM

text: pages

text: New

text: York,

text: NY,

text: USA.

text: ank

text: from

text: in-degree.

text: In

text: Algorithms

text: and

text: Models

text: for

text: the

text: ACM.

text: Web-Graph,

text: pages

text: Springer.

text: [Geisberger

text: et

text: al.,

text: Geisberger,

text: R.,

text: Sanders,

text: P.,

text: and

text: [Nocaj

text: et

text: al.,

text: Nocaj,

text: A.,

text: Ortmann,

text: M.,

text: and

text: Bran-

text: Schultes,

text: D.

text: Better

text: approximation

text: of

text: between-

text: des,

text: U.

text: Untangling

text: hairballs

text: from

text: to

text: ness

text: centrality.

text: In

text: ALENEX,

text: pages

text: SIAM.

text: degrees

text: of

text: separation.

text: In

text: Duncan,

text: C.

text: A.

text: and

text: Symvonis,

text: A.,

text: editors,

text: Graph

text: Drawing

text: International

text: Sympo-

text: [Gleiser

text: and

text: Danon,

text: Gleiser,

text: P.

text: M.

text: and

text: Danon,

text: L.

text: sium,

text: GD

text: Würzburg,

text: Germany,

text: September

text: Community

text: structure

text: in

text: jazz.

text: Advances

text: in

text: Com-

text: Revised

text: Selected

text: Papers,

text: volume

text: of

text: Lecture

text: plex

text: Systems,

text: Notes

text: in

text: Computer

text: Science,

text: pages

text: Springer.

text: [Hubert

text: and

text: Arabie,

text: Hubert,

text: L.

text: and

text: Arabie,

text: P.

text: [Ortmann

text: and

text: Brandes,

text: Ortmann,

text: M.

text: and

text: Bran-

text: Comparing

text: partitions.

text: Journal

text: of

text: Classiﬁca-

text: des,

text: U.

text: Triangle

text: listing

text: algorithms:

text: Back

text: from

text: tion,

text: the

text: diversion.

text: In

text: McGeoch,

text: C.

text: C.

text: and

text: Meyer,

text: U.,

text: edi-

text: tors,

text: Proceedings

text: of

text: the

text: Sixteenth

text: Workshop

text: on

text: Al-

text: [Keeling

text: and

text: Rohani,

text: Keeling,

text: M.

text: and

text: Rohani,

text: P.

text: gorithm

text: Engineering

text: and

text: Experiments,

text: ALENEX

text: Modeling

text: infectious

text: diseases

text: in

text: humans

text: and

text: an-

text: Portland,

text: Oregon,

text: USA,

text: January

text: pages

text: imals.

text: Princeton

text: University

text: Press.

text: SIAM.

text: [Lancichinetti

text: and

text: Fortunato,

text: Lancichinetti,

text: A.

text: and

text: Fortunato,

text: S.

text: Benchmarks

text: for

text: testing

text: [Page

text: et

text: al.,

text: Page,

text: L.,

text: Brin,

text: S.,

text: Motwani,

text: R.,

text: and

text: community

text: detection

text: algorithms

text: on

text: directed

text: and

text: Winograd,

text: T.

text: The

text: pagerank

text: citation

text: ranking:

text: weighted

text: graphs

text: with

text: overlapping

text: communities.

text: Phys.

text: Bringing

text: order

text: to

text: the

text: web.

text: Technical

text: Report

text: Rev.

text: E,

text: Stanford

text: InfoLab.

text: Previous

text: number

text: [Lancichinetti

text: and

text: Fortunato,

text: Lancichinetti,

text: A.

text: and

text: Fortunato,

text: S.

text: Community

text: detection

text: [Rosvall

text: et

text: al.,

text: Rosvall,

text: M.,

text: Axelsson,

text: D.,

text: and

text: algorithms:

text: A

text: comparative

text: analysis.

text: Phys.

text: Rev.

text: E,

text: Bergstrom,

text: C.

text: T.

text: The

text: map

text: equation.

text: The

text: Eu-

text: ropean

text: Physical

text: Journal

text: Special

text: Topics,

text: [Leskovec

text: and

text: Faloutsos,

text: Leskovec,

text: J.

text: and

text: Falout-

text: [Saha

text: et

text: al.,

text: Saha,

text: T.,

text: Rangwala,

text: H.,

text: and

text: Domeni-

text: sos,

text: C.

text: Sampling

text: from

text: large

text: graphs.

text: In

text: Proceed-

text: coni,

text: C.

text: Sparsiﬁcation

text: and

text: sampling

text: of

text: net-

text: ings

text: of

text: the

text: ACM

text: SIGKDD

text: International

text: Confer-

text: works

text: for

text: collective

text: classiﬁcation.

text: In

text: Social

text: Comput-

text: ence

text: on

text: Knowledge

text: Discovery

text: and

text: Data

text: Mining,

text: KDD

text: ing,

text: Behavioral-Cultural

text: Modeling

text: and

text: Prediction,

text: pages

text: pages

text: New

text: York,

text: NY,

text: USA.

text: ACM.

text: Springer.

text: [Leskovec

text: and

text: Mcauley,

text: Leskovec,

text: J.

text: and

text: Mcauley,

text: [Salathé

text: et

text: al.,

text: Salathé,

text: M.,

text: Kazandjieva,

text: M.,

text: Lee,

text: J.

text: J.

text: Learning

text: to

text: discover

text: social

text: circles

text: in

text: ego

text: J.

text: W.,

text: Levis,

text: P.,

text: Feldman,

text: M.

text: W.,

text: and

text: Jones,

text: J.

text: H.

text: networks.

text: In

text: Pereira,

text: F.,

text: Burges,

text: C.,

text: Bottou,

text: L.,

text: and

text: A

text: high-resolution

text: human

text: contact

text: network

text: for

text: Weinberger,

text: K.,

text: editors,

text: Advances

text: in

text: Neural

text: Informa-

text: infectious

text: disease

text: transmission.

text: Proceedings

text: of

text: the

text: Na-

text: tion

text: Processing

text: Systems

text: pages

text: Curran

text: As-

text: tional

text: Academy

text: of

text: Sciences,

text: sociates,

text: Inc.

text: [Lindner

text: et

text: al.,

text: Lindner,

text: G.,

text: Staudt,

text: C.

text: L.,

text: [Satuluri

text: et

text: al.,

text: Satuluri,

text: V.,

text: Parthasarathy,

text: S.,

text: and

text: Hamann,

text: M.,

text: Meyerhenke,

text: H.,

text: and

text: Wagner,

text: D.

text: Ruan,

text: Y.

text: Local

text: graph

text: sparsiﬁcation

text: for

text: scalable

text: Structure-preserving

text: sparsiﬁcation

text: of

text: social

text: networks.

text: clustering.

text: In

text: Proceedings

text: of

text: the

text: ACM

text: SIGMOD

text: In

text: Pei,

text: J.,

text: Silvestri,

text: F.,

text: and

text: Tang,

text: J.,

text: editors,

text: Proceed-

text: International

text: Conference

text: on

text: Management

text: of

text: Data,

text: SIG-

text: ings

text: of

text: the

text: IEEE/ACM

text: International

text: Conference

text: MOD

text: pages

text: New

text: York,

text: NY,

text: USA.

text: ACM.


text: Proc. of the 18th Int. Conference on Digital Audio Effects (DAFx-15), Trondheim, Norway, Nov 30 - Dec 3, 2015 (cid:98) − | | for β 1 of the order of a few semitones. h (ω). We show in this section that, for θ˙(t) and η˙(t) reasonably The wavelet ψ is now deﬁned as a product between wavelets regular over the support of ﬁrst-order wavelets, the local maxima λ2 in time, log-frequency, and octave index: of x are clustered on a plane in the (α, β, γ) space of scattering 2 coefﬁcients. This plane satisﬁes the Cartesian equation × × (cid:98) (cid:99) ψλ2(t, log λ1) = ψα(t) ψβ(log λ1) ψγ( log λ1 ). (9) θ¨(t) η¨(t) α + β + γ = 0. (13) θ˙(t) η˙(t) In the previous deﬁnition, ψ operates over the rectilinear log- β frequency variable log λ , not over the circular chroma variable In a polyphonic context, this result means that harmonic sounds { } 1 χ = log λ . This is to avoid artifacts at octave boundaries. overlapping both in time and frequency could be resolved accord- 1 1 Examples of the "spiral wavelet" ψ are shown in Figure 2 for ing to their respective source-ﬁlter velocities. λ2 different values of α, β and γ. To ensure invertibility and energy Our proof is driven by harmonicity and spectral smoothness conservation, the quefrencies β and γ must take negative values, properties — Equation (18) — and derives Equation (13) from the including zero. We adopt the shorthand notation computation of wavelet ridges on the pitch spiral [9]. 3.2. Source-ﬁlter factorization in the scalogram log λ2 = (log α, log |β|, sign β, log |γ|, sign γ) (10) Given λ1 near the pth partial pθ˙(t) where p ∈ N, we linearize θ(t) and η(t) over the support of the ﬁrst-order wavelet ψ (t). λ1 We work under the following assumptions: to specify their indexing. In the special case β = 0, ψβ is (a) Q large enough to discriminate the pth partial: Q > 2p, no longer a wavelet but a low-pass ﬁlter whose support covers one (cid:107) (cid:107) (cid:28) octa|ve|. By−c∞onvention, the corresponding log-fr(cid:98)equency index is (b) slowly varying source: θ¨/θ˙ ∞ λ1/Q, lcoogveβrs s=ix octa.veTsh.eSsianmceeirtsemFoarukriaeprptrlaienssftoorψmγψfor γis=cen0t,ewrehdicaht (c) slowly varying ﬁlter: (cid:107)η¨/η˙(cid:107)∞ (cid:28) λ1/Q, and λ2 (α, β, γ), the spiral wavelet ψ has a pitch chroma velocity of (d) spectral smoothness: α/β and a pitch height velocityλo2f α/γ, both measured in octaves (cid:107)d(log |hˆ|)/dω(cid:107)∞ × (cid:107)1/η˙(cid:107)∞ (cid:28) Q/λ . per second. 1 We write j∗1 to denote convolutions across neighboring oc- According to (a), partials p(cid:48) (cid:54)= p have a negligible contribution to taves. The deﬁnition for x is comparable to Equations (4) and the scalogram of the source at the log-frequency log λ1. For lack 2 of any interference, this scalogram is constant through time, and (7): we may drop the dependency in t: (cid:98) x2(t, log λ1, log λ2) = |x1 t,χ∗1,j1 ψλ2| (11) |e ∗t ψλ1| ≈ |ψλ1(p)|. (14) = |x ∗t ψ χ∗1 ψ j∗1 ψ |. 1 α β γ According to (b), the scalogram of the warped source e (t) θ Rolling up pitches into a spiral is a well-established idea in can be replaced by the scalogram of the original source translated music, if only because of circularity of musical pitch classes. It has along the log-frequency axis at the velocity log θ˙(t): been studied by Shepard [5], Risset [6], and Deutsch [7] to build (cid:98) paradoxes in perception of pitch, and is corroborated by functional imaging of the auditory cortex (see Warren [8]). |e ∗t ψ |(t) = |e ∗t ψ |(θ(t)) ≈ |ψ (pθ˙(t))|. (15) 3. DEFORMATIONS OF THE SOURCE-FILTER MODEL θ λ1 λ1 λ1 A classical model for voiced speech production consists in the convolution of a harmonic glottal source e(t) with a vocal tract According to (c), we linearize η(t) over the support of ψλ1(t). ﬁlter h(t). Introducing independent deformations to both com- According to (d), we approximate hˆ(ω) by a constant over the ponents brings realistic variability to pitch and spectral envelope. frequential support of the wavelet and factorize the ﬁltering as a (cid:18) (cid:19) (cid:18) (cid:19) This section studies the decomposition of the deformed source- product: ﬁlter model in th(cid:80)e spiral scattering transform. 3.1. Overview ∗ ≈ λ × η(t) (h ψ ) (t) hˆ 1 ψ . (16) Let e(t) = δ(t − n) be a harmonic signal and t (cid:55)→ θ(t) η λ1 η˙(t) λ1 η˙(t) n ◦ a time warp function. We deﬁne a warped source as e (t) = (e θ (cid:55)→ By plugging Equation (15) into Equation (16), the scalogram θ)(t). Similarly, we compose a ﬁlter h(t) and a warp t η(t) to ◦ of the deformable source-ﬁlter model appears as a separable prod- deﬁne h (t) = (h η)(t). The warped source-ﬁlter model is the η uct: signal (cid:12) (cid:18) (cid:19)(cid:12) (cid:12) (cid:12) (cid:98) (cid:12) (cid:12) x (t) = (e ∗t h )(t) (12) (cid:12) (cid:12) θ,η θ η |x ∗t ψ |(t) = |ψ (pθ˙(t))| × hˆ λ1 . (17) θ,η λ1 λ1 η˙(t) Observe that θ˙(t) induces a change of fundamental frequency, whereas η˙(t) accounts for a local dilation of the spectral envelope DAFX-3 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Proc.

label: paragraph

text: of

text: the

text: Int.

text: Conference

text: on

text: Digital

text: Audio

text: Effects

text: Trondheim,

text: Norway,

text: Nov

text: Dec

text: for

text: β

text: of

text: the

text: order

text: of

text: a

text: few

text: semitones.

text: h

text: (ω).

text: We

text: show

text: in

text: this

text: section

text: that,

text: for

text: θ˙(t)

text: and

text: η˙(t)

text: reasonably

text: The

text: wavelet

text: ψ

text: is

text: now

text: deﬁned

text: as

text: a

text: product

text: between

text: wavelets

text: regular

text: over

text: the

text: support

text: of

text: ﬁrst-order

text: wavelets,

text: the

text: local

text: maxima

text: λ2

text: in

text: time,

text: log-frequency,

text: and

text: octave

text: index:

text: of

text: x

text: are

text: clustered

text: on

text: a

text: plane

text: in

text: the

text: (α,

text: β,

text: γ)

text: space

text: of

text: scattering

text: coefﬁcients.

text: This

text: plane

text: satisﬁes

text: the

text: Cartesian

text: equation

label: equation

text: log

text: ψα(t)

text: ψβ(log

text: ψγ(

text: log

text: λ1

text: θ¨(t)

text: η¨(t)

text: α

text: β

text: γ

text: θ˙(t)

text: η˙(t)

text: In

text: the

text: previous

text: deﬁnition,

text: ψ

text: operates

text: over

text: the

text: rectilinear

text: log-

text: β

text: frequency

text: variable

text: log

text: λ

text: not

text: over

text: the

text: circular

text: chroma

text: variable

text: In

text: a

text: polyphonic

text: context,

text: this

text: result

text: means

text: that

text: harmonic

text: sounds

text: χ

text: log

text: λ

text: This

text: is

text: to

text: avoid

text: artifacts

text: at

text: octave

text: boundaries.

text: overlapping

text: both

text: in

text: time

text: and

text: frequency

text: could

text: be

text: resolved

text: accord-

text: Examples

text: of

text: the

text: "spiral

text: wavelet"

text: ψ

text: are

text: shown

text: in

text: Figure

text: for

text: ing

text: to

text: their

text: respective

text: source-ﬁlter

text: velocities.

text: λ2

text: different

text: values

text: of

text: α,

text: β

text: and

text: γ.

text: To

text: ensure

text: invertibility

text: and

text: energy

text: Our

text: proof

text: is

text: driven

text: by

text: harmonicity

text: and

text: spectral

text: smoothness

text: conservation,

text: the

text: quefrencies

text: β

text: and

text: γ

text: must

text: take

text: negative

text: values,

text: properties

text: Equation

text: and

text: derives

text: Equation

text: from

text: the

text: including

text: zero.

text: We

text: adopt

text: the

text: shorthand

text: notation

text: computation

text: of

text: wavelet

text: ridges

text: on

text: the

text: pitch

text: spiral

text: Source-ﬁlter

text: factorization

text: in

text: the

text: scalogram

text: log

text: λ2

text: (log

text: α,

text: log

text: |β|,

text: sign

text: β,

text: log

text: |γ|,

text: sign

text: γ)

text: Given

text: λ1

text: near

text: the

text: pth

text: partial

text: pθ˙(t)

text: where

text: p

text: N,

text: we

text: linearize

text: θ(t)

text: and

text: η(t)

text: over

text: the

text: support

text: of

text: the

text: ﬁrst-order

text: wavelet

text: ψ

text: (t).

text: λ1

text: We

text: work

text: under

text: the

text: following

text: assumptions:

text: to

text: specify

text: their

text: indexing.

text: In

text: the

text: special

text: case

text: β

text: ψβ

text: is

text: (a)

text: Q

text: large

text: enough

text: to

text: discriminate

text: the

text: pth

text: partial:

text: Q

text: no

text: longer

text: a

text: wavelet

text: but

text: a

text: low-pass

text: ﬁlter

text: whose

text: support

text: covers

text: one

text: octa|ve|.

text: By−c∞onvention,

text: the

text: corresponding

text: index

text: is

text: (b)

text: slowly

text: varying

text: source:

text: θ¨/θ˙

text: lcoogveβrs

text: s=ix

text: (c)

text: slowly

text: varying

text: ﬁlter:

text: and

text: λ2

text: (α,

text: β,

text: γ),

text: the

text: spiral

text: wavelet

text: ψ

text: has

text: a

text: pitch

text: chroma

text: velocity

text: of

text: (d)

text: spectral

text: smoothness:

text: α/β

text: and

text: a

text: pitch

text: height

text: α/γ,

text: both

text: measured

text: in

text: octaves

text: Q/λ

text: per

text: second.

text: We

text: write

text: to

text: denote

text: convolutions

text: across

text: neighboring

text: oc-

text: According

text: to

text: (a),

text: partials

text: p

text: have

text: a

text: negligible

text: contribution

text: to

text: taves.

text: The

text: deﬁnition

text: for

text: x

text: is

text: comparable

text: to

text: Equations

text: and

text: the

text: scalogram

text: of

text: the

text: source

text: at

text: the

text: log-frequency

text: log

text: For

text: lack

text: of

text: any

text: interference,

text: this

text: scalogram

text: is

text: constant

text: through

text: time,

text: and

text: we

text: may

text: drop

text: the

text: dependency

text: in

text: t:

text: log

text: log

text: ψλ2|

text: |e

text: ∗t

text: ψλ1|

text: |x

text: ∗t

text: ψ

text: χ∗1

text: ψ

text: ψ

text: α

text: β

text: γ

text: According

text: to

text: (b),

text: the

text: scalogram

text: of

text: the

text: warped

text: source

text: e

text: (t)

text: θ

text: Rolling

text: up

text: pitches

text: into

text: a

text: spiral

text: is

text: a

text: well-established

text: idea

text: in

text: can

text: be

text: replaced

text: by

text: the

text: scalogram

text: of

text: the

text: original

text: source

text: translated

text: music,

text: if

text: only

text: because

text: of

text: circularity

text: of

text: musical

text: pitch

text: classes.

text: It

text: has

text: along

text: the

text: log-frequency

text: axis

text: at

text: the

text: velocity

text: log

text: θ˙(t):

text: been

text: studied

text: by

text: Shepard

text: Risset

text: and

text: Deutsch

text: to

text: build

text: paradoxes

text: in

text: perception

text: of

text: pitch,

text: and

text: is

text: corroborated

text: by

text: functional

text: imaging

text: of

text: the

text: auditory

text: cortex

text: (see

text: Warren

text: |e

text: ∗t

text: ψ

text: |(t)

text: |e

text: ∗t

text: ψ

text: |(θ(t))

text: |ψ

text: (pθ˙(t))|.

text: DEFORMATIONS

text: OF

text: THE

text: SOURCE-FILTER

text: MODEL

text: θ

text: λ1

text: λ1

text: λ1

text: A

text: classical

text: model

text: for

text: voiced

text: speech

text: production

text: consists

text: in

text: the

text: convolution

text: of

text: a

text: harmonic

text: glottal

text: source

text: e(t)

text: with

text: a

text: vocal

text: tract

text: According

text: to

text: (c),

text: we

text: linearize

text: η(t)

text: over

text: the

text: support

text: of

text: ﬁlter

text: h(t).

text: Introducing

text: independent

text: deformations

text: to

text: both

text: com-

text: According

text: to

text: (d),

text: we

text: approximate

text: hˆ(ω)

text: by

text: a

text: constant

text: over

text: the

text: ponents

text: brings

text: realistic

text: variability

text: to

text: pitch

text: and

text: spectral

text: envelope.

text: frequential

text: support

text: of

text: the

text: wavelet

text: and

text: factorize

text: the

text: ﬁltering

text: as

text: a

text: This

text: section

text: studies

text: the

text: decomposition

text: of

text: the

text: deformed

text: source-

text: product:

text: ﬁlter

text: model

text: in

text: spiral

text: scattering

text: transform.

text: Overview

text: λ

text: η(t)

text: (h

text: ψ

text: (t)

text: hˆ

text: ψ

text: Let

text: e(t)

text: δ(t

text: n)

text: be

text: a

text: harmonic

text: signal

text: and

text: t

text: θ(t)

text: η

text: λ1

text: η˙(t)

text: λ1

text: η˙(t)

text: n

text: a

text: time

text: warp

text: function.

text: We

text: deﬁne

text: a

text: warped

text: source

text: as

text: e

text: (t)

text: (e

text: θ

text: By

text: plugging

text: Equation

text: into

text: Equation

text: the

text: scalogram

text: θ)(t).

text: Similarly,

text: we

text: compose

text: a

text: ﬁlter

text: h(t)

text: and

text: a

text: warp

text: t

text: η(t)

text: to

text: of

text: the

text: deformable

text: source-ﬁlter

text: model

text: appears

text: as

text: a

text: separable

text: prod-

text: deﬁne

text: h

text: (t)

text: (h

text: η)(t).

text: The

text: warped

text: source-ﬁlter

text: model

text: is

text: the

text: η

text: uct:

text: signal

text: x

text: (t)

text: (e

text: ∗t

text: h

text: )(t)

text: θ,η

text: θ

text: η

text: |x

text: ∗t

text: ψ

text: |(t)

text: |ψ

text: (pθ˙(t))|

text: hˆ

text: λ1

text: θ,η

text: λ1

text: λ1

text: η˙(t)

text: Observe

text: that

text: θ˙(t)

text: induces

text: a

text: change

text: of

text: fundamental

text: frequency,

text: whereas

text: η˙(t)

text: accounts

text: for

text: a

text: local

text: dilation

text: of

text: the

text: spectral

text: envelope

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: CON-COMP CON-COMP-MSG PAGERANK-FIXED 25 30 10 20 25 15 20 8 10 15 6 5 10 1 2 4 8 1 2 4 8 1 2 4 8 synch asynch synch asynch synch asynch (a) (b) (c) 45 60 57 40 40 37 50 33 40 44 45 30 27 34 40 33 30 20 27 26.9 30 26 25 24 24 23 21 11 12.3 21.3 20 17.6 9 9.3 10 20 10 1 2 4 8 1 2 4 8 1 2 4 8 synch asynch synch asynch synch asynch (d) (e) (f) Figure 14: Comparison of Graphlab’s synchronous and asynchronous execution for Connected Components, message based Connected Components and PageRank (from left to right) on the livejournal-links graph. The top diagrams shows the number of updated vertices, the middle and bottom ones the algorithm exection time. 15 snoillim ni setadpu xetrev s ni emiT

text: CON-COMP

text: CON-COMP-MSG

text: PAGERANK-FIXED

text: synch

text: asynch

text: synch

text: asynch

text: synch

text: asynch

text: (a)

text: (b)

text: (c)

text: synch

text: asynch

text: synch

text: asynch

text: synch

text: asynch

text: (d)

text: (e)

text: (f)

text: Figure

text: Comparison

label: caption

text: of

text: Graphlab’s

text: synchronous

text: and

text: asynchronous

text: execution

text: for

text: Connected

text: Components,

text: message

text: based

text: Connected

text: Components

text: and

text: PageRank

text: (from

text: left

text: to

text: right)

text: on

text: the

text: livejournal-links

text: graph.

text: The

text: top

text: diagrams

text: shows

text: the

text: number

text: of

text: updated

text: vertices,

text: the

text: middle

text: and

text: bottom

text: ones

text: the

text: algorithm

text: exection

text: time.

text: snoillim

text: ni

text: setadpu

text: xetrev

text: s

text: ni

text: emiT


text: Active Algorithm 1: Connected Components in Pregel model 1) 1 2 3 4 5 [1, 2, 3, 4, 5] 1 compute(vertex, messages) begin 2 if getSuperstep() = 0 then 3 vertex.component ← vertex.id 2) 1 2 1 4 4 [1, 2, 3, 4, 5] 4 changed ← true 5 else 6 minMsg ← getMinimum(messages) 3) 1 1 1 4 4 [2] 7 changed ← false 8 if minMsg < vertex.component then // found smaller component 4) 1 1 1 4 4 [ ] 9 changed ← true 10 vertex.component ← minMsg Figure 4: Example computation of connected components 11 if changed then in the vertex-centric Pregel model. The two connected // component has changed - send new id to components are separated by a larger gap in the middle. neighbors! 12 sendToAll(vertex.component) Gray arrows represent graph edges, black arrows repre- sent message passing, inactive vertices are indicated by a dotted line. Algorithm 2: Connected Components in GAS model P P 1 2 1 init(vertex) begin 2 vertex.component ← vertex.id 1 2 3 4 5 6 3 gather(vertex, edge) begin 4 return vertex.component 1) 1 1 1 3 3 3 5 gather_sum(v1, v2) begin 6 return minimum(v1, v2) 2) 1 1 1 1 1 1 7 apply(vertex, minimum) begin 8 changed ← false 9 if vertex.label > minimum then 3) 1 1 1 1 1 1 10 changed ← true 11 vertex.component ← minimum Figure 5: Example computation of connected components 12 scatter(vertex, edge) begin in the graph-centric model of Giraph++: For each bound- 13 if changed then ary vertex, a message with the component label is sent to // signal to inform neighbour of change the partition with the corresponding internal vertex. 14 signal(edge.target()) update it with the most frequent of the received labels. In the graph-centric model, the algorithm does the fol- Ties are broken systematically, e. g. uniformly at ran- lowing: In the ﬁrst superstep, a sequential algorithm is dom or by preferring the minimum label. The algo- used to ﬁnd all connected components in one partition. rithm can be executed synchronously or asynchronously. For each boundary vertex, a message with the newly found As the synchronous execution can lead to an oscillation component label is sent to the partition with the corre- of labels [Raghavan et al., 2007], the asynchronous exe- sponding internal vertex. If any of the incoming messages cution is preferred. When adapted suitably, the gen- have a smaller label for a vertex, then this vertex and all eral idea of label propagation is also useful for partition- other vertices within the same component and partition ing a network into equally sized blocks with few edges will be updated at once. Figure 5 shows an example run running between diﬀerent blocks [Meyerhenke et al., 2014, of the computation. Slota et al., 2014]. Such results are potentially useful for computing partitions in the graph-centric model. 4.2 Community Detection via Label In PACT, the algorithm is expressed as follows: The la- bel of a vertex is initialized with the vertex ID of a random Propagation neighbor. A bulk iteration is performed on the resulting Many real-word networks exhibit a community struc- data set. In each iteration, a join operator is used to ture, i. e. they can be decomposed into internally dense get tuples (vertexId, neighborLabel) for every vertex. and externally sparse subgraphs named communities. A group operator on both vertex and label followed by a Among heuristics for detecting communities, a label prop- sum aggregator counts the labels for each vertex. This data agation algorithm [Raghavan et al., 2007] is among the set is then grouped by the vertex ID, a reduce operator fastest and easiest to parallelize: Each vertex is initial- ﬁnds the most frequent labels and emits the result. ized with a unique community label, and vertices prop- The label propagation algorithm can be naturally ex- agate their label to all neighbors in each iteration and pressed in the vertex-centric model of Pregel. In the algo- 5 ##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##

text: Active

font: default

text: Algorithm

text: Connected

text: Components

text: in

text: Pregel

text: model

text: compute(vertex,

text: messages)

text: begin

text: if

text: getSuperstep()

text: then

text: vertex.component

text: vertex.id

text: changed

text: true

text: else

text: minMsg

text: getMinimum(messages)

text: changed

text: false

text: if

text: minMsg

text: vertex.component

text: then

text: found

text: smaller

text: component

text: changed

text: true

text: vertex.component

text: minMsg

text: Figure

text: Example

text: computation

text: of

text: connected

text: components

text: if

text: changed

text: then

text: in

text: the

text: vertex-centric

text: Pregel

text: model.

text: The

text: two

text: connected

text: component

text: has

text: changed

text: send

text: new

text: id

text: to

text: components

text: are

text: separated

text: by

text: a

text: larger

text: gap

text: in

text: the

text: middle.

text: neighbors!

text: sendToAll(vertex.component)

text: Gray

text: arrows

text: represent

text: graph

text: edges,

text: black

text: arrows

text: repre-

text: sent

text: message

text: passing,

text: inactive

text: vertices

text: are

text: indicated

text: by

text: a

text: dotted

text: line.

text: Algorithm

text: Connected

text: Components

text: in

text: GAS

text: model

text: P

text: P

text: init(vertex)

text: begin

text: vertex.component

text: vertex.id

text: gather(vertex,

text: edge)

text: begin

text: return

text: vertex.component

text: begin

text: return

text: apply(vertex,

text: minimum)

text: begin

text: changed

text: false

text: if

text: vertex.label

text: minimum

text: then

text: changed

text: true

text: vertex.component

text: minimum

text: Figure

text: Example

text: computation

text: of

text: connected

text: components

text: scatter(vertex,

text: edge)

text: begin

text: in

text: the

text: graph-centric

text: model

text: of

text: Giraph++:

text: For

text: each

text: bound-

text: if

text: changed

text: then

text: ary

text: vertex,

text: a

text: message

text: with

text: the

text: component

text: label

text: is

text: sent

text: to

text: signal

text: to

text: inform

text: neighbour

text: of

text: change

text: the

text: partition

text: with

text: the

text: corresponding

text: internal

text: vertex.

text: signal(edge.target())

text: update

text: it

text: with

text: the

text: most

text: frequent

text: of

text: the

text: received

text: labels.

text: In

text: the

text: graph-centric

text: model,

text: the

text: algorithm

text: does

text: the

text: fol-

text: Ties

text: are

text: broken

text: systematically,

text: e.

text: g.

text: uniformly

text: at

text: ran-

text: lowing:

text: In

text: the

text: ﬁrst

text: superstep,

text: a

text: sequential

text: algorithm

text: is

text: dom

text: or

text: by

text: preferring

text: the

text: minimum

text: label.

text: The

text: algo-

text: used

text: to

text: ﬁnd

text: all

text: connected

text: components

text: in

text: one

text: partition.

text: rithm

text: can

text: be

text: executed

text: synchronously

text: or

text: asynchronously.

text: For

text: each

text: boundary

text: vertex,

text: a

text: message

text: with

text: the

text: newly

text: found

text: As

text: the

text: synchronous

text: execution

text: can

text: lead

text: to

text: an

text: oscillation

text: component

text: label

text: is

text: sent

text: to

text: the

text: partition

text: with

text: the

text: corre-

text: of

text: labels

text: [Raghavan

text: et

text: al.,

text: the

text: asynchronous

text: exe-

text: sponding

text: internal

text: vertex.

text: If

text: any

text: of

text: the

text: incoming

text: messages

text: cution

text: is

text: preferred.

text: When

text: adapted

text: suitably,

text: the

text: gen-

text: have

text: a

text: smaller

text: label

text: for

text: a

text: vertex,

text: then

text: this

text: vertex

text: and

text: all

text: eral

text: idea

text: of

text: label

text: propagation

text: is

text: also

text: useful

text: for

text: partition-

text: other

text: vertices

text: within

text: the

text: same

text: component

text: and

text: partition

text: ing

text: a

text: network

text: into

text: equally

text: sized

text: blocks

text: with

text: few

text: edges

text: will

text: be

text: updated

text: at

text: once.

text: Figure

text: shows

text: an

text: example

text: run

text: running

text: between

text: diﬀerent

text: blocks

text: [Meyerhenke

text: et

text: al.,

text: of

text: the

text: computation.

text: Slota

text: et

text: al.,

text: Such

text: results

text: are

text: potentially

text: useful

text: for

text: computing

text: partitions

text: in

text: the

text: graph-centric

text: model.

text: Community

text: Detection

text: via

text: Label

text: In

text: PACT,

text: the

text: algorithm

text: is

text: expressed

text: as

text: follows:

text: The

text: la-

text: bel

text: of

text: a

text: vertex

text: is

text: initialized

text: with

text: the

text: vertex

text: ID

text: of

text: a

text: random

text: Propagation

text: neighbor.

text: A

text: bulk

text: iteration

text: is

text: performed

text: on

text: the

text: resulting

text: Many

text: real-word

text: networks

text: exhibit

text: a

text: community

text: struc-

text: data

text: set.

text: In

text: each

text: iteration,

text: a

text: join

text: operator

text: is

text: used

text: to

text: ture,

text: i.

text: e.

text: they

text: can

text: be

text: decomposed

text: into

text: internally

text: dense

text: get

text: tuples

text: (vertexId,

text: neighborLabel)

text: for

text: every

text: vertex.

text: and

text: externally

text: sparse

text: subgraphs

text: named

text: communities.

text: A

text: group

text: operator

text: on

text: both

text: vertex

text: and

text: label

text: followed

text: by

text: a

text: Among

text: heuristics

text: for

text: detecting

text: communities,

text: a

text: label

text: prop-

text: sum

text: aggregator

text: counts

text: the

text: labels

text: for

text: each

text: vertex.

text: This

text: data

text: agation

text: algorithm

text: [Raghavan

text: et

text: al.,

text: is

text: among

text: the

text: set

text: is

text: then

text: grouped

text: by

text: the

text: vertex

text: ID,

text: a

text: reduce

text: operator

text: fastest

text: and

text: easiest

text: to

text: parallelize:

text: Each

text: vertex

text: is

text: initial-

text: ﬁnds

text: the

text: most

text: frequent

text: labels

text: and

text: emits

text: the

text: result.

text: ized

text: with

text: a

text: unique

text: community

text: label,

text: and

text: vertices

text: prop-

text: The

text: label

text: propagation

text: algorithm

text: can

text: be

text: naturally

text: ex-

text: agate

text: their

text: label

text: to

text: all

text: neighbors

text: in

text: each

text: iteration

text: and

text: pressed

text: in

text: the

text: vertex-centric

text: model

text: of

text: Pregel.

text: In

text: the

text: algo-

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: In contrast to the bound state, the scattering states BS equation cannot be in general transformed into an equation for the Euclidean amplitude alone. As we will see later, when rotating the integration contour, some singularities are crossed and one must take into ac- √ count the residues in these poles [12]. These residues are proportional to the BS amplitude in − Minkowski space at the particular value k =ε ε , with ε = m2 + k2 and correspondingly 0 k ks k for ε . Applying the Wick rotation one obtains thus a system of coupled equations for the ks − two amplitudes F (k , k) and F (k = ε ε , k). This system of equations was derived in E 4 M 0 ks k [12, 13]. Solving this system of equations is a simpler task than solving the initial BS equation in Minkowski space but does not provide the full oﬀ-shell solution of the scattering problem. Since the on-shell condition k = 0 is equivalent to k = 0, the Minkowski and Euclidean 0 4 on-mass shell amplitudes coincide with each other F (k = 0, k ) = F (k = 0, k ) and the E 4 s M 0 s Euclidean amplitude F (k , k) obtained by solving the coupled equations is enough to provide E 0 the phase shifts. The diﬃculties for solving directly the scattering state BS equation in Minkowski space were recently overcome. A ﬁrst method is based on the Nakanishi integral [15] representation of the BS amplitude and solving the resulting equation for the Nakanishi weight function. It was successfully applied to bound states [5, 6, 7]. In Ref. [8] a scattering equation for the Nakanishi weight function was also derived. It was solved for zero incident momentum in [16]. A second method taking analytically into account all the singularities was developed and proved its eﬃciency for both the bound and, especially, the scattering states [17, 13]. Corre- sponding bound-to-scattering state transition electromagnetic form factor was found in [18]. → The main aim of this work is to show that in the limit of zero incident momentum (k 0) s the Euclidean BS amplitude F (k , k) decouples from the Minkowski part and can be thus E 4 obtained by solving a single integral equation in Euclidean metric. Like in the case of the bound state problem, the solution of the Euclidean equation determining F (k , k) can be obtained E 4 with high precision and low numerical cost. Once F (k , k) is determined, the scattering length − E 4 is given by a = F (0, 0)/m. The possibility, here illustrated, to obtain a scattering length 0 E from an Euclidean solution can have interesting applications in Lattice QCD calculations. It is worth mentioning that an Euclidean formulation of the relativistic quantum mechanics has been recently developed in [14]. The paper is organized as follows. In Sec. we derive the Euclidean BS equation for the spinless scattering amplitude at zero incident momentum k = 0. The numerical results for the s scattering length (for the ladder kernel) and comparison with the results found in Ref. [16] are given in Sec. . Sec. contains discussion and concluding remarks. 2. Deriving Euclidean equation We will derive in this section the integral equation satisﬁed by the oﬀ-shell Euclidean am- plitude F (k , k), corresponding to the zero incident momentum k = 0. E 4 s One possible way to proceed would be to consider the coupled Euclidean-Minkowski system → of equations derived in Ref. [13] (appendix C) and study their limit when k 0. However we s prefer to present here an independent and self consistent derivation of this equation. 3 ##LTLine##

text: In

text: contrast

text: to

text: the

text: bound

text: state,

text: the

text: scattering

text: states

text: BS

text: equation

text: cannot

text: be

text: in

text: general

text: transformed

text: into

text: an

text: equation

text: for

text: the

text: Euclidean

text: amplitude

text: alone.

text: As

text: we

text: will

text: see

text: later,

text: when

text: rotating

text: the

text: integration

text: contour,

text: some

text: singularities

text: are

text: crossed

text: and

text: one

text: must

text: take

text: into

text: ac-

text: count

text: the

text: residues

text: in

text: these

text: poles

text: These

text: residues

text: are

text: proportional

text: to

text: the

text: BS

text: amplitude

text: in

text: Minkowski

text: space

text: at

text: the

text: particular

text: value

text: k

text: =ε

text: ε

text: with

text: ε

text: and

text: correspondingly

text: k

text: ks

text: k

text: for

text: ε

text: Applying

text: the

text: Wick

text: rotation

text: one

text: obtains

text: thus

text: a

text: system

text: of

text: coupled

text: equations

text: for

text: the

text: ks

text: two

text: amplitudes

text: F

text: (k

text: k)

text: and

text: F

text: (k

text: ε

text: ε

text: k).

text: This

text: system

text: of

text: equations

text: was

text: derived

text: in

text: E

text: M

text: ks

text: k

text: Solving

text: this

text: system

text: of

text: equations

text: is

text: a

text: simpler

text: task

text: than

text: solving

text: the

text: initial

text: BS

text: equation

text: in

text: Minkowski

text: space

text: but

text: does

text: not

text: provide

text: the

text: full

text: oﬀ-shell

text: solution

text: of

text: the

text: scattering

text: problem.

text: Since

text: the

text: on-shell

text: condition

text: k

text: is

text: equivalent

text: to

text: k

text: the

text: Minkowski

text: and

text: Euclidean

text: on-mass

text: shell

text: amplitudes

text: coincide

text: with

text: each

text: other

text: F

text: (k

text: k

text: F

text: (k

text: k

text: and

text: the

text: E

text: s

text: M

text: s

text: Euclidean

text: amplitude

text: F

text: (k

text: k)

text: obtained

text: by

text: solving

text: the

text: coupled

text: equations

text: is

text: enough

text: to

text: provide

text: E

text: the

text: phase

text: shifts.

text: The

text: diﬃculties

text: for

text: solving

text: directly

text: the

text: scattering

text: state

text: BS

text: equation

text: in

text: Minkowski

text: space

text: were

text: recently

text: overcome.

text: A

text: ﬁrst

text: method

text: is

text: based

text: on

text: the

text: Nakanishi

text: integral

text: representation

text: of

text: the

text: BS

text: amplitude

text: and

text: solving

text: the

text: resulting

text: equation

text: for

text: the

text: Nakanishi

text: weight

text: function.

text: It

text: was

text: successfully

text: applied

text: to

text: bound

text: states

text: In

text: Ref.

text: a

text: scattering

text: equation

text: for

text: the

text: Nakanishi

text: weight

text: function

text: was

text: also

text: derived.

text: It

text: was

text: solved

text: for

text: zero

text: incident

text: momentum

text: in

text: A

text: second

text: method

text: taking

text: analytically

text: into

text: account

text: all

text: the

text: singularities

text: was

text: developed

text: and

text: proved

text: its

text: eﬃciency

text: for

text: both

text: the

text: bound

text: and,

text: especially,

text: the

text: scattering

text: states

text: Corre-

text: sponding

text: bound-to-scattering

text: state

text: transition

text: electromagnetic

text: form

text: factor

text: was

text: found

text: in

text: The

text: main

text: aim

text: of

text: this

text: work

text: is

text: to

text: show

text: that

text: in

text: the

text: limit

text: of

text: zero

text: incident

text: momentum

text: (k

text: s

text: the

text: Euclidean

text: BS

text: amplitude

text: F

text: (k

text: k)

text: decouples

text: from

text: the

text: Minkowski

text: part

text: and

text: can

text: be

text: thus

text: E

text: obtained

text: by

text: solving

text: a

text: single

text: integral

text: equation

text: in

text: Euclidean

text: metric.

text: Like

text: in

text: the

text: case

text: of

text: the

text: bound

text: state

text: problem,

text: the

text: solution

text: of

text: the

text: Euclidean

text: equation

text: determining

text: F

text: (k

text: k)

text: can

text: be

text: obtained

text: E

text: with

text: high

text: precision

text: and

text: low

text: numerical

text: cost.

text: Once

text: F

text: (k

text: k)

text: is

text: determined,

text: the

text: scattering

text: length

text: E

text: is

text: given

text: by

text: a

text: F

text: The

text: possibility,

text: here

text: illustrated,

text: to

text: obtain

text: a

text: scattering

text: length

text: E

text: from

text: an

text: Euclidean

text: solution

text: can

text: have

text: interesting

text: applications

text: in

text: Lattice

text: QCD

text: calculations.

text: It

text: is

text: worth

text: mentioning

text: that

text: an

text: Euclidean

text: formulation

text: of

text: the

text: relativistic

text: quantum

text: mechanics

text: has

text: been

text: recently

text: developed

text: in

text: The

text: paper

text: is

text: organized

text: as

text: follows.

text: In

text: Sec.

text: we

text: derive

text: the

text: Euclidean

text: BS

text: equation

text: for

text: the

text: spinless

text: scattering

text: amplitude

text: at

text: zero

text: incident

text: momentum

text: k

text: The

text: numerical

text: results

text: for

text: the

text: s

text: scattering

text: length

text: (for

text: the

text: ladder

text: kernel)

text: and

text: comparison

text: with

text: the

text: results

text: found

text: in

text: Ref.

text: are

text: given

text: in

text: Sec.

text: Sec.

text: contains

text: discussion

text: and

text: concluding

text: remarks.

text: Deriving

text: Euclidean

text: equation

text: We

text: will

text: derive

text: in

text: this

text: section

text: the

text: integral

text: equation

text: satisﬁed

text: by

text: the

text: oﬀ-shell

text: Euclidean

text: am-

text: plitude

text: F

text: (k

text: k),

text: corresponding

text: to

text: the

text: zero

text: incident

text: momentum

text: k

text: E

text: s

text: One

text: possible

text: way

text: to

text: proceed

text: would

text: be

text: to

text: consider

text: the

text: coupled

text: Euclidean-Minkowski

text: system

text: of

text: equations

text: derived

text: in

text: Ref.

text: (appendix

text: C)

text: and

text: study

text: their

text: limit

text: when

text: k

text: However

text: we

text: s

text: prefer

text: to

text: present

text: here

text: an

text: independent

text: and

text: self

text: consistent

text: derivation

text: of

text: this

text: equation.

text: ##LTLine##


text: 5 FIG. 5: Noise-induced transitions in analog simulations. (a): FIG. 6: Noise-induced bifurcations in numerical simulations Marginal coordinate PDF vs noise intensity, P(y; D). For of Eqs. (7). (a): Normalized coordinate PDF, P(y)/P vs max each value of noise intensity, D, the PDF P(y), was normal- noise intensity. (b): Eﬀective bifurcation parameter µ(D). ized to its maximal value, i.e. P (y) = P(y)/P . Blue dots Vertical dashed lines indicate positions of two pitchfork bi- n max show minima of the corresponding eﬀective potential (11). furcations. (c): Variances of coordinate (open black cir- (b): Eﬀective bifurcation parameter µ(D). Vertical dashed cles), σ2, and velocity (ﬁlled red circles), σ2 vs noise in- v v lines indicate positions of two pitchfork bifurcations. (c): Co- tensity. (d): Rice frequency, ω , vs noise intensity. Red R ordinate and velocity variance vs noise intensity. The coor- circles show values numerically obtained values; solid line dinate variance, σ2 is shown by the open black circles; the shows ω calculated from Eq. (13) with the eﬀective po- y R velocity variance which equals the eﬀective noise intensity, tential U and noise intensity, D . Other parameters are: eﬀ eﬀ D = σ2, is shown by ﬁlled red circles. (d): Rice frequency, ε = 0.01, c = 1, c = 9, c = 22, a = 1.2, b = 100. eﬀ v 1 3 5 ω , vs noise intensity. Open red circles show results of ana- R log simulations; solid line shows Eq.(13) with the eﬀective potential U and eﬀective noise D . eﬀ eﬀ crease of noise gives rise to the backward transition from mono- to bistable dynamics with doubly peaked coordinate PDF shown in Fig. 6(a). As for analog metastable states: the longer is the residence in simulations, noise-induced transitions are well described metastable states, the smaller is the Kramers’s rate by the eﬀective bifurcation parameter, µ(D), shown in and the Rice frequency. The dependence of the Rice Fig. 6(b). Similar to analog experiment, the velocity vari- frequency on noise intensity for our circuit is non- ance, σ2, which determines the eﬀective noise intensity, v monotonous [Fig. 5(d)]: ωR is low for weak and strong shows monotonous increase with D, while the coordinate noise, where the system is bistable, and attains its max- variance possesses a minimum, reﬂecting the ﬁrst noise- imal value for intermediate noise, corresponding to ef- induced transition from bi- to unimodal structure of the fective monostable dynamics with the minimal value of coordinate PDF [compare Figs. 5(c) and 6(c)]. Similarly, the bifurcation parameter, µ. Unlike for the Kramers os- the Rice frequency exhibit non-monotonous dependence cillator (1) which is characterized by Gaussian velocity on noise intensity attaining its maximum at D corre- distribution, the velocity PDF, P(v), for our bistable os- sponding to the minimal value of eﬀective bifurcation cillator is non-Gaussian [Fig. 4(b)]. Nevertheless the non- parameter, µ(D) [compare Figs. 5(d) and 6(d)]. monotonous dependence ω (D) is qualitatively approxi- R IV. MECHANISM OF NOISE-INDUCED mated by Eq.(13) with the eﬀective pot→ential and →noise TRANSITIONS intensity, i.e. with the substitution U U, D D eﬀ eﬀ in (13). Noise-induced changes in the oscillator’s dynamics can B. Numerical simulations be understood by studying the structure of the phase space of the corresping deterministic system described by Numerical simulations conﬁrmed the existence of Eqs.(7) with D = 0. Fig. 7(a) shows two stable nodes, multiple noise-induced transitions in the mathematical separated by the saddle at the origin, and nullclines of model of the circuit Eqs.(7) as shown in Fig. 6. Double- the system. The intrinsic feature of the system under peaked stationary coordinate PDF, P(y), becomes uni- study is an unusual structure of the nullcline v˙ = 0. Be- modal with the increase of noise intensity. Further in- sides the conventional N-shape branch passing through ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure##

text: FIG.

text: Noise-induced

text: transitions

text: in

text: analog

text: simulations.

text: (a):

text: FIG.

text: Noise-induced

text: bifurcations

text: in

text: numerical

text: simulations

text: Marginal

text: coordinate

text: PDF

text: vs

text: noise

text: intensity,

text: P(y;

text: D).

text: For

text: of

text: Eqs.

text: (a):

text: Normalized

text: coordinate

text: PDF,

text: P(y)/P

text: vs

text: max

text: each

text: value

text: of

text: noise

text: intensity,

text: D,

text: the

text: PDF

text: P(y),

text: was

text: normal-

text: noise

text: intensity.

text: (b):

text: Eﬀective

text: bifurcation

text: parameter

text: µ(D).

text: ized

text: to

text: its

text: maximal

text: value,

text: i.e.

text: P

text: (y)

text: P(y)/P

text: Blue

text: dots

text: Vertical

text: dashed

text: lines

text: indicate

text: positions

text: of

text: two

text: pitchfork

text: bi-

text: n

text: max

text: show

text: minima

text: of

text: the

text: corresponding

text: eﬀective

text: potential

text: furcations.

text: (c):

text: Variances

text: of

text: coordinate

text: (open

text: black

text: cir-

text: (b):

text: Eﬀective

text: bifurcation

text: parameter

text: µ(D).

text: Vertical

text: dashed

text: cles),

text: and

text: velocity

text: (ﬁlled

text: red

text: circles),

text: σ2

text: vs

text: noise

text: in-

text: v

text: v

text: lines

text: indicate

text: positions

text: of

text: two

text: pitchfork

text: bifurcations.

text: (c):

text: Co-

text: tensity.

text: (d):

text: Rice

text: frequency,

text: ω

text: vs

text: noise

text: intensity.

text: Red

text: R

text: ordinate

text: and

text: velocity

text: variance

text: vs

text: noise

text: intensity.

text: The

text: coor-

text: circles

text: show

text: values

text: numerically

text: obtained

text: values;

text: solid

text: line

text: dinate

text: variance,

text: σ2

text: is

text: shown

text: by

text: the

text: open

text: black

text: circles;

text: the

text: shows

text: ω

text: calculated

text: from

text: Eq.

text: with

text: the

text: eﬀective

text: po-

text: y

text: R

text: velocity

text: variance

text: which

text: equals

text: the

text: eﬀective

text: noise

text: intensity,

text: tential

text: U

text: and

text: noise

text: intensity,

text: D

text: Other

text: parameters

text: are:

text: eﬀ

text: eﬀ

text: D

text: is

text: shown

text: by

text: ﬁlled

text: red

text: circles.

text: (d):

text: Rice

text: frequency,

text: ε

text: c

text: c

text: c

text: a

text: b

text: eﬀ

text: v

text: ω

text: vs

text: noise

text: intensity.

text: Open

text: red

text: circles

text: show

text: results

text: of

text: ana-

text: R

text: log

text: simulations;

text: solid

text: line

text: shows

text: with

text: the

text: eﬀective

text: potential

text: U

text: and

text: eﬀective

text: noise

text: D

text: eﬀ

text: eﬀ

text: crease

text: of

text: noise

text: gives

text: rise

text: to

text: the

text: backward

text: transition

text: from

text: mono-

text: to

text: bistable

text: dynamics

text: with

text: doubly

text: peaked

text: coordinate

text: PDF

text: shown

text: in

text: Fig.

text: As

text: for

text: analog

text: metastable

text: states:

text: the

text: longer

text: is

text: the

text: residence

text: in

text: simulations,

text: noise-induced

text: transitions

text: are

text: well

text: described

text: metastable

text: states,

text: the

text: smaller

text: is

text: the

text: Kramers’s

text: rate

text: by

text: the

text: eﬀective

text: bifurcation

text: parameter,

text: µ(D),

text: shown

text: in

text: and

text: the

text: Rice

text: frequency.

text: The

text: dependence

text: of

text: the

text: Rice

text: Fig.

text: Similar

text: to

text: analog

text: experiment,

text: the

text: velocity

text: vari-

text: frequency

text: on

text: noise

text: intensity

text: for

text: our

text: circuit

text: is

text: non-

text: ance,

text: which

text: determines

text: the

text: eﬀective

text: noise

text: intensity,

text: v

text: monotonous

text: [Fig.

text: ωR

text: is

text: low

text: for

text: weak

text: and

text: strong

text: shows

text: monotonous

text: increase

text: with

text: D,

text: while

text: the

text: coordinate

text: noise,

text: where

text: the

text: system

text: is

text: bistable,

text: and

text: attains

text: its

text: max-

text: variance

text: possesses

text: a

text: minimum,

text: reﬂecting

text: the

text: ﬁrst

text: noise-

text: imal

text: value

text: for

text: intermediate

text: noise,

text: corresponding

text: to

text: ef-

text: induced

text: transition

text: from

text: bi-

text: to

text: unimodal

text: structure

text: of

text: the

text: fective

text: monostable

text: dynamics

text: with

text: the

text: minimal

text: value

text: of

text: coordinate

text: PDF

text: [compare

text: Figs.

text: and

text: Similarly,

text: the

text: bifurcation

text: parameter,

text: µ.

text: Unlike

text: for

text: the

text: Kramers

text: os-

text: the

text: Rice

text: frequency

text: exhibit

text: non-monotonous

text: dependence

text: cillator

text: which

text: is

text: characterized

text: by

text: Gaussian

text: velocity

text: on

text: noise

text: intensity

text: attaining

text: its

text: maximum

text: at

text: D

text: corre-

text: distribution,

text: the

text: velocity

text: PDF,

text: P(v),

text: for

text: our

text: bistable

text: os-

text: sponding

text: to

text: the

text: minimal

text: value

text: of

text: eﬀective

text: bifurcation

text: cillator

text: is

text: non-Gaussian

text: [Fig.

text: Nevertheless

text: the

text: non-

text: parameter,

text: µ(D)

text: [compare

text: Figs.

text: and

text: monotonous

text: dependence

text: ω

text: (D)

text: is

text: qualitatively

text: approxi-

text: R

text: IV.

text: MECHANISM

text: OF

text: NOISE-INDUCED

text: mated

text: by

text: with

text: the

text: eﬀective

text: pot→ential

text: and

text: →noise

text: TRANSITIONS

text: intensity,

text: i.e.

text: with

text: the

text: substitution

text: U

text: U,

text: D

text: D

text: eﬀ

text: eﬀ

text: in

text: Noise-induced

text: changes

text: in

text: the

text: oscillator’s

text: dynamics

text: can

text: B.

text: Numerical

text: simulations

text: be

text: understood

text: by

text: studying

text: the

text: structure

text: of

text: the

text: phase

text: space

text: of

text: the

text: corresping

text: deterministic

text: system

text: described

text: by

text: Numerical

text: simulations

text: conﬁrmed

text: the

text: existence

text: of

text: with

text: D

text: Fig.

text: shows

text: two

text: stable

text: nodes,

text: multiple

text: noise-induced

text: transitions

text: in

text: the

text: mathematical

text: separated

text: by

text: the

text: saddle

text: at

text: the

text: origin,

text: and

text: nullclines

text: of

text: model

text: of

text: the

text: circuit

text: as

text: shown

text: in

text: Fig.

text: Double-

text: the

text: system.

text: The

text: intrinsic

text: feature

text: of

text: the

text: system

text: under

text: peaked

text: stationary

text: coordinate

text: PDF,

text: P(y),

text: becomes

text: uni-

text: study

text: is

text: an

text: unusual

text: structure

text: of

text: the

text: nullcline

text: v˙

text: Be-

text: modal

text: with

text: the

text: increase

text: of

text: noise

text: intensity.

text: Further

text: in-

text: sides

text: the

text: conventional

text: N-shape

text: branch

text: passing

text: through

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##


text: 3 All bosons and fermions, however, still do originate as (ﬁ- nite dimensional) representations of the basic SU(3) sym- metry group, which will become important later. There are three families of particles corresponding to the sin- glets of A . Going to three space dimensions the in- 4 teraction changes from a conﬁning potential to a 1/r (or Yukawa) potential between the (electroweak) charges, which thus can be free, in contrast to the (color) SU(3) charges in one space dimension. IV. ELECTROWEAK SECTOR FIG. 1: SU(3) quantum number assignments for bosonic excitations. The right-moving positively charged (φ+R) and After the introduction of the covariant derivatives, part neutral (φ0 ) scalar ﬁelds are in an isospin doublet with Y = R − of the potential is included in the term +1, while the right-moving negatively charged (φ ) ﬁeld is in − R a weak iso−singlet with Y = 2. The left-moving negatively DµΦ∗D Φ = ∂µΦ∗∂ Φ + N CA g2AµA Φ∗Φ(.10) charged (φL−) and neutral (φ0L) ﬁelds are in an isospin doublet µ µ 2 µ with Y = 1 while the left-moving positively charged (φ+) L With C (G = SU(3)) = 4/3, the second term in Eq. 10 ﬁeld is in a weak isosinglet with Y = +2. A − is precisely V (Φ) and we are left with the 1 + 1 dimen- sional QCD lagrangian (without a Higgs mass-term), (cid:88) look at the covariant derivatives, − 1 − − L = 1∂µH∂ H FµνF +Ψ(iD/ M gv H)Ψ, (11) (cid:88) 2 µ 4 µν E(1, 1) : iD Φi = i∂ Φi + g Aa(T )iΦj, (7) µ µ µ a j ∈ but with a scalar ﬁeld, which does not seem harmful [11]. a G We will ﬁrst consider the electroweak structure of the lep- E(1, 3) : iD Φi = i∂ Φi + g Aa(T )iΦj. (8) µ µ µ a j ton sector before returning to that of the colored fermions ∈ (cid:48) a G (quarks). The ﬁrst expression applies to ﬁelds in E(1, 1) and ac- For the second option of the covariant derivative (cid:48) counts for local SU(3) gauge invariance. It involves eight (Eq. 8) w−e have CA(G ) = 2/3, the second term in Eq. 10 √ (color) gauge ﬁelds also living in E(1, 1). The second is only V (Φ)/2. This leaves the scalar ﬁeld massive expression is relevant for (asymptotic) ﬁelds in E(1, 3). with M = M/ 2. This is an experimentally interest- H Coupling for real continuous SO(3) transformations the ing scenario for the standard model if the fermion mass ﬁeld and space rotations, there are no gauge ﬁelds for is identiﬁed with the top quark mass M = M . t that part leaving only the complex transformations in- For the bosons, we have (in principle arbitrarily) as- volving four (electroweak) gauge ﬁelds living in E(1, 3). signed right to the triplet and left to the anti-triplet. The embedding of SO(3) directions into SU(3) is not The ﬁelds can be rotated into a single scalar ﬁeld with a   unique. The discrete symmetry group A governs the nonzero vacuum expectation value as is done in the usual 4 possible oriented embeddings. For singlet representa⊃- standard model treatm(cid:0) ent, (cid:88)even if the(cid:1)yform triplets, tions of this embedding group one can consider SU(3) × × ⊗ → ⊗ ⊗ 0 SO(3) A4 [SU(2) U(1)] SO(3) [SU(2) U(1)], Φ = √1 exp − i θaλ  1 + H  , decoupling space-time and internal symmetries [6]. The L 2 (cid:0) 2 a=(cid:88)1,2,3 a(cid:1)  0  unitary transformation matrix for these singlet states [7– 10] is the matrix W that rotates the symmetric embed- 1 + H  (cid:112)      √1 ding of th(cid:112)(cid:112)e vacuum into an electroweak embedding,  ΦR = 2 exp +2i a=1,2,3 θaλa 00 . 1/3 0 1 1 1 W† 1/3 = 1 for W = √1 ω2 1 ω , TgahuegeeletcrtarnoswfoeramkacthiaorngsesaraendidceonrtriﬁesepdownditihngthgeenSerUa(t2o)rs o⊗f 1/3 0 3 ω 1 ω2 U(1) transformations but with a single coupling cIon- Y √ (9) stant within SU(3). The charged ﬁelds are neither I3 = λ /2 or Y = λ 3 eigenstates but they are eigenstates 3 8 × where ω = exp(i 2π/3). Since the starting point only had of Q = I + Y/2. The breaking of the SU(2) U(1) 3 I Y SO(3) as a symmetry ⊗group, the vacuum indeed is not symmetry to U(1)Q after the choice of ground state be- invariant under SU(2) U(1) transformations, but it is ing neutral, produces three massive and one massless neutral for Q = I3 + Y/2. The symmetry pattern and its gauge boson. As discussed in a slightly diﬀerent context breaking thus is summarized as [12], the SU(3) embeddin(cid:18)g gives a weak mi(cid:19)xing angle, (cid:88) ⊗ sin θ = 1/2 after rewriting in IO(1, 1(cid:124)) SU((cid:123)3(cid:122)) (cid:125) (cid:124) (cid:123)(cid:122) (cid:125) W ⊃ × ⊗ ⊗ 3 IO(1, 1) SO(3) SU(2) U(1) . g I Y iD Φ = i∂ Φ + Wiλ + B λ Φ (12) → µ µ 2 µ i µ 8 IO(1,3) U(1)Q i=1 ##LTFigure## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: All

text: bosons

text: and

text: fermions,

text: however,

text: still

text: do

text: originate

text: as

text: (ﬁ-

text: nite

text: dimensional)

text: representations

text: of

text: the

text: basic

text: sym-

text: metry

text: group,

text: which

text: will

text: become

text: important

text: later.

text: There

text: are

text: three

text: families

text: of

text: particles

text: corresponding

text: to

text: the

text: sin-

text: glets

text: of

text: A

text: Going

text: to

text: three

text: space

text: dimensions

text: the

text: in-

text: teraction

text: changes

text: from

text: a

text: conﬁning

text: potential

text: to

text: a

text: (or

text: Yukawa)

text: potential

text: between

text: the

text: (electroweak)

text: charges,

text: which

text: thus

text: can

text: be

text: free,

text: in

text: contrast

text: to

text: the

text: (color)

text: charges

text: in

text: one

text: space

text: dimension.

text: IV.

label: section

text: ELECTROWEAK

text: SECTOR

text: FIG.

text: quantum

text: number

text: assignments

text: for

text: bosonic

text: excitations.

text: The

text: right-moving

text: positively

text: charged

text: (φ+R)

text: and

text: After

text: the

text: introduction

text: of

text: the

text: covariant

text: derivatives,

text: part

text: neutral

text: scalar

text: ﬁelds

text: are

text: in

text: an

text: isospin

text: doublet

text: with

text: Y

text: R

text: of

text: the

text: potential

text: is

text: included

text: in

text: the

text: term

text: while

text: the

text: right-moving

text: negatively

text: charged

text: (φ

text: ﬁeld

text: is

text: in

text: R

text: a

text: weak

text: iso−singlet

text: with

text: Y

text: The

text: left-moving

text: negatively

text: DµΦ∗D

text: Φ

text: ∂µΦ∗∂

text: Φ

text: N

text: CA

text: charged

text: (φL−)

text: and

text: neutral

text: ﬁelds

text: are

text: in

text: an

text: isospin

text: doublet

text: µ

text: µ

text: µ

text: with

text: Y

text: while

text: the

text: left-moving

text: positively

text: charged

text: (φ+)

text: L

text: With

text: C

text: (G

text: the

text: second

text: term

text: in

text: Eq.

text: ﬁeld

text: is

text: in

text: a

text: weak

text: isosinglet

text: with

text: Y

text: A

text: is

text: precisely

text: V

text: (Φ)

text: and

text: we

text: are

text: left

text: with

text: the

text: dimen-

text: sional

text: QCD

text: lagrangian

text: (without

text: a

text: Higgs

text: mass-term),

text: look

text: at

text: the

text: covariant

text: derivatives,

text: L

text: 1∂µH∂

text: H

text: FµνF

text: +Ψ(iD/

text: M

text: gv

text: H)Ψ,

text: µ

text: µν

text: iD

text: Φi

text: i∂

text: Φi

text: g

text: Aa(T

text: )iΦj,

text: µ

text: µ

text: µ

text: a

text: j

text: but

text: with

text: a

text: scalar

text: ﬁeld,

text: which

text: does

text: not

text: seem

text: harmful

text: a

text: G

text: We

text: will

text: ﬁrst

text: consider

text: the

text: electroweak

text: structure

text: of

text: the

text: lep-

text: iD

text: Φi

text: i∂

text: Φi

text: g

text: Aa(T

text: )iΦj.

text: µ

text: µ

text: µ

text: a

text: j

text: ton

text: sector

text: before

text: returning

text: to

text: that

text: of

text: the

text: colored

text: fermions

text: a

text: G

text: (quarks).

text: The

text: ﬁrst

text: expression

text: applies

text: to

text: ﬁelds

text: in

text: and

text: ac-

text: For

text: the

text: second

text: option

text: of

text: the

text: covariant

text: derivative

text: counts

text: for

text: local

text: gauge

text: invariance.

text: It

text: involves

text: eight

text: (Eq.

text: w−e

text: have

text: CA(G

text: the

text: second

text: term

text: in

text: Eq.

text: (color)

text: gauge

text: ﬁelds

text: also

text: living

text: in

text: The

text: second

text: is

text: only

text: V

text: This

text: leaves

text: the

text: scalar

text: ﬁeld

text: massive

text: expression

text: is

text: relevant

text: for

text: (asymptotic)

text: ﬁelds

text: in

text: with

text: M

text: M/

text: This

text: is

text: an

text: experimentally

text: interest-

text: H

text: Coupling

text: for

text: real

text: continuous

text: transformations

text: the

text: ing

text: scenario

text: for

text: the

text: standard

text: model

text: if

text: the

text: fermion

text: mass

text: ﬁeld

text: and

text: space

text: rotations,

text: there

text: are

text: no

text: gauge

text: ﬁelds

text: for

text: is

text: identiﬁed

text: with

text: the

text: top

text: quark

text: mass

text: M

text: M

text: t

text: that

text: part

text: leaving

text: only

text: the

text: complex

text: transformations

text: in-

text: For

text: the

text: bosons,

text: we

text: have

text: (in

text: principle

text: arbitrarily)

text: as-

text: volving

text: four

text: (electroweak)

text: gauge

text: ﬁelds

text: living

text: in

text: signed

text: right

text: to

text: the

text: triplet

text: and

text: left

text: to

text: the

text: anti-triplet.

text: The

text: embedding

text: of

text: directions

text: into

text: is

text: not

text: The

text: ﬁelds

text: can

text: be

text: rotated

text: into

text: a

text: single

text: scalar

text: ﬁeld

text: with

text: a

text: unique.

text: The

text: discrete

text: symmetry

text: group

text: A

text: governs

text: the

text: nonzero

text: vacuum

text: expectation

text: value

text: as

text: is

text: done

text: in

text: the

text: usual

text: possible

text: oriented

text: embeddings.

text: For

text: singlet

text: representa⊃-

text: standard

text: model

text: ent,

text: if

text: triplets,

text: tions

text: of

text: this

text: embedding

text: group

text: one

text: can

text: consider

text: Φ

text: √1

text: exp

text: i

text: θaλ

text: H

text: decoupling

text: space-time

text: and

text: internal

text: symmetries

text: The

text: L

text: unitary

text: transformation

text: matrix

text: for

text: these

text: singlet

text: states

text: is

text: the

text: matrix

text: W

text: that

text: rotates

text: the

text: symmetric

text: embed-

text: H

text: √1

text: ding

text: of

text: vacuum

text: into

text: an

text: electroweak

text: embedding,

text: ΦR

text: exp

text: θaλa

text: W†

text: for

text: W

text: √1

text: ω2

text: ω

text: o⊗f

text: ω

text: ω2

text: transformations

text: but

text: with

text: a

text: single

text: coupling

text: cIon-

text: Y

text: stant

text: within

text: The

text: charged

text: ﬁelds

text: are

text: neither

text: λ

text: or

text: Y

text: λ

text: eigenstates

text: but

text: they

text: are

text: eigenstates

text: where

text: ω

text: exp(i

text: Since

text: the

text: starting

text: point

text: only

text: had

text: of

text: Q

text: I

text: The

text: breaking

text: of

text: the

text: I

text: Y

text: as

text: a

text: symmetry

text: ⊗group,

text: the

text: vacuum

text: indeed

text: is

text: not

text: symmetry

text: to

text: after

text: the

text: choice

text: of

text: ground

text: state

text: be-

text: invariant

text: under

text: transformations,

text: but

text: it

text: is

text: ing

text: neutral,

text: produces

text: three

text: massive

text: and

text: one

text: massless

text: neutral

text: for

text: Q

text: The

text: symmetry

text: pattern

text: and

text: its

text: gauge

text: boson.

text: As

text: discussed

text: in

text: a

text: slightly

text: diﬀerent

text: context

text: breaking

text: thus

text: is

text: summarized

text: as

text: the

text: gives

text: a

text: weak

text: angle,

text: sin

text: θ

text: after

text: rewriting

text: in

text: W

text: g

text: I

text: Y

text: iD

text: Φ

text: i∂

text: Φ

text: Wiλ

text: B

text: λ

text: Φ

text: µ

text: µ

text: µ

text: i

text: µ

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##