Muutke küpsiste eelistusi

Complex Networks: A Networking and Signal Processing Perspective [Kõva köide]

, ,
  • Formaat: Hardback, 576 pages, kõrgus x laius x paksus: 236x185x36 mm, kaal: 800 g
  • Ilmumisaeg: 29-Jun-2018
  • Kirjastus: Pearson
  • ISBN-10: 0134786998
  • ISBN-13: 9780134786995
Teised raamatud teemal:
Complex Networks: A Networking and Signal Processing PerspectiveSuurem pilt
  • Formaat: Hardback, 576 pages, kõrgus x laius x paksus: 236x185x36 mm, kaal: 800 g
  • Ilmumisaeg: 29-Jun-2018
  • Kirjastus: Pearson
  • ISBN-10: 0134786998
  • ISBN-13: 9780134786995
Teised raamatud teemal:
Püsilink: https://www.kriso.ee/db/9780134786995.html
Märksõnad:

Advances in complex networks and graph signal processing have important implications in fields ranging from communications and social networking to big data and biology. In Complex Networks, three pioneering researchers offer balanced, up-to-date coverage that will be ideal for advanced undergraduates, graduate students, researchers, and industry practitioners alike.

 

The authors begin by introducing the fundamental concepts underlying graph theory and complex networks. Next, they illuminate current theory and research in random networks, small-world networks, scale-free networks, and both small-world wireless mesh and sensor networks. Readers will find full chapters on spectra and signal processing in complex networks, as well as detailed introductions to graph signal processing approaches for extracting information from structural data, as well as advanced multiscale analysis techniques.

 

To promote deeper learning and mastery, the book contains 100+ examples, 200+ figures, and 20+ comparison tables. Each chapter includes problems as well as a section describing open research issues in the field. Appendices provide valuable reference information about vectors, matrices, anchor points, classical multiscale analysis, asymptotic behavior of functions, and additional resources for students and researchers in the field.

