Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Complex networks : an algorithmic perspective
Erciyes K., CRC Press, Inc., Boca Raton, FL, 2014. 320 pp. Type: Book (978-1-466571-66-2)
Date Reviewed: Mar 25 2015

Given the recent proliferation of books on networks, a skeptical reader might wonder whether yet another book on complex networks, also known as network science, deserves space on his or her shelf. In this particular case, the answer depends on what our hypothetical reader might expect from such an addition to his or her library.

If the reader just wants to become acquainted with the emerging field of networks from an algorithmic perspective, well-known textbooks fit the bill [1,2]. Even though they were published a few years ago, they contain all the basic information one might need to understand more recent developments. Apart from some brief comments on algorithmic techniques, such as approximation algorithms for solving nondeterministic polynomial-time (NP) complete problems in practice, and a concise introduction to parallel and distribution algorithms using examples that are not necessarily related to complex networks, most of the content in the first part of Erciyes’ book can also be found in those textbooks [1,2], often in more detailed and thorough discussions. The matching index, which is defined as the ratio of shared neighbors to the overall number of neighbors for a pair of nodes, is an exception rather than the norm.

The second and central part of the book focuses on algorithms. This part starts with a rather lackluster chapter on shortest paths and centrality measures, which includes short descriptions of the algorithms needed for computing the major scores used to measure the importance of each node within a network. Surprisingly, Google’s PageRank is not described in detail here; it is just mentioned as a successful use of eigenvalue centrality and its proper treatment is postponed to one of the final chapters.

After this slow start, the book improves in the next chapters. First, special subgraphs and the algorithms needed to identify them are described from a graph-theoretical perspective. These subgraphs include independent sets, dominating sets, vertex covers, and matching. Next, a couple of chapters delve into clustering, better known as community detection in the networks field. Although the first of these chapters is the typical overview found in conventional data mining textbooks, the second one is more interesting. It describes traditional graph partitioning, including the Kernighan-Lin algorithm, spectral graph bisection, and multilevel partitioning. Basic graph clustering techniques based on minimum spanning trees and “clusterheads” are also mentioned, as well as algorithms for finding cliques and k-cores.

Up to this point, the author’s selection of topics is rather standard and the book’s coverage is that of a typical advanced undergraduate course on the subject. The truly distinguishing content of this book can be found in its final third, starting with a nifty chapter on network motif discovery. This chapter includes a nice description of the graph isomorphism problem and the algorithms employed to solve it. This is one of those interesting problems that have been shown to be in NP, but it is not known whether they are in P or they are NP-complete (as it is correctly stated on page 174, despite previous references to the problem on pages 13 and 66, where it is erroneously referred to as an NP-hard problem). The same chapter also includes a brief survey of motif discovery algorithms from the point of view of bioinformatics researchers, which is a nice complement to the typical algorithmic description of frequent subgraph mining found in more conventional data mining textbooks.

The final part of Erciyes’ book focuses on particular application domains, starting with protein interaction networks, the detection of protein complexes, and network alignment algorithms. The detection of protein complexes completes the previous discussion of network motifs, whereas network alignment is the counterpart of graph isomorphism in many practical problems. A short chapter on social networks covers community detection algorithms as the final leg of the three-legged presentation of unsupervised learning in networks that started in the previous part with conventional clustering algorithms and graph partitioning techniques. A third application domain, the Internet and the web, introduces the bow-tie structure of the web graph, some theoretical network formation models, and finally delves into PageRank and hyperlink-induced topic search (HITS) link analysis techniques, tying up a loose end from the book’s starting chapters. The final chapter briefly turns the reader’s attention to ad hoc wireless networks and mobile social networks, apparently one of the author’s main research interests.

This book provides concise descriptions and the pseudocode of many network algorithms of interest for researchers and practitioners, including some approximate and parallel algorithms not found in similar works. The presence of short text snippets describing a myriad of issues, the somewhat fragmented presentation order, and its sometimes unconventional selection of topics clearly denote the book’s origins as a set of detailed class notes for an advanced undergraduate or graduate course on networks. Whether the most unconventional parts fit a reader’s interests or not will probably determine whether he or she makes space on the shelf for yet another book about networks.

Reviewer:  Fernando Berzal Review #: CR143272 (1506-0450)
1) Newman, M. E. J. Networks: an introduction. Oxford University Press, Oxford, UK, 2010.
2) Easley, D.; Kleinberg, J. Networks, crowds, and markets: reasoning about a highly connected world. Cambridge University Press, New York, NY, 2010.
Bookmark and Share
  Reviewer Selected
Featured Reviewer
Network Problems (G.2.2 ... )
Nonnumerical Algorithms And Problems (F.2.2 )
Would you recommend this review?
Other reviews under "Network Problems": Date
The complexity of the residual node connectedness reliability problem
Sutner K., Satyanarayana A., Suffel C. SIAM Journal on Computing 20(1): 149-155, 1991. Type: Article
Mar 1 1992
Fast approximation algorithms for multicommodity flow problems
Leighton T., Stein C., Makedon F., Tardos É., Plotkin S., Tragoudas S.  Theory of computing (, New Orleans, LA, May 6-8, 1991)1111991. Type: Proceedings
Jul 1 1992
Computing the strength of a graph
Gusfield D. SIAM Journal on Computing 20(4): 639-654, 1991. Type: Article
Apr 1 1992

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