Complex Networks: A Networking and Signal Processing Perspective

Complex Networks: A Networking and Signal Processing Perspective

by Abhishek Chakraborty, B. S. Manoj, Rahul Singh
Released February 2018
Publisher(s): Pearson
ISBN: 9780134787145

Read it now on the O’Reilly learning platform with a 10-day free trial.

O’Reilly members get unlimited access to books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Start your free trial

Book 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

  1. Cover Page
  2. About This E-Book
  3. Title Page
  4. Copyright Page
  5. Dedication
  6. Contents
  7. Preface
  8. Acknowledgments
  9. About the Authors
  10. About the Cover
  11. 1 Introduction
    1. 1.1 Complex Networks
    2. 1.2 Types of Complex Networks
    3. 1.3 Benefits of Studying Complex Networks
      1. 1.3.1 Modeling and Characterizing Complex Physical World Systems
      2. 1.3.2 Design of New and Efficient Physical World Systems
      3. 1.3.3 Development of Solutions to Complex Real-World Problems
      4. 1.3.4 Enhancing Biomedical Research through Molecular Network Modeling
      5. 1.3.5 Network Medicine
      6. 1.3.6 Neutralizing Antisocial Networks
      7. 1.3.7 Enhanced Social Science Research through Social Networks
    4. 1.4 Challenges in Studying Complex Networks
    5. 1.5 What This Book Offers
    6. 1.6 Organization of the Book
      1. 1.6.1 Suggested Navigation for Contents of the Book
    7. 1.7 Support Materials Available for Instructors
    8. 1.8 Summary
  12. 2 Graph Theory Preliminaries
    1. 2.1 Introduction
    2. 2.2 Graphs
      1. 2.2.1 Subgraphs
      2. 2.2.2 Complement of a Graph
    3. 2.3 Matrices Related to a Graph
      1. 2.3.1 Weight Matrix
      2. 2.3.2 Adjacency Matrix
      3. 2.3.3 Incidence Matrix
      4. 2.3.4 Degree Matrix
      5. 2.3.5 Laplacian Matrix
    4. 2.4 Basic Graph Metrics
      1. 2.4.1 Average Neighbor Degree
      2. 2.4.2 Average Clustering Coefficient
      3. 2.4.3 Average Path Length
      4. 2.4.4 Average Edge Length
      5. 2.4.5 Graph Diameter and Volume
    5. 2.5 Basic Graph Definitions and Properties
      1. 2.5.1 Walk, Path, and Circuits
      2. 2.5.2 Connectivity
      3. 2.5.3 Acyclicity
      4. 2.5.4 Isomorphism
      5. 2.5.5 Planarity
      6. 2.5.6 Colorability
      7. 2.5.7 Traversability
      8. 2.5.8 Network Flows
      9. 2.5.9 Product Graphs
    6. 2.6 Types of Graphs
      1. 2.6.1 Regular Graph
      2. 2.6.2 Bipartite Graphs
      3. 2.6.3 Complete Graphs
      4. 2.6.4 Trees
      5. 2.6.5 Line Graph
      6. 2.6.6 Conflict Graphs
    7. 2.7 Other Important Measures for Graphs
      1. 2.7.1 Cheeger Constant
      2. 2.7.2 Clique Number
    8. 2.8 Graph Pathfinding Algorithms
      1. 2.8.1 Dijkstra’s Shortest Path Algorithm
      2. 2.8.2 All-Pair Shortest Path Algorithm
    9. 2.9 Summary
    10. Exercises
  13. 3 Introduction to Complex Networks
    1. 3.1 Major Types of Complex Networks
      1. 3.1.1 Random Networks
      2. 3.1.2 Small-World Networks
      3. 3.1.3 Scale-Free Networks
    2. 3.2 Complex Network Metrics
      1. 3.2.1 Average Neighbor Degree
      2. 3.2.2 Average Path Length
      3. 3.2.3 Network Diameter
      4. 3.2.4 Average Clustering Coefficient
      5. 3.2.5 Degree Distribution
      6. 3.2.6 Centrality Metrics
      7. 3.2.7 Degree-Degree Correlation in Complex Networks
      8. 3.2.8 Node Criticality
      9. 3.2.9 Network Resistance Distance
    3. 3.3 Community Detection in Complex Networks
      1. 3.3.1 Modularity Maximization
      2. 3.3.2 Surprise Maximization
      3. 3.3.3 Conflict Graph Transformation-Based Community Detection
    4. 3.4 Entropy in Complex Network
      1. 3.4.1 Network Entropy
      2. 3.4.2 Nodal Degree Entropy
      3. 3.4.3 Link Length Variability Entropy
      4. 3.4.4 Link Influence Entropy
    5. 3.5 Random Networks
      1. 3.5.1 Evolution of Random Networks
      2. 3.5.2 Erdös-Rényi Random Network Model
      3. 3.5.3 Properties of Random Networks
    6. 3.6 Open Research Issues
    7. 3.7 Summary
    8. Exercises
  14. 4 Small-World Networks
    1. 4.1 Introduction
    2. 4.2 Milgram’s Small-World Experiment
    3. 4.3 Characteristics of Small-World Networks
    4. 4.4 Real-World Small-World Networks
    5. 4.5 Creation and Evolution of Small-World Networks
      1. 4.5.1 Rewiring of Existing Links
      2. 4.5.2 Pure Random Addition of New LLs
      3. 4.5.3 Euclidean Distance-Based Addition of New Links
    6. 4.6 Capacity-Based Deterministic Addition of New Links
      1. 4.6.1 Max-Flow Min-Cut Theorem
      2. 4.6.2 Link Addition Based on Maximum Flow Capacity Strategy
    7. 4.7 Creation of Deterministic Small-World Networks
      1. 4.7.1 Link Addition Based on Minimum APL
      2. 4.7.2 Link Addition Based on Minimum AEL
      3. 4.7.3 Link Addition Based on Maximum BC
      4. 4.7.4 Link Addition Based on Maximum CC
    8. 4.8 Anchor Points in a String Topology Small-World Network
      1. 4.8.1 Significance of Anchor Points
      2. 4.8.2 Locations of Anchor Points
    9. 4.9 Heuristic Approach-Based Deterministic Link Addition
      1. 4.9.1 Maximum Closeness Centrality Disparity
      2. 4.9.2 Sequential Deterministic LL Addition
      3. 4.9.3 Average Flow Capacity Enhancement Using Small-World Characteristics
    10. 4.10 Routing in Small-World Networks
      1. 4.10.1 The Decentralized Routing Algorithm
      2. 4.10.2 The Adaptive Decentralized Routing Algorithm
      3. 4.10.3 The Lookahead Routing Algorithm
    11. 4.11 Capacity of Small-World Networks
      1. 4.11.1 Capacity of Small-World Networks with Rewiring of Existing NLs
      2. 4.11.2 Capacity of Small-World Networks with LL Addition
    12. 4.12 Open Research Issues
    13. 4.13 Summary
    14. Exercises
  15. 5 Scale-Free Networks
    1. 5.1 Introduction
      1. 5.1.1 What Does Scale-Free Mean?
    2. 5.2 Characteristics of Scale-Free Networks
    3. 5.3 Real-World Scale-Free Networks
      1. 5.3.1 The Author Citation Networks
      2. 5.3.2 The Autonomous Systems in the Internet
      3. 5.3.3 The Air Traffic Networks
      4. 5.3.4 Identification of Scale-Free Networks
    4. 5.4 Scale-Free Network Formation
      1. 5.4.1 Scale-Free Network Creation by Preferential Attachment
      2. 5.4.2 Scale-Free Network Creation by Fitness-Based Modeling
      3. 5.4.3 Scale-Free Network Creation by Varying Intrinsic Fitness
      4. 5.4.4 Scale-Free Network Creation by Optimization
      5. 5.4.5 Scale-Free Network Creation with Exponent 1
      6. 5.4.6 Scale-Free Network Creation with Greedy Global Decision Making
    5. 5.5 Preferential Attachment–Based Scale-Free Network Creation
      1. 5.5.1 Barabási-Albert (BA) Network Model
      2. 5.5.2 Observations and Discussion
    6. 5.6 Fitness-Based Scale-Free Network Creation
      1. 5.6.1 Fitness-Based Network Model
      2. 5.6.2 Observations and Discussion
    7. 5.7 Varying Intrinsic Fitness-Based Scale-Free Network Creation
      1. 5.7.1 Varying Intrinsic Fitness-Based Network Model
      2. 5.7.2 Observations and Discussion
    8. 5.8 Optimization-Based Scale-Free Network Creation
      1. 5.8.1 Observations and Discussion
    9. 5.9 Scale-Free Network Creation with Exponent 1
      1. 5.9.1 Scale-Free Network Creation with Rewiring
      2. 5.9.2 Observations and Discussion
    10. 5.10 Greedy Global Decision–Based Scale-Free Network Creation
      1. 5.10.1 Greedy Global LL Addition
      2. 5.10.2 Observations on Greedy Global Decision–Based Scale-Free Network
    11. 5.11 Deterministic Scale-Free Network Creation
      1. 5.11.1 Deterministic Scale-Free Network Model
      2. 5.11.2 Observations on Deterministic Scale-Free Network Creation
    12. 5.12 Open Research Issues
    13. 5.13 Summary
    14. Exercises
  16. 6 Small-World Wireless Mesh Networks
    1. 6.1 Introduction
      1. 6.1.1 The Small-World Characteristics
      2. 6.1.2 Small-World Wireless Mesh Networks
    2. 6.2 Classification of Small-World Wireless Mesh Networks
    3. 6.3 Creation of Random Long-Ranged Links
      1. 6.3.1 Random LL Creation by Rewiring the Normal Links
      2. 6.3.2 Random LL Creation by Addition of New Links
    4. 6.4 Small-World Based on Pure Random Link Addition
    5. 6.5 Small-World Based on Euclidean Distance
    6. 6.6 Realization of Small-World Networks Based on Antenna Metrics
      1. 6.6.1 LL Addition Based on Transmission Power
      2. 6.6.2 LL Addition Based on Randomized Beamforming
      3. 6.6.3 LL Addition Based on Transmission Power and Beamforming
    7. 6.7 Algorithmic Approaches to Create Small-World Wireless Mesh Networks
      1. 6.7.1 Contact-Based LL Creation
      2. 6.7.2 Genetic Algorithm–Based LL Addition
      3. 6.7.3 Small-World Cooperative Routing–Based LL Addition
    8. 6.8 Gateway-Router-Centric Small-World Network Formation
      1. 6.8.1 Single Gateway-Router-Based LL Addition
      2. 6.8.2 Multi-Gateway-Router-Based LL Addition
    9. 6.9 Creation of Deterministic Small-World Wireless Mesh Networks
      1. 6.9.1 Exhaustive Search–Based Deterministic LL Addition
      2. 6.9.2 Heuristic Approach-Based Deterministic LL Addition
    10. 6.10 Creation of Non-Persistent Small-World Wireless Mesh Networks
      1. 6.10.1 Data-Mule-Based LL Creation
      2. 6.10.2 Load-Aware Long-Ranged Link Creation
    11. 6.11 Non-Persistent Routing in Small-World Wireless Mesh Networks
      1. 6.11.1 Load-Aware Non-Persistent Small-World Routing
      2. 6.11.2 Performance Evaluation of LNPR Algorithm
    12. 6.12 Qualitative Comparison of Existing Solutions
    13. 6.13 Open Research Issues
    14. 6.14 Summary
    15. Exercises
  17. 7 Small-World Wireless Sensor Networks
    1. 7.1 Introduction
    2. 7.2 Small-World Wireless Mesh Networks vs. Small-World Wireless Sensor Networks
    3. 7.3 Why Small-World Wireless Sensor Networks?
    4. 7.4 Challenges in Transforming WSNs to SWWSNs
    5. 7.5 Types of Long-Ranged Links for SWWSNs
    6. 7.6 Approaches for Transforming WSNs to SWWSNs
      1. 7.6.1 Classification of Existing Approaches
      2. 7.6.2 Metrics for Performance Estimation
      3. 7.6.3 Transforming Regular Topology WSNs to SWWSNs
      4. 7.6.4 Random Model Heterogeneous SWWSNs
      5. 7.6.5 Newman-Watts Model–Based SWWSNs
      6. 7.6.6 Kleinberg Model–Based SWWSNs
      7. 7.6.7 Directed Random Model–Based SWWSNs
      8. 7.6.8 Variable Rate Adaptive Modulation–Based SWWSNs
      9. 7.6.9 Degree-Based LL Addition for Creating SWWSNs
      10. 7.6.10 Inhibition Distance–Based LL Addition for Creating SWWSNs
      11. 7.6.11 Homogeneous SWWSNs
    7. 7.7 SWWSNs with Wired LLs
    8. 7.8 Open Research Issues
    9. 7.9 Summary
    10. Exercises
  18. 8 Spectra of Complex Networks
    1. 8.1 Introduction
    2. 8.2 Spectrum of a Graph
    3. 8.3 Adjacency Matrix Spectrum of a Graph
      1. 8.3.1 Bounds on the Eigenvalues
      2. 8.3.2 Adjacency Matrix Spectra of Special Graphs
    4. 8.4 Adjacency Matrix Spectra of Complex Networks
      1. 8.4.1 Random Networks
      2. 8.4.2 Random Regular Networks
      3. 8.4.3 Small-World Networks
      4. 8.4.4 Scale-Free Networks
    5. 8.5 Laplacian Spectrum of a Graph
      1. 8.5.1 Bounds on the Eigenvalues of the Laplacian
      2. 8.5.2 Bounds on the Eigenvalues of the Normalized Laplacian
      3. 8.5.3 Matrix Tree Theorem
      4. 8.5.4 Laplacian Spectrum and Graph Connectivity
      5. 8.5.5 Spectral Graph Clustering
      6. 8.5.6 Laplacian Spectra of Special Graphs
    6. 8.6 Laplacian Spectra of Complex Networks
      1. 8.6.1 Random Networks
      2. 8.6.2 Random Regular Networks
      3. 8.6.3 Small-World Networks
      4. 8.6.4 Scale-Free Networks
    7. 8.7 Network Classification Using Spectral Densities
    8. 8.8 Open Research Issues
    9. 8.9 Summary
    10. Exercises
  19. 9 Signal Processing on Complex Networks
    1. 9.1 Introduction to Graph Signal Processing
      1. 9.1.1 Mathematical Representation of Graph Signals
    2. 9.2 Comparison between Classical and Graph Signal Processing
      1. 9.2.1 Relationship between GFT and Classical DFT
    3. 9.3 The Graph Laplacian as an Operator
      1. 9.3.1 Properties of the Graph Laplacian
      2. 9.3.2 Graph Spectrum
    4. 9.4 Quantifying Variations in Graph Signals
    5. 9.5 Graph Fourier Transform
      1. 9.5.1 Notion of Frequency and Frequency Ordering
      2. 9.5.2 Bandlimited Graph Signals
      3. 9.5.3 Effect of Vertex Indexing
    6. 9.6 Generalized Operators for Graph Signals
      1. 9.6.1 Filtering
      2. 9.6.2 Convolution
      3. 9.6.3 Translation
      4. 9.6.4 Modulation
    7. 9.7 Applications
      1. 9.7.1 Spectral Analysis of Node Centralities
      2. 9.7.2 Graph Fourier Transform Centrality
      3. 9.7.3 Malfunction Detection in Sensor Networks
    8. 9.8 Windowed Graph Fourier Transform
      1. 9.8.1 Example of WGFT
    9. 9.9 Open Research Issues
    10. 9.10 Summary
    11. Exercises
  20. 10 Graph Signal Processing Approaches
    1. 10.1 Introduction
    2. 10.2 Graph Signal Processing Based on Laplacian Matrix
    3. 10.3 DSPG Framework
      1. 10.3.1 Linear Graph Filters and Shift Invariance
    4. 10.4 DSPG Framework Based on Weight Matrix
      1. 10.4.1 Shift Operator
      2. 10.4.2 Linear Shift Invariant Graph Filters
      3. 10.4.3 Total Variation
      4. 10.4.4 Graph Fourier Transform
      5. 10.4.5 Frequency Response of LSI Graph Filters
    5. 10.5 DSPG Framework Based on Directed Laplacian
      1. 10.5.1 Directed Laplacian
      2. 10.5.2 Shift Operator
      3. 10.5.3 Linear Shift Invariant Graph Filters
      4. 10.5.4 Total Variation
      5. 10.5.5 Graph Fourier Transform Based on Directed Laplacian
      6. 10.5.6 Frequency Response of LSI Graph Filters
    6. 10.6 Comparison of Graph Signal Processing Approaches
    7. 10.7 Open Research Issues
    8. 10.8 Summary
    9. Exercises
  21. 11 Multiscale Analysis of Complex Networks
    1. 11.1 Introduction
    2. 11.2 Multiscale Transforms for Complex Network Data
      1. 11.2.1 Vertex Domain Designs
      2. 11.2.2 Spectral Domain Designs
    3. 11.3 Crovella and Kolaczyk Wavelet Transform
      1. 11.3.1 CK Wavelets
      2. 11.3.2 Wavelet Transform
      3. 11.3.3 Wavelet Properties
      4. 11.3.4 Examples
      5. 11.3.5 Advantages and Disadvantages
    4. 11.4 Random Transform
      1. 11.4.1 Advantages and Disadvantages
    5. 11.5 Lifting-Based Wavelets
      1. 11.5.1 Splitting of a Graph into Even and Odd Nodes
      2. 11.5.2 Lifting-Based Transform
    6. 11.6 Two-Channel Graph Wavelet Filter Banks
      1. 11.6.1 Downsampling and Upsampling in Graphs
      2. 11.6.2 Two-Channel Graph Wavelet Filter Banks
      3. 11.6.3 Graph Quadrature-Mirror Filterbanks
      4. 11.6.4 Multidimensional Separable Wavelet Filter Banks for Arbitrary Graphs
    7. 11.7 Spectral Graph Wavelet Transform
      1. 11.7.1 Matrix Form of SGWT
      2. 11.7.2 Wavelet Generating Kernels
      3. 11.7.3 An Example of SGWT
      4. 11.7.4 Advantages and Disadvantages
    8. 11.8 Spectral Graph Wavelet Transform Based on Directed Laplacian
      1. 11.8.1 Wavelets
      2. 11.8.2 Wavelet Generating Kernel
      3. 11.8.3 Examples
    9. 11.9 Diffusion Wavelets
      1. 11.9.1 Advantages and Disadvantages
    10. 11.10 Open Research Issues
    11. 11.11 Summary
    12. Exercises
  22. A Vectors and Matrices
    1. A.1 Vectors and Norms
      1. A.1.1 Orthogonal and Orthonormal Vectors
      2. A.1.2 Linear Span of a Set of Vectors
    2. A.2 Matrices
      1. A.2.1 Trace of a Matrix
      2. A.2.2 Matrix Vector Mutiplication
      3. A.2.3 Column Space, Null Space, and Rank of a Matrix
      4. A.2.4 Special Matrices
    3. A.3 Eigenvalues and Eigenvectors
      1. A.3.1 Characteristic Equation
      2. A.3.2 Eigenspaces
      3. A.3.3 Eigenvalue Multiplicity
    4. A.4 Matrix Diagonalization
    5. A.5 Jordan Decomposition
    6. A.6 Spectral Density
    7. A.7 Wigner’s Semicircle Law
    8. A.8 Gershgorin’s Theorem
  23. B Classical Signal Processing
    1. B.1 Linear Time Invariant Filters
      1. B.1.1 Impulse Response and Convolution
      2. B.1.2 Eigenfunctions
    2. B.2 Fourier Transform
      1. B.2.1 Continuous-Time Fourier Transform
      2. B.2.2 Discrete-Time Fourier Transform
      3. B.2.3 Discrete Fourier Transform
    3. B.3 Digital Filter Banks
      1. B.3.1 Downsampler and Upsampler
    4. B.4 Two-Channel Filter Bank
    5. B.5 Windowed Fourier Transform
      1. B.5.1 Spectrogram
    6. B.6 Continuous-Time Wavelet Transform
  24. C Analysis of Locations of Anchor Points
  25. D Asymptotic Behavior of Functions
    1. D.1 Big Oh (O(·)) Notation
    2. D.2 Big Omega (Ω(·)) Notation
    3. D.3 Big Theta (Θ(·)) Notation
  26. E Relevant Academic Courses and Programs
    1. E.1 Academic Courses on Complex Networks
    2. E.2 Online Courses on Complex Networks
    3. E.3 Selective Academic Programs on Complex Networks
  27. F Relevant Journals and Conferences
    1. F.1 List of Top Journals in Complex Networks
    2. F.2 List of Top Conferences in Complex Networks
  28. G Relevant Datasets and Visualization Tools
    1. G.1 Relevant Dataset Repositories
    2. G.2 Relevant Graph Visualization and Analysis Tools
  29. H Relevant Research Groups
    1. H.1 Other Important Resources
  30. Notation
  31. Acronyms
  32. Bibliography
  33. Index

Product information

  • Title: Complex Networks: A Networking and Signal Processing Perspective
  • Author(s): Abhishek Chakraborty, B. S. Manoj, Rahul Singh
  • Release date: February 2018
  • Publisher(s): Pearson
  • ISBN: 9780134787145