Emergent scalefree networks Christopher W. Lynn12 Caroline M. Holmes2 Stephanie E. Palmer34 1Initiative for the Theoretical Sciences Graduate Center City University of New York New York

2025-04-26 0 0 2.78MB 24 页 10玖币

侵权投诉

Emergent scale–free networks

Christopher W. Lynn1,2, Caroline M. Holmes2, & Stephanie E. Palmer3,4

1Initiative for the Theoretical Sciences, Graduate Center, City University of New York, New York,

NY 10016, USA

2Joseph Henry Laboratories of Physics and Lewis–Sigler Institute for Integrative Genomics,

Princeton University, Princeton, NJ 08544, USA

3Department of Organismal Biology and Anatomy, University of Chicago, Chicago, IL 60637,

USA

4Department of Physics, University of Chicago, Chicago, IL 60637, USA

Abstract

Many complex systems—from social and communication networks to biological networks

and the Internet—are thought to exhibit scale–free structure. However, prevailing explana-

tions rely on the constant addition of new nodes, an assumption that fails dramatically in

some real–world settings. Here, we propose a model in which nodes are allowed to die, and

their connections rearrange under a mixture of preferential and random attachment. Under

these simple dynamics, we show that networks self–organize towards scale–free structure,

with a power–law exponent γ= 1 + 1

pthat depends only on the proportion pof preferential

(rather than random) attachment. Applying our model to several real networks, we infer p

directly from data, and predict the relationship between network size and degree heterogene-

ity. Together, these results establish that realistic scale–free structure can emerge naturally in

networks of constant size and density, with broad implications for the structure and function

of complex systems.

arXiv:2210.06453v2 [nlin.AO] 9 Nov 2022

Introduction

Scale–free structure is a hallmark feature of many complex networks, with the probability of a

node having klinks (or degree k) following a power law k−γ. First studied in networks of scien-

tiﬁc citations,1, 2 scale–free structure has now been reported across a staggering array of complex

systems, from social networks (of romantic relationships,3scientiﬁc collaborations,4and online

friendships5); to biological networks (of connections in the brain,6metabolic interactions,7and

food webs8); to the online and physical wiring of the Internet;9–12 to language,13 transportation,14

and communication networks.15 Although empirically measuring power laws in real networks

poses important technical challenges,16, 17 the study of scale–free structure continues to provide

deep insights into the nature of complex systems.

Scale–free networks are highly heterogeneous (or heavy–tailed), with a small number of

well–connected hub nodes dominating in a sea of low–degree nodes.18 This heterogeneity has

critical implications for the function and dynamics of such systems.19 In networks of Kuramoto

oscillators, for example, the transition to synchronization depends precisely on the power–law ex-

ponent γ.20 Similarly, in Ising models, the critical temperature deﬁning the phase transition from

disorder to order varies systematically with γ.21, 22 Scale–free structure has also been used to ex-

plain the spread of viruses,23 to analyze the robustness of complex systems to errors and attacks,24

and to investigate the communication efﬁciency and compressibility of information networks.25–27

Despite extensive investigations, there remains a basic limitation in our understanding of how

scale–free structure emerges in real systems. Prevailing explanations primarily rely on two mech-

anisms: growth (wherein nodes are constantly added to the network) and preferential attachment

(such that well–connected nodes are more likely to gain new connections).2, 18 While alternatives

have been proposed to preferential attachment (such as random attachment to edges,28 random

copying of neighbors,29 and deterministic attachment rules30), the dependence on growth remains

widespread.19, 31, 32 In many real–world contexts, however, this dependence on constant growth is

unrealistic.31, 33, 34 In biological networks, for example, brains do not grow without bound,35 and

just as animals or species are added to a population, others die out.8, 36 In these systems, rather than

relying on growth, scale–free structure emerges organically at relatively constant size.

To describe such systems, a number of models have been proposed for scale–free networks

without growth.33, 34, 37–40 For instance, power–law degree distributions can result from the opti-

mization of network properties or by connecting nodes based on ﬁtness.37–40 However, these ex-

planations rely on global choices for the optimization or ﬁtness functions, and therefore do not

address the self–organization of network structure. Meanwhile, there exist models for the self–

organization of power–law degree distributions,33, 34 but these yield unrealistic exponents γ≤1,

whereas most real–world exponents lie in the range 2≤γ≤3. Thus, understanding whether, and

how, realistic scale–free structure self–organizes remains a central open question.

Here, we begin by analyzing the dynamics of real networks, demonstrating empirically that

systems can maintain scale–free structure even without growth. To explain this observation, we

propose an intuitive model in which nodes die at random, and the disconnected edges reattach to

new nodes either preferentially (with probability p) or randomly (with probability 1−p). Under

these simple dynamics, the number of edges is held constant, and the network quickly approaches

a steady–state size. Importantly, we show (both analytically and numerically) that scale–free struc-

ture emerges naturally, with a realistic power–law exponent γ= 1 + 1

p≥2that depends only on

the proportion pof preferential attachment.

Results

Emergent scale–free structure in real networks

In some complex systems—including many biological, language, and real–life social networks—

topological properties (such as scale–free structure) arise without constant growth.33, 34 Meanwhile,

other systems—particularly online social and communication networks, scientiﬁc collaborations,

and the Internet—are often viewed as growing by accumulating new nodes and edges over time.19

Yet even for these networks, we will see that scale–free structure can arise without growth.

