Complex Networks and their applications

Guido Caldarelli

The game field

Hawking said that in his opinion the twenty-first century would be the "century of complexity". 

We already know the basic laws of physics, we need to understand how they interact with each other.

Ashutosh Jogalekar Scientific American 23/4/2013

Stephen Hawking’s advice for twenty-first century grads:  Embrace Complexity.

Critical Phenomena

Critical phenomena is the collective name associated with the physics of critical points.

Most of them stem from the divergence of the correlation length, but also the dynamics slows down.

​

Critical phenomena are connected to

• scaling relations among different quantities,
• power-law divergences of some quantities (e.g. magnetic susceptibility in the ferromagnetic phase transition)
• universality,
• fractal behaviour,
• ergodicity breaking

​

The critical behavior is usually different from the mean-field approximation which is valid away from the phase transition, since the latter neglects correlations, which become increasingly important as the system approaches the critical point where the correlation length diverges.

​

Many properties of the critical behavior of a system can be derived in the framework of the renormalization group.

Fractals appear

2.5 10¹⁸ byte per day

In less than one year

(every year) Information available is

doubled

Statistical Physics

Statistical Society

What can we learn?

?????

People are not particles!!! We need more than few parameters (they are also distributed with fat tails)

All we know is the geometry of interactions

Physics of humans

GRAPH THEORY

Undirected

Directed

A

B

D

C

E

F

G

H

I

L

LINKS DO NOT HAVE DIRECTION

EXAMPLE

Collaborations (films, papers)

Protein Interactions

Internet

A

F

G

E

B

C

D

EXAMPLE

WWW

Phone calls

Metabolic Reactions

LINKS GO IN ONE DIRECTION

Properties of Networks

1 Scale Invariant that is they are very heterogeneous

​

2 Small-world structures that is you can travel them easily

​

3 Very clusterised that is we have many communities inside

​

4 Non trivial centrality distributions that is vertices are not at all the same

and much more...

1 Scale Invariance

Nobody is tall 2mm or 300 m

But somebody can have 10⁵ more contacts than you on Twitter

Scale-free Phenomena

Gaussian Phenomena

1 Scale Invariance

PNAS 2021 118 e2013825118

​

2 Small world

2 Small World

On average we are at 6 degrees of separation from others

Much less actually

3 Clustering from Bipartite

U

V

4 Centralities

A Degree Centrality

​

B Closeness Centrality

​

C Betweenness Centrality

​

D Eigenvector Centrality

4 communities

Mapping the world

​

Networks have the property to map space and to show what happens

In every Indo-European (past or present) To see = To know “*weyd-”

• in Latin we have video/videor = I see / It looks appropriate
• Ancient Greek (v)oida = I have seen and now I know
• in Sanscrit veda = to know
• in German wissen = to know
• In English wise

​

in Chinese the root is different, míngbai (shining white)

Complexity and Social

This is a map of alliances among

Florentine Families in the

Renaissance.

A link is a Marriage between two

individuals of the respective families

A visual inspection clarifies the central node of Medici and the peripheral of Pazzi.

Universal Behaviour

Fake News

Definition

following Lazer et al., fake news are "information that mimics news media content in form but not in organizational process or intent. Fake news overlaps with other information disorders, such as misinformation (false or misleading information)."

D. M. J. Lazer et al. “The science of fake

news”, Science 359, 1094–1096 (2018).

Ferrara, E.,

CoRR abs/1707.00086 (2017)

Fake News

In 2016, roughly 50% of Americans aged 18-29 used online platforms as their primary source of news while 27% watched the news on television and 5% read print newspapers [Niklewicz 2017];

As of August 2017, 67% of US adults report that they get at least some of their

news on social media [Shearer and Gottfried 2017];

Country of Descartes

forza nuova

Country of Renaissance

forza nuova

Financial Networks

Typically we focus on Big Structures but forget the microscopical part

Even in the vertex we can find complexity

Debtrank

LIABILITIES

ASSETS

BANKRUPT

Other

Interbank loans

Bonds

EQUITY

LIABILITIES

ASSETS

DISTRESS

Other

