Network Science: Theory and Applications

1 Origins 1

1.1 What Is Network Science?, 5

1.2 A Brief History of Network Science, 8

1.3 General Principles, 19

2 Graphs 23

2.1 Set-Theoretic Definition of a Graph, 25

2.2 Matrix Algebra Definition of a Graph, 33

2.3 The Bridges of Ko¨nigsberg Graph, 38

2.4 Spectral Properties of Graphs, 42

2.5 Types of Graphs, 46

2.6 Topological Structure, 54

2.7 Graphs in Software, 63

2.8 Exercises, 68

3 Regular Networks 71

3.1 Diameter, Centrality, and Average Path Length, 74

3.2 Binary Tree Network, 79

3.3 Toroidal Network, 85

3.4 Hypercube Networks, 89

3.5 Exercises, 95

4 Random Networks 97

4.1 Generation of Random Networks, 100

4.2 Degree Distribution of Random Networks, 106

4.3 Entropy of Random Networks, 110

4.4 Properties of Random Networks, 118

4.5 Weak Ties in Random Networks, 125

4.6 Randomization of Regular Networks, 127

4.7 Analysis, 128

4.8 Exercises, 129

5 Small-World Networks 131

5.1 Generating a Small-World Network, 135

5.2 Properties of Small-World Networks, 142

5.3 Phase Transition, 156

5.4 Navigating Small Worlds, 160

5.5 Weak Ties in Small-World Networks, 169

5.6 Analysis, 171

5.7 Exercises, 173

6 Scale-Free Networks 177

6.1 Generating a Scale-Free Network, 180

6.2 Properties of Scale-Free Networks, 190

6.3 Navigation in Scale-Free Networks, 203

6.4 Analysis, 207

6.5 Exercises, 214

7 Emergence 217

7.1 What is Network Emergence?, 219

7.2 Emergence in the Sciences, 223

7.3 Genetic Evolution, 225

7.4 Designer Networks, 233

7.5 Permutation Network Emergence, 243

7.6 An Application of Emergence, 252

7.7 Exercises, 258

8 Epidemics 261

8.1 Epidemic Models, 264

8.2 Persistent Epidemics in Networks, 275

8.3 Network Epidemic Simulation Software, 287

8.4 Countermeasures, 289

8.5 Exercises, 297

9 Synchrony 299

9.1 To Sync or Not to Sync, 300

9.2 A Cricket Social Network, 307

9.3 Kirchhoff Networks, 324

9.4 Pointville Electric Power Grid, 331

9.5 Exercises, 335

10 Influence Networks 337

10.1 Anatomy of Buzz, 340

10.2 Power in Social Networks, 347

10.3 Conflict in I-Nets, 357

10.4 Command Hierarchies, 360

10.5 Emergent Power in I-Nets, 362

10.6 Exercises, 371

11 Vulnerability 375

11.1 Network Risk, 378

11.2 Critical Node Analysis, 382

11.3 Game Theory Considerations, 407

11.4 The General Attacker–Defender Network Risk Problem, 408

11.5 Critical Link Analysis, 410

11.6 Stability Resilience in Kirchhoff Networks, 428

11.7 Exercises, 430

12 NetGain 433

12.1 Classical Diffusion Equations, 436

12.2 Multiproduct Networks, 443

12.3 Java Method for Netgain Emergence, 447

12.4 Nascent Market Networks, 448

12.5 Creative Destruction Networks, 453

12.6 Merger and Acquisition Networks, 463

12.7 Exercises, 466

13 Biology 469

13.1 Static Models, 471

13.2 Dynamic Analysis, 475

13.3 Protein Expression Networks, 481

13.4 Mass Kinetics Modeling, 484

13.5 Exercises, 490

Bibliography 493

About the Author 503

Index 505