Connections: An Introduction to the Economics of Networks

Connections

1

Introduction

1.1 Themes

I buy a new computer every few years. A computer is a sophisticated product and there are a number of different options open to me. To make an informed choice, I personally gather information on the different brands and models available—by going on the World Wide Web, visiting computer shops, and reading computer magazines—and I talk to my colleagues and friends to get tips about the different brands available. The time and effort I personally spend in collecting information depend very much on how well-informed my friends and colleagues are: if they are well-informed, then I rely upon their information and do not spend much time in collecting information myself.

My friends and colleagues face a similar situation, and their own efforts at collecting information in turn depend on how much information their acquaintances (including me) collect personally. Thus my efforts at collecting information personally will depend on the efforts of those whom I know, and the efforts of these individuals will in turn depend on the efforts of their friends, and so on. This suggests that individual choices concerning the gathering of information are shaped by the pattern of connections between persons in a society.

Indeed, it may well be worth my while to form connections with someone who is well-informed rather than carrying out the search myself. Moreover, I should compare the costs in terms of time and effort involved in forming such a connection with the potential benefits of obtaining valuable information. This line of reasoning leads us to the idea that the pattern of connections that obtain in a society will themselves reflect rational decision making of individuals.

This story helps us in framing two primary questions:

(i) What are the economic effects of the pattern of connections that obtain in a society?

(ii) What is the architecture of connections that emerges when individual entities form links with each other based on considerations of personal costs and benefits?

The study of these questions constitutes the subject matter of this book.

Relationships among individuals have a number of different dimensions. The first task is therefore to find a conceptual framework within which they can be described and then measured in a meaningful manner. We also need a language within which variations in relationships can be naturally expressed. The concept of a network addresses these requirements nicely: a network describes a collection of nodes and the links between them. The notion of nodes is fairly general: they may be individuals or firms or countries, or even collections of such entities. A link between two nodes signifies a direct relation between them; for instance, in a social context a link could be a friendship tie, while in the context of countries a link may be a free trade agreement or a mutual defense pact. Networks have been studied extensively in mathematics in the theory of graphs, and they have also been applied in a number of different subjects such as sociology, computer science, and statistical physics. Chapter 2 draws on these literatures to present the principal network concepts and notation which are used throughout the book. This chapter also identifies a number of common features in empirical networks. This discussion directs our attention to specific networks in our theoretical investigations of the subsequent chapters.

The first substantive part of the book, comprising chapters 3–6, studies the effects of network structures on individual behavior. Chapters 3 and 4 present and analyze games on networks, while chapters 5 and 6 study the generation and diffusion of information in networks.

A game on a network refers to strategic interaction in which players are located at distinct nodes of a network, and the effects of a player’s actions on other players are mediated by the structure of the network. The key idea here is that the effect of player i on player j depends on where i is located in the network vis-à-vis j. Networks allow for a natural way of modeling differential influences across players. The idea of local social influence is a well-known instance of this idea. Smoking by a friend is likely to have a much greater effect on a teenager’s decision on whether or not to smoke compared with the choices of the people whom she does not know personally. Similarly, a child usually learns the language spoken by her parents and neighbors. In the context of research by firms, similarly, the efforts of research partners have more spillovers on a firm’s technological capabilities compared with research of other firms.

There is the issue of whether or not the actions of others increase an individual player’s payoffs and her incentives to choose particular actions. Chapter 3 presents simple classifications of strategic effects in terms of positive and negative externalities and strategic substitutes and complements to bring out the range of possible strategic effects.

Over the last two decades, a number of important social and economic phenomena have been studied as arising out of network effects. Some examples of such phenomena are variations in crime, proliferation of research partnerships among firms, the prominence of mavens and opinion leaders, and differences in trust and social cooperation. This body of work has led to a rich set of models, which are taken up in chapters 3 and 4. The aim here is to show how the different models constitute special cases of the framework developed in chapter 3 and how they can be studied by using a set of common techniques. This presentation also highlights a number of interesting open problems.

Imperfect information is a key feature of economic environments. The next two chapters, 5 and 6, study the role that social networks play in the generation as well as the diffusion of valuable information. Chapter 5 considers situations where individual rewards depend only on personal actions, but the payoffs from different actions are not known. In such a situation the experience of friends, colleagues, and acquaintances, namely, the neighbors, is useful since it yields valuable information on alternative actions. The behavior of these neighbors is in turn affected by the choices and experience of their neighbors and so on. The chapter develops a theoretical framework to study the effects of network structure on individual choice and learning, over time. The aim is to characterize the properties of social networks that facilitate the diffusion of information about the payoffs from different actions.

