Complex networks : an algorithmic perspective

Network science is a rapidly emerging field of study that encompasses mathematics, computer science, physics, and engineering. A key issue in the study of complex networks is to understand the collective behavior of the various elements of these networks.

Although the results from graph theory have proven to be powerful in investigating the structures of complex networks, few books focus on the algorithmic aspects of complex network analysis. Filling this need, Complex Networks: An Algorithmic Perspective supplies the basic theoretical algorithmic and graph theoretic knowledge needed by every researcher and student of complex networks.

This book is about specifying, classifying, designing, and implementing mostly sequential and also parallel and distributed algorithms that can be used to analyze the static properties of complex networks. Providing a focused scope which consists of graph theory and algorithms for complex networks, the book identifies and describes a repertoire of algorithms that may be useful for any complex network.

Provides the basic background in terms of graph theory Supplies a survey of the key algorithms for the analysis of complex networks Presents case studies of complex networks that illustrate the implementation of algorithms in real-world networks, including protein interaction networks, social networks, and computer networks

Requiring only a basic discrete mathematics and algorithms background, the book supplies guidance that is accessible to beginning researchers and students with little background in complex networks. To help beginners in the field, most of the algorithms are provided in ready-to-be-executed form.

While not a primary textbook, the author has included pedagogical features such as learning objectives, end-of-chapter summaries, and review questions

Author Notes

Kayhan Erciyes is a professor of computer science and engineering and also the rector of Izmir University, Izmir, Turkey. Dr. Erciyes worked as a research and development engineer of Alcatel Turkey, Alcatel Portugal, and Alcatel SEL. He has worked as faculty in Oregon State University, UC Davis and California State University, US and Izmir and Aegean universities. His research interests are on distributed systems, graph theory and distributed algorithms for complex networks, mobile ad hoc networks, wireless sensor networks and the Grid and has published extensively in these areas. Dr. Erciyes is the designer and implementer of one of the first commercially available MODEMs in Turkey