Preface xvii
Acknowledgments xxi
About the Authors xxvii
About the Cover xxxi
1 Introduction 1(12)
1.1 Complex Networks
1(2)
1.2 Types of Complex Networks
3(2)
1.3 Benefits of Studying Complex Networks
5(3)
1.3.1 Modeling and Characterizing Complex Physical World Systems
6(1)
1.3.2 Design of New and Efficient Physical World Systems
6(1)
1.3.3 Development of Solutions to Complex Real-World Problems
7(1)
1.3.4 Enhancing Biomedical Research through Molecular Network Modeling
7(1)
1.3.5 Network Medicine
7(1)
1.3.6 Neutralizing Antisocial Networks
7(1)
1.3.7 Enhanced Social Science Research through Social Networks
8(1)
1.4 Challenges in Studying Complex Networks
8(1)
1.5 What This Book Offers
9(1)
1.6 Organization of the Book
9(3)
1.6.1 Suggested Navigation for Contents of the Book
11(1)
1.7 Support Materials Available for Instructors
12(1)
1.8 Summary
12(1)
2 Graph Theory Preliminaries 13(46)
2.1 Introduction
13(2)
2.2 Graphs
15(3)
2.2.1 Subgraphs
16(1)
2.2.2 Complement of a Graph
17(1)
2.3 Matrices Related to a Graph
18(5)
2.3.1 Weight Matrix
18(1)
2.3.2 Adjacency Matrix
19(1)
2.3.3 Incidence Matrix
19(1)
2.3.4 Degree Matrix
20(1)
2.3.5 Laplacian Matrix
20(3)
2.4 Basic Graph Metrics
23(4)
2.4.1 Average Neighbor Degree
23(1)
2.4.2 Average Clustering Coefficient
23(1)
2.4.3 Average Path Length
24(2)
2.4.4 Average Edge Length
26(1)
2.4.5 Graph Diameter and Volume
26(1)
2.5 Basic Graph Definitions and Properties
27(14)
2.5.1 Walk, Path, and Circuits
27(1)
2.5.2 Connectivity
27(2)
2.5.3 Acyclicity
29(3)
2.5.4 Isomorphism
32(1)
2.5.5 Planarity
32(2)
2.5.6 Colorability
34(1)
2.5.7 Traversability
35(1)
2.5.8 Network Flows
36(2)
2.5.9 Product Graphs
38(3)
2.6 Types of Graphs
41(7)
2.6.1 Regular Graph
41(1)
2.6.2 Bipartite Graphs
41(1)
2.6.3 Complete Graphs
42(1)
2.6.4 Trees
42(3)
2.6.5 Line Graph
45(1)
2.6.6 Conflict Graphs
46(2)
2.7 Other Important Measures for Graphs
48(1)
2.7.1 Cheeger Constant
48(1)
2.7.2 Clique Number
48(1)
2.8 Graph Pathfinding Algorithms
49(4)
2.8.1 Dijkstra's Shortest Path Algorithm
49(3)
2.8.2 All-Pair Shortest Path Algorithm
52(1)
2.9 Summary
53(1)
Exercises
54(5)
3 Introduction to Complex Networks 59(48)
3.1 Major Types of Complex Networks
59(3)
3.1.1 Random Networks
60(1)
3.1.2 Small-World Networks
60(1)
3.1.3 Scale-Free Networks
61(1)
3.2 Complex Network Metrics
62(8)
3.2.1 Average Neighbor Degree
62(1)
3.2.2 Average Path Length
62(1)
3.2.3 Network Diameter
62(1)
3.2.4 Average Clustering Coefficient
62(1)
3.2.5 Degree Distribution
63(1)
3.2.6 Centrality Metrics
63(5)
3.2.7 Degree-Degree Correlation in Complex Networks
68(1)
3.2.8 Node Criticality
69(1)
3.2.9 Network Resistance Distance
70(1)
3.3 Community Detection in Complex Networks
70(14)
3.3.1 Modularity Maximization
71(1)
3.3.2 Surprise Maximization
72(1)
3.3.3 Conflict Graph Transformation-Based Community Detection
72(12)
3.4 Entropy in Complex Network
84(12)
3.4.1 Network Entropy
84(1)
3.4.2 Nodal Degree Entropy
85(1)
3.4.3 Link Length Variability Entropy
86(1)
3.4.4 Link Influence Entropy
86(10)
3.5 Random Networks
96(4)
3.5.1 Evolution of Random Networks
96(1)
3.5.2 Erdos-Renyi Random Network Model
96(1)
3.5.3 Properties of Random Networks
97(3)
3.6 Open Research Issues
100(1)
3.7 Summary
101(1)
Exercises
102(5)
4 Small-World Networks 107(70)
4.1 Introduction
107(2)
4.2 Milgram's Small-World Experiment
109(1)
4.3 Characteristics of Small-World Networks
110(4)
4.4 Real-World Small-World Networks
114(3)
4.5 Creation and Evolution of Small-World Networks
117(8)
4.5.1 Rewiring of Existing Links
118(2)
4.5.2 Pure Random Addition of New LLs
120(3)
4.5.3 Euclidean Distance-Based Addition of New Links
123(2)
4.6 Capacity-Based Deterministic Addition of New Links
125(5)
4.6.1 Max-Flow Min-Cut Theorem
125(3)
4.6.2 Link Addition Based on Maximum Flow Capacity Strategy
128(2)
4.7 Creation of Deterministic Small-World Networks
130(4)
4.7.1 Link Addition Based on Minimum APL
131(2)
4.7.2 Link Addition Based on Minimum AEL
133(1)
4.7.3 Link Addition Based on Maximum BC
134(1)
4.7.4 Link Addition Based on Maximum CC
134(1)
4.8 Anchor Points in a String Topology Small-World Network
134(5)
4.8.1 Significance of Anchor Points
135(1)
4.8.2 Locations of Anchor Points
136(3)
4.9 Heuristic Approach-Based Deterministic Link Addition
139(20)
4.9.1 Maximum Closeness Centrality Disparity
140(6)
4.9.2 Sequential Deterministic LL Addition
146(5)
4.9.3 Average Flow Capacity Enhancement Using Small-World Characteristics
151(8)
4.10 Routing in Small-World Networks
159(7)
4.10.1 The Decentralized Routing Algorithm
160(1)
4.10.2 The Adaptive Decentralized Routing Algorithm
161(4)
4.10.3 The Lookahead Routing Algorithm
165(1)
4.11 Capacity of Small-World Networks
166(2)
4.11.1 Capacity of Small-World Networks with Rewiring of Existing NLs
167(1)
4.11.2 Capacity of Small-World Networks with LL Addition
168(1)
4.12 Open Research Issues
168(1)
4.13 Summary
169(2)
Exercises
171(6)
5 Scale-Free Networks 177(44)
5.1 Introduction
177(2)
5.1.1 What Does Scale-Free Mean?
178(1)
5.2 Characteristics of Scale-Free Networks
179(4)
5.3 Real-World Scale-Free Networks
183(13)
5.3.1 The Author Citation Networks
183(1)
5.3.2 The Autonomous Systems in the Internet
183(1)
5.3.3 The Air Traffic Networks
184(1)
5.3.4 Identification of Scale-Free Networks
185(11)
5.4 Scale-Free Network Formation
196(2)
5.4.1 Scale-Free Network Creation by Preferential Attachment
196(1)
5.4.2 Scale-Free Network Creation by Fitness-Based Modeling
197(1)
5.4.3 Scale-Free Network Creation by Varying Intrinsic Fitness
197(1)
5.4.4 Scale-Free Network Creation by Optimization
197(1)
5.4.5 Scale-Free Network Creation with Exponent 1
198(1)
5.4.6 Scale-Free Network Creation with Greedy Global Decision Making
198(1)
5.5 Preferential Attachment-Based Scale-Free Network Creation
198(2)
5.5.1 Barabasi-Albert (BA) Network Model
199(1)
5.5.2 Observations and Discussion
200(1)
5.6 Fitness-Based Scale-Free Network Creation
200(2)
5.6.1 Fitness-Based Network Model
201(1)
5.6.2 Observations and Discussion
202(1)
5.7 Varying Intrinsic Fitness-Based Scale-Free Network Creation
202(1)
5.7.1 Varying Intrinsic Fitness-Based Network Model
203(1)
5.7.2 Observations and Discussion
203(1)
5.8 Optimization-Based Scale-Free Network Creation
203(3)
5.8.1 Observations and Discussion
205(1)
5.9 Scale-Free Network Creation with Exponent 1
206(2)
5.9.1 Scale-Free Network Creation with Rewiring
206(2)
5.9.2 Observations and Discussion
208(1)
5.10 Greedy Global Decision-Based Scale-Free Network Creation
208(5)
5.10.1 Greedy Global LL Addition
208(3)
5.10.2 Observations on Greedy Global Decision-Based Scale-Free Network
211(2)
5.11 Deterministic Scale-Free Network Creation
213(2)
5.11.1 Deterministic Scale-Free Network Model
213(1)
5.11.2 Observations on Deterministic Scale-Free Network Creation
214(1)
5.12 Open Research Issues
215(1)
5.13 Summary
216(2)
Exercises
218(3)
6 Small-World Wireless Mesh Networks 221(46)
6.1 Introduction
221(3)
6.1.1 The Small-World Characteristics
223(1)
6.1.2 Small-World Wireless Mesh Networks
224(1)
6.2 Classification of Small-World Wireless Mesh Networks
224(1)
6.3 Creation of Random Long-Ranged Links
225(3)
6.3.1 Random LL Creation by Rewiring the Normal Links
227(1)
6.3.2 Random LL Creation by Addition of New Links
228(1)
6.4 Small-World Based on Pure Random Link Addition
228(1)
6.5 Small-World Based on Euclidean Distance
229(1)
6.6 Realization of Small-World Networks Based on Antenna Metrics
230(4)
6.6.1 LL Addition Based on Transmission Power
230(1)
6.6.2 LL Addition Based on Randomized Beamforming
231(2)
6.6.3 LL Addition Based on Transmission Power and Beamforming
233(1)
6.7 Algorithmic Approaches to Create Small-World Wireless Mesh Networks
234(1)
6.7.1 Contact-Based LL Creation
234(1)
6.7.2 Genetic Algorithm-Based LL Addition
235(1)
6.7.3 Small-World Cooperative Routing-Based LL Addition
235(2)
6.8 Gateway-Router-Centric Small-World Network Formation
237(8)
6.8.1 Single Gateway-Router-Based LL Addition
237(5)
6.8.2 Multi-Gateway-Router-Based LL Addition
242(3)
6.9 Creation of Deterministic Small-World Wireless Mesh Networks
245(3)
6.9.1 Exhaustive Search-Based Deterministic LL Addition
247(1)
6.9.2 Heuristic Approach-Based Deterministic LL Addition
247(1)
6.10 Creation of Non-Persistent Small-World Wireless Mesh Networks
248(4)
6.10.1 Data-Mule-Based LL Creation
248(1)
6.10.2 Load-Aware Long-Ranged Link Creation
249(3)
6.11 Non-Persistent Routing in Small-World Wireless Mesh Networks
252(5)
6.11.1 Load-Aware Non-Persistent Small-World Routing
253(2)
6.11.2 Performance Evaluation of LNPR Algorithm
255(2)
6.12 Qualitative Comparison of Existing Solutions
257(3)
6.13 Open Research Issues
260(1)
6.14 Summary
261(2)
Exercises
263(4)
7 Small-World Wireless Sensor Networks 267(42)
7.1 Introduction
267(2)
7.2 Small-World Wireless Mesh Networks vs. Small-World Wireless Sensor Networks
269(2)
7.3 Why Small-World Wireless Sensor Networks?
271(4)
7.4 Challenges in Transforming WSNs to SWWSNs
275(2)
7.5 Types of Long-Ranged Links for SWWSNs
277(1)
7.6 Approaches for Transforming WSNs to SWWSNs
278(21)
7.6.1 Classification of Existing Approaches
279(1)
7.6.2 Metrics for Performance Estimation
279(2)
7.6.3 Transforming Regular Topology WSNs to SWWSNs
281(5)
7.6.4 Random Model Heterogeneous SWWSNs
286(1)
7.6.5 Newman-Watts Model-Based SWWSNs
287(1)
7.6.6 Kleinberg Model-Based SWWSNs
288(1)
7.6.7 Directed Random Model-Based SWWSNs
289(3)
7.6.8 Variable Rate Adaptive Modulation-Based SWWSNs
292(2)
7.6.9 Degree-Based LL Addition for Creating SWWSNs
294(2)
7.6.10 Inhibition Distance-Based LL Addition for Creating SWWSNs
296(1)
7.6.11 Homogeneous SWWSNs
296(3)
7.7 SWWSNs with Wired LLs
299(2)
7.8 Open Research Issues
301(3)
7.9 Summary
304(1)
Exercises
305(4)
8 Spectra of Complex Networks 309(32)
8.1 Introduction
309(1)
8.2 Spectrum of a Graph
310(2)
8.3 Adjacency Matrix Spectrum of a Graph
312(4)
8.3.1 Bounds on the Eigenvalues
313(1)
8.3.2 Adjacency Matrix Spectra of Special Graphs
313(3)
8.4 Adjacency Matrix Spectra of Complex Networks
316(6)
8.4.1 Random Networks
317(1)
8.4.2 Random Regular Networks
318(1)
8.4.3 Small-World Networks
319(2)
8.4.4 Scale-Free Networks
321(1)
8.5 Laplacian Spectrum of a Graph
322(9)
8.5.1 Bounds on the Eigenvalues of the Laplacian
323(1)
8.5.2 Bounds on the Eigenvalues of the Normalized Laplacian
324(1)
8.5.3 Matrix Tree Theorem
324(1)
8.5.4 Laplacian Spectrum and Graph Connectivity
325(2)
8.5.5 Spectral Graph Clustering
327(1)
8.5.6 Laplacian Spectra of Special Graphs
328(3)
8.6 Laplacian Spectra of Complex Networks
331(4)
8.6.1 Random Networks
331(1)
8.6.2 Random Regular Networks
332(1)
8.6.3 Small-World Networks
332(2)
8.6.4 Scale-Free Networks
334(1)
8.7 Network Classification Using Spectral Densities
335(1)
8.8 Open Research Issues
335(1)
8.9 Summary
336(1)
Exercises
337(4)
9 Signal Processing on Complex Networks 341(52)
9.1 Introduction to Graph Signal Processing
341(4)
9.1.1 Mathematical Representation of Graph Signals
345(1)
9.2 Comparison between Classical and Graph Signal Processing
345(3)
9.2.1 Relationship between GFT and Classical DFT
347(1)
9.3 The Graph Laplacian as an Operator
348(1)
9.3.1 Properties of the Graph Laplacian
348(1)
9.3.2 Graph Spectrum
349(1)
9.4 Quantifying Variations in Graph Signals
349(2)
9.5 Graph Fourier Transform
351(10)
9.5.1 Notion of Frequency and Frequency Ordering
354(4)
9.5.2 Bandlimited Graph Signals
358(1)
9.5.3 Effect of Vertex Indexing
358(3)
9.6 Generalized Operators for Graph Signals
361(6)
9.6.1 Filtering
361(2)
9.6.2 Convolution
363(2)
9.6.3 Translation
365(1)
9.6.4 Modulation
366(1)
9.7 Applications
367(14)
9.7.1 Spectral Analysis of Node Centralities
367(8)
9.7.2 Graph Fourier Transform Centrality
375(4)
9.7.3 Malfunction Detection in Sensor Networks
379(2)
9.8 Windowed Graph Fourier Transform
381(2)
9.8.1 Example of WGFT
383(1)
9.9 Open Research Issues
383(2)
9.10 Summary
385(1)
Exercises
386(7)
10 Graph Signal Processing Approaches 393(36)
10.1 Introduction
393(1)
10.2 Graph Signal Processing Based on Laplacian Matrix
394(1)
10.3 DSPG Framework
394(3)
10.3.1 Linear Graph Filters and Shift Invariance
395(2)
10.4 DSPG Framework Based on Weight Matrix
397(8)
10.4.1 Shift Operator
397(1)
10.4.2 Linear Shift Invariant Graph Filters
398(1)
10.4.3 Total Variation
399(1)
10.4.4 Graph Fourier Transform
400(4)
10.4.5 Frequency Response of LSI Graph Filters
404(1)
10.5 DSPG Framework Based on Directed Laplacian
405(10)
10.5.1 Directed Laplacian
405(1)
10.5.2 Shift Operator
406(1)
10.5.3 Linear Shift Invariant Graph Filters
407(1)
10.5.4 Total Variation
408(1)
10.5.5 Graph Fourier Transform Based on Directed Laplacian
409(6)
10.5.6 Frequency Response of LSI Graph Filters
415(1)
10.6 Comparison of Graph Signal Processing Approaches
415(1)
10.7 Open Research Issues
416(1)
10.8 Summary
417(2)
Exercises
419(10)
11 Multiscale Analysis of Complex Networks 429(32)
11.1 Introduction
429(1)
11.2 Multiscale Transforms for Complex Network Data
430(2)
11.2.1 Vertex Domain Designs
431(1)
11.2.2 Spectral Domain Designs
431(1)
11.3 Crovella and Kolaczyk Wavelet Transform
432(3)
11.3.1 CK Wavelets
432(1)
11.3.2 Wavelet Transform
433(1)
11.3.3 Wavelet Properties
434(1)
11.3.4 Examples
434(1)
11.3.5 Advantages and Disadvantages
435(1)
11.4 Random Transform
435(2)
11.4.1 Advantages and Disadvantages
437(1)
11.5 Lifting-Based Wavelets
437(2)
11.5.1 Splitting of a Graph into Even and Odd Nodes
437(1)
11.5.2 Lifting-Based Transform
438(1)
11.6 Two-Channel Graph Wavelet Filter Banks
439(7)
11.6.1 Downsampling and Upsampling in Graphs
439(4)
11.6.2 Two-Channel Graph Wavelet Filter Banks
443(2)
11.6.3 Graph Quadrature-Mirror Filterbanks
445(1)
11.6.4 Multidimensional Separable Wavelet Filter Banks for Arbitrary Graphs
445(1)
11.7 Spectral Graph Wavelet Transform
446(4)
11.7.1 Matrix Form of SGWT
447(1)
11.7.2 Wavelet Generating Kernels
448(1)
11.7.3 An Example of SGWT
448(1)
11.7.4 Advantages and Disadvantages
449(1)
11.8 Spectral Graph Wavelet Transform Based on Directed Laplacian
450(4)
11.8.1 Wavelets
451(1)
11.8.2 Wavelet Generating Kernel
452(1)
11.8.3 Examples
453(1)
11.9 Diffusion Wavelets
454(1)
11.9.1 Advantages and Disadvantages
455(1)
11.10 Open Research Issues
455(1)
11.11 Summary
456(1)
Exercises
457(4)
A Vectors and Matrices 461(10)
A.1 Vectors and Norms
461(1)
A.1.1 Orthogonal and Orthonormal Vectors
462(1)
A.1.2 Linear Span of a Set of Vectors
462(1)
A.2 Matrices
462(2)
A.2.1 Trace of a Matrix
462(1)
A.2.2 Matrix Vector Multiplication
463(1)
A.2.3 Column Space, Null Space, and Rank of a Matrix
463(1)
A.2.4 Special Matrices
463(1)
A.3 Eigenvalues and Eigenvectors
464(2)
A.3.1 Characteristic Equation
465(1)
A.3.2 Eigenspaces
465(1)
A.3.3 Eigenvalue Multiplicity
465(1)
A.4 Matrix Diagonalization
466(1)
A.5 Jordan Decomposition
466(1)
A.6 Spectral Density
467(1)
A.7 Wigner's Semicircle Law
468(1)
A.8 Gershgorin's Theorem
469(2)
B Classical Signal Processing 471(8)
B.1 Linear Time Invariant Filters
471(1)
B.1.1 Impulse Response and Convolution
471(1)
B.1.2 Eigenfunctions
471(1)
B.2 Fourier Transform
472(2)
B.2.1 Continuous-Time Fourier Transform
472(1)
B.2.2 Discrete-Time Fourier Transform
472(1)
B.2.3 Discrete Fourier Transform
473(1)
B.3 Digital Filter Banks
474(1)
B.3.1 Downsampler and Upsampler
474(1)
B.4 Two-Channel Filter Bank
475(1)
B.5 Windowed Fourier Transform
476(1)
B.5.1 Spectrogram
476(1)
B.6 Continuous-Time Wavelet Transform
477(2)
C Analysis of Locations of Anchor Points 479(6)
D Asymptotic Behavior of Functions 485(4)
D.1 Big Oh Notation
485(1)
D.2 Big Omega Notation
486(1)
D.3 Big Theta Notation
486(3)
E Relevant Academic Courses and Programs 489(4)
E.1 Academic Courses on Complex Networks
489(2)
E.2 Online Courses on Complex Networks
491(1)
E.3 Selective Academic Programs on Complex Networks
492(1)
F Relevant Journals and Conferences 493(6)
F.1 List of Top Journals in Complex Networks
493(2)
F.2 List of Top Conferences in Complex Networks
495(4)
G Relevant Datasets and Visualization Tools 499(4)
G.1 Relevant Dataset Repositories
499(1)
G.2 Relevant Graph Visualization and Analysis Tools
500(3)
H Relevant Research Groups 503(4)
H.1 Other Important Resources
506(1)
Notation 507(2)
Acronyms 509(4)
Bibliography 513(16)
Index 529
B. S. Manoj is an associate professor in the Department of Avionics, Indian Institute of Space science and Technology (IIST), Thiruvananthapuram, India. He received his Ph.D. in computer science and engineering from the Indian Institute of Technology, Madras. Before joining IIST, he worked as assistant research scientist and lecturer in the Electrical and Computer Engineering Department, University of California at San Diego (UCSD). He has authored more than 140 publications, including 1 textbook, 9 contributed textbook chapters, 32 international journal publications, more than 90 international conference/workshop publications, and 7 Indian national conferences. He is coauthor of Ad Hoc Wireless Networks: Architectures and Protocols (Prentice Hall, 2004), which is widely used by many universities around the world.

 

Abhishek Chakraborty is currently working as a senior research fellow in the Department of Avionics at Indian Institute of Space science and Technology (IIST), Thiruvananthapuram, India. He obtained his M.E. degree in 2012 from Birla Institute of Technology (BIT), Mesra, India. Prior to that he worked as a programmer analyst at Cognizant Inc., India. From 2012 through 2013, he served as the IEEE Student Branch Chair at IIST. His current research interests focus on small-world networks, scale-free networks, signal processing over networks, wireless mesh networks, and wireless communications.

 

Rahul Singh is currently working toward his Ph.D. at Iowa State University. He obtained his M.Tech. degree in 2015 from Indian Institute of Space science and Technology (IIST), Thiruvananthapuram, India. He was a senior project fellow in the Department of Avionics at IIST, working on the area of complex networks. From 2011 through 2013, he worked in Tata Consultancy Services Ltd. His current research focuses on statistical signal processing and signal processing over networks.