Networks: An Introduction
This page contains information about the book Networks: An Introduction by M. E. J. Newman, a college-level textbook about the science of networks.

By M. E. J. Newman
Hardback, 784 pages
Oxford University Press, March 2010
ISBN13: 9780199206650
ISBN10: 0199206651

The study of networks, including computer networks, social networks, and biological networks, has attracted an enormous amount of interest in the last few years. The rise of the Internet and the wide availability of inexpensive computers have made it possible to gather and analyze network data on an unprecedented scale, and the development of new theoretical tools has allowed us to extract knowledge from networks of many different kinds. The study of networks is broadly interdisciplinary and central developments have occurred in many fields, including mathematics, physics, computer and information sciences, biology, and the social sciences. This book brings together for the first time the most important breakthroughs in each of these fields and presents them in a coherent fashion, highlighting the strong interconnections between work in different areas. Topics covered include the measurement and structure of networks, methods for analyzing network data, including methods developed in physics, statistics, and sociology, graph theory, computer algorithms, mathematical models of networks, including random graph models and generative models, and theories of dynamical processes taking place on networks.
Mark Newman is the Paul Dirac Collegiate Professor of Physics at the University of Michigan and an external faculty member of the Santa Fe Institute.


Table of Contents

  • Preface
  • 1 Introduction
  • 2 Technological networks
    • 2.1 The Internet
    • 2.2 The telephone network
    • 2.3 Power grids
    • 2.4 Transportation networks
    • 2.5 Delivery and distribution networks
  • 3 Social networks
    • 3.1 The empirical study of social networks
    • 3.2 Interviews and questionnaires
    • 3.3 Direct observation
    • 3.4 Data from archival or third-party records
    • 3.5 Affiliation networks
    • 3.6 The small-world experiment
    • 3.7 Snowball sampling, contact tracing, and random walks
  • 4 Networks of information
    • 4.1 The World Wide Web
    • 4.2 Citation networks
    • 4.3 Other information networks
  • 5 Biological networks
    • 5.1 Biochemical networks
    • 5.2 Neural networks
    • 5.3 Ecological networks
  • 6 Mathematics of networks
    • 6.1 Networks and their representation
    • 6.2 The adjacency matrix
    • 6.3 Weighted networks
    • 6.4 Directed networks
    • 6.5 Hypergraphs
    • 6.6 Bipartite networks
    • 6.7 Trees
    • 6.8 Planar networks
    • 6.9 Degree
    • 6.10 Paths
    • 6.11 Components
    • 6.12 Independent paths, connectivity, and cut sets
    • 6.13 The graph Laplacian
    • 6.14 Random walks
  • 7 Measures and metrics
    • 7.1 Degree centrality
    • 7.2 Eigenvector centrality
    • 7.3 Katz centrality
    • 7.4 PageRank
    • 7.5 Hubs and authorities
    • 7.6 Closeness centrality
    • 7.7 Betweenness centrality
    • 7.8 Groups of vertices
    • 7.9 Transitivity
    • 7.10 Reciprocity
    • 7.11 Signed edges and structural balance
    • 7.12 Similarity
    • 7.13 Homophily and assortative mixing
  • 8 The large-scale structure of networks
    • 8.1 Components
    • 8.2 Shortest paths and the small-world effect
    • 8.3 Degree distributions
    • 8.4 Power laws and scale-free networks
    • 8.5 Distributions of other centrality measures
    • 8.6 Clustering coefficients
    • 8.7 Assortative mixing
  • 9 Basic concepts of algorithms
    • 9.1 Running time and computational complexity
    • 9.2 Storing network data
    • 9.3 The adjacency matrix
    • 9.4 The adjacency list
    • 9.5 Trees
    • 9.6 Other network representations
    • 9.7 Heaps
  • 10 Fundamental network algorithms
    • 10.1 Algorithms for degrees and degree distributions
    • 10.2 Clustering coefficients
    • 10.3 Shortest paths and breadth-first search
    • 10.4 Shortest paths in networks with varying edge lengths
    • 10.5 Maximum flows and minimum cuts
  • 11 Matrix algorithms and graph partitioning
    • 11.1 Leading eigenvectors and eigenvector centrality
    • 11.2 Dividing networks into clusters
    • 11.3 Graph partitioning
    • 11.4 The Kernighan--Lin algorithm
    • 11.5 Spectral partitioning
    • 11.6 Community detection
    • 11.7 Simple modularity maximization
    • 11.8 Spectral modularity maximization
    • 11.9 Division into more than two groups
    • 11.10 Other modularity maximization methods
    • 11.11 Other algorithms for community detection
  • 12 Random graphs
    • 12.1 Random graphs
    • 12.2 Mean number of edges and mean degree
    • 12.3 Degree distribution
    • 12.4 Clustering coefficient
    • 12.5 Giant component
    • 12.6 Small components
    • 12.7 Path lengths
    • 12.8 Problems with the random graph
  • 13 Random graphs with general degree distributions
    • 13.1 Generating functions
    • 13.2 The configuration model
    • 13.3 Excess degree distribution
    • 13.4 Clustering coefficient
    • 13.5 Generating functions for degree distributions
    • 13.6 Number of second neighbors of a vertex
    • 13.7 Generating functions for the small components
    • 13.8 Giant component
    • 13.9 Size distribution for small components
    • 13.10 Power-law degree distributions
    • 13.11 Directed random graphs
  • 14 Models of network formation
    • 14.1 Preferential attachment
    • 14.2 The model of Barabasi and Albert
    • 14.3 Further properties of preferential attachment models
    • 14.4 Extensions of preferential attachment models
    • 14.5 Vertex copying models
    • 14.6 Network optimization models
  • 15 Other network models
    • 15.1 The small-world model
    • 15.2 Exponential random graphs
  • 16 Percolation and network resilience
    • 16.1 Percolation
    • 16.2 Uniform random removal of vertices
    • 16.3 Non-uniform removal of vertices
    • 16.4 Percolation in real-world networks
    • 16.5 Computer algorithms for percolation
  • 17 Epidemics on networks
    • 17.1 Models of the spread of disease
    • 17.2 The SI model
    • 17.3 The SIR model
    • 17.4 The SIS model
    • 17.5 The SIRS model
    • 17.6 Epidemic models on networks
    • 17.7 Late-time properties of epidemics on networks
    • 17.8 Late-time properties of the SIR model
    • 17.9 Time-dependent properties of epidemics on networks
    • 17.10 Time-dependent properties of the SI model
    • 17.11 Time-dependent properties of the SIR model
    • 17.12 Time-dependent properties of the SIS model
  • 18 Dynamical systems on networks
    • 18.1 Dynamical systems
    • 18.2 Dynamics on networks
    • 18.3 Dynamics with more than one variable per vertex
    • 18.4 Synchronization
  • 19 Network search
    • 19.1 Web search
    • 19.2 Searching distributed databases
    • 19.3 Message passing
  • References
  • Index

Availability
Networks: An Introduction is published by Oxford University Press. It costs $85 in hardback in the US and £45 in the UK. For pricing in other countries please see the publisher's web site. The book is available directly from the publisher as well as from booksellers such as Amazon, Barnes and Noble, and Blackwell's.
A solutions manual for instructors is available for free by request from the publisher.
A list of known errors and typos in the book is available here.


Last modified: August 19, 2010

Mark Newman