Chapter 6 studies the role of social networks in labor market networks. The matching between workers and their employers is characterized by significant imperfections in information. Two types of information are especially prominent in labor markets: the information on job vacancies and the information on the ability of workers. This chapter develops models in which social networks convey information across individual workers and between employers and workers. The aim is to study the different ways in which social networks influence the employment status of individuals and shape the income inequality in a society.

One of the main insights of the first part of the book is that individuals can exploit their network position to their own advantage. Moreover, these advantages are related systematically to aspects of the network structure. In many contexts, the connections that define a network arise out of investments in relationships made by the individual entities themselves. Connections take on different forms and so the nature of investments will vary. In the computer purchase story, for example, the crucial resource is time. I will ask myself whether I should spend time on a personal search or if it would be more worthwhile to spend the time talking to others who may have collected information either personally or through their friends and colleagues. In the context of firms which are deciding on whether to carry out research in-house or to collaborate with other firms, the resources include personnel and financial capital.

These examples suggest two key ideas: one, individuals will trade off the costs and benefits from investments in connections, and, two, an individual’s benefits from a connection may actually depend on the connections formed by others. Thus individual decisions on forming connections take place in a context characterized by externalities: if, for example, my friends invest in social connections which enable them to share information with others, then this may make it more attractive for me to invest in connections with them in turn. Similarly, if firms in an industry form connections, then this may alter the gains to a new firm from investing in alliances. So we are led to a study of strategic factors in the formation of networks.

The second part of the book, comprising chapters 7–10, is devoted to the theory of network formation. A game of network formation specifies a set of players, the link formation actions available to each player, and the payoffs to each player from the networks that arise out of individual linking decisions.

The above discussion highlights the possibility that a connection formed between players 1 and 2 may affect the payoffs to other players. This raises the important general issue about who has the power to decide on whether a connection is formed? One of the great attractions of networks is that they are amenable to subtle and quick transformations via local, and small-scale, linking and delinking activity. This consideration leads us to develop a model in which link formation and dissolution take place at a single-person or at a two-person level and the process is dynamic. A network is said to be strategically stable (or in equilibrium) if there are no incentives for individual players, either acting alone or in groups, to form or delete links and thereby alter the network. Chapter 7 presents this general model and also develops a number of ways of solving games of network formation, which correspond to different levels of individual foresight as well as decision-making power.

The last decade has witnessed a number of exciting developments in the theory of strategic network formation. There have also been a number of attempts to model network formation in specific social and economic contexts. Examples of this work include the formation of information-sharing networks, research collaboration networks among firms, coauthorship networks, labor market networks, buyer–seller networks, and free trade agreements among countries. This body of work addresses three general concerns: (i) What is the architecture of networks that arise in equilibrium? (ii) What is the relation between equilibrium and socially desirable networks? (iii) What are the implications of strategic networking for the distribution of individual earnings? Chapters 8–10 discuss this work and also point out a number of open research questions.

1.2 Networks in Economics

Traditionally, economists have studied social and economic phenomena by using a framework in which interaction is centralized and anonymous. Moreover, prices have been the principal device of coordination among individual actions. The theory of general equilibrium and the theory of oligopoly reflect this approach. In recent years, a growing body of empirical work has argued that this approach is inadequate for an understanding of a number of phenomena such as the diffusion of innovations, variations in crime, differences in trust and cooperativeness, peer effects in academic performance, the proliferation of research alliances among firms, and the extensive use of personal contacts by both employers and workers in labor markets.¹ I now discuss empirical patterns in the diffusion of innovation to bring out the central role of the pattern of interaction.

Technological change is central to economic growth and social development. The process of technological change is complicated and involves many steps starting from basic research and going on to wide-scale adoption. But it is generally agreed that wide diffusion is important for the full gains of a new technology to be realized. This rate of diffusion, however, seems to vary greatly. Consider the following examples:

• It took a millennium for the water mill to be widely adopted in Europe; it is felt that the main reason for this slow pace of diffusion was the absence of significant mobility during pre-medieval and medieval times.

