## Description

**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 DSP_{G} Framework 394

10.4 DSP_{G} Framework Based on Weight Matrix 397

10.5 DSP_{G} 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

Complex Networks: A Networking and Signal Processing Perspective

Add to Cart$80.00 | ISBN-13: 978-0-13-478699-5

*Free* Ground Shipping.