Introductory Notes on Networks

Leigh Tesfatsion
Agent-Based Computational Economics

Last Updated: 18 February 2024

Site Maintained By:

Professor Leigh Tesfatsion

tesfatsi AT iastate.edu

Syllabus for Econ 308

Glossary of Terms Related to Networks

Connectivity (cf. Batten, p. 89):

Roughly, the connectivity of a system consisting of a collection of agents is the degree to which the system agents interact with one another.

A connectivity measure would generally take into account two aspects of this interaction pattern: (1) Which agents are interacting with one another?; and (2) What is the strength (frequency, regularity, impact,...) of these interactions? As Batten stresses, connectivity is a fundamental aspect of both living and nonliving systems.

Network:

A network is a collection of entities together with a specified pattern of relationships among these entities. Three main tools have been used for the quantitative study of networks: graph theory; statistical and probability theory; and algebraic models. In Chapter 3, Batten uses basic concepts from graph theory to discuss network issues for socioeconomic systems.

Graph Theory Terminology (cf. Batten, pp. 92-105):

A graph G consists of a set V(G) of vertices (or nodes) together with a set E(G) of edges (or links) that connect various pairs of vertices.

The number of vertices of G -- i.e., the cardinality |V(G)| of the set V(G) -- is referred to as the order of the graph G.

The number of edges of G -- i.e., the cardinality |E(G)| of the set E(G) -- is referred to as the size of the graph G.

A graph G is a weighted graph if each of its edges has associated with it a number indicating the strength of the edge.

A graph G is called a directed graph (or digraph) if all of its edges are directional, i.e. if each edge between a pair of vertices v and v' in V(G) is a directional arrow that indicates a direction to the relationship between the vertices. A graph G is called an undirected graph if none of its edges is directional.

For any directed graph G, and any particular vertex v in V(G), the number of vertices v' in V(G) that are directly linked to v by an inward-pointing edge to v is called the in-degree of v, and the number of vertices v' in V(G) that are directly linked to v by an edge pointing outward from v is called the out-degree of v.

For any undirected graph G, and any particular vertex v in V(G), the number of vertices v' in V(G) that are directly linked to v is called the degree of v.

A graph G is called simple if it is undirected, unweighted, without self loops (i.e. loops directly connecting vertices to themselves), and has at most one edge connecting any pair of vertices.

A simple graph G is called regular if each of its vertices has the same degree.

A graph G is called random if its edges are generated in some random fashion.

The minimum number of edges that must be traversed to travel from a vertex v to another vertex v' of a graph G is called the shortest path length (or distance) between v and v'.

A graph G is connected if any vertex can be reached from any other vertex by traversing a path consisting of only finitely many edges, or equivalently, if the shortest path length between any two vertices is a well-defined finite number.

A graph G is disconnected if its vertices can be partitioned into two or more subsets in which there are no connecting edges between the vertices in the different subsets.

The maximal connected subsets of a graph G are called its components. For a connected graph, the graph itself is its only component.

Small-World Network Terminology:

Remark: See Watts (1999, pp. 26-33) for a more detailed discussion of small-world networks.

