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

Table of Contents

Chapter 1: Introduction

Part I: BACKGROUND
Chapter 2: Graph Theory
Chapter 3: Algorithms and Complexity
Chapter 4: Analysis of Complex Networks

Part II: ALGORITHMS
Chapter 5: Distance and Centrality
Chapter 6: Special Subgraphs
Chapter 7: Data Clustering
Chapter 8: Graph-based Clustering
Chapter 9: Network Motif Discovery

Part III: APPLICATIONS
Chapter 10: Protein InteractionNetworks
Chapter 11: Social Networks
Chapter 12: The Internet and the Web
Chapter 13: Ad hocWireless Networks