The dynamics of a network are deﬁned by a sequence of connections (it, jt), ordered by the

time tat which they occur. Letting these edges accumulate over time, we arrive at a single growing

network. Alternatively, one can divide the connections into groups of equal size E, thus deﬁning a

sequence of independent snapshots, each representing the structure of the network within a speciﬁc

window of time (Fig. 1a). For clarity, we let Ndenote the total number of nodes in the sequence,

while nreﬂects the size of a single snapshot (Fig. 1a). Consider, for example, the social network

of friendships on Flickr (Fig. 1b,c).41 Dividing the sequence of connections into groups of size

E= 103, we can study the evolution of different network properties. In particular, we ﬁnd that

the Flickr network ﬂuctuates around a constant size n(Fig. 1b). Yet even without growing, we see

that the network maintains a clear power–law degree distribution (Fig. 1c), and we verify that this

scale–free structure remains consistent over time (see Supplementary Information). By contrast,

if we randomize the edges in each snapshot, then the degrees drop off super–exponentially as a

Poisson distribution, and the scale–free structure vanishes (Fig. 1c).

We can repeat the above procedure for any time–evolving network, such as links between

pages on Wikipedia (Fig. 1d,e) or email correspondence among scientists (Fig. 1f,g).42, 43 Across

a number of different social, web, communication, and transportation networks (see Table 1 and

Methods for details on network selection), we divide the dynamics into snapshots with E= 103

edges each, the largest number that can be applied to all systems. While some networks grow

slowly in time (such as Wikipedia in Fig. 1d), all of the networks approach a steady–state size

(see Supplementary Information). In fact, the snapshots are limited to n≤2Eby deﬁnition, and

therefore cannot grow without bound. Even still, many of the networks exhibit scale–free structure

(such as Wikipedia in Fig. 1e). We note that some of the networks are not scale–free (such as the

emails in Fig. 1g), but even these still display heavy–tailed degree distributions with many of the

same structural properties.44 In what follows, we will develop a simple dynamical model capable

of describing all of these networks.

Model of emergent scale–free networks

The above results demonstrate that scale–free structure can arise without growth in real networks.

E = 5

0 2000 4000 6000 8000

600

800

1000

1200

1400

1600

0 100 200 300

250

300

350

400

450

100101102

10-5

10-4

10-3

10-2

10-1

100

100101102103

10-8

10-6

10-4

10-2

100

01234

200

400

600

800

1000

1200

1400

Network size n

Probability P(k)

Degree kDegree kNetwork number Network number

a b

d e f g

Real

Power law

Real

~ k -2.7

104

Emails

Wikipedia

Time

Flickr

100101102103

10-6

10-4

10-2

100

Probability P(k)

Degree k

~ k -2.5

Real

Random

Poisson

Power law

Network size n

Network number

Edges

N = 7

n = 6 n = 7 n = 5

N = 9 105

E = 103

N = 2 106

E = 103

N = 986

E = 103

Fig. 1 |Degree distributions of real dynamical networks. a, Procedure for measuring network dynamics.

We divide the sequence of edges into groups of equal size E, thus forming a series of network snapshots.

Each snapshot contains n≤Nnodes, where Nis the total number of nodes in the dataset. b, Trajectory

of system size nover time for the network of friendships on Flickr.41 c, Degree distribution of the Flickr

network (green) computed across all network snapshots. Randomizing each snapshot (grey) yields a Poisson

distribution (solid line). Dashed line illustrates a power law for comparison. d-e, Trajectory of network size

(d) and degree distribution (e) for the hyperlinks between pages on English Wikipedia.42 f-g, Trajectory of

network size (f) and degree distribution (g) for emails between scientists at a research institution.43

But how can we explain this observation? Here we present a simple model in which scale–free

structure emerges through self-organization, with connections rearranging under a mixture of pref-

erential and random attachment. We begin with an arbitrary network of Nnodes and Eedges (for

simplicity, we always begin with a random network). At each time step, one node dies at random,

losing all of its connections (Fig. 2a, center). Each of these connections then reattaches in one

of two ways: (i) with probability p, it connects to a node via preferential attachment (that is, it

attaches to node iwith probability proportional to its degree ki; Fig. 2a, bottom left), or (ii) with

probability 1−p, it connects to a random node (Fig. 2a, bottom right). In this way, the total num-

bers of nodes Nand edges Eremain constant, with the wiring between nodes simply rearranging

over time. Notably, besides Nand E, the model only contains a single parameter p, representing

the proportion of preferential (rather than random) attachment.

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

EmergentscalefreenetworksChristopherW.Lynn1;2,CarolineM.Holmes2,&StephanieE.Palmer3;41InitiativefortheTheoreticalSciences,GraduateCenter,CityUniversityofNewYork,NewYork,NY10016,USA2JosephHenryLaboratoriesofPhysicsandLewis–SiglerInstituteforIntegrativeGenomics,PrincetonUniversity,Princeton,NJ08544,U...

展开>> 收起<<

Emergent scalefree networks Christopher W. Lynn12 Caroline M. Holmes2 Stephanie E. Palmer34 1Initiative for the Theoretical Sciences Graduate Center City University of New York New York.pdf

共24页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Emergent scalefree networks Christopher W. Lynn12 Caroline M. Holmes2 Stephanie E. Palmer34 1Initiative for the Theoretical Sciences Graduate Center City University of New York New York

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: