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.
1
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-
tific citations,1, 2 scale–free structure has now been reported across a staggering array of complex
systems, from social networks (of romantic relationships,3scientific 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 defining 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 efficiency 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
2
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 fitness.37–40 However, these ex-
planations rely on global choices for the optimization or fitness 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, scientific 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.
3
The dynamics of a network are defined 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 defining a
sequence of independent snapshots, each representing the structure of the network within a specific
window of time (Fig. 1a). For clarity, we let Ndenote the total number of nodes in the sequence,
while nreflects 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 find that
the Flickr network fluctuates 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 definition, 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.
4
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
0
200
400
600
800
1000
1200
1400
Network size n
Network size n
Probability P(k)
Probability P(k)
Degree kDegree kNetwork number Network number
a b
d e f g
Power law
~ k -2.7
104
×
Emails
Wikipedia
Time
Flickr
100101102103
10-6
10-4
10-2
100
Probability P(k)
Degree k
~ k -2.5
Random
Poisson
Power law
c
Network size n
Network number
Edges
3
5
6
5
1
2
2
3
7
5
6
2
5
7
2
1
2
4
3
2
5
4
6
5
4
2
5
3
5
2
6
7
5
4
3
2
1
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.
5
摘要：

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

相关推荐

更多
立即下载
分类：图书资源 价格：10玖币 属性：24 页 大小：2.78MB 格式：PDF 时间：2025-04-26

开通VIP享超值会员特权

  • 多端同步记录
  • 高速下载文档
  • 免费文档工具
  • 分享文档赚钱
  • 每日登录抽奖
  • 优质衍生服务

作者详情

相关内容

更多

热门标签

人际关系 配电装置 动力学连接体 力的合成 高考理综 全宋诗作者索引 公务员考试
/ 24
评分 收藏
分享
立即下载
客服
关注