• The spread of new hybrid seeds has been central to the increase in agricultural productivity over the past century. The classical work of Ryan and Gross (1943) documents that hybrid corn seeds were adopted over a period of several years in the early twentieth century, in the United States. Moreover, diffusion of these seeds displayed clear spatial patterns: initially, a small group of farmers adopted the seed, followed by their neighbors adopting it, and this was followed by the neighbors of the neighbors adopting it, and so on.

• The period before the first prescription of a new medicine by doctors within the same city can vary widely. For instance, Coleman, Katz, and Mentzel (1966) found that this period ranged from six months to three years within a Midwestern town in the United States and also observed that a significant part of this variation is explained by the differences in social connections across doctors.

• The facsimile technology was available in 1843 and AT&T introduced a wire photo service in 1925. However, fax machines remained a niche product until the middle of the 1980s. Since then there has been an explosion in the use of fax machines.

The research on the determinants of diffusion suggests that the critical factor in the diffusion of a new technology is the uncertainty about its profitability. Information from governments and firms will alleviate this uncertainty. However, if the technology in question is complicated and involves substantial resources, such as adoption of crops or prescription of medicines, then it is clear that an individual is likely to place much greater faith in information from close friends, colleagues, and neighbors, and others in a similar decision situation. Moreover, in some instances, such as with fax machines, an individual’s payoffs from adopting the product depend on whether others with whom she interacts frequently adopt the same product. Thus the patterns of interaction between individuals are likely to play a key role in shaping individual choice and therefore shaping innovation at an aggregate level as well.

This example allows us to draw out two important theoretical points. The first point is about the descriptive appeal of social interaction: in many economic contexts, social interaction between individual entities is clearly present. The second point is about the functional aspect of social interaction: such interaction facilitates the transmission of valuable information. This suggests that the structure of interaction may be viewed as an instance of informal institutions that supplement formal markets in the presence of imperfect or asymmetric information. To the extent that information imperfections are pervasive, this suggests a potentially major role for patterns of connections in shaping economic activity.

These considerations suggest an ambitious research program which combines aspects of markets (e.g., prices and competition) along with explicit patterns of connections between individual entities to explain economic phenomena. In the last decade considerable progress has been made in this research program. The present book provides an overview of this work.

The research on networks reported in this book is related to, but distinct from, two other strands of research in economics: the study of network industries (such as airlines, telecommunications, electricity, software industries) and the empirical work on social interactions. It is important at the very outset to clarify this distinction. In the literature on network industries, profit-maximizing firms own and control the functioning of their network;² by contrast, a large part of this book is concerned with social and economic networks where there is no single entity who owns the network. The focus is in developing a framework where individual entities create their own links with others and this shapes the structure of economic and social interaction.³

An influential body of empirical work in economics argues that individual behavior is shaped by the patterns of social interaction. This work makes the following important point: a significant part of the variation in behavior across individuals arises due to these individuals being members of different groups.⁴ By contrast, the theoretical research on network effects (which is presented in chapters 3–6) is motivated by the idea that, within the same group, individuals will have different connections and that this difference in connections will have a bearing on their behavior.⁵

1.3 The Economic Approach and Other Subjects

The study of networks has become very popular in economics in the last decade. However, networks have been studied in sociology and mathematics for much longer and in recent years networks have also been extensively studied in statistical physics, computer science, business strategy, geography, and organization theory.⁶ It is therefore important to clarify what an economic approach brings to the study of networks. I will argue that the distinctiveness of the economic approach lies in the different methodology that is used. This methodology in turn raises substantive questions which have received little attention in other disciplines.

The study of networks has been concerned with network effects as well as network formation in all the different disciplines mentioned above. However, within this broad similarity of themes there are important differences. The similarity as well as the differences will be discussed in specific contexts throughout the book. Here, I discuss the differences at a general level. Social efficiency is another central concern for economists, but plays a relatively minor role in the other disciplines. Related to this is a central concern of economics: the relationship between socially desirable outcomes and the outcomes that actually arise out of the purposeful activity of individuals. This relationship has received relatively little attention in the other subjects. These differences can be traced to a substantive methodological premise in economics: social and economic phenomena must ultimately be explained in terms of the choices made by rational agents.

