book

Complex Networks: A Networking and Signal Processing Perspective

Name: Complex Networks: A Networking and Signal Processing Perspective
ISBN: 9780134787145

by Abhishek Chakraborty, B. S. Manoj, Rahul Singh

February 2018

Intermediate to advanced

576 pages

17h 47m

English

Pearson

Read now

Unlock full access

Cover Page
About This E-Book
Title Page
Copyright Page
Dedication
Contents
Preface
Acknowledgments
About the Authors
About the Cover

1 Introduction
1.1 Complex Networks1.2 Types of Complex Networks1.3 Benefits of Studying Complex Networks1.3.1 Modeling and Characterizing Complex Physical World Systems1.3.2 Design of New and Efficient Physical World Systems1.3.3 Development of Solutions to Complex Real-World Problems1.3.4 Enhancing Biomedical Research through Molecular Network Modeling1.3.5 Network Medicine1.3.6 Neutralizing Antisocial Networks1.3.7 Enhanced Social Science Research through Social Networks1.4 Challenges in Studying Complex Networks1.5 What This Book Offers1.6 Organization of the Book1.6.1 Suggested Navigation for Contents of the Book1.7 Support Materials Available for Instructors1.8 Summary
2 Graph Theory Preliminaries
2.1 Introduction2.2 Graphs2.2.1 Subgraphs2.2.2 Complement of a Graph2.3 Matrices Related to a Graph2.3.1 Weight Matrix2.3.2 Adjacency Matrix2.3.3 Incidence Matrix2.3.4 Degree Matrix2.3.5 Laplacian Matrix2.4 Basic Graph Metrics2.4.1 Average Neighbor Degree2.4.2 Average Clustering Coefficient2.4.3 Average Path Length2.4.4 Average Edge Length2.4.5 Graph Diameter and Volume2.5 Basic Graph Definitions and Properties2.5.1 Walk, Path, and Circuits2.5.2 Connectivity2.5.3 Acyclicity2.5.4 Isomorphism2.5.5 Planarity2.5.6 Colorability2.5.7 Traversability2.5.8 Network Flows2.5.9 Product Graphs2.6 Types of Graphs2.6.1 Regular Graph2.6.2 Bipartite Graphs2.6.3 Complete Graphs2.6.4 Trees2.6.5 Line Graph2.6.6 Conflict Graphs2.7 Other Important Measures for Graphs2.7.1 Cheeger Constant2.7.2 Clique Number2.8 Graph Pathfinding Algorithms2.8.1 Dijkstra’s Shortest Path Algorithm2.8.2 All-Pair Shortest Path Algorithm2.9 SummaryExercises
3 Introduction to Complex Networks
3.1 Major Types of Complex Networks3.1.1 Random Networks3.1.2 Small-World Networks3.1.3 Scale-Free Networks3.2 Complex Network Metrics3.2.1 Average Neighbor Degree3.2.2 Average Path Length3.2.3 Network Diameter3.2.4 Average Clustering Coefficient3.2.5 Degree Distribution3.2.6 Centrality Metrics3.2.7 Degree-Degree Correlation in Complex Networks3.2.8 Node Criticality3.2.9 Network Resistance Distance3.3 Community Detection in Complex Networks3.3.1 Modularity Maximization3.3.2 Surprise Maximization3.3.3 Conflict Graph Transformation-Based Community Detection3.4 Entropy in Complex Network3.4.1 Network Entropy3.4.2 Nodal Degree Entropy3.4.3 Link Length Variability Entropy3.4.4 Link Influence Entropy3.5 Random Networks3.5.1 Evolution of Random Networks3.5.2 Erdös-Rényi Random Network Model3.5.3 Properties of Random Networks3.6 Open Research Issues3.7 SummaryExercises
4 Small-World Networks
4.1 Introduction4.2 Milgram’s Small-World Experiment4.3 Characteristics of Small-World Networks4.4 Real-World Small-World Networks4.5 Creation and Evolution of Small-World Networks4.5.1 Rewiring of Existing Links4.5.2 Pure Random Addition of New LLs4.5.3 Euclidean Distance-Based Addition of New Links4.6 Capacity-Based Deterministic Addition of New Links4.6.1 Max-Flow Min-Cut Theorem4.6.2 Link Addition Based on Maximum Flow Capacity Strategy4.7 Creation of Deterministic Small-World Networks4.7.1 Link Addition Based on Minimum APL4.7.2 Link Addition Based on Minimum AEL4.7.3 Link Addition Based on Maximum BC4.7.4 Link Addition Based on Maximum CC4.8 Anchor Points in a String Topology Small-World Network4.8.1 Significance of Anchor Points4.8.2 Locations of Anchor Points4.9 Heuristic Approach-Based Deterministic Link Addition4.9.1 Maximum Closeness Centrality Disparity4.9.2 Sequential Deterministic LL Addition4.9.3 Average Flow Capacity Enhancement Using Small-World Characteristics4.10 Routing in Small-World Networks4.10.1 The Decentralized Routing Algorithm4.10.2 The Adaptive Decentralized Routing Algorithm4.10.3 The Lookahead Routing Algorithm4.11 Capacity of Small-World Networks4.11.1 Capacity of Small-World Networks with Rewiring of Existing NLs4.11.2 Capacity of Small-World Networks with LL Addition4.12 Open Research Issues4.13 SummaryExercises
5 Scale-Free Networks
5.1 Introduction5.1.1 What Does Scale-Free Mean?5.2 Characteristics of Scale-Free Networks5.3 Real-World Scale-Free Networks5.3.1 The Author Citation Networks5.3.2 The Autonomous Systems in the Internet5.3.3 The Air Traffic Networks5.3.4 Identification of Scale-Free Networks5.4 Scale-Free Network Formation5.4.1 Scale-Free Network Creation by Preferential Attachment5.4.2 Scale-Free Network Creation by Fitness-Based Modeling5.4.3 Scale-Free Network Creation by Varying Intrinsic Fitness5.4.4 Scale-Free Network Creation by Optimization5.4.5 Scale-Free Network Creation with Exponent 15.4.6 Scale-Free Network Creation with Greedy Global Decision Making5.5 Preferential Attachment–Based Scale-Free Network Creation5.5.1 Barabási-Albert (BA) Network Model5.5.2 Observations and Discussion5.6 Fitness-Based Scale-Free Network Creation5.6.1 Fitness-Based Network Model5.6.2 Observations and Discussion5.7 Varying Intrinsic Fitness-Based Scale-Free Network Creation5.7.1 Varying Intrinsic Fitness-Based Network Model5.7.2 Observations and Discussion5.8 Optimization-Based Scale-Free Network Creation5.8.1 Observations and Discussion5.9 Scale-Free Network Creation with Exponent 15.9.1 Scale-Free Network Creation with Rewiring5.9.2 Observations and Discussion5.10 Greedy Global Decision–Based Scale-Free Network Creation5.10.1 Greedy Global LL Addition5.10.2 Observations on Greedy Global Decision–Based Scale-Free Network5.11 Deterministic Scale-Free Network Creation5.11.1 Deterministic Scale-Free Network Model5.11.2 Observations on Deterministic Scale-Free Network Creation5.12 Open Research Issues5.13 SummaryExercises
6 Small-World Wireless Mesh Networks
6.1 Introduction6.1.1 The Small-World Characteristics6.1.2 Small-World Wireless Mesh Networks6.2 Classification of Small-World Wireless Mesh Networks6.3 Creation of Random Long-Ranged Links6.3.1 Random LL Creation by Rewiring the Normal Links6.3.2 Random LL Creation by Addition of New Links6.4 Small-World Based on Pure Random Link Addition6.5 Small-World Based on Euclidean Distance6.6 Realization of Small-World Networks Based on Antenna Metrics6.6.1 LL Addition Based on Transmission Power6.6.2 LL Addition Based on Randomized Beamforming6.6.3 LL Addition Based on Transmission Power and Beamforming6.7 Algorithmic Approaches to Create Small-World Wireless Mesh Networks6.7.1 Contact-Based LL Creation6.7.2 Genetic Algorithm–Based LL Addition6.7.3 Small-World Cooperative Routing–Based LL Addition6.8 Gateway-Router-Centric Small-World Network Formation6.8.1 Single Gateway-Router-Based LL Addition6.8.2 Multi-Gateway-Router-Based LL Addition6.9 Creation of Deterministic Small-World Wireless Mesh Networks6.9.1 Exhaustive Search–Based Deterministic LL Addition6.9.2 Heuristic Approach-Based Deterministic LL Addition6.10 Creation of Non-Persistent Small-World Wireless Mesh Networks6.10.1 Data-Mule-Based LL Creation6.10.2 Load-Aware Long-Ranged Link Creation6.11 Non-Persistent Routing in Small-World Wireless Mesh Networks6.11.1 Load-Aware Non-Persistent Small-World Routing6.11.2 Performance Evaluation of LNPR Algorithm6.12 Qualitative Comparison of Existing Solutions6.13 Open Research Issues6.14 SummaryExercises
7 Small-World Wireless Sensor Networks
7.1 Introduction7.2 Small-World Wireless Mesh Networks vs. Small-World Wireless Sensor Networks7.3 Why Small-World Wireless Sensor Networks?7.4 Challenges in Transforming WSNs to SWWSNs7.5 Types of Long-Ranged Links for SWWSNs7.6 Approaches for Transforming WSNs to SWWSNs7.6.1 Classification of Existing Approaches7.6.2 Metrics for Performance Estimation7.6.3 Transforming Regular Topology WSNs to SWWSNs7.6.4 Random Model Heterogeneous SWWSNs7.6.5 Newman-Watts Model–Based SWWSNs7.6.6 Kleinberg Model–Based SWWSNs7.6.7 Directed Random Model–Based SWWSNs7.6.8 Variable Rate Adaptive Modulation–Based SWWSNs7.6.9 Degree-Based LL Addition for Creating SWWSNs7.6.10 Inhibition Distance–Based LL Addition for Creating SWWSNs7.6.11 Homogeneous SWWSNs7.7 SWWSNs with Wired LLs7.8 Open Research Issues7.9 SummaryExercises
8 Spectra of Complex Networks
8.1 Introduction8.2 Spectrum of a Graph8.3 Adjacency Matrix Spectrum of a Graph8.3.1 Bounds on the Eigenvalues8.3.2 Adjacency Matrix Spectra of Special Graphs8.4 Adjacency Matrix Spectra of Complex Networks8.4.1 Random Networks8.4.2 Random Regular Networks8.4.3 Small-World Networks8.4.4 Scale-Free Networks8.5 Laplacian Spectrum of a Graph8.5.1 Bounds on the Eigenvalues of the Laplacian8.5.2 Bounds on the Eigenvalues of the Normalized Laplacian8.5.3 Matrix Tree Theorem8.5.4 Laplacian Spectrum and Graph Connectivity8.5.5 Spectral Graph Clustering8.5.6 Laplacian Spectra of Special Graphs8.6 Laplacian Spectra of Complex Networks8.6.1 Random Networks8.6.2 Random Regular Networks8.6.3 Small-World Networks8.6.4 Scale-Free Networks8.7 Network Classification Using Spectral Densities8.8 Open Research Issues8.9 SummaryExercises
9 Signal Processing on Complex Networks
9.1 Introduction to Graph Signal Processing9.1.1 Mathematical Representation of Graph Signals9.2 Comparison between Classical and Graph Signal Processing9.2.1 Relationship between GFT and Classical DFT9.3 The Graph Laplacian as an Operator9.3.1 Properties of the Graph Laplacian9.3.2 Graph Spectrum9.4 Quantifying Variations in Graph Signals9.5 Graph Fourier Transform9.5.1 Notion of Frequency and Frequency Ordering9.5.2 Bandlimited Graph Signals9.5.3 Effect of Vertex Indexing9.6 Generalized Operators for Graph Signals9.6.1 Filtering9.6.2 Convolution9.6.3 Translation9.6.4 Modulation9.7 Applications9.7.1 Spectral Analysis of Node Centralities9.7.2 Graph Fourier Transform Centrality9.7.3 Malfunction Detection in Sensor Networks9.8 Windowed Graph Fourier Transform9.8.1 Example of WGFT9.9 Open Research Issues9.10 SummaryExercises
10 Graph Signal Processing Approaches
10.1 Introduction10.2 Graph Signal Processing Based on Laplacian Matrix10.3 DSPG Framework10.3.1 Linear Graph Filters and Shift Invariance10.4 DSPG Framework Based on Weight Matrix10.4.1 Shift Operator10.4.2 Linear Shift Invariant Graph Filters10.4.3 Total Variation10.4.4 Graph Fourier Transform10.4.5 Frequency Response of LSI Graph Filters10.5 DSPG Framework Based on Directed Laplacian10.5.1 Directed Laplacian10.5.2 Shift Operator10.5.3 Linear Shift Invariant Graph Filters10.5.4 Total Variation10.5.5 Graph Fourier Transform Based on Directed Laplacian10.5.6 Frequency Response of LSI Graph Filters10.6 Comparison of Graph Signal Processing Approaches10.7 Open Research Issues10.8 SummaryExercises
11 Multiscale Analysis of Complex Networks
11.1 Introduction11.2 Multiscale Transforms for Complex Network Data11.2.1 Vertex Domain Designs11.2.2 Spectral Domain Designs11.3 Crovella and Kolaczyk Wavelet Transform11.3.1 CK Wavelets11.3.2 Wavelet Transform11.3.3 Wavelet Properties11.3.4 Examples11.3.5 Advantages and Disadvantages11.4 Random Transform11.4.1 Advantages and Disadvantages11.5 Lifting-Based Wavelets11.5.1 Splitting of a Graph into Even and Odd Nodes11.5.2 Lifting-Based Transform11.6 Two-Channel Graph Wavelet Filter Banks11.6.1 Downsampling and Upsampling in Graphs11.6.2 Two-Channel Graph Wavelet Filter Banks11.6.3 Graph Quadrature-Mirror Filterbanks11.6.4 Multidimensional Separable Wavelet Filter Banks for Arbitrary Graphs11.7 Spectral Graph Wavelet Transform11.7.1 Matrix Form of SGWT11.7.2 Wavelet Generating Kernels11.7.3 An Example of SGWT11.7.4 Advantages and Disadvantages11.8 Spectral Graph Wavelet Transform Based on Directed Laplacian11.8.1 Wavelets11.8.2 Wavelet Generating Kernel11.8.3 Examples11.9 Diffusion Wavelets11.9.1 Advantages and Disadvantages11.10 Open Research Issues11.11 SummaryExercises
A Vectors and Matrices
A.1 Vectors and NormsA.1.1 Orthogonal and Orthonormal VectorsA.1.2 Linear Span of a Set of VectorsA.2 MatricesA.2.1 Trace of a MatrixA.2.2 Matrix Vector MutiplicationA.2.3 Column Space, Null Space, and Rank of a MatrixA.2.4 Special MatricesA.3 Eigenvalues and EigenvectorsA.3.1 Characteristic EquationA.3.2 EigenspacesA.3.3 Eigenvalue MultiplicityA.4 Matrix DiagonalizationA.5 Jordan DecompositionA.6 Spectral DensityA.7 Wigner’s Semicircle LawA.8 Gershgorin’s Theorem
B Classical Signal Processing
B.1 Linear Time Invariant FiltersB.1.1 Impulse Response and ConvolutionB.1.2 EigenfunctionsB.2 Fourier TransformB.2.1 Continuous-Time Fourier TransformB.2.2 Discrete-Time Fourier TransformB.2.3 Discrete Fourier TransformB.3 Digital Filter BanksB.3.1 Downsampler and UpsamplerB.4 Two-Channel Filter BankB.5 Windowed Fourier TransformB.5.1 SpectrogramB.6 Continuous-Time Wavelet Transform
C Analysis of Locations of Anchor Points
D Asymptotic Behavior of Functions
D.1 Big Oh (O(·)) NotationD.2 Big Omega (Ω(·)) NotationD.3 Big Theta (Θ(·)) Notation
E Relevant Academic Courses and Programs
E.1 Academic Courses on Complex NetworksE.2 Online Courses on Complex NetworksE.3 Selective Academic Programs on Complex Networks
F Relevant Journals and Conferences
F.1 List of Top Journals in Complex NetworksF.2 List of Top Conferences in Complex Networks
G Relevant Datasets and Visualization Tools
G.1 Relevant Dataset RepositoriesG.2 Relevant Graph Visualization and Analysis Tools
H Relevant Research Groups
H.1 Other Important Resources
Notation
Acronyms
Bibliography
Index

