9 - The structure of networks: the generating function method

Summary

Introduction

A generalized random network is generally made up of several components. In the random generalized graph model, the structure of the network is determined only by the degree distribution, since no other structure or constraint is imposed on the network. In general, for many degree distributions the network is composed of many separate components, i.e., groups of nodes connected internally, but disconnected from other components. In each such component there exists a path between any two nodes, but there is no path between nodes in different components. When there is a component with size (the number of nodes) proportional to that of the entire network, it is called the giant component (sometimes also referred to as the infinite component or giant cluster or percolating cluster).

This chapter introduces a method for determining the component structure of a network, which is one of its most important structural properties. We will present a method for determining the existence of a giant component, and also a method for determining the sizes of all clusters using generating functions. The generating function method is a general and useful method for many probabilistic and combinatorial problems. An introduction to this method is given in Appendix A. The methods introduced in this chapter will be used in Chapter 10 to determine the robustness properties of networks and later in Chapters 14 and 15 to determine how epidemics propagate through networks and how they can be prevented by immunization.