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.
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.
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).
As defined by Watts and Strogatz (1998), a SMALL-WORLD NETWORK is a simple connected graph G exhibiting two properties:
In summary, then, small-world networks have both local connectivity (property 1) and global reach (property 2).
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.
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).
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:
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.
Albert-Lázló Barabási,
Linked: The New Science of Networks,
Cambridge, MA: Perseus Publishing
2002, Cloth: ISBN 0-738-20667-9.
Stanley Milgrom, "The Small World Problem", Psychology Today, 1967, Vol. 2, 60-67.
Leigh Tesfatsion, "Introductory Notes on the Structural and Dynamical Analysis of Networks" (pdf,2.3MB).
Leigh Tesfatsion, "Notes on Wilhite (2001)" (pdf,236K).