To make the content of this methodological premise more concrete, and to see its scope, consider the computer purchase example again. In that context, economists are particularly concerned with the incentives of individuals to gather information. Information is valuable as it influences choices of individuals and this in turn determines their purchase decisions. A simple way to study network effects is to examine the effects of adding links to a network. At first sight, it seems that adding links should benefit everyone, as more information sharing is made possible through additional links. However, an economic analysis of this issue proceeds via an examination of the effects of adding links on the incentives of individuals to collect information. If more information is freely available from social contacts, then there is a lower incentive to collect information personally. If private collection of information is costly, then the overall effect of adding links may well be a fall in the total information collected. The study of individual incentives and rational behavior thus yields an important insight into the potential negative effect of adding links.

This insight has important practical implications. To see this, consider the options available to a government which would like individuals to make more informed choices with regard to information technology. The government sends out information to individuals, who also collect information privately. In addition, people share information with their friends and colleagues. In a situation where new links are being formed and social networks are becoming denser, should the government increase or reduce its advertising? A simple-minded view is that denser networks will lead to better-informed individuals (due to greater sharing of information). If sending out information is costly, this suggests that governments can therefore invest less in sending out information. However, in a world where individuals respond optimally to the addition of social connections, this line of reasoning may be incorrect: new connections may actually lower the overall information available to individuals and the optimal response of the government should be an increase in investment.

These observations illustrate the key role of individual incentives in an economic approach to the study of networks. They also show how these incentives play a key role in the design of suitable public policies.

1.4 A Note on Style

The study of networks is thriving in economics as well as in a number of other subjects. I have therefore tried to provide an account of the economic approach which is broadly accessible as well as rigorous. The style of the book reflects these aims: the principal themes are motivated via simple examples and the main insights of the theory are discussed in nontechnical language. To complete the exposition, mathematical proofs of all the results are presented in appendices which accompany the chapters.

¹ There is a large body of work on these subjects; see Ryan and Gross (1943), Coleman, Katz, and Mentzel (1966), Griliches (1957), and Conley and Udry (2005) for diffusion of innovations, Dasgupta and Serageldin (1999) for the role of trust and social capital, Glaeser, Sacerdote, and Scheinkman (1996) for patterns of crime, and Granovetter (1994a) for the use of social contacts in labor markets. For a pioneering discussion on the role of networks in economics, see Kirman (1997).

²For surveys of the research on network industries, see Shy (2001) and Newberry (2002).

³This general framework is discussed in chapter 7.

⁴For example, Glaeser, Sacerdote, and Scheinkman (1996) argue that social interaction effects within a geographical neighborhood help explain variations in criminal activity, Bertrand, Luttmer, and Mullainathan (2000) show that ethnicity is important in understanding differences in participation in welfare programs, Banerjee and Munshi (2004) argue that membership of a community influences rates of capital investment, while Duflo and Saez (2003) argue that social interaction affects the choice of pensions policy. See Glaeser and Scheinkman (2002) for a survey of some of this work.

⁵The identification of such network effects is only just beginning; see, for example, Bandiera, Barankay, and Rasul (2006), Bramoullé, Djebbari, and Fortin (2006), Conley and Udry (2005), Calvó-Armengol, Patacchini, and Zenou (2006), and Fafchamps, Goyal, and van der Leij (2006).

⁶There are a number of excellent books which summarize research in these subjects; see, for example, Bollobás (1998) and Harary (1969) in graph theory and mathematics, Burt (1994), Coleman (1994), Granovetter (1994a), Smelser and Swedberg (1994), and Wasserman and Faust (1994) in sociology, Barabasi (2002), Dorogovtsev and Mendes (2002), and Watts (1999) in statistical physics, Bailey (1975) in mathematical biology, Castells (1999) in geography, and Roughgarden (2005) in computer science. For a recent presentation of the theory of complex networks, see Vega-Redondo (2007); for an interesting collection of articles on economic activity in complex networks, see Kirman and Zimmermann (2001).

2

Networks: Concepts and Empirics

2.1 Introduction

The first aim of this chapter is to present the principal concepts relating to networks which will be used in this book. This presentation in section 2.2 will draw upon work carried out in the theory of graphs, in mathematical sociology, and in statistical physics. The study of networks has a rich and distinguished tradition in each of these subjects and there are a number of excellent books available. The exposition below borrows heavily from Harary (1969), Bollobás (1998), and Wasserman and Faust (1994).