List of Figures	p. xv
List of Tables	p. xxi
Preface	p. xxiii
1 Introduction	p. 1
1.1 Overview	p. 1
1.2 Real-world Complex Networks	p. 2
1.2.1 Technological Networks	p. 2
1.2.2 Information Networks	p. 3
1.2.3 Social Networks	p. 3
1.2.4 Biological Networks	p. 4
1.3 Topological Properties of Complex Networks	p. 5
1.4 Algorithmic Challenges	p. 6
1.5 Outline of the Book	p. 7
References	p. 7
Section I Background	p. 9
2 Graph Theory	p. 11
2.1 Basics	p. 11
2.2 Subgraphs	p. 12
2.3 Graph Isomorphism	p. 13
2.4 Types of Graphs	p. 14
2.5 Paths and Cycles	p. 15
2.6 Connectivity	p. 16
2.7 Trees	p. 18
2.8 Graph Representations	p. 19
2.9 Spectral Properties of Graphs	p. 19
2.9.1 Eigenvalues and Eigenvectors	p. 20
2.9.2 The Laplacian Matrix	p. 21
2.10 Chapter Notes	p. 22
References	p. 24
3 Algorithms and Complexity	p. 27
3.1 Introduction	p. 27
3.2 Time Complexity	p. 29
3.3 Recurrences	p. 31
3.4 Divide and Conquer Algorithms	p. 32
3.5 Graph Algorithms	p. 33
3.5.1 Breadth-first Search	p. 34
3.5.2 Depth-first Search	p. 36
3.6 Dynamic Programming	p. 37
3.7 Greedy Algorithms	p. 39
3.8 NP-complete Problems	p. 41
3.8.1 NP Completeness	p. 41
3.8.2 Reductions	p. 43
3.8.2.1 Satisfiability Problems	p. 44
3.8.2.2 3-SAT to Independent Set	p. 45
3.8.2.3 Independent Set to Vertex Cover	p. 45
3.8.2.4 Independent Set to Clique	p. 46
3.9 Coping with NP Completeness	p. 48
3.9.1 Backtracking	p. 48
3.9.2 Branch and Bound	p. 49
3.10 Approximation Algorithms	p. 50
3.11 Parallel Algorithms	p. 53
3.11.1 Architectural Constraints	p. 54
3.11.2 Example Algorithms	p. 54
3.12 Distributed Systems and Algorithms	p. 57
3.13 Chapter Notes	p. 59
References	p. 61
4 Analysis of Complex Networks	p. 63
4.1 Introduction	p. 63
4.2 Vertex Degrees	p. 64
4.2.1 Degree Sequence	p. 65
4.2.2 Degree Distribution	p. 66
4.3 Communities	p. 67
4.3.1 Clustering Coefficient	p. 68
4.4 The Matching Index	p. 70
4.5 Centrality	p. 70
4.6 Network Motifs	p. 71
4.7 Models	p. 72
4.7.1 Classical Random Networks	p. 72
4.7.2 Small World Networks	p. 72
4.7.3 Scale-Free Networks	p. 73
4.8 Chapter Notes	p. 75
References	p. 77
Section II Algorithms	p. 79
5 Distance and Centrality	p. 81
5.1 Introduction	p. 81
5.2 Finding Distances	p. 81
5.2.1 Average Distance	p. 83
5.2.2 Dijkstra's Single Source Shortest Paths Algorithm	p. 83
5.2.3 Floyd-Warshall All Pairs Shortest Paths Algorithm	p. 84
5.3 Centrality	p. 87
5.3.1 Degree Centrality	p. 87
5.3.1.1 A Distributed Algorithm for k-hop Degree Centrality	p. 89
5.3.2 Closeness Centrality	p. 91
5.3.3 Stress Centrality	p. 92
5.3.4 Betweenness Centrality	p. 93
5.3.4.1 Newman's Algorithm	p. 94
5.3.4.2 Brandes' Algorithm	p. 95
5.3.5 Eigenvalue Centrality	p. 96
5.4 Chapter Notes	p. 97
References	p. 99
6 Special Subgraphs	p. 101
6.1 Introduction	p. 101
6.2 Maximal Independent Sets	p. 102
6.3 Dominating Sets	p. 103
6.3.1 A Greedy MDS Algorithm	p. 105
6.3.2 Guha-Khuller First MCDS Algorithm	p. 106
6.3.3 Guha-Khuller Second MCDS Algorithm	p. 106
6.4 Matching	p. 108
6.4.1 A Maximal Unweighted Matching Algorithm	p. 109
6.4.2 A Maximal Weighted Matching Algorithm	p. 109
6.5 Vertex Cover	p. 110
6.5.1 A Minimal Connected Vertex Cover Algorithm	p. 112
6.5.2 A Minimal Weighted Vertex Cover Algorithm	p. 113
6.6 A Distributed Algorithm for MWVC Construction	p. 114
6.7 Chapter Notes	p. 116
References	p. 118
7 Data Clustering	p. 121
7.1 Introduction	p. 121
7.2 Types of Data Clustering	p. 122
7.3 Agglomerative Hierarchical Clustering	p. 123
7.4 k-means Algorithm	p. 127
7.5 Nearest Neighbor Algorithm	p. 132
7.6 Fuzzy Clustering	p. 132
7.7 Density-based Clustering	p. 134
7.8 Parallel Data Clustering	p. 137
7.9 Chapter Notes	p. 138
References	p. 141
8 Graph-based Clustering	p. 143
8.1 Introduction	p. 143
8.2 Graph Partitioning	p. 144
8.2.1 BFS-based Partitioning	p. 145
8.2.2 Kernighan-Lin Algorithm	p. 147
8.2.3 Spectral Bisection	p. 151
8.2.4 Multi-level Partitioning	p. 152
8.2.5 Parallel Partitioning	p. 154
8.3 Graph Clustering	p. 155
8.3.1 MST-based Clustering	p. 156
8.3.2 Clustering with Clusterheads	p. 157
8.4 Discovery of Dense Subgraphs	p. 158
8.4.1 Definitions	p. 159
8.4.2 Clique Algorithms	p. 160
8.4.2.1 The First Algorithm	p. 160
8.4.2.2 The Second Algorithm	p. 161
8.4.3 k-core Algorithm	p. 162
8.5 Chapter Notes	p. 164
References	p. 167
9 Network Motif Discovery	p. 169
9.1 Introduction	p. 169
9.2 Network Motifs	p. 170
9.2.1 Measures of Motif Significance	p. 172
9.2.2 Generating Null Models	p. 173
9.2.3 Hardness of Motif Discovery	p. 174
9.3 Subgraph Isomorphism	p. 174
9.3.1 Vertex Invariants	p. 174
9.3.2 Algorithms	p. 175
9.3.2.1 Ullman's Algorithm	p. 176
9.3.2.2 Nauty Algorithm	p. 178
9.3.2.3 VF2 Algorithm	p. 179
9.3.2.4 BM1 Algorithm	p. 180
9.4 Motif Discovery Algorithms	p. 181
9.4.1 Exact Census Algorithms	p. 182
9.4.1.1 M finder Algorithm	p. 182
9.4.1.2 Enumerate Subgraphs (ESU) Algorithm	p. 183
9.4.1.3 Grochow and Kellis Algorithm	p. 184
9.4.1.4 Kavosh Algorithm	p. 186
9.4.1.5 MODA	p. 188
9.4.2 Approximate Algorithms with Sampling	p. 190
9.4.2.1 M finder with Sampling	p. 193
9.4.2.2 Randomized ESU Algorithm	p. 192
9.4.2.3 MODA with Sampling	p. 194
9.5 Chapter Notes	p. 194
References	p. 197
Section III Applications	p. 201
10 Protein Interaction Networks	p. 203
10.1 Introduction	p. 203
10.2 Topological Properties of PPI Networks	p. 204
10.3 Detection of Protein Complexes	p. 206
10.3.1 Highly Connected Subgraphs Algorithm	p. 206
10.3.2 Restricted Neighborhood Search Algorithm	p. 207
10.3.3 Molecular Complex Detection Algorithm	p. 208
10.3.4 Markov Clustering Algorithm	p. 209
10.4 Network Motifs in PPI Networks	p. 211
10.5 Network Alignment	p. 214
10.5.1 Quality of the Alignment	p. 216
10.5.1.1 Topological Similarity	p. 216
10.5.1.2 Node Similarity	p. 216
10.5.2 Algorithms	p. 217
10.5.2.1 Pat liB LAST	p. 217
10.5.2.2 MaWIsh	p. 217
10.5.2.3 JsoRank	p. 218
10.5.2.4 GRAAL	p. 219
10.5.2.5 Recent Algorithms	p. 220
10.6 Chapter Notes	p. 220
References	p. 223
11 Social Networks	p. 227
11.1 Introduction	p. 227
11.2 Relationships	p. 228
11.2.1 Homopbily	p. 228
11.2.2 Positive and Negative Relations	p. 229
11.2.3 Structural Balance	p. 230
11.3 Equivalence	p. 232
11.4 Community Detection Algorithms	p. 233
11.4.1 Edge Betweenness-based Algorithm	p. 233
11.4.2 Resistor Networks	p. 237
11.4.3 Random Walk Centrality	p. 238
11.4.4 Modularity-based Algorithm	p. 239
11.5 Chapter Notes	p. 241
References	p. 244
12 The Internet and the Web	p. 245
12.1 Introduction	p. 245
12.2 The Internet	p. 245
12.2.1 Services	p. 246
12.2.1.1 Services of Connection	p. 246
12.2.1.2 Circuit and Packet Switching	p. 247
12.2.1.3 Internet Protocol Suite	p. 247
12.2.2 Analysis	p. 248
12.3 The Web	p. 249
12.3.1 The Web Graph	p. 250
12.3.1.1 Properties	p. 251
12.3.1.2 Evolving Model	p. 253
12.3.1.3 Copying Model	p. 253
12.3.1.4 Growth-deletion Model	p. 254
12.3.1.5 Multi-layer Model	p. 254
12.3.1.6 Cyber Community Detection	p. 255
12.3.2 Link Analysis	p. 256
12.3.2.1 Hubs and Authorities	p. 258
12.3.2.2 Page Rank Algorithm	p. 259
12.4 Chapter Notes	p. 263
References	p. 265
13 Ad hoc Wireless Networks	p. 269
13.1 Introduction	p. 269
13.2 Clustering Algorithms	p. 271
13.2.1 Lowest-ID Algorithm	p. 271
13.2.2 Dominating Set-based Clustering	p. 273
13.2.3 Spanning Tree-based Clustering	p. 275
13.3 Mobile Social Networks	p. 277
13.3.1 Architecture	p. 278
13.3.2 Community Detection	p. 278
13.3.3 Middleware	p. 281
13.3.3.1 MobiSoC	p. 282
13.3.3.2 MobiClique	p. 282
13.3.3.3 SAMOA	p. 283
13.33.4 Yarta	p. 284
13.4 Chapter Notes	p. 285
References	p. 287
Index	p. 291

Available:*

On Order

Summary

Summary

Author Notes

Table of Contents