Notes on Network Effects:
Agent-Based Computational Economics

Last Updated: 7 March 2007

Site Maintained By:
Professor Leigh Tesfatsion
tesfatsi AT

Syllabus for Econ 308


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

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. However, if you are willing and able to handle a rather large download, the entire Batten book (figures included) in pdf can be accessed at here (pdf,17MB).

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

Andy Clark, Chapter 6: "Emergence and Explanation," pages 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.

Steven H. Strogatz, "Exploring Complex Networks", Nature, Volume 410, No. 6825, March 8, 2001.

Duncan J. Watts and Steven H. Strogatz, "Collective Dynamics of `Small-World' Networks", 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.

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

Key Issues

1. Distinguishing between "simple" and "complex" economic systems (Batten, pp. 85-88)

Batten proposes the following distinction between simple and complex economic systems: "By and large, simple economic systems are homogeneous and weakly interactive. Individual beliefs and expectations must be sufficiently uniform, and the level of interactions sufficiently weak or trivial, for us to be able to predict collective patterns of behavior with any confidence. ... By way of comparison, complex economies are heterogeneous and strongly interactive. They lie beyond the point where individual behavior can be discerned with any degree of confidence (see Figure 3.1). ... A complex economy is never additive. It behaves quite differently from what we'd expect by simply adding up these pairs, trios, and quartets of interaction. Self-organizing economies are not additive; they're emergent. This is precisely why some of the collective behaviors can't be predicted in advance."

This discussion by Batten blends the idea of "predictability" with possible factors (heterogeneous expectations, strong interaction effects, non-additivity) that might make prediction difficult. For reasons clarified below, a more rigorous and useful way to define the difference between "simple" and "complex" economic systems would seem to be to focus on the degree of predictability per se. A secondary issue then arises: Which system features (if any) systematically affect the degree of predictability? Proposed definitions for "simple" and "complex" systems along these lines are outlined below.

Suppose a dynamic economic system can be simulated subject to controlled experimental conditions. That is, starting from any feasible initial state, the system can be run multiple times and its observed outcomes recorded. Call the economic system simple if, starting from any given initial state, the observed outcomes of multiple runs of the system have a central tendency distribution, in the sense that there exists a unique "attractor" (most likely outcome) around which the observed outcomes tend to cluster. In this case, the system structure (the initial state) determines a reliable "point prediction" for the system outcome: namely, the unique attractor corresponding to the initial state.

Example of a Simple System: W. Brian Arthur's El Farol Bar Problem (Batten, Chapter 2, pp. 62-67).

Suppose a group of 100 people in Santa Fe are fond of attending the El Farol bar on Thursday nights, when Irish music is featured. Space is limited, however, and each person would prefer to stay home rather than go to El Farol if he expects a crowd above sixty. The diabolical aspect of this prediction problem is that homogeneous expectations can never be correct. If everyone expects El Farol to be crowded, all 100 people will stay home and the bar will not be crowded. If everyone expects El Farol not to be crowded, all 100 people will go to the bar and it will be crowded.

Arthur (1994) constructs an agent-based computational model to study how agents might coevolve their expectations in this situation. Each of his 100 computational agents uses a classifier system to evolve a predictor for bar attendance. The experimentally observed bar attendance rates tend to cluster tightly around the 60 percent level (see Figure 2.4, p. 65). This 60 percent outcome is supported by a continually evolving ecology of heterogeneous expectations, not by uniform expectations. This contradicts Batten's assertion (pp. 85-86), quoted above, that individual beliefs and expectations must be "sufficiently uniform" in order for the outcome of collective behavior to be predicted with any accuracy.

In contrast, call an economic system complex if, starting from any given initial state, the observed outcomes of multiple runs of the system have a spectral distribution with two or more distinct attractors around which the observed outcomes tend to cluster. In this case, the system structure in and of itself does not determine a reliable point prediction of the system outcome.

Examples of Complex Systems: Systems with path dependence and lock-in effects, such as labor markets with adaptive job search, and economic systems with technological innovations whose value increases with the number of users. Such systems will be the focus of Section VII of the course.

2. Is the global economy becoming strongly interactive? (Batten, p. 98)

Batten points to the following phenomena which he claims are indeed causing the global economy to become strongly interactive: Rising levels of international trade; Increased "foreign direct investment" (i.e., increased foreign ownership of domestically located productive assets); Rise of "multinational" (i.e., multi-country owned) corporations.

On pages 96-98 he discusses an example to support his thesis. He asks: Who actually stands to gain most from increased beef exports from America to Japan? He visualizes the possible relationships by means of signed digraphs (Figures 3.3 and 3.4).

NOTE: The positive weights in Figures 3.3 and 3.4 on the outgoing link from X (the yen/dollar exchange rate) to A (export of American beef to Japan) and G (export of American grain to Japan) are not plausible. A higher yen/dollar exchange rate X means that more yen are now needed to buy each dollar's worth of American goods. All else equal, this should cause Japanese consumers to lower their demand for imported American goods since the yen price of these goods will now be higher.

Below I have combined and extended Batten's digraphs to a single signed digraph that more fully reflects Batten's accompanying text discussion. The following assumptions are made for illustration only, to illustrate Batten's points about possible complicating effects. (It would be interesting to see actual empirical data related to these effects).

  1. Japanese cattle are raised entirely on American grain;

  2. Some America-based cattle ranches have Japanese owners, and these ranches are the primary beneficiaries of an increase in exports of beef from America to Japan;

  3. Some cattle ranches in Japan have American owners;

  4. Grain farms in America are entirely owned by Americans;

The nodes of the modified digraph are as follows:

            /|\           /|\
          +1 |             | +1
             |             |
    +1      \|/     -1    \|/       +1    --------------
 X<------ JConsBA ----- JConsBJ ------>     ProdBeefJ
   ------>   |                           --------------
    -1       |  +1                      +1  |    +1  |
             |                              |        |
            \|/                          IncJRJ   IncARJ
          ExpABeefJ                         |        |
             |                          +1 \|/   +1 \|/
             |                           --------------
          +1 |                             ExpGrainAJ
             |                           --------------
             |                                  |
            \|/                             +1  |
   ---------------         +1                  \|/
     ProdBeefA    ----------------------->  ProdGrainA
   ---------------                              |
   +1 |   +1 |                              +1  |
      |      |                                 \|/
     \|/    \|/                             IncGrainA
   IncARA IncJRA                          

Suppose that the U.S. government convinces Japan to eliminate the tariff on imports of American beef into Japan. Assuming this cut is immediately passed through to the retail level, it will decrease the yen price of American beef relative to the yen price of Japanese beef for Japanese consumers from 13 yen per pound to 10 yen per pound. All else equal, this should lead to an increase in JConsBA (Japanese consumption of beef imported from America). The issue is who ultimately gets helped and who ultimately gets hurt by this change? In particular, is America better off or worse off overall as a result of this Japanese tariff cut?

Batten claims that standard "partial equilibrium" international trade models tend to focus only on the chain consisting of the positively weighted links connecting JConsBA to ExpABeefJ to ProdBeefA to IncARA. This chain predicts that a tariff cut causing an increase in JConsBA will ultimately increase the income IncARA of American-owned cattle ranches, a good thing for America. Batten points out, however, that complicated network effects make it difficult to predict the overall impact of this tariff cut on the welfare of American citizens.

Specifically, the increase in JConsBA due to a cut in the yen price of American beef for Japanese consumers will have a negative impact on JConsBJ (Japanese consumption of beef produced in Japan) as Japanese consumers now substitute American beef for Japanese beef. This, in turn, will have a negative effect on ProdBeefJ, the production of beef in Japan. This will decrease the income of cattle ranches in Japan, hence in particular it will decrease the income IncARJ of American-owned cattle ranches in Japan.

In addition, the reduction in ProdBeefJ will decrease ExpGrainAJ (the export of grain from America to Japan) since not as much grain will be needed in Japan to feed cattle. This decrease in the amount of American grain needed to feed cattle in Japan will not be fully offset by an increase in the amount of American grain needed to feed cattle in America since at least part of any increase in beef exports to Japan will represent a switch of already existing beef production from American consumers to Japanese consumers. Consequently, the overall production ProdGrainA of grain in America will decline, which will decrease the income IncGrainA of American grain farmers.

NOTE: Realistically, for Japanese consumers to convince American beef producers to sell more beef to them in the short run, before American beef production can be increased to fully meet this increase in demand, the Japanese consumers will have to bid up the dollar price of American beef (thus discouraging American demand for American beef). However, the tariff cut gives Japanese consumers some leeway to do this while still ensuring they pay a lower yen price for American beef than before the tariff cut. For example, assuming the exchange rate X stays fixed at 2 yen per dollar, even if Japanese consumers bid up the dollar price of American beef from $5/pound to $6/pound, they will only pay 12 yen per pound of American beef, which is still lower than the 13 yen per pound they paid prior to the tariff cut. Note that any such rise in the dollar price of American beef would decrease the welfare of American beef consumers.

Finally, the income earned by cattle ranchers in America will increase due to the increase in ProdBeefA, the production of beef in America, but the overall increase in income to cattle ranches in America will be divided between IncARA and IncJRA, i.e., between the incomes of American and Japanese-owned cattle ranches in America.

The ultimate effect of the tariff cut on the welfare of American citizens (grain farmers, cattle ranchers, and beef consumers) is therefore ambiguous without further information regarding the timing and magnitudes of the indicated production and income changes.

QUESTIONS: How can these complicated network effects be more rigorously modeled? By an equation-based model? By an agent-based model? By some other approach? What are the advantages and drawbacks of each approach?

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

Notes:The graph theory terminology used below is explained above in the "Basic Concepts from Graph Theory" portion of these notes. For a more rigorous and detailed treatment of random graphs, see Bollobás (1985), Strogatz (2001), and Watts and Strogatz (1999). The first researchers to study how the connectivity of a random graph changes as a function of the number of its links were Erdös and Rényi (1960).

For any graph G, let R(G) denote the ratio of its size (number of links) to its order (number of nodes), and let M(G) denote the size (number of links) 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=Size of|                   -
largest  |
component|                  -
         |                 -
         |               -
         |         -
         |______________________________________________ R


                  R = Ratio of Links to Nodes

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 nodes and 0 links. Choose two nodes at random from the nodes of G_0 and connect them with a link. The resulting graph has N nodes and one link -- call this graph G_1. Next, choose two nodes at random from the nodes of G_1 and connect them with a link -- 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: What is the upper bound of M? In Batten's description of his construction procedure (pp. 99-100), the sequential selection of nodes for linking appears to be "with replacement" each time, which would permit multiple selections of the same nodes. In particular, self-loops and multiple links between the same two nodes would be permitted. In this case, however, the upper limit of M would be infinite since additional links could always be incorporated. This is not consistent with Batten's series of figures (Figure 3.5(a)-(e), pp. 100-102), in which no self-loops or multiple links are exhibited. Moreover, it is not consistent with Batten's Figure 3.6, in which the upper bound of M is depicted as being 380 = 20*19. Consequently, although Batten does not clarify this, it would appear that self-looping is ruled out in his construction procedure, and that at most two links are permitted between any two nodes. Consistent with Figure 3.6, the upper bound of M would then be N*[N-1], the number of distinct ways in which two nodes can be selected from among a collection of N nodes (with order taken into account).

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

Note: The graph theory and small-world network terminology used below is explained above in the "Basic Concepts" portion of these notes. 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; traffic on city highways. He notes that he will discuss the traffic example in detail in his later Chapter 6.

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 an analysis of small world networks (Watts and Strogatz, 1998; Watts, 1999). These authors explored a simple family of graphs G(p) that could be tuned by a parameter p to range all the way from a regular graph G(0) at p=0 (every node has the same number of links) to a random graph G(1) at p=1 (all links are randomly generated). 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 lengths L(p) of the networks are almost as small as for a random graph yet the clustering coefficients C(p) of the networks are much greater than for a random graph. The small L(p) values result from the introduction of a few "short cut" links that connect nodes 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 nodes but also between their immediate neighborhoods, and between neighborhoods of neighborhoods, and so forth. In contrast, for small p, a link 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, 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) notes, 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 (nodes) might be able to preferentially determine their relationships (links) 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.

The issue of evolving interaction networks will constitute one of the main topics of Section VII of the course, which focuses on the ACE modelling of markets with strong learning and network effects.

6. Does learning through interaction promote cooperation? (Batten, pp. 109-111)

Batten asserts (p. 111) that "learning by interacting proves to be an adaptive process out of which a desire for cooperation emerges." As will be seen in Section VII of this course, this is too simplistic. Certain structural conditions promote cooperation; others do not. For example, basic market structural conditions (e.g., costs, capacities,...) and biases inherent in market protocols (e.g., who gets to bid first) can systematically advantage buyers over sellers, or vice versa, encouraging aggressive and predatory behaviors on the part of the advantaged group.

Glossary of Basic Concepts

Coevolutionary Learning (Batten, p. 81):

"What agents believe affects what happens to the economy, and in turn, what happens to the economy affects what agents believe. We call (this positive feedback loop) coevolutionary learning."

Fallacy of Composition (Batten, pp. 81-82):

"What seems to be true for individuals isn't always true for society as a whole. Conversely, what seems to be true for all may be quite false for any one individual." (p. 81)

Example: If ONE farmer succeeds in producing a bumper corn crop, he will likely be rewarded with a higher income (relative to other farmers). However, if EACH farmer succeeds in producing a bumper corn crop, the most likely outcome will be an aggregate excess supply of corn a the current corn price, a sugsequent drop in the corn price, and lower incomes for all corn farmers.

"(Fallacy of Composition is) a fallacy in which what is true of a part is, on that account alone, alleged to be also necesarily true of the whole." (p. 82)

Simple vs. Complex Economic Systems (Batten, pp. 85-86):

This distinction is taken up in detail as a "Key Issue," below.

Phase Transition (Batten, p. 86):

An abrupt marked change in the pattern of behavior exhibited by the state of a dynamical system. For example, a smooth flow of traffic might suddenly degenerate into stop-and-go traffic, or a system exhibiting large temperature fluctuations might suddenly transit to a constant temperature state. Phase transitions can occur due to the intrinsic dynamics of a system (e.g., a traffic accident) or in response to external effects (e.g., a deliberate change in the value of an exogenously set system parameter).

Batten (p. 86) identifies a phase transition as an "unexpected" change, but this is not the meaning of "phase transition" as typically used in mathematics. "Abrupt" changes need not be "unexpected" changes.

Emergent Property (Batten, p. 88; Clark, Chapter 6):

Roughly, a system consisting of a collection of agents is said to exhibit an emergent property if it develops a global (system-wide) property that cannot be predicted solely on the basis of the inherent properties of the agents themselves. The idea is that the emergent property depends on the interaction pattern among the agents, not just on their intrinsic structural aspects. Consequently, the emergent property cannot be deduced simply by "adding up" what is known about the individual agents, considered one by one.

Example: A system consisting of a container of gas molecules (the "agents") exhibits a temperature (the "emergent property").

Andy Clark devotes Chapter 6 ("Emergence and Explanation") to a detailed discussion of this controversial concept. On page 112 he defines a collective variable to be a variable that tracks a pattern resulting from the interactions among multiple elements of a system. He calls a phenomenon emergent if it is best understood by attention to the changing values of a collective variable.

Clark goes on to say: "Different degrees of emergence can now be identified according to the complexity of the interactions involved. Multiple, nonlinear, temporally asynchronous interactions yield the strongest forms of emergence; systems that exhibit only simple linear interactions with very limited feedback do not generally required understanding in terms of collective variables and emergent properties at all. Phenomenon may be emergent even if they are under the control of some simple parameter, just so long as the role of the parameter is merely to lead the system through a sequence of states themselves best described by appeal to a collective variable (e.g., the temperature gradient that leads a liquid through a sequence of states described by a collective variable marking the varying amplitude of the convection rolls)... Emergence, thus defined, is linked to the notion of what variables figure in a good explanation of the behavior of a system."

Connectivity (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.


A network is a finite 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.

Basic Concepts from Graph Theory (Batten, pp. 92-105; Watts, Section 2.2, pp. 25-40):

A graph is a set of nodes (or vertices) together with a set of links (or edges) that connect various pairs of nodes.

The number of links joining a node n to other nodes (including possibly itself) is called the degree of node n.
A graph is called regular if each of its nodes has the same number of links as any other node, i.e., if each node has the same degree. A graph is called random if its links are generated in some random fashion. The number of nodes of a graph is referred to as the order of the graph and the number of links of a graph is referred to as the size of the graph.

The minimum number of links that must be traversed to travel from a node n to another node n' is called the shortest path length or distance between n and n'. A graph is connected if any node can be reached from any other node by traversing a path consisting of only finitely many links, or equivalently, if the shortest path length between any two nodes is a well-defined finite number. Otherwise the graph is disconnected.

If a graph is disconnected, its nodes can be partitioned into two or more subsets in which there are no connecting links between the nodes in the different subsets. The maximal connected subsets of a graph are called its components. For a connected graph, the graph itself is its only component.

A graph is called a directed graph, or digraph, if each of its links is a directional arrow (or arc) between nodes that indicates a direction to the nodal relationship. A graph is called undirected if all of its links are undirected. A (di)graph is referred to as a weighted (di)graph if each of its links has associated with it a number indicating the strength of the link.

A signed digraph is a weighted digraph in which the weights are either +1 or -1. Consider a directed link from some node n to another node n'. A weight of +1 on this link indicates that node n and node n' move in the same direction: that is, an increase in node n will cause an increase in node n', and a decrease in node n will cause a decrease in node n'. Conversely, a weight of -1 on the link between node n and n' indicates that these nodes move in opposite directions: that is, an increase in node n will cause a decrease in node n', and a decrease in node n will cause an increase in node n'.

Terminological Note: In graph theory, a link connecting a node back to itself is called a "loop." Batten uses "loop" in a more general way to refer to any collection of one or more nodes in a digraph whose directed links result in a circular pattern of links, e.g., from n to n' to n'' and then back to n. To avoid confusion below, a link connecting a node to itself will be referred to as a self-loop and a circular pattern of links will be referred to as a closed chain.

A closed chain in a signed digraph that has a +1 weight on all of its links is deviation amplifying; it constitutes a special case of a positive feedback loop. A closed chain in a signed digraph that has a -1 weight on all of its links is deviation counteracting; it constitutes a special case of a negative feedback loop.

Basic Graph Theory Concepts Related Specifically to Small-World Networks (Relevant for Batten's discussion, pp. 99-105 and Key Issue 5, below):

Following Watts (1999, pp. 26-33), the average distance between pairs of nodes in a connected graph is referred to as the graph's "characteristic path length." More precisely, the characteristic path length L(G) of a connected graph G is the median of the means of the shortest path lengths connecting each node to all other nodes.

A graph is called simple if it has no self-loops and no multiple links between the same pair of nodes. The "clustering coefficient" of a simple graph measures the extent to which nodes linked to any given node n are also linked to each other. Or in other words, are the friends of my friends also my friends?

To be more precise about this, given a node n of a simple graph G, define the neighborhood of n to be the collection of all nodes that are adjacent (directly linked) to n, not including n itself. If this neighborhood contains k nodes, then k*[k-1]/2 is the maximum possible number of links that could exist among nodes in this neighborhood. Given any simple graph G, and any node n of G, the clustering coefficient for node n is defined to be the fraction C_n of possible links that actually occur in the neighborhood of n; and the clustering coefficient C(G) for G is defined to be the average of C_n over all of the nodes n of G.

As defined by Watts and Strogatz (1998), a small-world network is a connected simple graph exhibiting two properties:
  1. Large Clustering Coefficient: Each node of G is linked to a relatively well-connected set of neighboring nodes, resulting in a large value for the clustering coefficient C(G);
  2. Small Characteristic Path Length: The presence of short-cut connections between some nodes results in a small characteristic path length L(G).

In summary, then, small-world networks have both local connectivity and global reach.

Isotropic Random Graph (Batten, p. 103):

Following Kauffman (1993, p. 307), an isotropic random graph is a random graph such that the probability an edge joins any pair of points is equal.

Explorers vs. Sheep (Batten, pp. 106-109):

Batten uses explorers (or innovators) to describe one extreme of the learning spectrum -- inductive learners who are always actively searching for new possibilities. He uses sheep (or imitators) to describe the other extreme of the learning spectrum, deductive learners who prefer to remain with the status quo.

In more neutral terms, Batten recognizes that successful decision making typically involves two distinct behavioral modes: (1) Exploration: Actively seeking to learn more about your decision environment through information collection and experimentation; and (2) Exploitation: Making use of the information already in your possession. In systems science, this is known as the dual control problem -- having to learn about your problem environment even as you seek to optimize your situation within this environment.

Copyright © 2007 Leigh Tesfatsion. All Rights Reserved.