Complex Networks: A Networking and Signal Processing Perspective

The Up-to-Date Guide to Complex Networks for Students, Researchers, and Practitioners   Networks with complex and irregular connectivity patterns appear in biology, chemistry, communications, social networks, transportation systems, power grids, the Internet, and many big data applications. Complex Networks offers a novel engineering perspective on these networks, focusing on their key communications, networking, and signal processing dimensions.   Three leading researchers draw on recent advances to illuminate the design and characterization of complex computer networks and graph signal processing systems. The authors cover both the fundamental concepts underlying graph theory and complex networks, as well as current theory and research. They discuss spectra and signal processing in complex networks, graph signal processing approaches for extracting information from structural data, and advanced techniques for multiscale analysis. What makes networks complex, and how to successfully characterize them Graph theory foundations, definitions, and concepts Full chapters on small-world, scale-free, small-world wireless mesh, and small-world wireless sensor networks Complex network spectra and graph signal processing concepts and techniques Multiscale analysis via transforms and wavelets

Table of Contents:
Preface xvii Acknowledgments xxi About the Authors xxvii About the Cover xxxi   Chapter 1: Introduction 1 1.1 Complex Networks 1 1.2 Types of Complex Networks 3 1.3 Benefits of Studying Complex Networks 5 1.4 Challenges in Studying Complex Networks 8 1.5 What This Book Offers 9 1.6 Organization of the Book 9 1.7 Support Materials Available for Instructors 12 1.8 Summary 12   Chapter 2: Graph Theory Preliminaries 13 2.1 Introduction 13 2.2 Graphs 15 2.3 Matrices Related to a Graph 18 2.4 Basic Graph Metrics 23 2.5 Basic Graph Definitions and Properties 27 2.6 Types of Graphs 41 2.7 Other Important Measures for Graphs 48 2.8 Graph Pathfinding Algorithms 49 2.9 Summary 53   Chapter 3: Introduction to Complex Networks 59 3.1 Major Types of Complex Networks 59 3.2 Complex Network Metrics 62 3.3 Community Detection in Complex Networks 70 3.4 Entropy in Complex Network 84 3.5 Random Networks 96 3.6 Open Research Issues 100 3.7 Summary 101   Chapter 4: Small-World Networks 107 4.1 Introduction 107 4.2 Milgram’s Small-World Experiment 109 4.3 Characteristics of Small-World Networks 110 4.4 Real-World Small-World Networks 114 4.5 Creation and Evolution of Small-World Networks 117 4.6 Capacity-Based Deterministic Addition of New Links 125 4.7 Creation of Deterministic Small-World Networks 130 4.8 Anchor Points in a String Topology Small-World Network 134 4.9 Heuristic Approach-Based Deterministic Link Addition 139 4.10 Routing in Small-World Networks 159 4.11 Capacity of Small-World Networks 166 4.12 Open Research Issues 168 4.13 Summary 169   Chapter 5: Scale-Free Networks 177 5.1 Introduction 177 5.2 Characteristics of Scale-Free Networks 179 5.3 Real-World Scale-Free Networks 183 5.4 Scale-Free Network Formation 196 5.5 Preferential Attachment–Based Scale-Free Network Creation 198 5.6 Fitness-Based Scale-Free Network Creation 200 5.7 Varying Intrinsic Fitness-Based Scale-Free Network Creation 202 5.8 Optimization-Based Scale-Free Network Creation 203 5.9 Scale-Free Network Creation with Exponent 1 206 5.10 Greedy Global Decision–Based Scale-Free Network Creation 208 5.11 Deterministic Scale-Free Network Creation 213 5.12 Open Research Issues 215 5.13 Summary 216   Chapter 6: Small-World Wireless Mesh Networks 221 6.1 Introduction 221 6.2 Classification of Small-World Wireless Mesh Networks 224 6.3 Creation of Random Long-Ranged Links 225 6.4 Small-World Based on Pure Random Link Addition 228 6.5 Small-World Based on Euclidean Distance 229 6.6 Realization of Small-World Networks Based on Antenna Metrics 230 6.7 Algorithmic Approaches to Create Small-World Wireless Mesh Networks 234 6.8 Gateway-Router-Centric Small-World Network Formation 237 6.9 Creation of Deterministic Small-World Wireless Mesh Networks 245 6.10 Creation of Non-Persistent Small-World Wireless Mesh Networks 248 6.11 Non-Persistent Routing in Small-World Wireless Mesh Networks 252 6.12 Qualitative Comparison of Existing Solutions 257 6.13 Open Research Issues 260 6.14 Summary 261   Chapter 7: Small-World Wireless Sensor Networks 267 7.1 Introduction 267 7.2 Small-World Wireless Mesh Networks vs. Small-World Wireless Sensor Networks 269 7.3 Why Small-World Wireless Sensor Networks? 271 7.4 Challenges in Transforming WSNs to SWWSNs 275 7.5 Types of Long-Ranged Links for SWWSNs 277 7.6 Approaches for Transforming WSNs to SWWSNs 278 7.7 SWWSNs with Wired LLs 299 7.8 Open Research Issues 301 7.9 Summary 304   Chapter 8: Spectra of Complex Networks 309 8.1 Introduction 309 8.2 Spectrum of a Graph 310 8.3 Adjacency Matrix Spectrum of a Graph 312 8.4 Adjacency Matrix Spectra of Complex Networks 316 8.5 Laplacian Spectrum of a Graph 322 8.6 Laplacian Spectra of Complex Networks 331 8.7 Network Classification Using Spectral Densities 335 8.8 Open Research Issues 335 8.9 Summary 336   Chapter 9: Signal Processing on Complex Networks 341 9.1 Introduction to Graph Signal Processing 341 9.2 Comparison between Classical and Graph Signal Processing 345 9.3 The Graph Laplacian as an Operator 348 9.4 Quantifying Variations in Graph Signals 349 9.5 Graph Fourier Transform 351 9.6 Generalized Operators for Graph Signals 361 9.7 Applications 367 9.8 Windowed Graph Fourier Transform 381 9.9 Open Research Issues 383 9.10 Summary 385   Chapter 10: Graph Signal Processing Approaches 393 10.1 Introduction 393 10.2 Graph Signal Processing Based on Laplacian Matrix 394 10.3 DSPG Framework 394 10.4 DSPG Framework Based on Weight Matrix 397 10.5 DSPG Framework Based on Directed Laplacian 405 10.6 Comparison of Graph Signal Processing Approaches 415 10.7 Open Research Issues 416 10.8 Summary 417   Chapter 11: Multiscale Analysis of Complex Networks 429 11.1 Introduction 429 11.2 Multiscale Transforms for Complex Network Data 430 11.3 Crovella and Kolaczyk Wavelet Transform 432 11.4 Random Transform 435 11.5 Lifting-Based Wavelets 437 11.6 Two-Channel Graph Wavelet Filter Banks 439 11.7 Spectral Graph Wavelet Transform 446 11.8 Spectral Graph Wavelet Transform Based on Directed Laplacian 450 11.9 Diffusion Wavelets 454 11.10 Open Research Issues 455 11.11 Summary 456   Appendix A: Vectors and Matrices 461 A.1 Vectors and Norms 461 A.2 Matrices 462 A.3 Eigenvalues and Eigenvectors 464 A.4 Matrix Diagonalization 466 A.5 Jordan Decomposition 466 A.6 Spectral Density 467 A.7 Wigner’s Semicircle Law 468 A.8 Gershgorin’s Theorem 469   Appendix B: Classical Signal Processing 471 B.1 Linear Time Invariant Filters 471 B.2 Fourier Transform 472 B.3 Digital Filter Banks 474 B.4 Two-Channel Filter Bank 475 B.5 Windowed Fourier Transform 476 B.6 Continuous-Time Wavelet Transform 477   Appendix C: Analysis of Locations of Anchor Points 479 D Asymptotic Behavior of Functions 485 D.1 Big Oh (O(·)) Notation 485 D.2 Big Omega (Ω(·)) Notation 486 D.3 Big Theta (Θ(·)) Notation 486   Appendix E: Relevant Academic Courses and Programs 489 E.1 Academic Courses on Complex Networks 489 E.2 Online Courses on Complex Networks 491 E.3 Selective Academic Programs on Complex Networks 492   Appendix F: Relevant Journals and Conferences 493 F.1 List of Top Journals in Complex Networks 493 F.2 List of Top Conferences in Complex Networks 495   Appendix G: Relevant Datasets and Visualization Tools 499 G.1 Relevant Dataset Repositories 499 G.2 Relevant Graph Visualization and Analysis Tools 500   Appendix H: Relevant Research Groups 503   Notation 507 Acronyms 509 Bibliography 513 Index 529