A First Course in Network Theory

  The authors provide an introduction to the mathematical elements needed to start with network analysis. Networks have for some time been a neglected partially recreational aspect of graph theory, but they recently became an important tool in many and very diverse application domains, such as chemistry, nanotechnology, biology, social networks, communication, transportation, or recommendation systems, etc. On the other hand, network analysis relies on several branches of mathematics: of course graph theory and mainly linear algebra, but network models also use stochastics and elements from thermodynamics or from mechanical and even quantum mechanical systems. Going hand in hand with Big Data, network analysis, with its interdisciplinary aspects became a research hype and is now finding its way into the educational curricula.

The authors have lectured on this topic on several occasions, and, because of the diverse applications and disciplines involved, often the students had different interests and quite diverse backgrounds. The present book is based on these lectures and therefore it is written at the level of advanced undergraduate students but it provides also some of the quite elementary tools such as proof by induction or proof by contradiction. The analogy with mechanical systems is well explained, but for quantum mechanics, the introduction is rather compact and there the concept of a Hilbert space is for example assumed known, which is a bit surprising if a previous chapter is completely devoted to elementary proof techniques. But of course some chapters can be easily skipped.

The style is mimicking the popular calculus textbooks, printed on glossy paper with many illustrations, a wide margin, important sections, summaries or examples are standing out by framing it on a colored background. Rather than a rigorous theorem-proof approach, the authors choose for exactness but instead of proving things, there are many examples to illustrate the idea, and some example problems are solved. This recurrent structure is used in all the chapters. Every chapter starts with a short summary of what follows, a section motivating the rest of the chapter, examples, some solved problems, and they end with some references for further reading.

The first five chapters are introductory. They give elementary concepts of graph theory, proof techniques, data analysis (errors, smoothing and fitting), and linear algebra to result in a spectral analysis of adjacency matrices. Another tool is the graph Laplacian. Its spectrum can for example tell us something about the connectivity of the network. The Lagrangian and Hamiltonian of a classical mechanical mass-spring system (or an electrical circuit) are introduced to study networks were edges (springs) can be weighted by forces between the nodes (masses). Some stochastics are introduced for the next chapters where different random networks are discussed, their clustering coefficients and degree distributions. Another interrupt is for a mathematical chapter defining matrix functions. The chapters then switch back to more network analysis with formulas to detect network motifs (i.e., smaller subgraphs with a particular structure like e.g. a triangle, tadpole, square, diamond, etc.), the computation of node centrality (of different types: degree, closeness, betweenness, and spectral centrality). For example Google's PageRank is an eigenvector centrality in a directed network. Next is again a diversion into quantum physics where the Hamiltonian is introduced and the Hubbard and Ising models to be used for modelling networks. The next two chapters deal with global properties such as how well high degree nodes (hubs) are connected (assortativty) or how well information leaving a node in a directed network flows back to the source (reciprocity), or how close a network is to a bipartite one (bipartivity) or how well two nodes are connected (communicability). Once more there is an interruption to introduce concepts from thermodynamics and statistical mechanics. The idea is to connect macroscopic statistics with the microscopic structure (entropy is a basic concept here). Some of the previous concepts are used in the final chapter to detect densely connected communities in large networks.

Some chapters are dealing with rather elementary topics, while others are much more demanding. Anyway, it is advisable that the reader should be familiar with some graph theory, with linear algebra, and with elements from mechanics. Also the chapters are almost independent chunks that sometimes have almost no connection with previous or subsequent chapters. Network analysis is interrupted by mathematical or physical chapters while it is not clear where and how these concepts are then used in other chapters (if used at all in another chapter). It may have been clear from my previous enumeration of the contents that these chapters feel like interrupts serving no purpose for the sequel. There is obviously a link with networks, but that link is not worked out in detail. So the student interested in networks may be a bit at a loss of what to do with all these mechanics. This holds a bit for all the chapters. They are scratching the surface, but except for some elementary academic examples, they are not really applied or lead to a deeper understanding. There is not an algorithmic approach on how to really compute these coefficients in more practical situations, proofs are left out, so that after working through this book, the student will not be fully prepared to dive into the current professional literature. The chapters should be seen as introduction of a topic that should be worked out by assimilating (at least some of) the additional literature listed after the chapter. This will improve on a better understanding, but will not help much on the cohesion of the tpoics treated. That is why it is probably called a first course but a better description might have been Selected topics introducing to network theory. To be useful as a course on networks, it should be accompanied by a more advanced course to provide a more thorough understanding of the material or to embark on practical applications.    

Adhemar Bultheel
Book details

This is an introductory course to network analysis. It introduces the mathematical tools from linear algebra but also the mechanical and quantum physics to understand the models used for the networks. It is generally addressing a readership of advanced undergraduate students.



978-0-19-872646-3 (pbk)
£ 29.99 (pbk)

User login