Contents
1.3 Benefits of Studying Complex Networks
1.3.1 Modeling and Characterizing Complex Physical World Systems
1.3.2 Design of New and Efficient Physical World Systems
1.3.3 Development of Solutions to Complex Real-World Problems
1.3.4 Enhancing Biomedical Research through Molecular Network Modeling
1.3.6 Neutralizing Antisocial Networks
1.3.7 Enhanced Social Science Research through Social Networks
1.4 Challenges in Studying Complex Networks
1.6.1 Suggested Navigation for Contents of the Book
1.7 Support Materials Available for Instructors
2.3 Matrices Related to a Graph
2.4.2 Average Clustering Coefficient
2.4.5 Graph Diameter and Volume
2.5 Basic Graph Definitions and Properties
2.5.1 Walk, Path, and Circuits
2.7 Other Important Measures for Graphs
2.8 Graph Pathfinding Algorithms
2.8.1 Dijkstra’s Shortest Path Algorithm
2.8.2 All-Pair Shortest Path Algorithm
3 Introduction to Complex Networks
3.1 Major Types of Complex Networks
3.2.4 Average Clustering Coefficient
3.2.7 Degree-Degree Correlation in Complex Networks
3.2.9 Network Resistance Distance
3.3 Community Detection in Complex Networks
3.3.3 Conflict Graph Transformation-Based Community Detection
3.4 Entropy in Complex Network
3.4.3 Link Length Variability Entropy
3.5.1 Evolution of Random Networks
3.5.2 Erdös-Rényi Random Network Model
3.5.3 Properties of Random Networks
4.2 Milgram’s Small-World Experiment
4.3 Characteristics of Small-World Networks
4.4 Real-World Small-World Networks
4.5 Creation and Evolution of Small-World Networks
4.5.1 Rewiring of Existing Links
4.5.2 Pure Random Addition of New LLs
4.5.3 Euclidean Distance-Based Addition of New Links
4.6 Capacity-Based Deterministic Addition of New Links
4.6.1 Max-Flow Min-Cut Theorem
4.6.2 Link Addition Based on Maximum Flow Capacity Strategy
4.7 Creation of Deterministic Small-World Networks
4.7.1 Link Addition Based on Minimum APL
4.7.2 Link Addition Based on Minimum AEL
4.7.3 Link Addition Based on Maximum BC
4.7.4 Link Addition Based on Maximum CC
4.8 Anchor Points in a String Topology Small-World Network
4.8.1 Significance of Anchor Points
4.8.2 Locations of Anchor Points
4.9 Heuristic Approach-Based Deterministic Link Addition
4.9.1 Maximum Closeness Centrality Disparity
4.9.2 Sequential Deterministic LL Addition
4.9.3 Average Flow Capacity Enhancement Using Small-World Characteristics
4.10 Routing in Small-World Networks
4.10.1 The Decentralized Routing Algorithm
4.10.2 The Adaptive Decentralized Routing Algorithm
4.10.3 The Lookahead Routing Algorithm
4.11 Capacity of Small-World Networks
4.11.1 Capacity of Small-World Networks with Rewiring of Existing NLs
4.11.2 Capacity of Small-World Networks with LL Addition
5.1.1 What Does Scale-Free Mean?
5.2 Characteristics of Scale-Free Networks
5.3 Real-World Scale-Free Networks
5.3.1 The Author Citation Networks
5.3.2 The Autonomous Systems in the Internet
5.3.3 The Air Traffic Networks
5.3.4 Identification of Scale-Free Networks
5.4 Scale-Free Network Formation
5.4.1 Scale-Free Network Creation by Preferential Attachment
5.4.2 Scale-Free Network Creation by Fitness-Based Modeling
5.4.3 Scale-Free Network Creation by Varying Intrinsic Fitness
5.4.4 Scale-Free Network Creation by Optimization
5.4.5 Scale-Free Network Creation with Exponent 1
5.4.6 Scale-Free Network Creation with Greedy Global Decision Making
5.5 Preferential Attachment–Based Scale-Free Network Creation
5.5.1 Barabási-Albert (BA) Network Model
5.5.2 Observations and Discussion
5.6 Fitness-Based Scale-Free Network Creation
5.6.1 Fitness-Based Network Model
5.6.2 Observations and Discussion
5.7 Varying Intrinsic Fitness-Based Scale-Free Network Creation
5.7.1 Varying Intrinsic Fitness-Based Network Model
5.7.2 Observations and Discussion
5.8 Optimization-Based Scale-Free Network Creation
5.8.1 Observations and Discussion
5.9 Scale-Free Network Creation with Exponent 1
5.9.1 Scale-Free Network Creation with Rewiring
5.9.2 Observations and Discussion
5.10 Greedy Global Decision–Based Scale-Free Network Creation
5.10.1 Greedy Global LL Addition
5.10.2 Observations on Greedy Global Decision–Based Scale-Free Network
5.11 Deterministic Scale-Free Network Creation
5.11.1 Deterministic Scale-Free Network Model
5.11.2 Observations on Deterministic Scale-Free Network Creation
6 Small-World Wireless Mesh Networks
6.1.1 The Small-World Characteristics
6.1.2 Small-World Wireless Mesh Networks
6.2 Classification of Small-World Wireless Mesh Networks
6.3 Creation of Random Long-Ranged Links
6.3.1 Random LL Creation by Rewiring the Normal Links
6.3.2 Random LL Creation by Addition of New Links
6.4 Small-World Based on Pure Random Link Addition
6.5 Small-World Based on Euclidean Distance
6.6 Realization of Small-World Networks Based on Antenna Metrics
6.6.1 LL Addition Based on Transmission Power
6.6.2 LL Addition Based on Randomized Beamforming
6.6.3 LL Addition Based on Transmission Power and Beamforming
6.7 Algorithmic Approaches to Create Small-World Wireless Mesh Networks
6.7.1 Contact-Based LL Creation
6.7.2 Genetic Algorithm–Based LL Addition
6.7.3 Small-World Cooperative Routing–Based LL Addition
6.8 Gateway-Router-Centric Small-World Network Formation
6.8.1 Single Gateway-Router-Based LL Addition
6.8.2 Multi-Gateway-Router-Based LL Addition
6.9 Creation of Deterministic Small-World Wireless Mesh Networks
6.9.1 Exhaustive Search–Based Deterministic LL Addition
6.9.2 Heuristic Approach-Based Deterministic LL Addition
6.10 Creation of Non-Persistent Small-World Wireless Mesh Networks
6.10.1 Data-Mule-Based LL Creation
6.10.2 Load-Aware Long-Ranged Link Creation
6.11 Non-Persistent Routing in Small-World Wireless Mesh Networks
6.11.1 Load-Aware Non-Persistent Small-World Routing
6.11.2 Performance Evaluation of LNPR Algorithm
6.12 Qualitative Comparison of Existing Solutions
7 Small-World Wireless Sensor Networks
7.2 Small-World Wireless Mesh Networks vs. Small-World Wireless Sensor Networks
7.3 Why Small-World Wireless Sensor Networks?
7.4 Challenges in Transforming WSNs to SWWSNs
7.5 Types of Long-Ranged Links for SWWSNs
7.6 Approaches for Transforming WSNs to SWWSNs
7.6.1 Classification of Existing Approaches
7.6.2 Metrics for Performance Estimation
7.6.3 Transforming Regular Topology WSNs to SWWSNs
7.6.4 Random Model Heterogeneous SWWSNs
7.6.5 Newman-Watts Model–Based SWWSNs
7.6.6 Kleinberg Model–Based SWWSNs
7.6.7 Directed Random Model–Based SWWSNs
7.6.8 Variable Rate Adaptive Modulation–Based SWWSNs
7.6.9 Degree-Based LL Addition for Creating SWWSNs
7.6.10 Inhibition Distance–Based LL Addition for Creating SWWSNs
8.3 Adjacency Matrix Spectrum of a Graph
8.3.1 Bounds on the Eigenvalues
8.3.2 Adjacency Matrix Spectra of Special Graphs
8.4 Adjacency Matrix Spectra of Complex Networks
8.5 Laplacian Spectrum of a Graph
8.5.1 Bounds on the Eigenvalues of the Laplacian
8.5.2 Bounds on the Eigenvalues of the Normalized Laplacian
8.5.4 Laplacian Spectrum and Graph Connectivity
8.5.5 Spectral Graph Clustering
8.5.6 Laplacian Spectra of Special Graphs
8.6 Laplacian Spectra of Complex Networks
8.7 Network Classification Using Spectral Densities
9 Signal Processing on Complex Networks
9.1 Introduction to Graph Signal Processing
9.1.1 Mathematical Representation of Graph Signals
9.2 Comparison between Classical and Graph Signal Processing
9.2.1 Relationship between GFT and Classical DFT
9.3 The Graph Laplacian as an Operator
9.3.1 Properties of the Graph Laplacian
9.4 Quantifying Variations in Graph Signals
9.5.1 Notion of Frequency and Frequency Ordering
9.5.2 Bandlimited Graph Signals
9.5.3 Effect of Vertex Indexing
9.6 Generalized Operators for Graph Signals
9.7.1 Spectral Analysis of Node Centralities
9.7.2 Graph Fourier Transform Centrality
9.7.3 Malfunction Detection in Sensor Networks
9.8 Windowed Graph Fourier Transform
10 Graph Signal Processing Approaches
10.2 Graph Signal Processing Based on Laplacian Matrix
10.3.1 Linear Graph Filters and Shift Invariance
10.4 DSPG Framework Based on Weight Matrix
10.4.2 Linear Shift Invariant Graph Filters
10.4.4 Graph Fourier Transform
10.4.5 Frequency Response of LSI Graph Filters
10.5 DSPG Framework Based on Directed Laplacian
10.5.3 Linear Shift Invariant Graph Filters
10.5.5 Graph Fourier Transform Based on Directed Laplacian
10.5.6 Frequency Response of LSI Graph Filters
10.6 Comparison of Graph Signal Processing Approaches
11 Multiscale Analysis of Complex Networks
11.2 Multiscale Transforms for Complex Network Data
11.2.2 Spectral Domain Designs
11.3 Crovella and Kolaczyk Wavelet Transform
11.3.5 Advantages and Disadvantages
11.4.1 Advantages and Disadvantages
11.5.1 Splitting of a Graph into Even and Odd Nodes
11.5.2 Lifting-Based Transform
11.6 Two-Channel Graph Wavelet Filter Banks
11.6.1 Downsampling and Upsampling in Graphs
11.6.2 Two-Channel Graph Wavelet Filter Banks
11.6.3 Graph Quadrature-Mirror Filterbanks
11.6.4 Multidimensional Separable Wavelet Filter Banks for Arbitrary Graphs
11.7 Spectral Graph Wavelet Transform
11.7.2 Wavelet Generating Kernels
11.7.4 Advantages and Disadvantages
11.8 Spectral Graph Wavelet Transform Based on Directed Laplacian
11.8.2 Wavelet Generating Kernel
11.9.1 Advantages and Disadvantages
A.1.1 Orthogonal and Orthonormal Vectors
A.1.2 Linear Span of a Set of Vectors
A.2.2 Matrix Vector Mutiplication
A.2.3 Column Space, Null Space, and Rank of a Matrix
A.3 Eigenvalues and Eigenvectors
B.1 Linear Time Invariant Filters
B.1.1 Impulse Response and Convolution
B.2.1 Continuous-Time Fourier Transform
B.2.2 Discrete-Time Fourier Transform
B.2.3 Discrete Fourier Transform
B.3.1 Downsampler and Upsampler
B.5 Windowed Fourier Transform
B.6 Continuous-Time Wavelet Transform
C Analysis of Locations of Anchor Points
D Asymptotic Behavior of Functions
E Relevant Academic Courses and Programs
E.1 Academic Courses on Complex Networks
E.2 Online Courses on Complex Networks
E.3 Selective Academic Programs on Complex Networks
F Relevant Journals and Conferences
F.1 List of Top Journals in Complex Networks
F.2 List of Top Conferences in Complex Networks
G Relevant Datasets and Visualization Tools
G.1 Relevant Dataset Repositories