Erciyes Complex Networks

An Algorithmic Perspective
1. Auflage 2014
ISBN: 978-1-4665-7167-9
Verlag: Taylor & Francis
Format: PDF
Kopierschutz: Adobe DRM (»Systemvoraussetzungen)

E-Book, Englisch, 320 Seiten

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

Zielgruppe

Senior and graduate students; researchers of computer science, engineering, physics, and applied mathematics.

Autoren/Hrsg.

Erciyes, Kayhan

Fachgebiete

• Mathematik | Informatik EDV | Informatik Computerkommunikation & -vernetzung

Inhaltsverzeichnis

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

Über Autor(innen)

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