For any connected graph G, the average distance between pairs of vertices is referred to as the graph's "characteristic path length." More precisely, for any two vertices v and v' in V(G), let L(v,v') denote the shortest path length connecting v to v'. Let L(v) denote the average of L(v,v') across all vertices v' in V(G) with v' not equal to v. Finally, define the characteristic path length L(G) of G to be the average of L(v) across all vertices v in V(G).

For any simple connected graph G with at least two vertices, the "clustering coefficient" C(G) measures the extent to which vertices linked to any given vertex v are also linked to each other. Or in other words, are the friends of my friends also my friends?

More formally, consider any simple connected graph G with vertex set V(G) and edge set E(G). For any particular vertex v in V(G), define N(v) to be the neighborhood of v consisting of all vertices v' in V(G) that are directly connected to v through an edge in E(G). (By the assumption of simplicity, v itself is not contained in N(v); and by the assumption of connectivity, N(v) contains at least one node unless V(G) is a singleton.) If N(v) contains 0 or 1 nodes, define the clustering coefficient C(v) for v to be 1. Otherwise, define C(v) to be the number NEActual_v of edges actually existing between vertices in N(v) divided by the number NEPossible_v of all possible edges that could exist between vertices in N(v). That is,

                      NEActual_v
             C(v) =  --------------
                      NEPossible_v  

The clustering coefficient C(G) for G is then defined to be the average of C(v) over v in V(G).

Note:: Letting m = |N(v)| denote the cardinality of N(v), the assumed simplicity of G implies that NEPossible_v = m[m-1]/2.

As defined by Watts and Strogatz (1998), a Small-World Network is a simple connected graph G exhibiting two properties:

1. Large Clustering Coefficient: Each vertex of G is linked to a relatively well-connected set of neighboring vertices, resulting in a large value for the clustering coefficient C(G);

2. Small Characteristic Path Length: The presence of short-cut connections between some vertices results in a small characteristic path length L(G).

In summary, then, small-world networks have both local connectivity (property 1) and global reach (property 2).

ISSUE 1: What type of phase transition do random graphs undergo as connectivity increases? (Batten, pp. 99-104)

Remark: See the glossary (above) for explanations of the terminology used below. For a more rigorous and detailed treatment of random graphs, see Bollobás (1985), Strogatz (2001), and Watts and Strogatz (1999). Erdös and Rényi (1960) were the first researchers to study how the connectivity of a random graph changes as a function of the number of its edges.

For any graph G, let R denote the ratio of its size (number of edges) to its order (number of vertices), and let M denote the size of its largest component.

Batten notes that the plot of M against R for a sequence of random graphs G_0, G_1, G_2,... with steadily increasing R values reveals that the random graphs undergo a phase transition as R passes through the critical value R=0.50. Specifically, as depicted in Figure 3.6 (p. 103), the random graphs transit from being "nearly unconnected" to "nearly connected" at the critical value R=0.50, in the sense that the value of M undergoes a sudden dramatic increase.

         M
         |
         |                         _     -          -
         |                     -
M = Size |                   -
of the   |
largest  |                  -
component|
         |                 -
         |
         |               -
         |         -
         |______________________________________________ R

                        0.50

         R = Ratio of Number of Edges to Number of Vertices

Batten describes the construction of the random graph sequence G_0, G_1, G_2,... as follows. Let N denote some suitably large integer (Batten selects N=20). Start with a completely disconnected graph G_0 having N vertices and 0 edges. Choose two vertices at random from the vertices of G_0 and connect them with an edge. The resulting graph has N vertices and one edge -- call this graph G_1. Next, choose two vertices at random from the vertices of G_1 and connect them with an edge -- call this graph G_2. And so forth.

For each graph G_i in the sequence G_0, G_1, G_2,..., plot M(G_i) against R(G_i). Batten claims that the resulting plot will lie along an S-shaped ("sigmoid") curve as depicted in Figure 3.6 (p. 103). At first the value of M will increase at a slow but slightly accelerating rate. However, as R approaches the critical value 0.50, the value of M will suddenly exhibit a substantial increase. As R continues to increase beyond 0.50, the value of M will increase at an ever diminishing rate as it approaches an upper bound.

NOTE: Although Batten does not clarify this, it would appear that the graphs G_n are directed graphs, that self-looping is ruled out in his construction procedure, and that at most two (directed) edges e_{ij} and e_{ji} are permitted between any two vertices i and j. Consistent with Figure 3.6, the upper bound of M would then be N*[N-1], the number of distinct ways in which two vertices can be selected from among a collection of N vertices with order of selection taken into account.

ISSUE 2: Do socioeconomic systems also undergo some kind of phase transition as connectivity increases? (Batten, pp. 104-105)

Remark: See the glossary (above) for explanations of the terminology used below. A more rigorous and detailed treatment of the small-world network findings discussed below can be found in Strogatz (2001), Watts and Strogatz (1998), Watts (1999), and Wilhite (2001).

Batten points to several suggestive examples of socioeconomic systems exhibiting phase transitions as connectivity increases: for example, the formation of community common interest groups (e.g., voting blocs, political parties, unions, clubs); an audience watching a performer; and traffic on city highways. He notes that he discusses the traffic example in detail in his Chapter 6 of his book.

At the time he wrote his book, Batten was apparently unaware of the attempts by Duncan Watts and Steven Strogatz to rigorously address his question through the quantitative analysis of Stanley Milgrom's conception of a small world network (Milgrom, (1967); Watts and Strogatz, 1998; Watts, 1999).

ISSUE 3: Small World Networks as Trade Networks?

Watts and Strogatz (1998) explore a parameterized family of simple connected graphs G(p) that can be tuned by the parameter p to range all the way from a graph G(0) at p=0 that is regular (every vertex has the same degree) to a graph G(1) at p=1 that is random (every vertex has a randomly determined degree).

For intermediate values of p, they discovered a range of "small world networks" G(p) displaying a number of interesting properties. The networks exhibited global reachability (similar to random graphs) yet had high degrees of local neighborhood clustering (similar to regular graphs).

More precisely, as detailed in Strogatz and Watts (1998, pp. 440-441), these small-world networks G(p) arise for an intermediate range of p values where the characteristic path length L(G(p)) = L(p) of the graph G(p) is almost as small as for a random graph yet the clustering coefficient C(G(p)) = C(p) of the graph G(p) is much greater than for a random graph.

The small L(p) values result from the introduction of a few "short cut" edges that connect vertices that otherwise would be very far apart. For small p, each short cut has a highly nonlinear effect on L(p), contracting the distance not just between the directly connected pair of vertices but also between their immediate neighborhoods, and between neighborhoods of neighborhoods, and so forth.

In contrast, for small p, an edge removed from a clustered neighborhood to form a short cut has at most a linear contracting effect on C(p). Thus, for small p, an increase in p causes L(p) to drop very rapidly while C(p) decreases only slowly.

After discovering this small-world form of network connectivity, Stogatz and Watts (1998) investigated its empirical significance. They found that small-world network architectures appear to characterize a wide variety of real-world networks as disparate as the neural network of the nematode worm Caenorhabditis elegans (C. elegans), the power grid of the western United States, and the collaboration pattern of motion picture actors. They conjectured that one reason for the ubiquity of small-world network architectures might be enhanced signal-propagation speed, computational power, and synchronizability.

A number of ACE researchers have begun to consider small-world networks in relation to economic processes. For example, Wilhite (2001) uses an ACE model of a bilateral exchange economy to explore the consequences of restricting trade to small-world trade networks.

Specifically, Wilhite focuses on the trade-off between market efficiency and transaction costs under four types of trade networks:

• (a) completely connected trade networks (every trader can trade with every other trader);

• (b) locally disconnected trade networks consisting of disjoint trade groups;

• (c) locally connected trade networks consisting of trade groups aligned around a ring with a one-trader overlap at each meeting point; and

• (d) small-world trade networks constructed from the locally connected trade networks by permitting from one to five randomly specified short-cut trade links between members of non-neighboring trade groups.

Given each type of trade network, traders endowed with stocks of two goods seek out feasible partners, negotiate prices, and then trade with those who offer the best deals.

Wilhite's key finding is that small-world trade networks provide most of the market-efficiency advantages of the completely connected trade networks while retaining almost all of the transaction cost economies of the locally connected trade networks.

His findings also suggest that there exist micro-level incentives for the formation of small-world trade networks, since the traders who use this type of network tend to do well relative to the traders who do not.

As Strogatz (2001) and Barabasi (2002) both note, however, for social networks it is not enough to focus on the implications of a fixed or parametrically varied network architecture. Feedback mechanisms are at work in social networks that reduce the ability to predict system performance solely on the basis of initial structural conditions.

For example, in social networks, the participants (vertices) might be able to preferentially determine their relationships (edges) over time by means of adaptive choice and refusal of partners. In such cases, interaction networks might continually coevolve over time through the operation of intricate feedback loops: who I partner with today depends on the behaviors expressed by myself and my partners in past interactions, and how I behave today depends on whom I partnered with in past interactions.

Evolving interaction networks in economic contexts will constitute the main focus of my next lecture.

References and Recommended Further Readings:

Frederic Amblard, "Simulating Social Networks: A Review of Three Books" (html), Journal of Artificial Societies and Social Simulation (Electronic Journal), Vol. 6, Issue 2, 2003.

W. Brian Arthur, "Inductive Reasoning and Bounded Rationality: The El Farol Problem" (html), American Economic Review (Papers and Proceedings) 84, 1994, 406-411.

Albert-Lázló Barabási, Linked: The New Science of Networks, Cambridge, MA: Perseus Publishing
2002, Cloth: ISBN 0-738-20667-9.

David F. Batten, Chapter 3:"Sheep, Explorers, and Phase Transitions" (pdf preprint - no figures, 203K), pages 81-115 in Discovering Artificial Economics: How Agents Learn and Economies Evolve, Westview Press, Boulder, Colorado, 2000, ISBN: 0-8133-9770-7. NOTE: Unfortunately this book is now out of print.

B. Bollobás, Random Graphs, Academic Press, London, 1985.

Andy Clark, Chapter 6: "Emergence and Explanation", pp. 103-128 in Andy Clark, Being There: Putting Brain, Body, and World Together Again, MIT Press, Cambridge, MA, 1998.

P. Erdös and A. Rényi, "On the Evolution of Random Graphs, Publications of the Mathematical Institute of the Hungarian Academy of Sciences, Vol. 5 (1960), 17-61.

Stuart Kauffman, Origins of Order, Oxford University Press, 1993.

Stanley Milgrom, "The Small World Problem", Psychology Today, 1967, Vol. 2, 60-67.

Steven H. Strogatz, "Exploring Complex Networks" (pdf,589K), Nature, Volume 410, No. 6825, March 8, 2001.

Leigh Tesfatsion, "Introductory Notes on the Structural and Dynamical Analysis of Networks" (pdf,2.3MB).

NOTE: These presentation slides summarize and graphically illustrate key points from the above notes.

Leigh Tesfatsion, "Notes on Wilhite (2001)" (pdf,236K).

NOTE: These presentation slides summarize key points from the article by Wilhite (2001), linked below.

Duncan J. Watts and Steven H. Strogatz, "Collective Dynamics of `Small-World' Networks", (pdf,294K), Nature, Volume 393, No. 6684, 18 June 1998, pp. 440-442.

Duncan J. Watts, Small Worlds: The Dynamics of Networks Between Order and Randomness, Princeton Studies in Complexity, Princeton University Press, Princeton, N.J., 1999.

Duncan J. Watts, Six Degrees: The Science of a Connected Age, W. W. Norton & Co., Reprint Edition, 2004, 368pp.

Allen Wilhite, "Bilateral Trade and `Small-World' Networks", (pdf,181K), Computational Economics, Volume 18, No. 1, August 2001, 49-64.

Copyright © Leigh Tesfatsion. All Rights Reserved.