Contents
Preface vi i
Chapter 1. Grap h Theor y i n the Informatio n Ag e 1
1.1. Introductio n 1
1.2. Basi c definition s 3
1.3. Degre e sequence s an d th e powe r la w 6
1.4. Histor y o f the powe r la w 8
1.5. Example s o f power la w graphs 10
1.6. A n outlin e o f the boo k 17
Chapter 2 . Ol d an d Ne w Concentratio n Inequalitie s 2 1
2.1. Th e binomia l distributio n an d it s asymptoti c behavio r 2 1
2.2. Genera l Chernof f inequalitie s 2 5
2.3. Mor e concentratio n inequalitie s 3 0
2.4. A concentration inequalit y wit h a larg e erro r estimat e 3 3
2.5. Martingale s an d Azuma' s inequalit y 3 5
2.6. Genera l martingal e inequalitie s 3 8
2.7. Supermartingale s an d Submartingale s 4 1
2.8. Th e decisio n tre e an d relaxe d concentratio n inequalitie s 4 6
Chapter 3 . A Generativ e Mode l the Preferentia l Attachmen t Schem e 5 5
3.1. Basi c step s o f the preferentia l attachmen t schem e 5 5
3.2. Analyzin g th e preferentia l attachmen t mode l 5 6
3.3. A useful lemm a fo r rigorou s proof s 5 9
3.4. Th e peri l o f heuristics vi a a n exampl e o f balls-and-bin s 6 0
3.5. Scale-fre e network s 6 2
3.6. Th e shar p concentratio n o f preferential attachmen t schem e 6 4
3.7. Model s fo r directe d graph s 7 0
Chapter 4 . Duplicatio n Model s fo r Biologica l Network s 7 5
4.1. Biologica l network s 7 5
4.2. Th e duplicatio n mode l 7 6
4.3. Expecte d degree s o f a random grap h i n th e duplicatio n mode l 7 7
4.4. Th e convergenc e o f the expecte d degree s 7 9
4.5. Th e generatin g function s fo r th e expecte d degree s 8 3
4.6. Tw o concentratio n result s fo r th e duplicatio n mode l 8 4
4.7. Powe r la w distributio n o f generalized duplicatio n model s 8 9
Chapter 5 . Rando m Graph s wit h Give n Expecte d Degree s 9 1
5.1. Th e Erdos-Reny i mode l 9
5.2. Th e diamete r o f G
n v
9 5
Previous Page Next Page