The second aim of this chapter is to discuss these concepts in relation to empirically observed networks. This discussion is presented in section 2.3. The empirical study of networks has been a very active field of study in the last decade. The discussion highlights some of the key features that have been identified by this research. In doing so, it directs our attention to specific networks which are then taken up in the theoretical investigations of the subsequent chapters.

2.2 Concepts

There is a set of nodes, N = {1, 2, 3, . . . , n}, where n is a finite number. Relationships between nodes are conceptualized in terms of binary variables, so that a relationship either exists or does not exist. Denote by gij {0, 1} a relationship between two nodes i and j. The variable gij takes on a value of 1 if there exists a link between i and j and 0 otherwise.¹ The set of nodes taken along with the links between them defines the network; this network is denoted by g and the collection of all possible networks on n .

Given a network g, g + gij and g − gij have the natural interpretation. When gij = 0 in g, g + gij adds the link gij = 1, while if gij = 1 in g, then g + gij = g.

Figure 2.1. Regular networks for n = 4.

Similarly, if gij = 1 in g, g − gij deletes the link gij, while if gij = 0 in g, then g − gij = g.

Neighbors and degrees. Let Ni(g) = {j N | gij = 1} denote the nodes with which node i has a link; this set will be referred to as the neighbors of i. Let ηi(g) = |Ni (g)| denote the number of neighbors of node i in network gbe the d-neighborhood of i in g: this is defined inductively,

Let N1(g), N2(g), . . . , Nn−1(g) be a division of nodes into distinct groups, where nodes belong to the same group if and only if they have the same number of links, i.e., i, j Nk(g), k = 1, 2, . . . , n − 1, if and only if ηi(g) = ηj(g). With this notation in hand we can now describe a number of well-known networks.

A network is said to be regular if every node has the same number of links, i.e., ηi(g) = η, ∀i N (and so all nodes belong to one group in the above partition).² The complete network, gc, is a regular network in which η = n − 1, while the empty network, ge, is a regular network in which η = 0. Figure 2.1 presents regular networks for n = 4.

Figure 2.2. Star and variants.

A core–periphery network structure describes the following situation. There are two groups of nodes, N1(g) and Nk(g), with k > |Nk(g)|. Nodes in N1(g) constitute the periphery and have a single link each and this link is with a node in Nk(g); nodes in the set Nk(g) constitute the core and are fully linked with each other and with a subset of nodes in N1(g). The star network is a special case of such an architecture in which the core contains a single node. Figure 2.2 presents a core–periphery network.

An interlinked stars network consists of two groups Nk(g)and Nn−1(g) which satisfy the following condition: Ni (g) = Nn−1(g) for i Nk(g). The star network is again a special case of such an architecture with |Nn−1(g)| = 1 and |N1(g)| = n − 1. In an interlinked star network, nodes which have n − 1 links are referred to as central nodes or as hubs, while the complementary set of nodes are referred to as peripheral nodes or as spokes. Figure 2.2 presents interlinked stars with two and three central players.

An exclusive groups network consists of m + 1 groups, a group of isolated nodes D1(g), and m 1 distinct groups of completely linked nodes, D2(g), . . . , Dm+1(g). Thus ηi (g) = 0 for i D1(g), while ηj (g) = |DX(g)| − 1 for j Dx(g), x {2, 3, . . . , m + 1}. A special case of this architecture is the dominant group network in which there is one complete component with 1 < k < n nodes while n − k > 0 nodes are isolated. Figure 2.3 illustrates exclusive group networks.

Figure 2.3. Exclusive group networks.

Figure 2.4. Line network.

A line network consists of two groups of nodes, N1(g) and N2(g), with |N1(g)| = 2 and |N2(g)| = n − 2. As the name suggests, the network has the form of a line; the two nodes with one link each are at the two ends of the line, while the nodes with two links are in between. Figure 2.4 presents a line network with n = 6 nodes.

These figures give us a first impression of how different networks can look! The examples all contain relatively few nodes; in some economic and social contexts of interest, such as the diffusion of information or the evolution of social coordination and cooperation it is more natural to consider networks with a large number of nodes. When analyzing large networks it is more convenient to work with distributions of links.

