Networks: An Introduction

Post date: Sep 15, 2011 9:42:21 PM

Networks have always been relevant to computer scientists, since graphs provide a nice mathematical model to represent relationships of any kind. However, until the publication of some significant network models around the turn of the century [1,2], they were not in the spotlight in scientific domains other than social networks and mathematical graph theory. The early models spurred the development of the study of networks as an interdisciplinary field, with myriad applications in computer science, sociology, economics, physics, biology, and many other realms of scientific endeavor.

Until recently, in order to get an idea of the state of the art in the field of networks, scientists and researchers had to wade through journal papers, resort to some published surveys, and peruse major paper collections [3]; more general overviews were only available from popular science titles [4,5]. Fortunately, several recent textbooks have tried to organize what is currently known about networks and their structure and behavior, from different points of view [6,7,8]. Newman adds a new perspective--that of a physicist with a keen eye on networks--to this collection of textbooks.

Newman’s book consists of five parts of increasing complexity, from an informative description of different types of networks to the study of dynamic processes on networks. His writing style is engaging, witty, clear, and instructive--and mathematically rigorous when needed--without being condescending. The book starts with a survey of the most relevant kinds of technological, social, information, and biological networks, as well as the empirical techniques used to discover their structures.

The second part of the book focuses on network theory in general, beyond particular application domains. It provides the fundamental mathematical tools needed for the scientific study of networks, along with a nice introduction to graph theory and a thorough survey of the measures and metrics employed to characterize networks. This part ends with a chapter on the large-scale structure of networks, including their connectivity, shortest paths, degree distributions, and clustering coefficients.

Algorithms for networks are discussed in the next part. After an introductory chapter on data structures and algorithmic complexity for non-computer scientists, Part 3 complements Part 2 by providing efficient algorithmic solutions for computing some of the most common network features: clustering coefficients, shortest paths, and maximum flows/minimum costs. It also analyzes matrix algorithms for computing matrix eigenvalues and eigenvectors--which are needed for some centrality metrics--and discusses the problem of graph partitioning and community detection in networks.

Part 4 is the most mathematically demanding, since it deals with theoretical network models. Its pages are devoted to the study of random graphs, different models of network formation, and other relevant network models. Starting from classic results attributed to Erdős and Rényi, Newman analyzes and proves the formal properties of random graphs with arbitrary degree distributions (such as the configuration model), preferential attachment models (such as the Barabási-Albert model), vertex copying models, network optimization models, and exponential random graphs. Beyond the mathematical proofs and the formal study of particular models--which may not always correspond to what is found in practice--the reader gets a general understanding of network properties and what might lie behind them. For example, in Section 13.3, “Excess Degree Distributions,” readers will discover that, in general, “your friends have more friends than you do.”

The last part of the book turns attention toward processes on networks. Although still in its infancy as a research area, some interesting results are discussed. For instance, Newman discusses what happens when nodes are removed--a process that physicists refer to as “percolation.” This process has severe implications concerning network resilience, and has application as a model for the effects of vaccination. The related issue of epidemics is also studied, by applying classical epidemiological models on networks in order to analyze the spread of diseases, fads, and ideas. The last couple of chapters provide a general overview of stability analysis, synchronization, search, and message passing on networks.

Overall, this is an excellent textbook for the growing field of networks. It is cleverly written and suitable as both an introduction for undergraduate students (particularly Parts 1 to 3) and as a roadmap for graduate students. Furthermore, its more than 300 bibliographic references will guide readers who are interested in particular topics. Being highly self-contained, computer scientists and professionals from other fields can also use the book--in fact, the author himself is a physicist. In short, this book is a delight for the inquisitive mind.

[ACM Computing Reviews, October 2010]

También disponible en