Content preview from Complex Networks: A Networking and Signal Processing Perspective

Appendix AVectors and Matrices

A.1 Vectors and Norms

A vector is an array of real or complex numbers. We denote vectors by lowercase bold letters and assume a vector to be a column vector. For example, a vector of length n is

$𝐱 = [\begin{matrix} x_{1} \\ x_{2} \\ ⋮ \\ x_{n} \end{matrix}] .$

The number of elements in a vector is also known as the dimension of the vector. If the elements x₁, x₂,... , x_n are real, then we say that x is a real n-dimensional vector, and we can denote it as $𝐱 \in ℝ^{n}$ . On the other hand, if the elements are complex, then we say that x is a complex n-dimensional vector, and it is denoted as $𝐱 \in ℂ^{n}$ .

Various norms are defined to measure the magnitude of a vector. One such measure is ℓ_p norm, which is defined as

(A.1.1) $| | X | |_{p} = {[Σ_{i = 1}^{n} | x_{i} |^{p}]}^{1 / p},$

where n is the dimension of ...

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.

Read now

Unlock full access

More than 5,000 organizations count on O’Reilly

O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.

Julian F.

Head of Cybersecurity

I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.

Addison B.

Field Engineer

I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.

Amir M.

Data Platform Tech Lead

I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.

Mark W.

Embedded Software Engineer

Digital Signal Processing with Kernel Methods

Publisher Resources

ISBN: 9780134787145

Cloud Computing

Data Engineering

Data Science

AI & ML

Programming Languages

Software Architecture

IT/Ops

Security

Design

Business

Soft Skills

Complex Networks: A Networking and Signal Processing Perspective

by Abhishek Chakraborty, B. S. Manoj, Rahul Singh