Complex networks : structure, robustness, and function

Examining important results and analytical techniques, this graduate-level textbook is a step-by-step presentation of the structure and function of complex networks. Using a range of examples, from the stability of the internet to efficient methods of immunizing populations, and from epidemic spreading to how one might efficiently search for individuals, this textbook explains the theoretical methods that can be used, and the experimental and analytical results obtained in the study and research of complex networks. Giving detailed derivations of many results in complex networks theory, this is an ideal text to be used by graduate students entering the field. End-of-chapter review questions help students monitor their own understanding of the materials presented. Half-title......Page 3 Title......Page 5 Copyright......Page 6 Contents......Page 7 1 Introduction......Page 11 1.2 Scale-free processes and fractal structures......Page 14 Part I Random Network Models......Page 17 2.1 Erdos–Rényi graphs......Page 19 2.2 Scale-free networks......Page 20 2.3 Diameter and fractal dimensions......Page 22 2.4 Random graphs as a model of real networks......Page 23 2.5 Outlook and applications......Page 24 3.1.1 Computer networks and the Internet......Page 26 3.1.3 Virtual technological networks and the WWW......Page 27 3.1.6 Biological networks......Page 29 3.2.1 Degree distribution......Page 31 3.2.4 Clustering......Page 34 3.2.6 Modular and hierarchical networks......Page 36 3.3 Betweenness centrality what is your importance in the network?......Page 37 3.4 Conclusions......Page 39 4.2.1 Introduction......Page 41 4.2.2 Clustering in a small-world network......Page 43 4.3.1 Introduction......Page 45 4.3.2 Random regular graphs......Page 46 4.3.3 Generalized random graphs......Page 47 4.3.4 A related model......Page 48 4.5.1 Introduction......Page 49 4.5.2 Generalized randomly directed graphs......Page 50 4.6.1 Introduction......Page 51 4.6.2 Defining the model......Page 52 4.6.3 Additional methods......Page 54 4.6.4 Random geometrical graphs, continuum percolation, and ad hoc networks......Page 55 4.7 Hierarchical and fractal networks......Page 58 Exercises......Page 59 5.1 The Barabasi–Albert model......Page 61 5.1.1 Analysis......Page 62 5.2.1 Non-linear growing models......Page 64 5.2.3 Copying models......Page 66 5.3 Linearized chord diagram (LCD)......Page 67 5.4 Fitness models......Page 69 Exercises......Page 72 Part II Structure and Robustness of Complex Networks......Page 73 6.1 Introduction......Page 75 6.2 Minimal distance networks......Page 77 6.3 Random scale-free networks......Page 79 6.4.1 Description......Page 82 6.4.2 Theory......Page 83 6.4.3 Simulations......Page 86 6.4.4 Bounds and implications......Page 87 6.5 Discussion and conclusions......Page 89 Exercises......Page 90 7 Self-similarity in complex networks......Page 91 8 Distances in geographically embedded networks......Page 98 9.2.1 Condition for the existence of a giant component......Page 101 9.2.2 Generating functions......Page 103 9.3.1 Description......Page 104 Exercises......Page 105 10.1 Introduction......Page 107 10.2.2 Critical threshold for percolation......Page 108 10.2.3 Scale-free networks......Page 110 10.3.1 Description......Page 111 10.3.2 Theory......Page 112 10.4.1 Introduction......Page 115 10.4.2 Size of the giant component at criticality......Page 116 10.4.3 Finite component size distribution......Page 119 10.4.5 Fractal and upper critical dimensions......Page 121 10.5 Percolation in networks with correlations......Page 124 10.5.1 Percolation in correlated scale-free networks......Page 125 10.6 k-core percolation: fault tolerant networks......Page 126 10.7 Conclusions......Page 130 Exercises......Page 131 11.1 Introduction......Page 133 11.3 The giant component......Page 134 11.4 Percolation in directed scale-free networks......Page 135 11.5 Critical exponents......Page 138 11.5.1 Size of the giant component......Page 139 11.5.2 Finite component sizes......Page 140 Exercises......Page 141 12.1 Introduction......Page 143 12.2 Random weighted networks......Page 144 12.3 Correlated weighted networks......Page 150 Exercises......Page 152 Part III Network function: Dynamics and Applications......Page 153 13.1 Introduction......Page 155 13.2 Optimization analysis......Page 156 13.3 General results......Page 159 13.4 Summary......Page 162 14.1 Introduction......Page 164 14.2 Epidemic dynamics and epidemiological models......Page 165 14.2.1 The SIS model......Page 166 The SIS model in networks......Page 167 The SIR model as bond percolation......Page 168 14.2.3 The SIRS model......Page 169 Exercises......Page 170 15.1 Random immunization......Page 171 15.2 Targeted immunization: choosing the right people to immunize......Page 172 15.3.1 Description......Page 173 15.3.2 Analysis......Page 174 15.3.3 Discussion......Page 177 15.3.4 Practical issues......Page 179 15.5 Conclusion......Page 180 Exercises......Page 182 16.1 Introduction......Page 183 16.2 The Ising model in complex networks......Page 184 16.2.1 The critical temperature......Page 186 16.2.2 The critical exponents......Page 187 16.3 Summary......Page 189 Exercises......Page 190 17.1 The spectrum of the adjacency matrix......Page 191 17.2 The Laplacian......Page 192 17.3 The spectral gap and diffusion on graphs......Page 194 17.3.1 The spectral gap......Page 195 17.3.2 Expander graphs......Page 196 17.3.3 Expansion of random networks......Page 199 17.5 Summary......Page 201 Exercises......Page 202 18.2 Searching using degrees......Page 203 18.3 Searching in networks using shortcuts......Page 205 18.4 Summary......Page 208 Exercises......Page 209 19 Biological networks and network motifs......Page 210 19.3 Network motifs......Page 211 19.4 Summary......Page 216 A.1 Probabilities and distributions......Page 217 A.2 Continuous variables and probability densities......Page 218 A.3 Conditional probabilities and Bayes’ rule......Page 219 A.4 Branching processes......Page 220 A.5.1 Abelian and Tauberian theorems......Page 221 Exercises......Page 222 Exercises......Page 223 C.1.1 Generating scale-free networks......Page 225 C.1.2 Simulation of random breakdown......Page 226 C.3 Networks with different properties: Metropolis style algorithms......Page 227 C.4 Finding shortest and optimal paths......Page 229 C.6 Finding communities in networks......Page 230 References......Page 232 Index......Page 246 Machine generated contents note: 1. Introduction; Part I. Random Network Models: 2. The Erdos-Renyi models; 3. Observations in real-world networks; 4. Models for complex networks; 5. Growing network models; Part II. Structure and Robustness of Complex Networks: 6. Distances in scale-free networks - the ultra small world; 7. Self-similarity in complex networks; 8. Distances in geographically embedded networks; 9. The network's structure - the generating function method; 10. Percolation on complex networks; 11. Structure of random directed networks - the bow tie; 12. Introducing weights - bandwidth allocation and multimedia broadcasting; Part III. Network Function - Dynamics and Applications: 13. Optimization of the network structure; 14. Epidemiological models; 15. Immunization; 16. Thermodynamic models on networks; 17. Spectral properties, transport, diffusion and dynamics; 18. Searching in networks; 19. Biological networks and network motifs; Part IV. Appendices; References; Index. "Examining important results and analytical techniques, this graduate-level textbook is a step-by-step presentation of the structure and function of complex networks. From the stability of the Internet to efficient methods of immunizing populations, from the spread of epidemics to how to search efficiently for individuals, this textbook explains the theoretical methods used, and the experimental and analytical results obtained. Ideal for graduate students entering this field, it gives detailed derivations of many results in complex networks theory. End-of-chapter review questions help students monitor their understanding of the materials presented"-- Provided by publisher