https://sites.google.com/site/matteorichiardi/teaching/complexity-economics

​

Matteo Richiardi

Complexity Economics

University of Turin

February-April 2024

​

Lecture 8:�Networks

Matteo Richiardi

Complexity Economics

University of Turin

February-April 2024

​

Sources:

• Mitchell, ch. 15,16
• Bookstaber, ch. 11,12

In Ersilia, to establish the relationships that sustain the city’s life, the inhabitants stretch strings from the corners of the houses, white or black or gray or black-and-white according to whether they mark a relationship of blood, of trade, authority, agency. When the strings become so numerous that you can no longer pass among them, the inhabitants leave: the houses are dismantled; only the strings and their supports remain.

From a mountainside, camping with their household goods, Ersilia’s refugees look at the labyrinth of taut strings and poles that rise in the plain. That is the city of Ersilia still, and they are nothing.

They rebuild Ersilia elsewhere. They weave a similar pattern of strings which they would like to be more complex and at the same time more regular than the other. Then they abandon it and take themselves and their houses still farther away.

Thus, when traveling in the territory of Ersilia, you come upon the ruins of abandoned cities, without the walls which do not last, without the bones of the dead which the wind rolls away: spiderwebs of intricate relationships seeking a form.

—Italo Calvino, Invisible Cities (1972)

A Ersilia, per stabilire i rapporti che reggono la vita della città, gli abitanti tendono dei fili tra gli spigoli delle case, bianchi o neri o grigi o bianco-e-neri a seconda se segnano relazioni di parentela, scambio, autorità, rappresentanza. Quando i fili sono tanti che non si può più passare in mezzo, gli abitanti vanno via: le case vengono smontate; restano solo i fili e i sostegni dei fili.

​

Dalla costa d’un monte, accampati con le masserizie, i profughi di Ersilia guardano l’intrico di fili tesi e pali che s’innalza nella pianura. E’ quello ancora la città di Ersilia, e loro sono niente.

​

Riedificano Ersilia altrove. Tessono con i fili una figura simile che vorrebbero più complicata e insieme più regolare dell’altra. Poi l’abbandonano e trasportano ancora più lontano sé e le case.

​

Così viaggiando nel territorio di Ersilia incontri le rovine delle città abbandonate, senza le mura che non durano, senza le ossa dei morti che il vento fa rotolare: ragnatele di rapporti intricati che cercano una forma. �

Small worlds

• In the 1950s, the Harvard University psychologist Stanley Milgram designed an experiment to determine, on average, how many links it would take to get from any person to any other person in the United States.
• Ordinary people would attempt to relay a letter to a distant stranger by giving the letter to an acquaintance, having the acquaintance give the letter to one of his or her acquaintances, and so on, until the intended recipient was reached at the end of the chain.
• For the letters that made it to their target, the median number of intermediate acquaintances from starter to target was 5 �🡪 “six degrees of separation” (a bit of an urban myth).

Networks: Basic concepts

• Nodes (vertices, points)
• Links (edges, lines, connections)
• Directed vs. undirected (bidirectional) graphs
• Degree: The number of links that nodes have to other nodes �(in-degree, out-degree).
• Degree distribution: The fraction of nodes with degree k=1,2,....
• Path length:Number of links on the shortest path between 2 nodes

Networks as matrixes

Average path length and diameter

• Diameter: The shortest distance between the two most distant nodes.
• The diameter of the WWW is around 20, which means the two most distant pages on the planet are about 20 connections away from each other.
• The diameter of Facebook is around 40 (average path length: 4.7).

​

• Average path length (distance): The average number of steps along the shortest paths for all possible pairs of nodes in the network

​

​

​

​

Degree Centrality

• Capture importance of a node’s position �in the network.
• Degree Centrality: The number of edges connected to a node.
• The red dude has the �highest importance if our criteria is �degree centrality

Eigenvector Centrality

• Imagine a high school student with 100 friends at his school, compared to an individual who is friends with 10 congressmen (with hundreds of connections).
• Degree centrality would be agnostic to the importance of neighboring nodes, and would consider the high school student more important in this case.
• Eigenvector centrality gives each node a score that is proportional to the sum of the scores of all its neighbors.

Closeness centrality

🡪 If a node is on average closer to other nodes, it’s more important.

Betweenness Centrality

• The amount of influence a node has over the flow of information in a network.
• Nodes with high betweenness centrality are often acting as a bridge of information from one part of the network to another.

Node 22 doesn’t have a high degree but it’s playing a key role in connecting two clusters

Clustering Coefficient

• Local: for each node, it is the proportion of connections between its neighbors (i.e., nodes connected to the node) relative to the maximum possible number of such connections.
• Global: It is the average for all nodes

• C’s neighbours are A, B, D and E.
• AB is the only existing connection between C’s neighbours…
• …out of 6 possible connections: AD, AE, BD, BE, DE and AB.

🡪 The clustering coefficient for C is 1/6

Regular networks

• Each vertex has the same number of neighbours

Random networks

• Graph is wired randomly

Star networks

• Spoke-hub structure, where every node is connected to a central node

Complete networks

• Every pair of distinct nodes is connected by a unique link.

Small-world network

• Random rewiring of some of the links of a regular network
• Relatively few long-distance �connections
• Small average path-length �relative to the total number �of nodes.
• High degree of clustering: �for any nodes A, B, and C, �if node A is connected to �nodes B and C, then B and C �are also likely to be connected to one another.

Example: Kevin Bacon game

• Network of movie actors: two actors are linked if the have appeared in at least one movie together
• “Popularity” of an actor as the shortest path to the actor Kevin Bacon, due to his prolific screen career covering a diverse range of genres.

Why small-world?

It has been hypothesized that at least two conflicting evolutionary selective pressures are responsible for the ubiquity of small-world properties:�

1. The need for information to travel quickly within the system, and
2. The high cost of creating and maintaining reliable long-distance connections.

Scale-free networks

• the World Wide Web
• air transport
• Finance
• …

Scale-free networks

• Degrees follow a power law �(negative exponential, or Pareto) distribution
• Remember anything? (Zipf’s law)

Pareto and Zipf

• Zipf’s law refers to the ‘importance’ n of an occurrence of an event relative to it's rank r: n ~ r^-b
• Pareto was interested in the distribution of income. Instead of asking what the r-th largest income is, he asked how many people have an income greater than x: P[X > x] ~ x^-k
• At first, it appears that we have discovered two separate power laws, one produced by ranking the variables, the other by looking at the frequency distribution. 
• The phrase "The r-th largest city has n inhabitants" is equivalent to saying "r cities have n or more inhabitants". This is exactly the definition of the Pareto distribution, except the x and y axes are flipped.

Pareto and Zipf

• Whereas for Zipf, r is on the x-axis and n is on the y-axis, for Pareto, r is on the y-axis and n is on the x-axis.
• Simply inverting the axes, we get that if the rank exponent is b, i.e.�n ~ r^-b in Zipf,   (n = income, r = rank of person with income n)�then the Pareto exponent is 1/b so that�r ~ n^-1/b   (n = income, r = number of people whose income is n or higher)

George Kingsley Zipf (1902-1950)

�Vilfredo Pareto�(1848-1923)

Network resilience

• A very important property of small-world (SM) and scale-free (SF) networks is their resilience to the deletion of nodes.
• This means that if a set of random nodes (along with their links) are deleted from a large scale-free network, the network’s basic properties do not change.
• SM and SF networks achieve resilience through different mechanisms.

​

Resilience in small-world networks

• In a small-world network, random deletion of nodes or edges tends to disrupt local clustering but maintains the overall short path lengths due to the presence of a few long-range connections.
• This property makes small-world networks resilient to random deletions because even though local clusters may be disrupted, the overall network connectivity remains intact.

Resilience in scale-free networks

• In a scale-free network, random deletion is overwhelmingly likely to affect low-degree nodes, since these constitute nearly all nodes in the network.
• Deleting such nodes will have little effect on the overall degree distribution and path lengths.
• However, if one or more of the hubs is deleted, the network will be likely to lose all its scale-free properties and cease to function properly.