iv CONTENT S
5.3. A general rando m grap h mode l 9 7
5.4. Size , volume an d highe r orde r volume s 9 7
5.5. Basi c properties o f G(w) 100
5.6. Neighborhoo d expansio n i n rando m graph s 103
5.7. A random powe r la w grap h mode l 107
5.8. Actua l versu s expecte d degre e sequenc e 109
Chapter 6 . Th e Ris e of the Gian t Componen t 113
6.1. N o giant componen t if w 1? 114
6.2. I s there a giant componen t if w 1? 115
6.3. N o giant componen t if w 1? 116
6.4. Existenc e an d uniquenes s o f the gian t componen t 117
6.5. A lemma o n neighborhood growt h 126
6.6. Th e volum e o f the gian t componen t 129
6.7. Provin g th e volum e estimat e o f the gian t componen t 131
6.8. Lowe r bound s fo r th e volum e o f the gian t componen t 136
6.9. Th e complemen t o f the gian t componen t an d it s siz e 138
6.10. Comparin g theoretica l result s wit h th e collaboratio n grap h 141
Chapter 7 . Averag e Distanc e an d th e Diamete r 143
7.1. Th e smal l world phenomeno n 143
7.2. Preliminarie s o n the averag e distanc e an d diamete r 144
7.3. A lower boun d lemm a 146
7.4. A n uppe r boun d fo r th e averag e distanc e an d diamete r 147
7.5. Averag e distanc e an d diamete r o f random powe r la w graphs 149
7.6. Example s an d remark s 158
Chapter 8 . Eigenvalue s o f the Adjacenc y Matri x o f G(w) 161
8.1. Th e spectra l radiu s o f a graph 161
8.2. Th e Perron-Frobeniu s Theore m an d severa l usefu l fact s 162
8.3. Tw o lowe r bound s fo r th e spectra l radiu s 163
8.4. A n eigenvalu e uppe r boun d fo r G(w ) 164
8.5. Eigenvalu e theorem s fo r G(w ) 165
8.6. Example s an d counterexample s 169
8.7. Th e spectru m o f the adjacenc y matri x o f power la w graph s 170
Chapter 9 . Th e Semi-Circl e La w fo r G(w ) 173
9.1. Rando m matrice s an d Wigner' s semi-circl e la w 173
9.2. Thre e spectr a o f a grap h 174
9.3. Th e Laplacia n o f a graph 175
9.4. Th e Laplacia n o f a random grap h i n G(w ) 176
9.5. A bound fo r rando m graph s wit h larg e minimu m degre e 177
9.6. Th e semi-circl e la w for Laplacia n eigenvalue s o f graphs 179
9.7. A n uppe r boun d o n the spectra l nor m o f the Laplacia n 180
9.8. Implication s o f Laplacian eigenvalue s fo r G(w ) 185
9.9. A n exampl e o f eigenvalues o f a random powe r la w grap h 187
Chapter 10. Couplin g On-lin e an d Off-lin e Analyse s o f Rando m Graph s 189
10.1. On-lin e versu s off-lin e 189
10.2. Comparin g rando m graph s 190
Previous Page Next Page