Fixed link

Evolution of Networks. From Biological Nets to the Internet and WWW

S. N. Dorogovtsev and J. F. F. Mendes

posted on 17 November 2004

reviewed by Marian Boguñá

This book is the first technical text on the currently fashionable field of complex networks. It represents an attempt to review the astonishing progress made in this subject during recent years, both from a theoretical and empirical point of view. Networks are mathematical representations of interacting systems in which vertices represent the typical units and edges the interaction between these units. Unlike regular lattices, with strong local ordering, complex networks usually involve some type of randomness in their connections leading to considerable heterogeneity in properties of individual units and loss of the metric structure. In this respect, the smallworld effect (the surprisingly small distance between any two vertices of a network) and the scale-free property (the very presence of hubs with a large number of connections, characterized by a power law degree distribution) observed in many real networks are the two cornerstones of the book. This is fully justified by the important role that these properties play in problems as diverse as communication and searching processes, percolation problems, or virus spreading. Professors Dorogovtsev and Mendes are well known for their important contributions in this field of research. Through the pages of the book, they introduce, from their personal perspectives, the key ideas leading to the understanding of the ubiquity of the complex topologies present in real nets as well as describing the most relevant models and the, by now, standard techniques used to analyze them. The book is organized in eight chapters, although there is a clear division in four main parts (Chapters 3 to 6) describing empirical results, equilibrium networks, non-equilibrium growing networks and global topology of networks respectively. After an introductory chapter to graph theory (Chapter 1) and a short chapter devoted to the idea of preferential attachment (Chapter 2), in Chapter 3, the authors give an overview of the main empirical results obtained for an eclectic set of real networks. Examples of the analyzed nets are as diverse as communication networks, such as the Internet or the WWW, social networks, biological networks, industrial networks, or the word web of human language to name just a few. The second main part of the book (Chapter 4) discuses in detail equilibrium networks, starting with the simplest model, the classical random graph (first studied by P. Erdös and A. Rényi), and ending with equilibrium nets with given correlation structures. The chapter is nicely written although I personally miss, for pedagogical purposes, the complete statistical mechanical description of the classical random graph model. Such a derivation would give the reader deeper insights into the meaning of the term equilibrium network. Chapter 5 develops in detail the ideas of growing and preferential attachment previously introduced in Chapter 2. These two ingredients, when combined, are mainly responsible for the appearance of the scale-free property in networks. In this chapter the continuous- time rate approximation is introduced, which has proved to be a valuable and powerful tool in these class of problems. Global topological properties are described in Chapter 6. Percolation problems, in a variety of different forms (failures and attacks, random breakdowns, epidemic spreading, etc.), are analyzed as well. The section on the Ising model on random networks is worthy of our full attention. In scale-free networks, in which fluctuations in the number of connections of a vertex diverges, the critical temperature for the Ising model diverges as well, which, in turn, implies that the ferromagnetic ordering is never completely destroyed. Finally, Chapter 7 presents a short discussion about self-organization of networks and multiplicative stochastic processes. It must be said that the reader will not find in this book the customary mathematical rigor of graph theory. As the authors say in the preface experiment and empirical data are more valuable than an estimate; an estimate is more valuable than an approximate calculation; an approximate calculation is more valuable than a rigorous result. Nevertheless, this lack of mathematical rigor has lead to spectacular advances in a very short period of time. In any case, I strongly recommend this book to anyone interested in this new and interdisciplinary field of research.