The Architecture of Complexity:
From the Topology of the WWW to theStructure of the Cell

Albert-László Barabási
Center for Complex Networks ResearchNortheastern UniversityDepartment of Medicine and CCSBHarvard Medical School

www.BarabasiLab.com

InternetStructure of an organization

Red, blue, or green: departments
Yellow: consultants
Grey: external experts

www.orgnet.com

Business ties in US biotech-industry

Nodes: companies
investment
pharmaresearch labs
publicbiotechnology

Links: collaborations
financialR&D

http://ecclectic.ss.uci.edu/~drwhite/Movie

Complex systems
Made of many non-identical elements
connected by diverse interactions.

NETWORK

Erdös-Rényi model(1960)
Connect withprobability p
p=1/6
N=10〈k〉 ~ 1.5- Democratic- RandomPál Erdös(1913-1996)

Poisson distribution

ROBOT: collects all URL’s
found in a document andfollows them recursively

P(k) ~ k-γ
Found

Scale-free Network

Nodes: WWW documents
Links: URL links
Over 10 billion documents

ExpectedExponential Network

World Wide Web

R. Albert, H. Jeong, A-L Barabási, Nature, 401 130 (1999).

INTERNET BACKBONE
Nodes: computers, routers
Links: physical lines(Faloutsos, Faloutsos and Faloutsos, 1999)

Online communities
Nodes: online user
Links: email contact

Pussokram.com onlinecommunity; 512 days,
25,000 users.

Kiel University log files
112 days, N=59,912 nodes

Ebel, Mielsch, Bornholdtz, PRE 2002.

Holme, Edling, Liljeros, 2002.

SCIENCE COAUTHORSHIP
Nodes: scientist (authors)
Links: write paper together(Newman, 2000, Barabási et al 2001)

SCIENCE CITATION INDEX
25Nodes: papers
Links: citations
H.E. Stanley,...

1736 PRL papers (1988)
648

P(k) ~k-γ(γ = 3)
(S. Redner, 1998)

Swedish sex-web
Nodes: people (Females; Males)
Links: sexual relationships

4781 Swedes; 18-74;
59% response rate.
Liljeros et al. Nature 2001

Origin of SF networks: Growth and preferential attachment(1) Networks continuously expandby the addition of new nodes

GROWTH:
add a new node with m links

WWW : addition of new documents(2) New nodes prefer to link tohighly connected nodes.
WWW : linking to well known sites

PREFERENTIAL ATTACHMENT: theprobability that a node connects to anode with k links is proportional to k.

kiΠ ( ki ) =Σ jk jP(k) ~k-3
Barabási & Albert, Science 286, 509 (1999)

Fitness Model: Can Latecomers Make It?
SF model:k(t)~t ½

fitness (η )ηi ki
Π(ki ) ≅∑j ηj k j

Degree (k)Fitness model:(first mover advantage)

time
Bianconi & Barabási, Physical Review Letters 2001; Europhys. Lett. 2001.

k(η,t)~tβ(η)β(η) =η/CGENOME

protein-geneinteractions

PROTEOME
protein-protein
interactions

METABOLISM
Bio-chemical
reactions
Citrate Cycle

Metabolic Network

Protein Interactions

Jeong, Tombor, Albert, Oltvai, & Barabási, Nature (2000); Jeong, Mason, Barabási &.
Oltvai, Nature (2001); Wagner & Fell, Proc. R. Soc. B (2001)

Human Interaction Network

Rual et al. Nature 2005; Stelze et al. Cell 2005

Robustness
Complex systems maintain their basic functions even under errors and failures(cell → mutations; Internet → router breakdowns)
1
Sfc
0
1
Fraction of removed nodes, fnode failureRobustness of scale-free networks

1Attacks

FailuresSγ ≤ 3 : fc=1
(R. Cohen et al PRL, 2000)

0fc

1fAlbert, Jeong, Barabási, Nature 406 378 (2000)

Achilles’ Heel of complex networksfailureattack
Internet

R. Albert, H. Jeong, A.L. Barabási, Nature 406 378 (2000)

Hubs and Essentiality

18%

24%

62%

Hubs evolve slower: they are more alike in different organisms[H Fraser et al., Science (2002). Krylov, et al. Genome Res.(2003)]
Hub removal has more phenotypic consequences [Yu et al. Science (2008)]
Jeong, Mason, Barabási, and Oltvai, Nature 411, 41-42 (2001Epidemic threshold in scale-free networks
λ:spreading
rate of a virusρ:density ofinfected usersρ
Active phaseVirus deathλc

Biology:
If a virus is not too infectious,
it will die out

λ c= <k><k2>

λEconomics and social sciences:
If a product or an idea is not
too ‘sticky,’ it will not succeed.

<k2> Æ ∞λ c→ 0

Pastor Satorras & Vespignani, Physical Review Letters (2001)

NRC Panel on “Network Science”

What is “network science”?
An attempt to understand networks emerging in nature, technology and society
using a unified set of tools and principles.

What is new here?
Despite the apparent differences, many networks emerge and evolve driven by afundamental set of laws and mechanism.

Réka Albert,

Penn State

Hawoong Jeong,

KAIST, Korea

Ginestra Bianconi,

ICTP, Trieste

Kwang-Il Goh,

Korea University

Cesar Hidalgo,

Notre Dame

Mark Vidal,

Dana-Farber, Harvard

Michael E. Cusick,Dana Farber, Harvard

David Valle,

Johns Hopkins

Barton Childs, Johns Hopkins
Nicholas Christakis,

HarvardDeok-Sun Lee,

Northeastern University & DF

Juyong Park,

Northeastern University & DF

Zoltan N. Oltvai,

Pitssburgh Medical School

Dashun Wang,

Northeastern University

www.BarabasiLab.com