The degree of node i is the number of i’s direct connections; so ηi (g) = |Ni (g)| denotes the degree of node i in network g. The degree distribution in a network is a vector P, where P(k) = |Nk (g)|/n is the frequency/fraction of nodes with degree k; thus P(k0 for each k= {0, 1, 2, . . . , n − 1}. The average degree in network g is defined as

In a star network the degree distribution has support on degrees 1 and n − 1, with n − 1 nodes having degree 1, and 1 node having degree n − 1. The average degree in a star is 2 − 2/n.

An important concern in the study of networks is the variation in the degrees. This variation is interesting in its own right but it also has an important instrumental aspect: degree may be related to node behavior and well-being. Indeed, one of the primary motivations for the study of networks in economics is the issue of how nodes extract advantages on account of their connections. There are a number of different ways of measuring variations in degrees. Let us start with two standard measures: the variance and the range.³ The variance in the degree distribution is defined as

The degree variance in a star grows with n, while the variance in any regular network is 0 for all n. The range of degrees in network g is

The range has a maximum value of n − 2 and a minimum value of 0. The range in a star is n − 2, while the range in any regular network is 0.

The description of a network in terms of a degree distribution allows for an elegant way to study the addition and the redistribution of links. The idea of adding links is captured in the relation of first-order stochastic domination; similarly, the idea of redistributing links is captured in the relation of mean-preserving spreads and second-order stochastic domination. Given a degree distribution P: {0, 1, 2, . . . , n−1} → [0, 1], where

Let P and P′ be two degree distributions defined on {0, 1, 2, . . . , n ′ the two corresponding cumulative distribution functions, respectively.

Definition 2.1. P first-order stochastically dominates (FOSD) P(k′(k) for every k {0, 1, 2, . . . , n − 1}.

Definition 2.2. P second-order stochastically dominates P′ if and only if

for every x {0, 1, 2, . . . , n − 1}.

Definition 2.3. P′ is a mean-preserving spread of P if and only if P and P′ have the same mean and P second-order stochastically dominates P′.

A simple example of first-order shift in degree distribution arises when we move from a regular network with degree k to a regular network with degree k + 1. A simple example of a second-order shift arises when we move from a cycle with n = 6 nodes to a network in which node 1 is linked to all nodes, nodes 2, 3, and 4 have just this one link with node 1, while nodes 5 and 6 have two links each, a link with node 1 and a link with each other. Figure 2.5 illustrates such a mean-preserving spread transformation of the degree distribution.

Figure 2.5. Mean-preserving spread in degree distributions.

In particular, note that if P first-order stochastically dominates P′, then the mean degree under P is higher than that under P′, but the converse is not true. Similarly, if P′ is a mean-preserving spread of P, then the variance under P′ is higher than that under P, but the converse is not true.

Walks, paths, and distances. A major concern throughout the book will be the ways in which a node can be reached from another node in the network. The first step in understanding this issue is the notion of walk: a walk is a sequence of nodes in which two nodes have a link between them in the network (they are neighbors). Note that a node or a link may appear more than once in a walk. So a walk is the most general sequence of nodes and links possible in a network, subject to the restriction that any two consecutive nodes must have a link in the network. The length of a walk is simply the number of links it crosses; this is simply equal to the number of nodes involved minus one.

A walk in which all links are distinct is called a trail. A trail in which there are three or more nodes and the initial and the end node are the same is called a cycle. A trail in which every node is distinct is called a path. Formally, there is a path between two distinct nodes i and j either if gij = 1 or if there is a set of distinct intermediate nodes j1, j2, . . . , jn such that gij1 = gj1j2 = ··· = gjnj = 1.

Figure 2.6 represents a network with n = 5. A possible walk in this network is 2, 3, 4, 3, 2. This walk contains the links g23 and g34 twice and the nodes 2 and 3 also appear twice each. This walk is therefore not a trail. A possible trail in the network is 3, 4, 5, 3. Next note that this trail does have three nodes and the initial node and the terminal node are the same, so this trail is a cycle. However, since node 3 appears twice this trail is not a path. A possible path in this network is 2, 3, 4, 5.

Figure 2.6. Walks, trails, cycles, and paths.

Two nodes belong to the same component if and only if there exists a path between them. A network is connected if there exists a path between any pair of nodes i, j N. It follows that there exists only one component in a connected network. In the case of an unconnected network, the components can be ordered in terms of their size, and the network has a giant component if, informally speaking, the largest component covers a relatively large fraction of the nodes while all other components are small.⁴

The notion of minimality will play an important role in this book. Intuitively speaking, minimality of a network reflects the idea that no link is superfluous. A component is said to be minimal if the deletion of any single link in the component breaks the component into two components. A network is said to