Interbank loans

Mortgages

Shares

EQUITY

LIABILITIES

ASSETS

EQUITY

THE INNER DYNAMICS OF SINGLE FINANCIAL INSTITUTION

Shares

Interbank

deposits

Households

(deposits)

Bonds

Interbank

deposits

Households

(deposits)

Bonds

Interbank

deposits

Households

(deposits)

Other

Interbank loans

Shares

Households (mortgages)

Households (mortgages)

Debtrank

A_ij is the Asset of type j owned by i i “owns” j

L_ij is the Liability of i against j i “has a debt” with j

E_i is the equity (must be > 0 @maturity) owned by i E=A-L

S. Battiston et al. Scientific Reports 2 541 (2012).

M. Bardoscia, et al. Plos One, 10, e0130406 (2015)

(Accounting) Leverage in j is defined as

the investment of i divided by its equity

Leverage

Investors are said to be leveraged when they borrow money to invest.

Mortgage are a form of leverage,

If we put a capital of $ 40,000 as a down payment and we borrow $160,000 to buy

a house worth $ 200,000, then our leverage is equal to 5:

the value of our assets (the house) divided by our capital (the Equities).

​

Leverage is related to risk, because it amplifies our gains & losses.

If the value of the house increases to $ 220,000, we could sell it, pay back our debt

(let us assume for simplicity there is no interest rate) and we would have gained  

$ 20,000.

An increase of 10% in the value of the house -> increase of 50% of our initial capital.

That is the meaning of leverage equal to 5

Leverage

external shock implies devaluation of own asset

Interbank

loans

Shares

Other

Mortgages

Interbank

(deposit)

Bonds

Households

(deposit)

EQUITY

j

Interbank loans

Other

Mortgages

Interbank

(deposit)

Bonds

Household

(deposit)

EQUITY

Shares

i

`

So what happens in a real transaction?

Debtrank

DebtRank is the total loss of equity after distress of one/more institutions

People used avalanche dynamics in the stress tests:

As long as you are not bankrupt, you do not propagate distress

This produce an underestimation of the risk in the financial system

A relative loss of equity h_i(t) of the borrower implies an equal relative devaluation of interbank asset of the lender

loss of equity is h_i(t)=[E_i(0)-E_i(t)]/E_i(0)

A_ij(t+1)/A_ij(t)=E_j(t)/E_j(t-1)

Debtrank

DEBTRANK HAS BEEN USED FOR STRESS TEST

We can distinguish between different banks

We go beyond too big to fail procedure

European Central Bank

What do we learn?

network effect are of the same order of initial shocks

Debtrank

Back to Statistical Physics

We want to be able to consider Graphs as Thermodynamical systems and be able to exchange time average with

ensemble average

Exponential Random Graphs

The assumption of taking as relevant the configuration G with the largest probability

P(G) means to maximise the entropy S

The entropy must be maximised by taking into account the constraints,

corresponding to find the maximum of the functional

That is

Jaynes E.T., Physical Review 106, 620-630 (1957)

Wasserman S., Faust K., Social Network Analysis CUP (1994)

Bollobás, B. Modern graph theory, Springer (1998)

This is known as exponential random graph formalism

Exponential Random Graphs

all graphs are equiprobable, this is the Random Graphs model

if the only constraint is on normalization

Back to Statistical Physics

by knowing just a portion we can reconstruct what is missing

By maximising entropy and by taking into account max likelyhood we recover fitness model

The fitness of the node is the vertex probability

i,j —-> x_i, x_j

Bianconi, G., Barabási, A-L Europhysics Letters 54 436–442 (2001)

K.-I. Goh, B. Kahng, and D. Kim, Phys. Rev. Lett. 87, 278701 (2001);

Caldarelli, G., Capocci, A., De Los Rios, P. Munoz, M-A Phys. Rev. Lett. 89, 258702 (2002).

Conclusions

Complex Systems deal with phenomena of many constituents interactingwith each other and

creating an emergent behaviour often not represented by average quantities.

We need a new way to look at problems

​

We need also some new technique to address the problems (networks)

​

Applications range from social to technological systems