Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Complex networks : principles, methods and applications
Latora V., Nicosia V., Russo G., Cambridge University Press, New York, NY, 2017. 594 pp. Type: Book (978-1-107103-18-4)
Date Reviewed: Aug 1 2018

As any computer science (CS) undergraduate knows after a first course on algorithms and data structures, graphs provide the most versatile means to represent any situation. By making explicit the pairwise connections between items, they play a critical role in a vast array of computational applications [1]. Starting from abstract mathematical objects, as studied by graph theory since Euler solved the seven bridges of Königsberg problem in 1736, so-called “network science” has evolved over the last two decades to address the study of complex systems. In a complex system, the system is more than the sum of its parts. Those parts are represented as nodes, and their interactions are mapped as the links within a complex network. A complex network is no more than a graph on steroids: a graph whose nodes and links carry information in the form of weights or attributes.

Like other noteworthy textbooks on the topic [2,3,4], Latora et al. cover a variety of common topics and applications. Starting with some fundamentals of graph theory, the book surveys some of the most frequently used centrality measures in social network analysis (that is, the criteria that can be used to rank the nodes in a network according to a suitable measure of “importance,” which is not always the same for every application).

Almost half of the book is devoted to different kinds of network models. As you might expect, the authors analyze the model details and structural properties of Erdős–Rényi random graphs, Watts–Strogatz small worlds, and Barabási–Albert preferential attachment networks with power-law degree distributions. They also discuss the configuration model, random graphs with arbitrary degree distributions, many variations of the better-known models, and the use of probability generating distributions as an elegant tool to derive the properties of random graphs.

After a detailed roundup of network models, the final set of chapters delves into some interesting topics. Chapter 7, on degree-degree correlations, introduces the concept of degree assortativity and disassortativity, as measured by Newman’s correlation coefficient.

Chapter 8, “Cycles and Motifs,” provides an overview of motif analysis. Spatial networks of urban streets illustrate cycles and biological transcription regulatory networks and highlight the presence of small network motifs, the building blocks of networks whose functional role might help explain their behavior. Unfortunately, this chapter is too shallow; the interested reader will have to look elsewhere for a more detailed treatment of motif discovery (for example, see [5] for a more algorithmic perspective).

Chapter 9, on the community structure of complex networks, presents an introduction to community detection methods. In networks, community detection is the name we use for clustering, a form of unsupervised machine learning. Here, readers will encounter the prototypical example, Zachary’s karate club, and descriptions of community detection techniques such as spectral bisection, hierarchical clustering, the Girvan–Newman method, a greedy modularity optimization technique, and a local label propagation algorithm. Again, other references provide a more detailed treatment of algorithmic solutions to this problem (for example, [2]), yet they do not always discuss graph models that can be used to benchmark community detection methods. In this book, however, readers will learn about the planted partition model, the Girvan–Newman benchmark, and the Lancichinetti–Fortunato–Radicchi benchmark.

Finally, the last chapter focuses on weighted networks, whose link weights tune the interactions between nodes. Different formal models for growing weighted networks are also described, namely, the Antal-Krapivsky (AK), Barrat–Barthélemy–Vespignani (BBV), Dorogovtsev-Mendes (DM), and Kumpula-Onnela-Saramäki-Kaski-Kertész (KOSKK) models. An air traffic network and the correlation of stocks in financial markets serve as case studies to introduce standard network metrics for weighted networks, for example, weighted clustering coefficient, weighted rich-club coefficient, and weighted modularity. You will learn how to introduce weights into your network modeling efforts to extract important information from complex systems (yet you should not expect to discover how to predict stock prices).

The book follows a student-friendly style, with step-by-step instructions and thorough explanations--a worthwhile feature in a textbook that could have easily been overwhelmed with theoretical results if presented in a more academic way. Each chapter concludes with a “What We Have Learned and Further Readings” section that recapitulates the main ideas and results, as well as includes pointers for delving deeper into each topic. Each chapter also includes a short problem list with reasonable exercises.

The book is designed for a first course on network science for students coming from different scientific disciplines, from physics, mathematics, and engineering to biology, neuroscience, and the social sciences. Therefore, the authors defer all algorithmic details to 125 pages of appendices. CS students, however, might find this separation somewhat inconvenient, since they will often find themselves flipping book pages whenever they encounter one of the many forward references to the algorithms described in the appendices.

More reviews about this item: Amazon

Reviewer:  Fernando Berzal Review #: CR146180 (1810-0523)
1) Sedgewick , R.; Wayne, K. Algorithms (4th ed.). Addison-Wesley, Boston, MA, 2011.
2) Newman, M. Networks: an introduction. Oxford University Press, Oxford, UK, 2010.
3) Easley , D.; Kleinberg, J. Networks, crowds, and markets: reasoning about a highly connected world. Cambridge University Press, New York, NY, 2010.
4) Jackson, M. O. Social and economic networks. Princeton University Press, Princeton, NJ, 2008.
5) Erciyes, K. Complex networks: an algorithmic perspective. CRC Press, Boca Raton, FL, 2015.
Bookmark and Share
  Featured Reviewer  
 
General (C.2.0 )
 
Would you recommend this review?
yes
no
Other reviews under "General": Date
Comparative evaluation of networks and protocols
Pooch U., John Wiley & Sons, Inc., New York, NY, 1984. Type: Book (9780471262336)
Aug 1 1985
Data communications, networks, and systems
Bartee T., Sams, Indianapolis, IN, 1985. Type: Book (9780672222351)
May 1 1987
Introduction to data communications and computer networks
Halsall F. (ed), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1985. Type: Book (9789780201145472)
May 1 1986
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy