As we have seen, networks, such as the Internet and World Wide Web, social networks (e.g., Facebook and LinkedIn), biological networks (e.g., gene regulatory networks, PPI networks, networks of the brain), transportation networks, and ecological networks are becoming larger and larger in today’s interconnected world. Some of these networks are truly huge and difficult, if not impossible, to analyze completely and efficiently. In this chapter, we discuss some of the issues involving comparing networks for similarity or differences, including choice of similarity measures, exchangeable random structures of networks, and property testing in networks.

In this chapter, we introduce a number of parametric statistical models that have been used to model network data. The social network literature has named them $p_1$, $p_2$, and $p^{*}$ models, the last of which has also been referred to as an ERGM (exponential random graph model).

When a network is too large to study completely, we sample from that network just as we would sample from any large population. The structure of network data, however, is more complicated than that of standard statistical data. The main question is, how can one sample from a network that has nodes and edges? Should we sample the nodes? Or should we sample the edges? The answers to these questions depend upon the complexity of the network. In this chapter, we examine various methods of sampling a network.

Random graphs were introduced by the Hungarian mathematicians Erdős and Rényi (, ), who imposed a probabilistic framework on classical combinatorial graph theory. At the same time, Edgar N. Gilbert () also studied the theoretical properties of random graphs.

Much of what is studied in network analysis derives from the observation that nodes in a graph $\mathcal{G}$ often tend to form “cohesive groups” or, as they are called in social networks, communities, clusters, or modules. This chapter describes statistical methods for identifying such communities using the stochastic blockmodel and an approach based upon the concept of modularity.

In this and the next three chapters, we study the problem of graph partitioning, which deals with the question of how to divide up the nodes into homogeneous groups (if they exist). This topic is currently receiving the greater part of research activity within the network science community. In this chapter, we describe various methods for graph partitioning using graph cuts, including binary cuts, ratio cuts, normalized cuts, and multiway cuts.

In this book, we develop the theory and methodology for modeling networks. Before we do that, however, we will find it useful to describe examples of the types of real-world networks that exist today. We will be referring to these networks throughout the book. Indeed, there are many different kinds of networks, some small and some big, some simple and some, by the nature of their underlying structure, very complicated.

So far, we have assumed that if there are several communities in a network, then those communities are distinct and non-overlapping. In this chapter, we discuss situations in which communities overlap with each other. We describe a number of algorithms for modeling overlapping communities, such as mixed-membership SBMs, link-based clustering, overlapping SBMs, the community-affiliation graph model, and the latent cluster random-effects model.

The aim of this chapter is to provide readers with an introduction to the basic ideas of networks and their representation by graphs. We will be using ideas, definitions, terminology, and notation from graph theory throughout this book.

There have been several attempts at incorporating real-world components into network generation and growth. Most attention has centered on trying to create a desired structure for the node-degree distribution, such as clustering and the power-law property. This chapter discusses the advantages and disadvantages of the “configuration” and the “expected-degree” models, and describes how the growth of a network can be formulated through the “preferential-attachment” and “random-copying” (or “duplication”) models.

This chapter describes the small-world phenomenon and the Watts–Strogatz model, degree distributions, power-law distributions, and scale-free networks.

The previous two chapters have focused on the problem of graph partitioning, which has seen enormous interest and research work in recent years. We continue that aspect of network analysis by introducing the notion of spectral clustering. The main tool of this chapter is the graph Laplacian, which can be unnormalized or normalized. Also discussed is a regularized version of the adjacency matrix.

In recent years, the science of “networks” has become a very popular research topic and a growth area in many different disciplines. Two journals, Social Networks (first published in 1978) and Network Science (first published in 2013), have appeared that focus on network theory and applications. In its inaugural issue, the journal Network Science defined network science as the “study of the collection, management, analysis, interpretation, and presentation of relational data,” and noted that the more one learns about networks, the more one sees networks everywhere.

In this chapter, we recognize that the configurations of almost all networks vary with time. We define dynamic networks, which can be observed in discrete or continuous time. Discrete-time dynamic networks can be visualized as a sequence of snapshots of the network taken at different points in time. Continuous-time dynamic networks are more complicated, both visually and theoretically, and assume that edges can appear and disappear continuously through time. We discuss the idea of dynamic community discovery in which community detection strategies are applied to dynamic networks.