BACKGROUND
Introduction
Overview
Real-World Complex Networks
Technological Networks
Information Networks
Social Networks
Biological Networks
Topological Properties of Complex Networks
Algorithmic Challenges
Outline of the Book
References
Graph Theory
Basics
Subgraphs
Graph Isomorphism
Types of Graphs
Paths and Cycles
Connectivity
Trees
Graph Representations
Spectral Properties of Graphs
Eigenvalues and Eigenvectors
The Laplacian Matrix
Chapter Notes
References
Algorithms and Complexity
Introduction
Time Complexity
Recurrences
Divide and Conquer Algorithms
Graph Algorithms
Breadth-first Search
Depth-first Search
Dynamic Programming
Greedy Algorithms
NP-Complete Problems
NP Completeness
Reductions
Satisfiability Problems
3-SAT to Independent Set
Independent Set to Vertex Cover
Independent Set to Clique
Coping with NP Completeness
Backtracking
Branch and Bound
Approximation Algorithms
Parallel Algorithms
Architectural Constraints
Example Algorithms
Distributed Systems and Algorithms
Chapter Notes
References
Analysis of Complex Networks
Introduction
Vertex Degrees
Degree Sequence
Degree Distribution
Communities
Clustering Coefficient
The Matching Index
Centrality
Network Motifs
Models
Small World Networks
Scale-Free Networks
Chapter Notes
References
ALGORITHMS
Distance and Centrality
Introduction
Finding Distances
Average Distance
Dijkstra’s Single Source Shortest Paths Algorithm
Floyd-Warshall All Pairs Shortest Paths Algorithm
Centrality
Degree Centrality
A Distributed Algorithm for k-hop Degree Centrality
Closeness Centrality
Stress Centrality
Betweenness Centrality
Newman’s Algorithm
Brandes’ Algorithm
Eigenvalue Centrality
Chapter Notes
References
Special Subgraphs
Introduction
Maximal Independent Sets
Dominating Sets
A Greedy MDS Algorithm
Guha-Khuller First MCDS Algorithm
Guha-Khuller Second MCDS Algorithm
Matching
A Maximal Unweighted Matching Algorithm
A MaximalWeighted Matching Algorithm
Vertex Cover
A Minimal Connected Vertex Cover Algorithm
A Minimal Weighted Vertex Cover Algorithm
A Distributed Algorithm for MWVC Construction
Chapter Notes
References
Data Clustering
Introduction
Types of Data Clustering
Agglomerative Hierarchical Clustering
k-means Algorithm
Nearest Neighbor Algorithm
Fuzzy Clustering
Density-based Clustering
Parallel Data Clustering
Chapter Notes
References
Graph-based Clustering
Introduction
Graph Partitioning
BFS-based Partitioning
Kernighan-Lin Algorithm
Spectral Bisection
Multi-level Partitioning
Parallel Partitioning
Graph Clustering
MST-based Clustering
Clustering with Clusterheads
Discovery of Dense Subgraphs
Definitions
Clique Algorithms
The First Algorithm
The Second Algorithm
k-core Algorithm
Chapter Notes
References
Network Motif Discovery
Introduction
Network Motifs
Measures of Motif Significance
Generating Null Models
Hardness of Motif Discovery
Subgraph Isomorphism
Vertex Invariants
Algorithms
Ullman’s Algorithm
Nauty Algorithm
VF2 Algorithm
BM1 Algorithm
Motif Discovery Algorithms
Exact Census Algorithms
Mf inder Algorithm
Enumerate Subgraphs (ESU) Algorithm
Grochow and Kellis Algorithm
Kavosh Algorithm
MODA
Approximate Algorithms with Sampling
Mf inder with Sampling
Randomized ESU Algorithm
MODA with Sampling
Chapter Notes
References
APPLICATIONS
Protein Interaction Networks
Introduction
Topological Properties of PPI Networks
Detection of Protein Complexes
Highly Connected Subgraphs Algorithm
Restricted Neighborhood Search Algorithm
Molecular Complex Detection Algorithm
Markov Clustering Algorithm
Network Motifs in PPI Networks
Network Alignment
Quality of the Alignment
Topological Similarity
Node Similarity
Algorithms
PathBLAST
MaWIsh
IsoRank
GRAAL
Recent Algorithms
Chapter Notes
References
Social Networks
Introduction
Relationships
Homophily
Positive and Negative Relations
Structural Balance
Equivalence
Community Detection Algorithms
Edge Betweenness-based Algorithm
Resistor Networks
RandomWalk Centrality
Modularity-based Algorithm
Chapter Notes
References
The Internet and the Web
Introduction
The Internet
Services
Services of Connection
Circuit and Packet Switching
Internet Protocol Suite
Analysis
The Web
The Web Graph
Properties
Models
Evolving Model
Copying Model
Growth-deletion Model
Multi-layer Model
Cyber Community Detection
Link Analysis
Hubs and Authorities
Page Rank Algorithm
Chapter Notes
References
Ad hoc Wireless Networks
Introduction
Clustering Algorithms
Lowest-ID Algorithm
Dominating Set-based Clustering
Spanning Tree-based Clustering
Mobile Social Networks
Architecture
Community Detection
Middleware
MobiSoC
MobiClique
SAMOA
Yarta
Chapter Notes
References
Index
Biography
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
