Overview of Complex Networks Complex Networks, SFI Summer School, June, 2010

Overview
Overview of Complex Networks
Complex Networks, SFI Summer School, June, 2010
Plan
Basic definitions
Popularity
Examples of
Complex Networks
Prof. Peter Dodds
Properties of
Complex Networks
Department of Mathematics & Statistics
Center for Complex Systems
Vermont Advanced Computing Center
University of Vermont
Nutshell
References
Frame 1/49
Licensed under the Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License
.
Overview
Outline
Plan
Plan
Basic definitions
Basic definitions
Examples of
Complex Networks
Popularity
Popularity
Properties of
Complex Networks
Nutshell
References
Examples of Complex Networks
Properties of Complex Networks
Nutshell
References
Frame 2/49
Overview
Something of a plan:
Plan
Basic definitions
Popularity
I
Lecture 1: Overview; Background
I
Lecture 2: Random, Scale-free,
and Small-World networks
I
Lecture 3: Models of Contagion
I
Lecture 4: Transportation networks;
Discovering structure
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
Frame 3/49
Overview
Something of a plan:
Plan
Basic definitions
Popularity
I
Lecture 1: Overview; Background
I
Lecture 2: Random, Scale-free,
and Small-World networks
I
Lecture 3: Models of Contagion
I
Lecture 4: Transportation networks;
Discovering structure
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
Frame 3/49
Overview
Something of a plan:
Plan
Basic definitions
Popularity
I
Lecture 1: Overview; Background
I
Lecture 2: Random, Scale-free,
and Small-World networks
I
Lecture 3: Models of Contagion
I
Lecture 4: Transportation networks;
Discovering structure
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
Frame 3/49
Overview
Something of a plan:
Plan
Basic definitions
Popularity
I
Lecture 1: Overview; Background
I
Lecture 2: Random, Scale-free,
and Small-World networks
I
Lecture 3: Models of Contagion
I
Lecture 4: Transportation networks;
Discovering structure
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
Frame 3/49
Overview
Exciting details regarding these slides:
Plan
I
Three versions (all in pdf):
1. Presentation,
2. Flat Presentation,
3. Handout (2x2).
I
Presentation versions are navigable and hyperlinks
are clickable.
I
Web links look like this ().
I
References in slides link to full citation at end. [2]
I
Citations contain links to papers in pdf (if available).
I
50 hours of lectures → 5 hours.
I
Brought to you by a concoction of LATEX, Beamer,
perl, and madness.
Basic definitions
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
Frame 4/49
Overview
Exciting details regarding these slides:
Plan
I
Three versions (all in pdf):
1. Presentation,
2. Flat Presentation,
3. Handout (2x2).
I
Presentation versions are navigable and hyperlinks
are clickable.
I
Web links look like this ().
I
References in slides link to full citation at end. [2]
I
Citations contain links to papers in pdf (if available).
I
50 hours of lectures → 5 hours.
I
Brought to you by a concoction of LATEX, Beamer,
perl, and madness.
Basic definitions
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
Frame 4/49
Overview
Exciting details regarding these slides:
Plan
I
Three versions (all in pdf):
1. Presentation,
2. Flat Presentation,
3. Handout (2x2).
I
Presentation versions are navigable and hyperlinks
are clickable.
I
Web links look like this ().
I
References in slides link to full citation at end. [2]
I
Citations contain links to papers in pdf (if available).
I
50 hours of lectures → 5 hours.
I
Brought to you by a concoction of LATEX, Beamer,
perl, and madness.
Basic definitions
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
Frame 4/49
Overview
Exciting details regarding these slides:
Plan
I
Three versions (all in pdf):
1. Presentation,
2. Flat Presentation,
3. Handout (2x2).
I
Presentation versions are navigable and hyperlinks
are clickable.
I
Web links look like this ().
I
References in slides link to full citation at end. [2]
I
Citations contain links to papers in pdf (if available).
I
50 hours of lectures → 5 hours.
I
Brought to you by a concoction of LATEX, Beamer,
perl, and madness.
Basic definitions
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
Frame 4/49
Overview
Exciting details regarding these slides:
Plan
I
Three versions (all in pdf):
1. Presentation,
2. Flat Presentation,
3. Handout (2x2).
I
Presentation versions are navigable and hyperlinks
are clickable.
I
Web links look like this ().
I
References in slides link to full citation at end. [2]
I
Citations contain links to papers in pdf (if available).
I
50 hours of lectures → 5 hours.
I
Brought to you by a concoction of LATEX, Beamer,
perl, and madness.
Basic definitions
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
Frame 4/49
Overview
Exciting details regarding these slides:
Plan
I
Three versions (all in pdf):
1. Presentation,
2. Flat Presentation,
3. Handout (2x2).
I
Presentation versions are navigable and hyperlinks
are clickable.
I
Web links look like this ().
I
References in slides link to full citation at end. [2]
I
Citations contain links to papers in pdf (if available).
I
50 hours of lectures → 5 hours.
I
Brought to you by a concoction of LATEX, Beamer,
perl, and madness.
Basic definitions
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
Frame 4/49
Overview
Exciting details regarding these slides:
Plan
I
Three versions (all in pdf):
1. Presentation,
2. Flat Presentation,
3. Handout (2x2).
I
Presentation versions are navigable and hyperlinks
are clickable.
I
Web links look like this ().
I
References in slides link to full citation at end. [2]
I
Citations contain links to papers in pdf (if available).
I
50 hours of lectures → 5 hours.
I
Brought to you by a concoction of LATEX, Beamer,
perl, and madness.
Basic definitions
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
Frame 4/49
Overview
Bonus materials:
Plan
Graduate Course Websites:
I
SFI Summer School Course (this one!):
Basic definitions
Popularity
http://www.uvm.edu/∼pdodds/teaching/courses/2010-06SFI-networks/ ()
Examples of
Complex Networks
I
Principles of Complex Systems (), University of Vermont
Properties of
Complex Networks
I
Complex Networks (), University of Vermont
Nutshell
References
Textbooks:
I
Mark Newman (Physics, Michigan)
“Networks: An Introduction” ()
I
David Easley and Jon Kleinberg (Economics and
Computer Science, Cornell)
“Networks, Crowds, and Markets: Reasoning About a
Highly Connected World” ()
Frame 5/49
Overview
Bonus materials:
Plan
Graduate Course Websites:
I
SFI Summer School Course (this one!):
Basic definitions
Popularity
http://www.uvm.edu/∼pdodds/teaching/courses/2010-06SFI-networks/ ()
Examples of
Complex Networks
I
Principles of Complex Systems (), University of Vermont
Properties of
Complex Networks
I
Complex Networks (), University of Vermont
Nutshell
References
Textbooks:
I
Mark Newman (Physics, Michigan)
“Networks: An Introduction” ()
I
David Easley and Jon Kleinberg (Economics and
Computer Science, Cornell)
“Networks, Crowds, and Markets: Reasoning About a
Highly Connected World” ()
Frame 5/49
Overview
Bonus materials:
Plan
Basic definitions
Review articles:
I
S. Boccaletti et al.
“Complex networks: structure and dynamics” [4]
Times cited: 1,028 (as of June 7, 2010)
I
M. Newman
“The structure and function of complex networks” [15]
Times cited: 2,559 (as of June 7, 2010)
I
R. Albert and A.-L. Barabási
“Statistical mechanics of complex networks” [1]
Times cited: 3,995 (as of June 7, 2010)
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
Frame 6/49
Overview
Basic definitions
Plan
Complex System—Some ingredients:
I
Distributed system of many interrelated parts
I
No centralized control
I
Nonlinear relationships
I
Existence of feedback loops
I
Complex systems are open (out of equilibrium)
I
Presence of Memory
I
Modular (nested)/multiscale structure
I
Opaque boundaries
I
Emergence—‘More is Different’ [2]
Basic definitions
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
Frame 7/49
Overview
Basic definitions
Plan
Complex System—Some ingredients:
I
Distributed system of many interrelated parts
I
No centralized control
I
Nonlinear relationships
I
Existence of feedback loops
I
Complex systems are open (out of equilibrium)
I
Presence of Memory
I
Modular (nested)/multiscale structure
I
Opaque boundaries
I
Emergence—‘More is Different’ [2]
Basic definitions
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
Frame 7/49
Overview
Basic definitions
Plan
Complex System—Some ingredients:
I
Distributed system of many interrelated parts
I
No centralized control
I
Nonlinear relationships
I
Existence of feedback loops
I
Complex systems are open (out of equilibrium)
I
Presence of Memory
I
Modular (nested)/multiscale structure
I
Opaque boundaries
I
Emergence—‘More is Different’ [2]
Basic definitions
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
Frame 7/49
Overview
Basic definitions
Plan
Complex System—Some ingredients:
I
Distributed system of many interrelated parts
I
No centralized control
I
Nonlinear relationships
I
Existence of feedback loops
I
Complex systems are open (out of equilibrium)
I
Presence of Memory
I
Modular (nested)/multiscale structure
I
Opaque boundaries
I
Emergence—‘More is Different’ [2]
Basic definitions
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
Frame 7/49
Overview
Basic definitions
Plan
Complex System—Some ingredients:
I
Distributed system of many interrelated parts
I
No centralized control
I
Nonlinear relationships
I
Existence of feedback loops
I
Complex systems are open (out of equilibrium)
I
Presence of Memory
I
Modular (nested)/multiscale structure
I
Opaque boundaries
I
Emergence—‘More is Different’ [2]
Basic definitions
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
Frame 7/49
Overview
Basic definitions
Plan
Complex System—Some ingredients:
I
Distributed system of many interrelated parts
I
No centralized control
I
Nonlinear relationships
I
Existence of feedback loops
I
Complex systems are open (out of equilibrium)
I
Presence of Memory
I
Modular (nested)/multiscale structure
I
Opaque boundaries
I
Emergence—‘More is Different’ [2]
Basic definitions
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
Frame 7/49
Overview
Basic definitions
Plan
Complex System—Some ingredients:
I
Distributed system of many interrelated parts
I
No centralized control
I
Nonlinear relationships
I
Existence of feedback loops
I
Complex systems are open (out of equilibrium)
I
Presence of Memory
I
Modular (nested)/multiscale structure
I
Opaque boundaries
I
Emergence—‘More is Different’ [2]
Basic definitions
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
Frame 7/49
Overview
Basic definitions
Plan
Complex System—Some ingredients:
I
Distributed system of many interrelated parts
I
No centralized control
I
Nonlinear relationships
I
Existence of feedback loops
I
Complex systems are open (out of equilibrium)
I
Presence of Memory
I
Modular (nested)/multiscale structure
I
Opaque boundaries
I
Emergence—‘More is Different’ [2]
Basic definitions
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
Frame 7/49
Overview
Basic definitions
Plan
Complex System—Some ingredients:
I
Distributed system of many interrelated parts
I
No centralized control
I
Nonlinear relationships
I
Existence of feedback loops
I
Complex systems are open (out of equilibrium)
I
Presence of Memory
I
Modular (nested)/multiscale structure
I
Opaque boundaries
I
Emergence—‘More is Different’ [2]
Basic definitions
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
Frame 7/49
Overview
Basic definitions
Plan
Complex System—Some ingredients:
I
Distributed system of many interrelated parts
I
No centralized control
I
Nonlinear relationships
I
Existence of feedback loops
I
Complex systems are open (out of equilibrium)
I
Presence of Memory
I
Modular (nested)/multiscale structure
I
Opaque boundaries
I
Emergence—‘More is Different’ [2]
Basic definitions
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
Frame 7/49
Overview
Basic definitions
Plan
Basic definitions
Popularity
Examples of
Complex Networks
Complex: (Latin = with + fold/weave (com + plex))
Adjective
I
Made up of multiple parts; intricate or detailed.
I
Not simple or straightforward.
Properties of
Complex Networks
Nutshell
References
Frame 8/49
Overview
Thesaurus deliciousness:
Plan
Basic definitions
Popularity
network
Examples of
Complex Networks
noun
1 a network of arteries WEB, lattice, net, matrix, mesh,
crisscross, grid, reticulum, reticulation; Anatomy plexus.
2 a network of lanes MAZE , labyrinth, warren, tangle.
3 a network of friends SYSTEM, complex, nexus, web,
webwork.
Properties of
Complex Networks
Nutshell
References
Frame 9/49
Overview
Ancestry:
Plan
Basic definitions
From Keith Briggs’s excellent
etymological investigation: ()
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
I
Opus reticulatum:
I
A Latin origin?
[http://serialconsign.com/2007/11/we-put-net-network]
Frame 10/49
gan nette (with a net-work of clouds), Cd. Th. 182, Ii; Exod. 74. [Goth, nati: O. Sax. netti,
Frs. nette: Icel. net; gen. pl. netja : O. H. Ger. nezzi rete.] v. æl-, boge-, breóst-, deór-,
fisc-, fleóh-, here-, bring-, inwit-, mycg-, searo-, wæl-nett, and next word.
Overview
Ancestry:
e caul :-- Nette (under the heading de membris hominum) disceptum i. reticulum (cf. hoc
guedo circa jecur [fat around liver], 704, 7), Wülck. Gl. 293,6. Nettae oligia, 35, 34. Nytte
ng, bandage], Wrt. Voc. i. 45, 18. Nette, ii. 63, 39 : disceptum, 26,19. [Icel. netja the
. Ger. nezzi adeps [fat] intestini; pl. intestina.] v. neta.
Net and Work are venerable old words:
cognates in Germanic languages and a probable one in Latin. The Germanic words are
er (except for nót which is feminine); the Latin word is feminine. Note that the normal
a net is rete, although there may have also been a Vulgar Latin word *tragina for a
ord
I
ati
et(t),
etti
I
et
Plan
Basic definitions
‘Net’ first used to mean spider web (King Ælfréd, 888).
Popularity
‘Work’ appears to have long meant purposeful action.
Examples of
Complex Networks
Keith Briggs: : Etymology of `network'
et
et
6/6/09 9:45 PM
Properties
of
Complex Networks
Nutshell
ezzi
References
etze
etz
ette
etti
et
etja
),
ót
et
sources
I
ät
assa
‘Network’ = something built based on the idea of
natural, flexible lattice or web.
rd occurs exactly seven times in the bible. It takes the form natja in the dative. Because
earliest record of Germanic (from about 350), it is worth looking at all these occurrences:
I
Bosworth, Joseph: (Northcote Toller, T. ed.) An Anglo-Saxon Dictionary. Dictionary, Supplement and
Addenda Oxford University Press, 1st ed. n.d., reprinted 1983, 1966, 1972. [Abbreviations: Wrt. Voc. i:
T. Wright, A volume of vocabularies, 1857. Quoted by page and number of gloss. Wrt. Voc. ii: T. Wright,
A second volume of vocabularies, 1873. Quoted by page and line. Ælfc. Gr: Ælfric's Grammar. Ps. Spl.:
Psalterium Davidis Latino-Saxonicum vetus. Lk. Skt.: The gospel according to St. Luke. Mt. Kmbl.: The
gospel according to St. Matthew in Anglo-Saxon and Northumbrian versions. ed. J. M. Kemble. Jn. Skt.:
The gospel according to St. John. Som.: Dictionarium Saxonico-Latino-Anglicum, by E. Somner, Oxford
1659. Coll. Monast. Th.: Colloquium ad pueros linguae Latinae locutione exercendos ad Ælfrico
compilatum. Homl. Th.: The homilies of Ælfric. Wülck. Gl.: Anglo-Saxon and Old English vocabularies,
by Thomas Wright, edited by R. P. Wülcker, London 1884. Cd. Th.: Cædmon's metrical paraphrase, by
B. Thorpe, London 1832.]
c.f., ironwork, stonework, fretwork.
Frame 11/49
Page 2 of 4
Stamm, Friedrich Ludwig: Friedrich Ludwig Stamm's Ulfilas oder die uns erhaltenen Denkmäler der
gotischen Sprache: Text, Wörterbuch und Grammatik Ungekürzte Neuauflage, Nachdruck der Ausgabe
aus dem Jahre 1872 [Essen]: Magnus-Verlag, [1984]. ISBN: 3884001655
gan nette (with a net-work of clouds), Cd. Th. 182, Ii; Exod. 74. [Goth, nati: O. Sax. netti,
Frs. nette: Icel. net; gen. pl. netja : O. H. Ger. nezzi rete.] v. æl-, boge-, breóst-, deór-,
fisc-, fleóh-, here-, bring-, inwit-, mycg-, searo-, wæl-nett, and next word.
Overview
Ancestry:
e caul :-- Nette (under the heading de membris hominum) disceptum i. reticulum (cf. hoc
guedo circa jecur [fat around liver], 704, 7), Wülck. Gl. 293,6. Nettae oligia, 35, 34. Nytte
ng, bandage], Wrt. Voc. i. 45, 18. Nette, ii. 63, 39 : disceptum, 26,19. [Icel. netja the
. Ger. nezzi adeps [fat] intestini; pl. intestina.] v. neta.
Net and Work are venerable old words:
cognates in Germanic languages and a probable one in Latin. The Germanic words are
er (except for nót which is feminine); the Latin word is feminine. Note that the normal
a net is rete, although there may have also been a Vulgar Latin word *tragina for a
ord
I
ati
et(t),
etti
I
et
Plan
Basic definitions
‘Net’ first used to mean spider web (King Ælfréd, 888).
Popularity
‘Work’ appears to have long meant purposeful action.
Examples of
Complex Networks
Keith Briggs: : Etymology of `network'
et
et
6/6/09 9:45 PM
Properties
of
Complex Networks
Nutshell
ezzi
References
etze
etz
ette
etti
et
etja
),
ót
et
sources
I
ät
assa
‘Network’ = something built based on the idea of
natural, flexible lattice or web.
rd occurs exactly seven times in the bible. It takes the form natja in the dative. Because
earliest record of Germanic (from about 350), it is worth looking at all these occurrences:
I
Bosworth, Joseph: (Northcote Toller, T. ed.) An Anglo-Saxon Dictionary. Dictionary, Supplement and
Addenda Oxford University Press, 1st ed. n.d., reprinted 1983, 1966, 1972. [Abbreviations: Wrt. Voc. i:
T. Wright, A volume of vocabularies, 1857. Quoted by page and number of gloss. Wrt. Voc. ii: T. Wright,
A second volume of vocabularies, 1873. Quoted by page and line. Ælfc. Gr: Ælfric's Grammar. Ps. Spl.:
Psalterium Davidis Latino-Saxonicum vetus. Lk. Skt.: The gospel according to St. Luke. Mt. Kmbl.: The
gospel according to St. Matthew in Anglo-Saxon and Northumbrian versions. ed. J. M. Kemble. Jn. Skt.:
The gospel according to St. John. Som.: Dictionarium Saxonico-Latino-Anglicum, by E. Somner, Oxford
1659. Coll. Monast. Th.: Colloquium ad pueros linguae Latinae locutione exercendos ad Ælfrico
compilatum. Homl. Th.: The homilies of Ælfric. Wülck. Gl.: Anglo-Saxon and Old English vocabularies,
by Thomas Wright, edited by R. P. Wülcker, London 1884. Cd. Th.: Cædmon's metrical paraphrase, by
B. Thorpe, London 1832.]
c.f., ironwork, stonework, fretwork.
Frame 11/49
Page 2 of 4
Stamm, Friedrich Ludwig: Friedrich Ludwig Stamm's Ulfilas oder die uns erhaltenen Denkmäler der
gotischen Sprache: Text, Wörterbuch und Grammatik Ungekürzte Neuauflage, Nachdruck der Ausgabe
aus dem Jahre 1872 [Essen]: Magnus-Verlag, [1984]. ISBN: 3884001655
gan nette (with a net-work of clouds), Cd. Th. 182, Ii; Exod. 74. [Goth, nati: O. Sax. netti,
Frs. nette: Icel. net; gen. pl. netja : O. H. Ger. nezzi rete.] v. æl-, boge-, breóst-, deór-,
fisc-, fleóh-, here-, bring-, inwit-, mycg-, searo-, wæl-nett, and next word.
Overview
Ancestry:
e caul :-- Nette (under the heading de membris hominum) disceptum i. reticulum (cf. hoc
guedo circa jecur [fat around liver], 704, 7), Wülck. Gl. 293,6. Nettae oligia, 35, 34. Nytte
ng, bandage], Wrt. Voc. i. 45, 18. Nette, ii. 63, 39 : disceptum, 26,19. [Icel. netja the
. Ger. nezzi adeps [fat] intestini; pl. intestina.] v. neta.
Net and Work are venerable old words:
cognates in Germanic languages and a probable one in Latin. The Germanic words are
er (except for nót which is feminine); the Latin word is feminine. Note that the normal
a net is rete, although there may have also been a Vulgar Latin word *tragina for a
ord
I
ati
et(t),
etti
I
et
Plan
Basic definitions
‘Net’ first used to mean spider web (King Ælfréd, 888).
Popularity
‘Work’ appears to have long meant purposeful action.
Examples of
Complex Networks
Keith Briggs: : Etymology of `network'
et
et
6/6/09 9:45 PM
Properties
of
Complex Networks
Nutshell
ezzi
References
etze
etz
ette
etti
et
etja
),
ót
et
sources
I
ät
assa
‘Network’ = something built based on the idea of
natural, flexible lattice or web.
rd occurs exactly seven times in the bible. It takes the form natja in the dative. Because
earliest record of Germanic (from about 350), it is worth looking at all these occurrences:
I
Bosworth, Joseph: (Northcote Toller, T. ed.) An Anglo-Saxon Dictionary. Dictionary, Supplement and
Addenda Oxford University Press, 1st ed. n.d., reprinted 1983, 1966, 1972. [Abbreviations: Wrt. Voc. i:
T. Wright, A volume of vocabularies, 1857. Quoted by page and number of gloss. Wrt. Voc. ii: T. Wright,
A second volume of vocabularies, 1873. Quoted by page and line. Ælfc. Gr: Ælfric's Grammar. Ps. Spl.:
Psalterium Davidis Latino-Saxonicum vetus. Lk. Skt.: The gospel according to St. Luke. Mt. Kmbl.: The
gospel according to St. Matthew in Anglo-Saxon and Northumbrian versions. ed. J. M. Kemble. Jn. Skt.:
The gospel according to St. John. Som.: Dictionarium Saxonico-Latino-Anglicum, by E. Somner, Oxford
1659. Coll. Monast. Th.: Colloquium ad pueros linguae Latinae locutione exercendos ad Ælfrico
compilatum. Homl. Th.: The homilies of Ælfric. Wülck. Gl.: Anglo-Saxon and Old English vocabularies,
by Thomas Wright, edited by R. P. Wülcker, London 1884. Cd. Th.: Cædmon's metrical paraphrase, by
B. Thorpe, London 1832.]
c.f., ironwork, stonework, fretwork.
Frame 11/49
Page 2 of 4
Stamm, Friedrich Ludwig: Friedrich Ludwig Stamm's Ulfilas oder die uns erhaltenen Denkmäler der
gotischen Sprache: Text, Wörterbuch und Grammatik Ungekürzte Neuauflage, Nachdruck der Ausgabe
aus dem Jahre 1872 [Essen]: Magnus-Verlag, [1984]. ISBN: 3884001655
Overview
Ancestry:
First known use: Geneva Bible, 1560
Plan
‘And thou shalt make unto it a grate like networke of
brass (Exodus xxvii 4).’
Basic definitions
From the OED via Briggs:
I
1658–: reticulate structures in animals
I
1839–: rivers and canals
I
1869–: railways
I
1883–: distribution network of electrical cables
I
1914–: wireless broadcasting networks
I
Natural → man-made
I
Physical connections → Wire-less connections →
abstract connections
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
Frame 12/49
Overview
Ancestry:
First known use: Geneva Bible, 1560
Plan
‘And thou shalt make unto it a grate like networke of
brass (Exodus xxvii 4).’
Basic definitions
From the OED via Briggs:
I
1658–: reticulate structures in animals
I
1839–: rivers and canals
I
1869–: railways
I
1883–: distribution network of electrical cables
I
1914–: wireless broadcasting networks
I
Natural → man-made
I
Physical connections → Wire-less connections →
abstract connections
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
Frame 12/49
Overview
Ancestry:
First known use: Geneva Bible, 1560
Plan
‘And thou shalt make unto it a grate like networke of
brass (Exodus xxvii 4).’
Basic definitions
From the OED via Briggs:
I
1658–: reticulate structures in animals
I
1839–: rivers and canals
I
1869–: railways
I
1883–: distribution network of electrical cables
I
1914–: wireless broadcasting networks
I
Natural → man-made
I
Physical connections → Wire-less connections →
abstract connections
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
Frame 12/49
Overview
Ancestry:
First known use: Geneva Bible, 1560
Plan
‘And thou shalt make unto it a grate like networke of
brass (Exodus xxvii 4).’
Basic definitions
From the OED via Briggs:
I
1658–: reticulate structures in animals
I
1839–: rivers and canals
I
1869–: railways
I
1883–: distribution network of electrical cables
I
1914–: wireless broadcasting networks
I
Natural → man-made
I
Physical connections → Wire-less connections →
abstract connections
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
Frame 12/49
Overview
Ancestry:
First known use: Geneva Bible, 1560
Plan
‘And thou shalt make unto it a grate like networke of
brass (Exodus xxvii 4).’
Basic definitions
From the OED via Briggs:
I
1658–: reticulate structures in animals
I
1839–: rivers and canals
I
1869–: railways
I
1883–: distribution network of electrical cables
I
1914–: wireless broadcasting networks
I
Natural → man-made
I
Physical connections → Wire-less connections →
abstract connections
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
Frame 12/49
Overview
Ancestry:
First known use: Geneva Bible, 1560
Plan
‘And thou shalt make unto it a grate like networke of
brass (Exodus xxvii 4).’
Basic definitions
From the OED via Briggs:
I
1658–: reticulate structures in animals
I
1839–: rivers and canals
I
1869–: railways
I
1883–: distribution network of electrical cables
I
1914–: wireless broadcasting networks
I
Natural → man-made
I
Physical connections → Wire-less connections →
abstract connections
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
Frame 12/49
Overview
Ancestry:
First known use: Geneva Bible, 1560
Plan
‘And thou shalt make unto it a grate like networke of
brass (Exodus xxvii 4).’
Basic definitions
From the OED via Briggs:
I
1658–: reticulate structures in animals
I
1839–: rivers and canals
I
1869–: railways
I
1883–: distribution network of electrical cables
I
1914–: wireless broadcasting networks
I
Natural → man-made
I
Physical connections → Wire-less connections →
abstract connections
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
Frame 12/49
Overview
Ancestry:
First known use: Geneva Bible, 1560
Plan
‘And thou shalt make unto it a grate like networke of
brass (Exodus xxvii 4).’
Basic definitions
From the OED via Briggs:
I
1658–: reticulate structures in animals
I
1839–: rivers and canals
I
1869–: railways
I
1883–: distribution network of electrical cables
I
1914–: wireless broadcasting networks
I
Natural → man-made
I
Physical connections → Wire-less connections →
abstract connections
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
Frame 12/49
Overview
Key Observation:
I
Many complex systems
can be viewed as complex networks
of physical or abstract interactions.
I
Opens door to mathematical and numerical analysis.
I
Dominant approach of last decade of a
theoretical-physics/stat-mechish flavor.
I
Mindboggling amount of work published on complex
networks since 1998...
I
... largely due to your typical theoretical physicist:
Plan
Basic definitions
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
Frame 13/49
Overview
Key Observation:
I
Many complex systems
can be viewed as complex networks
of physical or abstract interactions.
I
Opens door to mathematical and numerical analysis.
I
Dominant approach of last decade of a
theoretical-physics/stat-mechish flavor.
I
Mindboggling amount of work published on complex
networks since 1998...
I
... largely due to your typical theoretical physicist:
Plan
Basic definitions
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
Frame 13/49
Overview
Key Observation:
I
Many complex systems
can be viewed as complex networks
of physical or abstract interactions.
I
Opens door to mathematical and numerical analysis.
I
Dominant approach of last decade of a
theoretical-physics/stat-mechish flavor.
I
Mindboggling amount of work published on complex
networks since 1998...
I
... largely due to your typical theoretical physicist:
Plan
Basic definitions
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
Frame 13/49
Overview
Key Observation:
I
Many complex systems
can be viewed as complex networks
of physical or abstract interactions.
I
Opens door to mathematical and numerical analysis.
I
Dominant approach of last decade of a
theoretical-physics/stat-mechish flavor.
I
Mindboggling amount of work published on complex
networks since 1998...
I
... largely due to your typical theoretical physicist:
Plan
Basic definitions
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
Frame 13/49
Overview
Key Observation:
I
Many complex systems
can be viewed as complex networks
of physical or abstract interactions.
I
Opens door to mathematical and numerical analysis.
I
Dominant approach of last decade of a
theoretical-physics/stat-mechish flavor.
I
Mindboggling amount of work published on complex
networks since 1998...
I
... largely due to your typical theoretical physicist:
Plan
Basic definitions
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
Frame 13/49
Overview
Key Observation:
I
Many complex systems
can be viewed as complex networks
of physical or abstract interactions.
I
Opens door to mathematical and numerical analysis.
I
Dominant approach of last decade of a
theoretical-physics/stat-mechish flavor.
I
Mindboggling amount of work published on complex
networks since 1998...
I
... largely due to your typical theoretical physicist:
I
Piranha physicus
I
Hunt in packs.
I
Feast on new and interesting ideas
(see chaos, cellular automata, ...)
Plan
Basic definitions
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
Frame 13/49
Overview
Key Observation:
I
Many complex systems
can be viewed as complex networks
of physical or abstract interactions.
I
Opens door to mathematical and numerical analysis.
I
Dominant approach of last decade of a
theoretical-physics/stat-mechish flavor.
I
Mindboggling amount of work published on complex
networks since 1998...
I
... largely due to your typical theoretical physicist:
I
Piranha physicus
I
Hunt in packs.
I
Feast on new and interesting ideas
(see chaos, cellular automata, ...)
Plan
Basic definitions
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
Frame 13/49
Overview
Key Observation:
I
Many complex systems
can be viewed as complex networks
of physical or abstract interactions.
I
Opens door to mathematical and numerical analysis.
I
Dominant approach of last decade of a
theoretical-physics/stat-mechish flavor.
I
Mindboggling amount of work published on complex
networks since 1998...
I
... largely due to your typical theoretical physicist:
I
Piranha physicus
I
Hunt in packs.
I
Feast on new and interesting ideas
(see chaos, cellular automata, ...)
Plan
Basic definitions
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
Frame 13/49
Overview
Popularity (according to ISI Web of
Knowledge)
Plan
Basic definitions
“Collective dynamics of ‘small-world’ networks” [21]
I
I
I
Watts and Strogatz
Nature, 1998
Cited ≈ 4325 times (as of June 7, 2010)
Over 1100 citations in 2008.
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
“Emergence of scaling in random networks” [3]
I
Barabási and Albert
Science, 1999
I
Cited ≈ 4769 times (as of June 7, 2010)
I
Over 1100 citations in 2008.
Frame 14/49
Overview
Popularity according to books:
Plan
Basic definitions
Popularity
The Tipping Point: How Little Things can
make a Big Difference—Malcolm Gladwell [10]
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
Nexus: Small Worlds and the Groundbreaking
Science of Networks—Mark Buchanan
Frame 15/49
Overview
Popularity according to books:
Plan
Basic definitions
Popularity
Linked: How Everything Is Connected to
Everything Else and What It
Means—Albert-Laszlo Barabási
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
Six Degrees: The Science of a Connected
Age—Duncan Watts [20]
Frame 16/49
Overview
Numerous others:
I
Complex Social Networks—F. Vega-Redondo [19]
I
Fractal River Basins: Chance and Self-Organization—I.
Rodríguez-Iturbe and A. Rinaldo [16]
Plan
Basic definitions
Popularity
I
Random Graph Dynamics—R. Durette
Examples of
Complex Networks
I
Scale-Free Networks—Guido Caldarelli
Properties of
Complex Networks
I
Evolution and Structure of the Internet: A Statistical
Physics Approach—Romu Pastor-Satorras and
Alessandro Vespignani
I
Complex Graphs and Networks—Fan Chung
I
Social Network Analysis—Stanley Wasserman and
Kathleen Faust
I
Handbook of Graphs and Networks—Eds: Stefan
Bornholdt and H. G. Schuster [6]
I
Evolution of Networks—S. N. Dorogovtsev and J. F. F.
Mendes [9]
Nutshell
References
Frame 17/49
Overview
More observations
Plan
Basic definitions
I
But surely networks aren’t new...
I
Graph theory is well established...
I
Study of social networks started in the 1930’s...
I
So why all this ‘new’ research on networks?
I
Answer: Oodles of Easily Accessible Data.
I
We can now inform (alas) our theories
with a much more measurable reality.∗
I
A worthy goal: establish mechanistic explanations.
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
Frame 18/49
Overview
More observations
Plan
Basic definitions
I
But surely networks aren’t new...
I
Graph theory is well established...
I
Study of social networks started in the 1930’s...
I
So why all this ‘new’ research on networks?
I
Answer: Oodles of Easily Accessible Data.
I
We can now inform (alas) our theories
with a much more measurable reality.∗
I
A worthy goal: establish mechanistic explanations.
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
Frame 18/49
Overview
More observations
Plan
Basic definitions
I
But surely networks aren’t new...
I
Graph theory is well established...
I
Study of social networks started in the 1930’s...
I
So why all this ‘new’ research on networks?
I
Answer: Oodles of Easily Accessible Data.
I
We can now inform (alas) our theories
with a much more measurable reality.∗
I
A worthy goal: establish mechanistic explanations.
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
Frame 18/49
Overview
More observations
Plan
Basic definitions
I
But surely networks aren’t new...
I
Graph theory is well established...
I
Study of social networks started in the 1930’s...
I
So why all this ‘new’ research on networks?
I
Answer: Oodles of Easily Accessible Data.
I
We can now inform (alas) our theories
with a much more measurable reality.∗
I
A worthy goal: establish mechanistic explanations.
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
Frame 18/49
Overview
More observations
Plan
Basic definitions
I
But surely networks aren’t new...
I
Graph theory is well established...
I
Study of social networks started in the 1930’s...
I
So why all this ‘new’ research on networks?
I
Answer: Oodles of Easily Accessible Data.
I
We can now inform (alas) our theories
with a much more measurable reality.∗
I
A worthy goal: establish mechanistic explanations.
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
Frame 18/49
Overview
More observations
Plan
Basic definitions
I
But surely networks aren’t new...
I
Graph theory is well established...
I
Study of social networks started in the 1930’s...
I
So why all this ‘new’ research on networks?
I
Answer: Oodles of Easily Accessible Data.
I
We can now inform (alas) our theories
with a much more measurable reality.∗
I
A worthy goal: establish mechanistic explanations.
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
Frame 18/49
Overview
More observations
Plan
Basic definitions
I
But surely networks aren’t new...
I
Graph theory is well established...
I
Study of social networks started in the 1930’s...
I
So why all this ‘new’ research on networks?
I
Answer: Oodles of Easily Accessible Data.
I
We can now inform (alas) our theories
with a much more measurable reality.∗
I
A worthy goal: establish mechanistic explanations.
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
Frame 18/49
Overview
More observations
Plan
Basic definitions
I
But surely networks aren’t new...
I
Graph theory is well established...
I
Study of social networks started in the 1930’s...
I
So why all this ‘new’ research on networks?
I
Answer: Oodles of Easily Accessible Data.
I
We can now inform (alas) our theories
with a much more measurable reality.∗
I
A worthy goal: establish mechanistic explanations.
∗
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
If this is upsetting, maybe string theory is for you...
Frame 18/49
Overview
More observations
Plan
I
Web-scale data sets can be overly exciting.
Witness:
I
I
The End of Theory: The Data Deluge Makes the
Scientific Theory Obsolete (Anderson, Wired) ()
“The Unreasonable Effectiveness of Data,”
Halevy et al. [11] .
Basic definitions
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
But:
I
For scientists, description is only part of the battle.
I
We still need to understand.
Frame 19/49
Overview
More observations
Plan
I
Web-scale data sets can be overly exciting.
Witness:
I
I
The End of Theory: The Data Deluge Makes the
Scientific Theory Obsolete (Anderson, Wired) ()
“The Unreasonable Effectiveness of Data,”
Halevy et al. [11] .
Basic definitions
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
But:
I
For scientists, description is only part of the battle.
I
We still need to understand.
Frame 19/49
Overview
More observations
Plan
I
Web-scale data sets can be overly exciting.
Witness:
I
I
The End of Theory: The Data Deluge Makes the
Scientific Theory Obsolete (Anderson, Wired) ()
“The Unreasonable Effectiveness of Data,”
Halevy et al. [11] .
Basic definitions
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
But:
I
For scientists, description is only part of the battle.
I
We still need to understand.
Frame 19/49
Overview
More observations
Plan
I
Web-scale data sets can be overly exciting.
Witness:
I
I
The End of Theory: The Data Deluge Makes the
Scientific Theory Obsolete (Anderson, Wired) ()
“The Unreasonable Effectiveness of Data,”
Halevy et al. [11] .
Basic definitions
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
But:
I
For scientists, description is only part of the battle.
I
We still need to understand.
Frame 19/49
Overview
More observations
Plan
I
Web-scale data sets can be overly exciting.
Witness:
I
I
The End of Theory: The Data Deluge Makes the
Scientific Theory Obsolete (Anderson, Wired) ()
“The Unreasonable Effectiveness of Data,”
Halevy et al. [11] .
Basic definitions
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
But:
I
For scientists, description is only part of the battle.
I
We still need to understand.
Frame 19/49
Overview
Super Basic definitions
Plan
Basic definitions
Nodes = A collection of entities which have
properties that are somehow related to each other
I
e.g., people, forks in rivers, proteins, webpages,
organisms,...
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
Links = Connections between nodes
I
Links may be directed or undirected.
I
Links may be binary or weighted.
Other spiffing words: vertices and edges.
Frame 20/49
Overview
Super Basic definitions
Plan
Basic definitions
Nodes = A collection of entities which have
properties that are somehow related to each other
I
e.g., people, forks in rivers, proteins, webpages,
organisms,...
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
Links = Connections between nodes
I
Links may be directed or undirected.
I
Links may be binary or weighted.
Other spiffing words: vertices and edges.
Frame 20/49
Overview
Super Basic definitions
Plan
Basic definitions
Nodes = A collection of entities which have
properties that are somehow related to each other
I
e.g., people, forks in rivers, proteins, webpages,
organisms,...
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
Links = Connections between nodes
I
Links may be directed or undirected.
I
Links may be binary or weighted.
Other spiffing words: vertices and edges.
Frame 20/49
Overview
Super Basic definitions
Plan
Basic definitions
Nodes = A collection of entities which have
properties that are somehow related to each other
I
e.g., people, forks in rivers, proteins, webpages,
organisms,...
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
Links = Connections between nodes
I
Links may be directed or undirected.
I
Links may be binary or weighted.
Other spiffing words: vertices and edges.
Frame 20/49
Overview
Super Basic definitions
Plan
Basic definitions
Nodes = A collection of entities which have
properties that are somehow related to each other
I
e.g., people, forks in rivers, proteins, webpages,
organisms,...
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
Links = Connections between nodes
I
Links may be directed or undirected.
I
Links may be binary or weighted.
Other spiffing words: vertices and edges.
Frame 20/49
Overview
Super Basic definitions
Plan
Basic definitions
Nodes = A collection of entities which have
properties that are somehow related to each other
I
e.g., people, forks in rivers, proteins, webpages,
organisms,...
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
Links = Connections between nodes
I
Links may be directed or undirected.
I
Links may be binary or weighted.
Other spiffing words: vertices and edges.
Frame 20/49
Overview
Super Basic definitions
Plan
Basic definitions
Node degree = Number of links per node
I
Notation: Node i’s degree = ki .
I
ki = 0,1,2,. . . .
I
Notation: the average degree of a network = hk i
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
I
I
Connection between number of edges m and
average degree:
2m
hk i =
.
N
Defn: Ni = the set of i’s ki neighbors
Frame 21/49
Overview
Super Basic definitions
Plan
Basic definitions
Node degree = Number of links per node
I
Notation: Node i’s degree = ki .
I
ki = 0,1,2,. . . .
I
Notation: the average degree of a network = hk i
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
I
I
Connection between number of edges m and
average degree:
2m
hk i =
.
N
Defn: Ni = the set of i’s ki neighbors
Frame 21/49
Overview
Super Basic definitions
Plan
Basic definitions
Node degree = Number of links per node
I
Notation: Node i’s degree = ki .
I
ki = 0,1,2,. . . .
I
Notation: the average degree of a network = hk i
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
I
I
Connection between number of edges m and
average degree:
2m
hk i =
.
N
Defn: Ni = the set of i’s ki neighbors
Frame 21/49
Overview
Super Basic definitions
Plan
Basic definitions
Node degree = Number of links per node
I
Notation: Node i’s degree = ki .
I
ki = 0,1,2,. . . .
I
Notation: the average degree of a network = hk i
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
I
I
Connection between number of edges m and
average degree:
2m
hk i =
.
N
Defn: Ni = the set of i’s ki neighbors
Frame 21/49
Overview
Super Basic definitions
Plan
Basic definitions
Node degree = Number of links per node
I
Notation: Node i’s degree = ki .
I
ki = 0,1,2,. . . .
I
Notation: the average degree of a network = hk i
(and sometimes z)
I
I
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
Connection between number of edges m and
average degree:
2m
hk i =
.
N
Defn: Ni = the set of i’s ki neighbors
Frame 21/49
Overview
Super Basic definitions
Plan
Basic definitions
Node degree = Number of links per node
I
Notation: Node i’s degree = ki .
I
ki = 0,1,2,. . . .
I
Notation: the average degree of a network = hk i
(and sometimes z)
I
I
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
Connection between number of edges m and
average degree:
2m
hk i =
.
N
Defn: Ni = the set of i’s ki neighbors
Frame 21/49
Overview
Super Basic definitions
Plan
Basic definitions
Node degree = Number of links per node
I
Notation: Node i’s degree = ki .
I
ki = 0,1,2,. . . .
I
Notation: the average degree of a network = hk i
(and sometimes z)
I
I
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
Connection between number of edges m and
average degree:
2m
hk i =
.
N
Defn: Ni = the set of i’s ki neighbors
Frame 21/49
Overview
Super Basic definitions
Plan
Basic definitions
Adjacency matrix:
I
I
Popularity
We represent a directed network by a matrix A with
link weight aij for nodes i and j in entry (i, j).
e.g.,



A=


I
0
0
1
0
0
1
0
0
1
1
1
1
0
0
0
1
0
0
0
1
0
1
0
1
0

Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References





(n.b., for numerical work, we always use sparse
matrices.)
Frame 22/49
Overview
Super Basic definitions
Plan
Basic definitions
Adjacency matrix:
I
I
Popularity
We represent a directed network by a matrix A with
link weight aij for nodes i and j in entry (i, j).
e.g.,



A=


I
0
0
1
0
0
1
0
0
1
1
1
1
0
0
0
1
0
0
0
1
0
1
0
1
0

Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References





(n.b., for numerical work, we always use sparse
matrices.)
Frame 22/49
Overview
Super Basic definitions
Plan
Basic definitions
Adjacency matrix:
I
I
Popularity
We represent a directed network by a matrix A with
link weight aij for nodes i and j in entry (i, j).
e.g.,



A=


I
0
0
1
0
0
1
0
0
1
1
1
1
0
0
0
1
0
0
0
1
0
1
0
1
0

Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References





(n.b., for numerical work, we always use sparse
matrices.)
Frame 22/49
Overview
Examples
Plan
Basic definitions
Popularity
So what passes for a complex network?
Examples of
Complex Networks
I
Complex networks are large (in node number)
Properties of
Complex Networks
I
Complex networks are sparse (low edge to node
ratio)
References
I
Complex networks are usually dynamic and evolving
I
Complex networks can be social, economic, natural,
informational, abstract, ...
Nutshell
Frame 23/49
Overview
Examples
Plan
Basic definitions
Popularity
So what passes for a complex network?
Examples of
Complex Networks
I
Complex networks are large (in node number)
Properties of
Complex Networks
I
Complex networks are sparse (low edge to node
ratio)
References
I
Complex networks are usually dynamic and evolving
I
Complex networks can be social, economic, natural,
informational, abstract, ...
Nutshell
Frame 23/49
Overview
Examples
Plan
Basic definitions
Popularity
So what passes for a complex network?
Examples of
Complex Networks
I
Complex networks are large (in node number)
Properties of
Complex Networks
I
Complex networks are sparse (low edge to node
ratio)
References
I
Complex networks are usually dynamic and evolving
I
Complex networks can be social, economic, natural,
informational, abstract, ...
Nutshell
Frame 23/49
Overview
Examples
Plan
Basic definitions
Popularity
So what passes for a complex network?
Examples of
Complex Networks
I
Complex networks are large (in node number)
Properties of
Complex Networks
I
Complex networks are sparse (low edge to node
ratio)
References
I
Complex networks are usually dynamic and evolving
I
Complex networks can be social, economic, natural,
informational, abstract, ...
Nutshell
Frame 23/49
Overview
Examples
Plan
Basic definitions
Popularity
So what passes for a complex network?
Examples of
Complex Networks
I
Complex networks are large (in node number)
Properties of
Complex Networks
I
Complex networks are sparse (low edge to node
ratio)
References
I
Complex networks are usually dynamic and evolving
I
Complex networks can be social, economic, natural,
informational, abstract, ...
Nutshell
Frame 23/49
Overview
Examples
Plan
Physical networks
I
River networks
I
Neural networks
I
Trees and leaves
I
Blood networks
I
Basic definitions
Popularity
I
The Internet
I
Road networks
I
Power grids
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
Distribution (branching) vs. redistribution (cyclical)
Frame 24/49
Overview
Examples
Plan
Physical networks
I
River networks
I
Neural networks
I
Trees and leaves
I
Blood networks
I
Basic definitions
Popularity
I
The Internet
I
Road networks
I
Power grids
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
Distribution (branching) vs. redistribution (cyclical)
Frame 24/49
Overview
Examples
Plan
Physical networks
I
River networks
I
Neural networks
I
Trees and leaves
I
Blood networks
I
Basic definitions
Popularity
I
The Internet
I
Road networks
I
Power grids
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
Distribution (branching) vs. redistribution (cyclical)
Frame 24/49
Overview
Examples
Plan
Physical networks
I
River networks
I
Neural networks
I
Trees and leaves
I
Blood networks
I
Basic definitions
Popularity
I
The Internet
I
Road networks
I
Power grids
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
Distribution (branching) vs. redistribution (cyclical)
Frame 24/49
Overview
Examples
Plan
Physical networks
I
River networks
I
Neural networks
I
Trees and leaves
I
Blood networks
I
Basic definitions
Popularity
I
The Internet
I
Road networks
I
Power grids
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
Distribution (branching) vs. redistribution (cyclical)
Frame 24/49
Overview
Examples
Plan
Physical networks
I
River networks
I
Neural networks
I
Trees and leaves
I
Blood networks
I
Basic definitions
Popularity
I
The Internet
I
Road networks
I
Power grids
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
Distribution (branching) vs. redistribution (cyclical)
Frame 24/49
Overview
Examples
Plan
Physical networks
I
River networks
I
Neural networks
I
Trees and leaves
I
Blood networks
I
Basic definitions
Popularity
I
The Internet
I
Road networks
I
Power grids
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
Distribution (branching) vs. redistribution (cyclical)
Frame 24/49
Overview
Examples
Plan
Physical networks
I
River networks
I
Neural networks
I
Trees and leaves
I
Blood networks
I
Basic definitions
Popularity
I
The Internet
I
Road networks
I
Power grids
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
Distribution (branching) vs. redistribution (cyclical)
Frame 24/49
Overview
Examples
Interaction networks
I
The Blogosphere
I
Biochemical
networks
I
Gene-protein
networks
I
Food webs: who
eats whom
I
The World Wide
Web (?)
I
Airline networks
I
Call networks
(AT&T)
I
The Media
I
Paper citations
Plan
Basic definitions
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
datamining.typepad.com ()
Frame 25/49
Overview
Examples
Interaction networks
I
The Blogosphere
I
Biochemical
networks
I
Gene-protein
networks
I
Food webs: who
eats whom
I
The World Wide
Web (?)
I
Airline networks
I
Call networks
(AT&T)
I
The Media
I
Paper citations
Plan
Basic definitions
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
datamining.typepad.com ()
Frame 25/49
Overview
Examples
Interaction networks
I
The Blogosphere
I
Biochemical
networks
I
Gene-protein
networks
I
Food webs: who
eats whom
I
The World Wide
Web (?)
I
Airline networks
I
Call networks
(AT&T)
I
The Media
I
Paper citations
Plan
Basic definitions
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
datamining.typepad.com ()
Frame 25/49
Overview
Examples
Interaction networks
I
The Blogosphere
I
Biochemical
networks
I
Gene-protein
networks
I
Food webs: who
eats whom
I
The World Wide
Web (?)
I
Airline networks
I
Call networks
(AT&T)
I
The Media
I
Paper citations
Plan
Basic definitions
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
datamining.typepad.com ()
Frame 25/49
Overview
Examples
Interaction networks
I
The Blogosphere
I
Biochemical
networks
I
Gene-protein
networks
I
Food webs: who
eats whom
I
The World Wide
Web (?)
I
Airline networks
I
Call networks
(AT&T)
I
The Media
I
Paper citations
Plan
Basic definitions
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
datamining.typepad.com ()
Frame 25/49
Overview
Examples
Interaction networks
I
The Blogosphere
I
Biochemical
networks
I
Gene-protein
networks
I
Food webs: who
eats whom
I
The World Wide
Web (?)
I
Airline networks
I
Call networks
(AT&T)
I
The Media
I
Paper citations
Plan
Basic definitions
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
datamining.typepad.com ()
Frame 25/49
Overview
Examples
Interaction networks
I
The Blogosphere
I
Biochemical
networks
I
Gene-protein
networks
I
Food webs: who
eats whom
I
The World Wide
Web (?)
I
Airline networks
I
Call networks
(AT&T)
I
The Media
I
Paper citations
Plan
Basic definitions
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
datamining.typepad.com ()
Frame 25/49
Overview
Examples
Interaction networks
I
The Blogosphere
I
Biochemical
networks
I
Gene-protein
networks
I
Food webs: who
eats whom
I
The World Wide
Web (?)
I
Airline networks
I
Call networks
(AT&T)
I
The Media
I
Paper citations
Plan
Basic definitions
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
datamining.typepad.com ()
Frame 25/49
Overview
Examples
Interaction networks
I
The Blogosphere
I
Biochemical
networks
I
Gene-protein
networks
I
Food webs: who
eats whom
I
The World Wide
Web (?)
I
Airline networks
I
Call networks
(AT&T)
I
The Media
I
Paper citations
Plan
Basic definitions
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
datamining.typepad.com ()
Frame 25/49
Overview
Examples
Plan
Interaction networks:
social networks
Basic definitions
Popularity
I
Snogging
Examples of
Complex Networks
I
Friendships
Properties of
Complex Networks
I
Acquaintances
I
Boards and
directors
I
Organizations
I
facebook.com (),
twitter.com ()
I
Nutshell
References
(Bearman et al., 2004)
‘Remotely sensed’ by: email activity, instant
messaging, phone logs (*cough*).
Frame 26/49
Overview
Examples
Plan
Interaction networks:
social networks
Basic definitions
Popularity
I
Snogging
Examples of
Complex Networks
I
Friendships
Properties of
Complex Networks
I
Acquaintances
I
Boards and
directors
I
Organizations
I
facebook.com (),
twitter.com ()
I
Nutshell
References
(Bearman et al., 2004)
‘Remotely sensed’ by: email activity, instant
messaging, phone logs (*cough*).
Frame 26/49
Overview
Examples
Plan
Interaction networks:
social networks
Basic definitions
Popularity
I
Snogging
Examples of
Complex Networks
I
Friendships
Properties of
Complex Networks
I
Acquaintances
I
Boards and
directors
I
Organizations
I
facebook.com (),
twitter.com ()
I
Nutshell
References
(Bearman et al., 2004)
‘Remotely sensed’ by: email activity, instant
messaging, phone logs (*cough*).
Frame 26/49
Overview
Examples
Plan
Interaction networks:
social networks
Basic definitions
Popularity
I
Snogging
Examples of
Complex Networks
I
Friendships
Properties of
Complex Networks
I
Acquaintances
I
Boards and
directors
I
Organizations
I
facebook.com (),
twitter.com ()
I
Nutshell
References
(Bearman et al., 2004)
‘Remotely sensed’ by: email activity, instant
messaging, phone logs (*cough*).
Frame 26/49
Overview
Examples
Plan
Interaction networks:
social networks
Basic definitions
Popularity
I
Snogging
Examples of
Complex Networks
I
Friendships
Properties of
Complex Networks
I
Acquaintances
I
Boards and
directors
I
Organizations
I
facebook.com (),
twitter.com ()
I
Nutshell
References
(Bearman et al., 2004)
‘Remotely sensed’ by: email activity, instant
messaging, phone logs (*cough*).
Frame 26/49
Overview
Examples
Plan
Interaction networks:
social networks
Basic definitions
Popularity
I
Snogging
Examples of
Complex Networks
I
Friendships
Properties of
Complex Networks
I
Acquaintances
I
Boards and
directors
I
Organizations
I
facebook.com (),
twitter.com ()
I
Nutshell
References
(Bearman et al., 2004)
‘Remotely sensed’ by: email activity, instant
messaging, phone logs (*cough*).
Frame 26/49
Overview
Examples
Plan
Interaction networks:
social networks
Basic definitions
Popularity
I
Snogging
Examples of
Complex Networks
I
Friendships
Properties of
Complex Networks
I
Acquaintances
I
Boards and
directors
I
Organizations
I
facebook.com (),
twitter.com ()
I
Nutshell
References
(Bearman et al., 2004)
‘Remotely sensed’ by: email activity, instant
messaging, phone logs (*cough*).
Frame 26/49
Overview
Examples
Plan
Interaction networks:
social networks
Basic definitions
Popularity
I
Snogging
Examples of
Complex Networks
I
Friendships
Properties of
Complex Networks
I
Acquaintances
I
Boards and
directors
I
Organizations
I
facebook.com (),
twitter.com ()
I
Nutshell
References
(Bearman et al., 2004)
‘Remotely sensed’ by: email activity, instant
messaging, phone logs (*cough*).
Frame 26/49
Overview
Examples
Plan
Basic definitions
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
Frame 27/49
Overview
Examples
Relational networks
Plan
Consumer purchases
Basic definitions
I
Thesauri: Networks of words generated by meanings
Examples of
Complex Networks
I
Knowledge/Databases/Ideas
Properties of
Complex Networks
I
Metadata—Tagging: del.icio.us (), flickr ()
I
Popularity
Nutshell
References
Frame 28/49
Overview
Examples
Relational networks
Plan
Consumer purchases
(Wal-Mart: ≈ 1 petabyte = 1015 bytes)
Popularity
I
Thesauri: Networks of words generated by meanings
Examples of
Complex Networks
I
Knowledge/Databases/Ideas
Properties of
Complex Networks
I
Metadata—Tagging: del.icio.us (), flickr ()
I
Basic definitions
Nutshell
References
Frame 28/49
Overview
Examples
Relational networks
Plan
Consumer purchases
(Wal-Mart: ≈ 1 petabyte = 1015 bytes)
Popularity
I
Thesauri: Networks of words generated by meanings
Examples of
Complex Networks
I
Knowledge/Databases/Ideas
Properties of
Complex Networks
I
Metadata—Tagging: del.icio.us (), flickr ()
I
Basic definitions
Nutshell
References
Frame 28/49
Overview
Examples
Relational networks
Plan
Consumer purchases
(Wal-Mart: ≈ 1 petabyte = 1015 bytes)
Popularity
I
Thesauri: Networks of words generated by meanings
Examples of
Complex Networks
I
Knowledge/Databases/Ideas
Properties of
Complex Networks
I
Metadata—Tagging: del.icio.us (), flickr ()
I
Basic definitions
Nutshell
References
Frame 28/49
Overview
Examples
Plan
I
login | register | help Basic definitions
Consumer purchases
15
Popularity
(Wal-Mart: ≈ 1 petabyte = 10 bytes)
Thesauri:
i/Main_Page
06
popular | recent
Relational networks
I
Networks of words generated
del.icio.usby meanings
search
I
Knowledge/Databases/Ideas
I
Metadata—Tagging: del.icio.us (), flickr ()
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
common tags
cloud | list
community daily dictionary education
encyclopedia
english free imported info information internet knowledge
learning
news
resources
search
reference
tools
useful
research
web
web2.0
resource
wiki
wikipedia
Frame 28/49
iterations of the FR algorithm.
Connections. The journal connections shown in the map are
given by M’, not the FR algorithm. They are thus not artifacts of
the visualization.
Clustering. The FR algorithm will pull together small-scale
clusters of journals that are strongly connected in M’. The
appearance of small-scale journal clusters is thus directly related to
centrality rankings and an alternative model of journal relations
derived from classification data.
Clickworthy Science:
A clickstream map of science
Any interpretation of the visual structure of the map in Fig. 5
will be governed by the following considerations:
Overview
Plan
Basic definitions
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
Bollen et al. [5]
Figure 5. Map of science derived from clickstream data. Circles represent individual journals. The lines that connect journals are the edges of
the clickstream model in M’. Colors correspond to the AAT classification of the journal. Labels have been assigned to local clusters of journals that
correspond to particular scientific disciplines.
doi:10.1371/journal.pone.0004803.g005
PLoS ONE | www.plosone.org
5
March 2009 | Volume 4 | Issue 3 | e4803
Frame 29/49
Overview
A notable feature of large-scale networks:
I
Graphical renderings are often just a big mess.
Plan
Basic definitions
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
I
And even when renderings somehow look good:
I
We need to extract digestible, meaningful aspects.
Frame 30/49
Overview
A notable feature of large-scale networks:
I
Graphical renderings are often just a big mess.
Plan
Basic definitions
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
I
And even when renderings somehow look good:
I
We need to extract digestible, meaningful aspects.
Frame 30/49
Overview
A notable feature of large-scale networks:
I
Graphical renderings are often just a big mess.
Plan
Basic definitions
Popularity
⇐ Typical hairball
I
number of nodes N = 500
I
number of edges m = 1000
I
average degree hk i = ?
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
I
And even when renderings somehow look good:
I
We need to extract digestible, meaningful aspects.
References
Frame 30/49
Overview
A notable feature of large-scale networks:
I
Graphical renderings are often just a big mess.
Plan
Basic definitions
Popularity
⇐ Typical hairball
I
number of nodes N = 500
I
number of edges m = 1000
I
average degree hk i = ?
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
I
And even when renderings somehow look good:
I
We need to extract digestible, meaningful aspects.
References
Frame 30/49
Overview
A notable feature of large-scale networks:
I
Graphical renderings are often just a big mess.
Plan
Basic definitions
Popularity
⇐ Typical hairball
I
number of nodes N = 500
I
number of edges m = 1000
I
average degree hk i = ?
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
I
References
And even when renderings somehow look good:
“That is a very graphic analogy which aids
understanding wonderfully while being, strictly
speaking, wrong in every possible way”
said Ponder [Stibbons] —Making Money, T. Pratchett.
I
We need to extract digestible, meaningful aspects.
Frame 30/49
Overview
A notable feature of large-scale networks:
I
Graphical renderings are often just a big mess.
Plan
Basic definitions
Popularity
⇐ Typical hairball
I
number of nodes N = 500
I
number of edges m = 1000
I
average degree hk i = ?
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
I
References
And even when renderings somehow look good:
“That is a very graphic analogy which aids
understanding wonderfully while being, strictly
speaking, wrong in every possible way”
said Ponder [Stibbons] —Making Money, T. Pratchett.
I
We need to extract digestible, meaningful aspects.
Frame 30/49
Overview
A notable feature of large-scale networks:
I
Graphical renderings are often just a big mess.
Plan
Basic definitions
Popularity
⇐ Typical hairball
I
number of nodes N = 500
I
number of edges m = 1000
I
average degree hk i = 4
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
I
References
And even when renderings somehow look good:
“That is a very graphic analogy which aids
understanding wonderfully while being, strictly
speaking, wrong in every possible way”
said Ponder [Stibbons] —Making Money, T. Pratchett.
I
We need to extract digestible, meaningful aspects.
Frame 30/49
Overview
Properties
Plan
Basic definitions
Some key features of real complex networks:
I
I
Degree
distribution
Popularity
I
Concurrency
Examples of
Complex Networks
I
Hierarchical
scaling
Properties of
Complex Networks
Nutshell
References
I
Assortativity
I
Homophily
I
Network distances
I
Clustering
I
Centrality
I
Motifs
I
Efficiency
I
Modularity
I
Robustness
Coevolution of network structure
and processes on networks.
Frame 31/49
Overview
Properties
Plan
Basic definitions
1. Degree distribution Pk
I
Pk is the probability that a randomly selected node
has degree k
I
Big deal: Form of Pk key to network’s behavior
I
ex 1: Erdős-Rényi random networks have a Poisson
distribution:
Pk = e−hk i hk ik /k !
I
ex 2: “Scale-free” networks: Pk ∝ k −γ ⇒ ‘hubs’
I
We’ll come back to this business soon...
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
Frame 32/49
Overview
Properties
Plan
Basic definitions
1. Degree distribution Pk
I
Pk is the probability that a randomly selected node
has degree k
I
Big deal: Form of Pk key to network’s behavior
I
ex 1: Erdős-Rényi random networks have a Poisson
distribution:
Pk = e−hk i hk ik /k !
I
ex 2: “Scale-free” networks: Pk ∝ k −γ ⇒ ‘hubs’
I
We’ll come back to this business soon...
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
Frame 32/49
Overview
Properties
Plan
Basic definitions
1. Degree distribution Pk
I
Pk is the probability that a randomly selected node
has degree k
I
Big deal: Form of Pk key to network’s behavior
I
ex 1: Erdős-Rényi random networks have a Poisson
distribution:
Pk = e−hk i hk ik /k !
I
ex 2: “Scale-free” networks: Pk ∝ k −γ ⇒ ‘hubs’
I
We’ll come back to this business soon...
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
Frame 32/49
Overview
Properties
Plan
Basic definitions
1. Degree distribution Pk
I
Pk is the probability that a randomly selected node
has degree k
I
Big deal: Form of Pk key to network’s behavior
I
ex 1: Erdős-Rényi random networks have a Poisson
distribution:
Pk = e−hk i hk ik /k !
I
ex 2: “Scale-free” networks: Pk ∝ k −γ ⇒ ‘hubs’
I
We’ll come back to this business soon...
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
Frame 32/49
Overview
Properties
Plan
Basic definitions
1. Degree distribution Pk
I
Pk is the probability that a randomly selected node
has degree k
I
Big deal: Form of Pk key to network’s behavior
I
ex 1: Erdős-Rényi random networks have a Poisson
distribution:
Pk = e−hk i hk ik /k !
I
ex 2: “Scale-free” networks: Pk ∝ k −γ ⇒ ‘hubs’
I
We’ll come back to this business soon...
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
Frame 32/49
Overview
Properties
Plan
2. Assortativity/3. Homophily:
Basic definitions
Popularity
I
Social networks: Homophily () = birds of a feather
Examples of
Complex Networks
I
e.g., degree is standard property for sorting:
measure degree-degree correlations.
Properties of
Complex Networks
I
Assortative network: [14] similar degree nodes
connecting to each other.
I
Disassortative network: high degree nodes
connecting to low degree nodes.
Nutshell
References
Frame 33/49
Overview
Properties
Plan
2. Assortativity/3. Homophily:
Basic definitions
Popularity
I
Social networks: Homophily () = birds of a feather
Examples of
Complex Networks
I
e.g., degree is standard property for sorting:
measure degree-degree correlations.
Properties of
Complex Networks
I
Assortative network: [14] similar degree nodes
connecting to each other.
I
Disassortative network: high degree nodes
connecting to low degree nodes.
Nutshell
References
Frame 33/49
Overview
Properties
Plan
2. Assortativity/3. Homophily:
Basic definitions
Popularity
I
Social networks: Homophily () = birds of a feather
Examples of
Complex Networks
I
e.g., degree is standard property for sorting:
measure degree-degree correlations.
Properties of
Complex Networks
I
Assortative network: [14] similar degree nodes
connecting to each other.
I
Disassortative network: high degree nodes
connecting to low degree nodes.
Nutshell
References
Frame 33/49
Overview
Properties
Plan
2. Assortativity/3. Homophily:
Basic definitions
Popularity
I
Social networks: Homophily () = birds of a feather
Examples of
Complex Networks
I
e.g., degree is standard property for sorting:
measure degree-degree correlations.
Properties of
Complex Networks
I
Assortative network: [14] similar degree nodes
connecting to each other.
I
Disassortative network: high degree nodes
connecting to low degree nodes.
Nutshell
References
Frame 33/49
Overview
Properties
Plan
2. Assortativity/3. Homophily:
Basic definitions
Popularity
I
Social networks: Homophily () = birds of a feather
Examples of
Complex Networks
I
e.g., degree is standard property for sorting:
measure degree-degree correlations.
Properties of
Complex Networks
I
Assortative network: [14] similar degree nodes
connecting to each other.
I
I
Nutshell
References
Often social: company directors, coauthors, actors.
Disassortative network: high degree nodes
connecting to low degree nodes.
Frame 33/49
Overview
Properties
Plan
2. Assortativity/3. Homophily:
Basic definitions
Popularity
I
Social networks: Homophily () = birds of a feather
Examples of
Complex Networks
I
e.g., degree is standard property for sorting:
measure degree-degree correlations.
Properties of
Complex Networks
I
Assortative network: [14] similar degree nodes
connecting to each other.
I
I
Nutshell
References
Often social: company directors, coauthors, actors.
Disassortative network: high degree nodes
connecting to low degree nodes.
I
Often techological or biological: Internet, protein
interactions, neural networks, food webs.
Frame 33/49
Overview
Properties
Plan
4. Clustering:
Basic definitions
I
Your friends tend to know each other.
I
Two measures:
*P
C1 =
j1 j2 ∈Ni
aj1 j2
ki (ki − 1)/2
C2 =
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
+
due to Watts & Strogatz [21]
i
Nutshell
References
3 × #triangles
due to Newman [15]
#triples
I
C1 is the average fraction of pairs of neighbors who
are connected.
I
Interpret C2 as probability two of a node’s friends
know each other.
Frame 34/49
Overview
Properties
Plan
4. Clustering:
Basic definitions
I
Your friends tend to know each other.
I
Two measures:
*P
C1 =
j1 j2 ∈Ni
aj1 j2
ki (ki − 1)/2
C2 =
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
+
due to Watts & Strogatz [21]
i
Nutshell
References
3 × #triangles
due to Newman [15]
#triples
I
C1 is the average fraction of pairs of neighbors who
are connected.
I
Interpret C2 as probability two of a node’s friends
know each other.
Frame 34/49
Overview
Properties
Plan
4. Clustering:
Basic definitions
I
Your friends tend to know each other.
I
Two measures:
*P
C1 =
j1 j2 ∈Ni
aj1 j2
ki (ki − 1)/2
C2 =
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
+
due to Watts & Strogatz [21]
i
Nutshell
References
3 × #triangles
due to Newman [15]
#triples
I
C1 is the average fraction of pairs of neighbors who
are connected.
I
Interpret C2 as probability two of a node’s friends
know each other.
Frame 34/49
Overview
Properties
Plan
4. Clustering:
Basic definitions
I
Your friends tend to know each other.
I
Two measures:
*P
C1 =
j1 j2 ∈Ni
aj1 j2
ki (ki − 1)/2
C2 =
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
+
due to Watts & Strogatz [21]
i
Nutshell
References
3 × #triangles
due to Newman [15]
#triples
I
C1 is the average fraction of pairs of neighbors who
are connected.
I
Interpret C2 as probability two of a node’s friends
know each other.
Frame 34/49
Overview
Properties
Plan
4. Clustering:
Basic definitions
I
Your friends tend to know each other.
I
Two measures:
*P
C1 =
j1 j2 ∈Ni
aj1 j2
ki (ki − 1)/2
C2 =
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
+
due to Watts & Strogatz [21]
i
Nutshell
References
3 × #triangles
due to Newman [15]
#triples
I
C1 is the average fraction of pairs of neighbors who
are connected.
I
Interpret C2 as probability two of a node’s friends
know each other.
Frame 34/49
Overview
Properties
Plan
Basic definitions
Popularity
5. Motifs:
I
Small, recurring functional subnetworks
I
e.g., Feed Forward Loop:
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
Shen-Orr, Uri Alon, et al. [17]
Frame 35/49
Overview
Properties
letter
Plan
Basic definitions
Network motifs in the transcriptional regulation
Popularity
network of Escherichia coli
Examples of
5. Motifs:
Shai S. Shen-Orr1, Ron Milo2, Shmoolik Mangan1 & Uri Alon1,2
I
Small, recurring functional subnetworks
I
e.g., Feed Forward Loop:
© 2002 Nature Publishing Group http://genetics.nature.com
Published online: 22 April 2002, DOI: 10.1038/ng881
a
Nutshell
feedforward loop
X
b
Shen-Orr, Uri Alon, et al. [17]
X
Y
Y
Z
n
crp
araC
araBAD
c
single input module (SIM)
X
Z1 Z2
d
Complex Networks
Properties of
Complex Networks
X
... Zn
n
Little is known about the design principles1–10 of tra
tional regulation networks References
that control gene express
cells. Recent advances in data collection and analysi
however, are generating unprecedented amounts of in
tion about gene regulation networks. To understand
complex wiring diagrams1–10,13, we sought to break dow
networks into basic building blocks2. We generalize the
of motifs, widely used for sequence analysis, to the le
networks. We define ‘network motifs’ as patterns of in
nections that recur in many different parts of a network
quencies much higher than those found in rando
networks. We applied new algorithms for system
detecting network motifs to one of the best-characteriz
ulation networks, that of direct transcriptional interact
Escherichia coli3,6. We find that much of the network i
posed of repeated appearances of three highly sign
motifs. Each network motif has a specific function in det
ing gene expression, such as generating temporal exp
programs and governing the responses to fluctuating e
signals. The motif structure also allows an easily interp
view of the entire known transcriptional network of the
ism. This approach may helpFrame
define the
basic comput
35/49
elements of other biological networks.
We compiled a data set of direct transcriptional inter
between transcription factors and the operons they regul
operon is a group of contiguous genes that are transcribed
Overview
Properties
6. modularity:
Plan
Basic definitions
Popularity
49
53
58
63
46
83
28
33
25
11
97
88
1
59
67
73
105
103
24
50
89
69
110
109
36
57
44
90
66
91
31
86
112
0
18
54
92
7
104
29
8
41
61
94
35
78
68
21
55
77
10
111
81
71
99
19
22
3
30
101
79
108
51
52
85
38
84
98
2
107
40
References
80
48
9
23
Nutshell
82
75
93
34
42
16
5
Properties of
Complex Networks
37
45
4
Examples of
Complex Networks
114
74
113
76
60
17
39
72
102
6
47
70
26
14
95
13
100
43
62
27
12
96
15
65
106
64
32
20
87
56
Clauset et al., 2006 [7] : NCAA football
Frame 36/49
Overview
Properties
Plan
Basic definitions
Popularity
7. Concurrency:
I
Transmission of a contagious element only occurs
during contact [13]
I
Rather obvious but easily missed in a simple model
I
Dynamic property—static networks are not enough
I
Knowledge of previous contacts crucial
I
Beware cumulated network data!
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
Frame 37/49
Overview
Properties
Plan
Basic definitions
Popularity
7. Concurrency:
I
Transmission of a contagious element only occurs
during contact [13]
I
Rather obvious but easily missed in a simple model
I
Dynamic property—static networks are not enough
I
Knowledge of previous contacts crucial
I
Beware cumulated network data!
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
Frame 37/49
Overview
Properties
Plan
Basic definitions
Popularity
7. Concurrency:
I
Transmission of a contagious element only occurs
during contact [13]
I
Rather obvious but easily missed in a simple model
I
Dynamic property—static networks are not enough
I
Knowledge of previous contacts crucial
I
Beware cumulated network data!
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
Frame 37/49
Overview
Properties
Plan
Basic definitions
Popularity
7. Concurrency:
I
Transmission of a contagious element only occurs
during contact [13]
I
Rather obvious but easily missed in a simple model
I
Dynamic property—static networks are not enough
I
Knowledge of previous contacts crucial
I
Beware cumulated network data!
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
Frame 37/49
Overview
Properties
Plan
Basic definitions
Popularity
7. Concurrency:
I
Transmission of a contagious element only occurs
during contact [13]
I
Rather obvious but easily missed in a simple model
I
Dynamic property—static networks are not enough
I
Knowledge of previous contacts crucial
I
Beware cumulated network data!
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
Frame 37/49
Overview
Properties
8. Horton-Strahler stream ordering:
I
Plan
Basic definitions
Metrics for branching networks:
I
I
I
I
Popularity
Method for ordering streams hierarchically
Reveals fractal nature of natural branching networks
Hierarchy is not pure but mixed (Tokunaga). [18, 8]
Major examples: rivers and blood networks.
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
(a)
I
(b)
(c)
Beautifully described but poorly explained.
Frame 38/49
Overview
Properties
8. Horton-Strahler stream ordering:
I
Plan
Basic definitions
Metrics for branching networks:
I
I
I
I
Popularity
Method for ordering streams hierarchically
Reveals fractal nature of natural branching networks
Hierarchy is not pure but mixed (Tokunaga). [18, 8]
Major examples: rivers and blood networks.
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
(a)
I
(b)
(c)
Beautifully described but poorly explained.
Frame 38/49
Overview
Properties
8. Horton-Strahler stream ordering:
I
Plan
Basic definitions
Metrics for branching networks:
I
I
I
I
Popularity
Method for ordering streams hierarchically
Reveals fractal nature of natural branching networks
Hierarchy is not pure but mixed (Tokunaga). [18, 8]
Major examples: rivers and blood networks.
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
(a)
I
(b)
(c)
Beautifully described but poorly explained.
Frame 38/49
Overview
Properties
8. Horton-Strahler stream ordering:
I
Plan
Basic definitions
Metrics for branching networks:
I
I
I
I
Popularity
Method for ordering streams hierarchically
Reveals fractal nature of natural branching networks
Hierarchy is not pure but mixed (Tokunaga). [18, 8]
Major examples: rivers and blood networks.
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
(a)
I
(b)
(c)
Beautifully described but poorly explained.
Frame 38/49
Overview
Properties
8. Horton-Strahler stream ordering:
I
Plan
Basic definitions
Metrics for branching networks:
I
I
I
I
Popularity
Method for ordering streams hierarchically
Reveals fractal nature of natural branching networks
Hierarchy is not pure but mixed (Tokunaga). [18, 8]
Major examples: rivers and blood networks.
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
(a)
I
(b)
(c)
Beautifully described but poorly explained.
Frame 38/49
Overview
Properties
8. Horton-Strahler stream ordering:
I
Plan
Basic definitions
Metrics for branching networks:
I
I
I
I
Popularity
Method for ordering streams hierarchically
Reveals fractal nature of natural branching networks
Hierarchy is not pure but mixed (Tokunaga). [18, 8]
Major examples: rivers and blood networks.
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
(a)
I
(b)
(c)
Beautifully described but poorly explained.
Frame 38/49
Overview
Properties
Plan
Basic definitions
9. Network distances:
Popularity
(a) shortest path length dij :
Examples of
Complex Networks
I
Fewest number of steps between nodes i and j.
I
(Also called the chemical distance between i and j.)
Properties of
Complex Networks
Nutshell
References
(b) average path length hdij i:
I
Average shortest path length in whole network.
I
Good algorithms exist for calculation.
I
Weighted links can be accommodated.
Frame 39/49
Overview
Properties
Plan
Basic definitions
9. Network distances:
Popularity
(a) shortest path length dij :
Examples of
Complex Networks
I
Fewest number of steps between nodes i and j.
I
(Also called the chemical distance between i and j.)
Properties of
Complex Networks
Nutshell
References
(b) average path length hdij i:
I
Average shortest path length in whole network.
I
Good algorithms exist for calculation.
I
Weighted links can be accommodated.
Frame 39/49
Overview
Properties
Plan
Basic definitions
9. Network distances:
Popularity
(a) shortest path length dij :
Examples of
Complex Networks
I
Fewest number of steps between nodes i and j.
I
(Also called the chemical distance between i and j.)
Properties of
Complex Networks
Nutshell
References
(b) average path length hdij i:
I
Average shortest path length in whole network.
I
Good algorithms exist for calculation.
I
Weighted links can be accommodated.
Frame 39/49
Overview
Properties
Plan
Basic definitions
9. Network distances:
Popularity
(a) shortest path length dij :
Examples of
Complex Networks
I
Fewest number of steps between nodes i and j.
I
(Also called the chemical distance between i and j.)
Properties of
Complex Networks
Nutshell
References
(b) average path length hdij i:
I
Average shortest path length in whole network.
I
Good algorithms exist for calculation.
I
Weighted links can be accommodated.
Frame 39/49
Overview
Properties
Plan
Basic definitions
9. Network distances:
Popularity
(a) shortest path length dij :
Examples of
Complex Networks
I
Fewest number of steps between nodes i and j.
I
(Also called the chemical distance between i and j.)
Properties of
Complex Networks
Nutshell
References
(b) average path length hdij i:
I
Average shortest path length in whole network.
I
Good algorithms exist for calculation.
I
Weighted links can be accommodated.
Frame 39/49
Overview
Properties
Plan
Basic definitions
9. Network distances:
Popularity
(a) shortest path length dij :
Examples of
Complex Networks
I
Fewest number of steps between nodes i and j.
I
(Also called the chemical distance between i and j.)
Properties of
Complex Networks
Nutshell
References
(b) average path length hdij i:
I
Average shortest path length in whole network.
I
Good algorithms exist for calculation.
I
Weighted links can be accommodated.
Frame 39/49
Overview
Properties
Plan
Basic definitions
9. Network distances:
Popularity
(a) shortest path length dij :
Examples of
Complex Networks
I
Fewest number of steps between nodes i and j.
I
(Also called the chemical distance between i and j.)
Properties of
Complex Networks
Nutshell
References
(b) average path length hdij i:
I
Average shortest path length in whole network.
I
Good algorithms exist for calculation.
I
Weighted links can be accommodated.
Frame 39/49
Overview
Properties
Plan
Basic definitions
9. Network distances:
Popularity
(a) shortest path length dij :
Examples of
Complex Networks
I
Fewest number of steps between nodes i and j.
I
(Also called the chemical distance between i and j.)
Properties of
Complex Networks
Nutshell
References
(b) average path length hdij i:
I
Average shortest path length in whole network.
I
Good algorithms exist for calculation.
I
Weighted links can be accommodated.
Frame 39/49
Overview
Properties
Plan
Basic definitions
9. Network distances:
Popularity
Examples of
Complex Networks
(c) Network diameter dmax :
I
Maximum shortest path length in network.
(d) Closeness dcl = [
P
ij
dij −1 /
n
2
Properties of
Complex Networks
Nutshell
References
−1
] :
I
Average ‘distance’ between any two nodes.
I
Closeness handles disconnected networks (dij = ∞)
I
dcl = ∞ only when all nodes are isolated.
Frame 40/49
Overview
Properties
Plan
Basic definitions
9. Network distances:
Popularity
Examples of
Complex Networks
(c) Network diameter dmax :
I
Maximum shortest path length in network.
(d) Closeness dcl = [
P
ij
dij −1 /
n
2
Properties of
Complex Networks
Nutshell
References
−1
] :
I
Average ‘distance’ between any two nodes.
I
Closeness handles disconnected networks (dij = ∞)
I
dcl = ∞ only when all nodes are isolated.
Frame 40/49
Overview
Properties
Plan
Basic definitions
9. Network distances:
Popularity
Examples of
Complex Networks
(c) Network diameter dmax :
I
Maximum shortest path length in network.
(d) Closeness dcl = [
P
ij
dij −1 /
n
2
Properties of
Complex Networks
Nutshell
References
−1
] :
I
Average ‘distance’ between any two nodes.
I
Closeness handles disconnected networks (dij = ∞)
I
dcl = ∞ only when all nodes are isolated.
Frame 40/49
Overview
Properties
Plan
Basic definitions
9. Network distances:
Popularity
Examples of
Complex Networks
(c) Network diameter dmax :
I
Maximum shortest path length in network.
(d) Closeness dcl = [
P
ij
dij −1 /
n
2
Properties of
Complex Networks
Nutshell
References
−1
] :
I
Average ‘distance’ between any two nodes.
I
Closeness handles disconnected networks (dij = ∞)
I
dcl = ∞ only when all nodes are isolated.
Frame 40/49
Overview
Properties
Plan
Basic definitions
9. Network distances:
Popularity
Examples of
Complex Networks
(c) Network diameter dmax :
I
Maximum shortest path length in network.
(d) Closeness dcl = [
P
ij
dij −1 /
n
2
Properties of
Complex Networks
Nutshell
References
−1
] :
I
Average ‘distance’ between any two nodes.
I
Closeness handles disconnected networks (dij = ∞)
I
dcl = ∞ only when all nodes are isolated.
Frame 40/49
Overview
Properties
Plan
Basic definitions
9. Network distances:
Popularity
Examples of
Complex Networks
(c) Network diameter dmax :
I
Maximum shortest path length in network.
(d) Closeness dcl = [
P
ij
dij −1 /
n
2
Properties of
Complex Networks
Nutshell
References
−1
] :
I
Average ‘distance’ between any two nodes.
I
Closeness handles disconnected networks (dij = ∞)
I
dcl = ∞ only when all nodes are isolated.
Frame 40/49
Overview
Properties
Plan
Basic definitions
10. Centrality:
I
Many such measures of a node’s ‘importance.’
I
ex 1: Degree centrality: ki .
I
ex 2: Node i’s betweenness
= fraction of shortest paths that pass through i.
I
ex 3: Edge `’s betweenness
= fraction of shortest paths that travel along `.
I
ex 4: Recursive centrality: Hubs and Authorities (Jon
Kleinberg [12] )
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
Frame 41/49
Overview
Properties
Plan
Basic definitions
10. Centrality:
I
Many such measures of a node’s ‘importance.’
I
ex 1: Degree centrality: ki .
I
ex 2: Node i’s betweenness
= fraction of shortest paths that pass through i.
I
ex 3: Edge `’s betweenness
= fraction of shortest paths that travel along `.
I
ex 4: Recursive centrality: Hubs and Authorities (Jon
Kleinberg [12] )
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
Frame 41/49
Overview
Properties
Plan
Basic definitions
10. Centrality:
I
Many such measures of a node’s ‘importance.’
I
ex 1: Degree centrality: ki .
I
ex 2: Node i’s betweenness
= fraction of shortest paths that pass through i.
I
ex 3: Edge `’s betweenness
= fraction of shortest paths that travel along `.
I
ex 4: Recursive centrality: Hubs and Authorities (Jon
Kleinberg [12] )
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
Frame 41/49
Overview
Properties
Plan
Basic definitions
10. Centrality:
I
Many such measures of a node’s ‘importance.’
I
ex 1: Degree centrality: ki .
I
ex 2: Node i’s betweenness
= fraction of shortest paths that pass through i.
I
ex 3: Edge `’s betweenness
= fraction of shortest paths that travel along `.
I
ex 4: Recursive centrality: Hubs and Authorities (Jon
Kleinberg [12] )
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
Frame 41/49
Overview
Properties
Plan
Basic definitions
10. Centrality:
I
Many such measures of a node’s ‘importance.’
I
ex 1: Degree centrality: ki .
I
ex 2: Node i’s betweenness
= fraction of shortest paths that pass through i.
I
ex 3: Edge `’s betweenness
= fraction of shortest paths that travel along `.
I
ex 4: Recursive centrality: Hubs and Authorities (Jon
Kleinberg [12] )
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
Frame 41/49
Overview
Properties
Plan
Basic definitions
10. Centrality:
I
Many such measures of a node’s ‘importance.’
I
ex 1: Degree centrality: ki .
I
ex 2: Node i’s betweenness
= fraction of shortest paths that pass through i.
I
ex 3: Edge `’s betweenness
= fraction of shortest paths that travel along `.
I
ex 4: Recursive centrality: Hubs and Authorities (Jon
Kleinberg [12] )
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
Frame 41/49
Overview
Nutshell:
Plan
Overview Key Points:
Basic definitions
Popularity
I
The field of complex networks came into existence in
the late 1990s.
I
Explosion of papers and interest since 1998/99.
I
Hardened up much thinking about complex systems.
I
Specific focus on networks that are large-scale,
sparse, natural or man-made, evolving and dynamic,
and (crucially) measurable.
Three main (blurred) categories:
I
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
1. Physical (e.g., river networks),
2. Interactional (e.g., social networks),
3. Abstract (e.g., thesauri).
Frame 42/49
Overview
Nutshell:
Plan
Overview Key Points:
Basic definitions
Popularity
I
The field of complex networks came into existence in
the late 1990s.
I
Explosion of papers and interest since 1998/99.
I
Hardened up much thinking about complex systems.
I
Specific focus on networks that are large-scale,
sparse, natural or man-made, evolving and dynamic,
and (crucially) measurable.
Three main (blurred) categories:
I
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
1. Physical (e.g., river networks),
2. Interactional (e.g., social networks),
3. Abstract (e.g., thesauri).
Frame 42/49
Overview
Nutshell:
Plan
Overview Key Points:
Basic definitions
Popularity
I
The field of complex networks came into existence in
the late 1990s.
I
Explosion of papers and interest since 1998/99.
I
Hardened up much thinking about complex systems.
I
Specific focus on networks that are large-scale,
sparse, natural or man-made, evolving and dynamic,
and (crucially) measurable.
Three main (blurred) categories:
I
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
1. Physical (e.g., river networks),
2. Interactional (e.g., social networks),
3. Abstract (e.g., thesauri).
Frame 42/49
Overview
Nutshell:
Plan
Overview Key Points:
Basic definitions
Popularity
I
The field of complex networks came into existence in
the late 1990s.
I
Explosion of papers and interest since 1998/99.
I
Hardened up much thinking about complex systems.
I
Specific focus on networks that are large-scale,
sparse, natural or man-made, evolving and dynamic,
and (crucially) measurable.
Three main (blurred) categories:
I
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
1. Physical (e.g., river networks),
2. Interactional (e.g., social networks),
3. Abstract (e.g., thesauri).
Frame 42/49
Overview
Nutshell:
Plan
Overview Key Points:
Basic definitions
Popularity
I
The field of complex networks came into existence in
the late 1990s.
I
Explosion of papers and interest since 1998/99.
I
Hardened up much thinking about complex systems.
I
Specific focus on networks that are large-scale,
sparse, natural or man-made, evolving and dynamic,
and (crucially) measurable.
Three main (blurred) categories:
I
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
1. Physical (e.g., river networks),
2. Interactional (e.g., social networks),
3. Abstract (e.g., thesauri).
Frame 42/49
Overview
Nutshell:
Overview Key Points (cont.):
I
I
I
Obvious connections with the vast extant field of
graph theory.
But focus on dynamics is more of a
physics/stat-mech/comp-sci flavor.
Two main areas of focus:
Plan
Basic definitions
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
1. Description: Characterizing very large networks
2. Explanation: Micro story ⇒ Macro features
I
Some essential structural aspects are understood:
degree distribution, clustering, assortativity, group
structure, overall structure,...
I
Still much work to be done, especially with respect to
dynamics...
Frame 43/49
Overview
Nutshell:
Overview Key Points (cont.):
I
I
I
Obvious connections with the vast extant field of
graph theory.
But focus on dynamics is more of a
physics/stat-mech/comp-sci flavor.
Two main areas of focus:
Plan
Basic definitions
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
1. Description: Characterizing very large networks
2. Explanation: Micro story ⇒ Macro features
I
Some essential structural aspects are understood:
degree distribution, clustering, assortativity, group
structure, overall structure,...
I
Still much work to be done, especially with respect to
dynamics...
Frame 43/49
Overview
Nutshell:
Overview Key Points (cont.):
I
I
I
Obvious connections with the vast extant field of
graph theory.
But focus on dynamics is more of a
physics/stat-mech/comp-sci flavor.
Two main areas of focus:
Plan
Basic definitions
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
1. Description: Characterizing very large networks
2. Explanation: Micro story ⇒ Macro features
I
Some essential structural aspects are understood:
degree distribution, clustering, assortativity, group
structure, overall structure,...
I
Still much work to be done, especially with respect to
dynamics...
Frame 43/49
Overview
Nutshell:
Overview Key Points (cont.):
I
I
I
Obvious connections with the vast extant field of
graph theory.
But focus on dynamics is more of a
physics/stat-mech/comp-sci flavor.
Two main areas of focus:
Plan
Basic definitions
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
1. Description: Characterizing very large networks
2. Explanation: Micro story ⇒ Macro features
I
Some essential structural aspects are understood:
degree distribution, clustering, assortativity, group
structure, overall structure,...
I
Still much work to be done, especially with respect to
dynamics...
Frame 43/49
Overview
Nutshell:
Overview Key Points (cont.):
I
I
I
Obvious connections with the vast extant field of
graph theory.
But focus on dynamics is more of a
physics/stat-mech/comp-sci flavor.
Two main areas of focus:
Plan
Basic definitions
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
1. Description: Characterizing very large networks
2. Explanation: Micro story ⇒ Macro features
I
Some essential structural aspects are understood:
degree distribution, clustering, assortativity, group
structure, overall structure,...
I
Still much work to be done, especially with respect to
dynamics...
Frame 43/49
Overview
References I
[1] R. Albert and A.-L. Barabási.
Statistical mechanics of complex networks.
Rev. Mod. Phys., 74:47–97, 2002. pdf ()
[2] P. W. Anderson.
More is different.
Science, 177(4047):393–396, August 1972. pdf ()
Plan
Basic definitions
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
[3] A.-L. Barabási and R. Albert.
Emergence of scaling in random networks.
Science, 286:509–511, 1999. pdf ()
[4] S. Boccaletti, V. Latora, Y. Moreno, M. Chavez,
and D.-U. Hwang.
Complex networks: Structure and dynamics.
Physics Reports, 424:175–308, 2006. pdf ()
Frame 44/49
Overview
References II
[5] J. Bollen, H. Van de Sompel, A. Hagberg,
L. Bettencourt, R. Chute, M. A. Rodriguez, and
B. Lyudmila.
Clickstream data yields high-resolution maps of
science.
PLoS ONE, 4:e4803, 2009. pdf ()
Plan
Basic definitions
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
[6] S. Bornholdt and H. G. Schuster, editors.
Handbook of Graphs and Networks.
Wiley-VCH, Berlin, 2003.
References
[7] A. Clauset, C. Moore, and M. E. J. Newman.
Structural inference of hierarchies in networks, 2006.
pdf ()
[8] P. S. Dodds and D. H. Rothman.
Unified view of scaling laws for river networks.
Physical Review E, 59(5):4865–4877, 1999. pdf ()
Frame 45/49
Overview
References III
Plan
[9] S. N. Dorogovtsev and J. F. F. Mendes.
Evolution of Networks.
Oxford University Press, Oxford, UK, 2003.
[10] M. Gladwell.
The Tipping Point.
Little, Brown and Company, New York, 2000.
Basic definitions
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
[11] A. Halevy, P. Norvig, and F. Pereira.
The unreasonable effectiveness of data.
IEEE Intelligent Systems, 24:8–12, 2009. pdf ()
[12] J. M. Kleinberg.
Authoritative sources in a hyperlinked environment.
Proc. 9th ACM-SIAM Symposium on Discrete
Algorithms, 1998. pdf ()
Frame 46/49
Overview
References IV
[13] M. Kretzschmar and M. Morris.
Measures of concurrency in networks and the spread
of infectious disease.
Math. Biosci., 133:165–95, 1996. pdf ()
[14] M. Newman.
Assortative mixing in networks.
Phys. Rev. Lett., 89:208701, 2002. pdf ()
Plan
Basic definitions
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
[15] M. E. J. Newman.
The structure and function of complex networks.
SIAM Review, 45(2):167–256, 2003. pdf ()
[16] I. Rodríguez-Iturbe and A. Rinaldo.
Fractal River Basins: Chance and Self-Organization.
Cambridge University Press, Cambrigde, UK, 1997.
Frame 47/49
Overview
References V
[17] S. S. Shen-Orr, R. Milo, S. Mangan, and U. Alon.
Network motifs in the transcriptional regulation
network of Escherichia coli.
Nature Genetics, pages 64–68, 2002. pdf ()
[18] E. Tokunaga.
The composition of drainage network in Toyohira
River Basin and the valuation of Horton’s first law.
Geophysical Bulletin of Hokkaido University, 15:1–19,
1966.
Plan
Basic definitions
Popularity
Examples of
Complex Networks
Properties of
Complex Networks
Nutshell
References
[19] F. Vega-Redondo.
Complex Social Networks.
Cambridge University Press, 2007.
[20] D. J. Watts.
Six Degrees.
Norton, New York, 2003.
Frame 48/49
Overview
References VI
Plan
Basic definitions
Popularity
Examples of
Complex Networks
[21] D. J. Watts and S. J. Strogatz.
Collective dynamics of ‘small-world’ networks.
Nature, 393:440–442, 1998. pdf ()
Properties of
Complex Networks
Nutshell
References
Frame 49/49