01HFVQW Networked Control Systems

Master Program Mechatronic Engineering

Lecture 6. Complex Graphs and Network Science

Graphs in Our Lectures vs. Real-World Graphs

• Many graphs around us are giant (millions/billions of nodes)

• The structures of edges are very entangled

• The graphs evolve: nodes add and leave, connections are established and lost

• Graph is a central part of a system, called network (some objects or life beings = nodes,
relationship = edges, processes in the system depend on the graph)

• Examples include but are not limited to: Internet, social networks and communities, trade
networks, financial networks etc.

• Just several pictures to show you how big and beautiful the graphs are!!!
Real-world Graphs (1): Criminal Networks

From Dutch police reports 2008-2011: a criminal network

Light (green/yellow) nodes – cannabis cultivators and sellers.

[At that time, c. was illegal]

Dark – criminal “macro-network” (all persons connected through

some criminal activities)

P.A. Duijn et al., The Relative Ineffectiveness of Criminal Network Disruption, Scientific Reports 4, p. 4238, 2014
Real-world Graphs (2): Transportation Networks

Major airports in the globe and their connections.

The data was obtained from the International Air Transportation
Association (IATA).
• Each node represents an airport, and
• Each edge is a regular flight between two airports.

Colors and closeness to the center – numbers of connections

[Link]
Real-world Graphs (3): World Wide Web (WWW)

Hyperlink Graph for a segment of WWW

Nodes = web pages (more than 3bln)

Edges = hyperlinks (128bln)

Such graphs are used in search engines, SPAM detectors etc.

[Link]
Naïve Questions

• Can we say anything general about structures of networks?

• Can we say anything about the laws governing their growth and restructuring?

• Can we at least compare two different graphs and say if they are similar or not?

• Can we generate on a computer some network whose structure is similar (in one way
or another) to real-world huge graphs? [Desirable for testing various networked
models – opinion formation, epidemic spread, fake news propagation… You may want
to do this in your project]

These questions may seem hopeless, but fortunately graphs are not the first complex
system scientists meet. A lot of tools to “tame” complexity exist in physics!
Parallels with [Statistical] Physics and Thermodynamics

• Describing matter on the molecular level seems rather hopeless.

• Macroscopic (statistical) characteristics allow to compare different systems or different
phases of same system (e.g., solid, liquid, gas).
• Examples: volume, shape, temperature, pressure, distribution of kinetic energies, entropies

• To compare different graphs and understand dynamics of a graph, some macroscopic

characteristics can be used. Inspiration from physics!
The advent of Network Science (2000s)
• The world around us is very connected and linked.
• People, companies, infrastructures create complicated networks.

• Many networks are often found in the nature, they exist on all levels of matter (atomic
ensembles, fungal mycelium, neural tissue, animal and social groups, ecosystem)

• Connected world creates many opportunities: travel, friendship, information exchange…

• But networked structure makes the society vulnerable: DDos attacks, epidemics and malware
spread, fake news and extremism in social networks etc.

• Huge interest of security services and the militaries in networks, also, because of the network-
centric war concept (1990s). Special research had been ordered by US Army to US National
Academy of Sciences, that defined the scope of the Network Science:

National Research Council. 2005. Network Science. Washington, DC: The National
Academies Press. Downloadable from [Link]
Good Introductions to Network Science

Nice introduction to random graphs Here: useful chapter 21 on epidemics

Many other useful applications
Attempts to Define the Network Science
• Applications: Biology (metabolic, regulatory, genetic networks, neural networks, and ecological networks
like), Social and Economic Studies (social interactions, financial systems, economic alliances),
Infrastructures (communication networks, power grids, supply chains, connected vehicles etc.)

• Structural properties: Degree of connectivity (average degree), degree distribution, clustering coefficients
(density of communities), shortest path. Three major classes of large-scale networks: almost regular graphs
(degrees are equal or slightly vary – crystals, lattices etc.), totally random graphs (Erdős–Rényi models) –
Poisson distribution of degrees, neither regular nor random graphs with the scale-free distribution of degrees.

• What processes and mechanisms give rise to the network characteristics? Can we generate
networks with structural characteristics that mimic the properties of selected real networks? Various models of
random graphs. Help to test the relations between desired structural characteristics and behaviours of
networks. Say, how does the distribution of degrees influence epidemics spread of a network?

• Dynamics of and over a network, functions of networks, resilience to attacks and errors etc.

National Research Council. 2005. Network Science. Washington, DC: The National
Academies Press. Appendix C: Content of Network Science Courses (not applies to our course!)
Reminder from introduction to Lab2: Normal Distribution

If some numerical parameter (weight, height, blood pressure, wealth etc.) characterizes an
individual or an object, then its distribution across a big population/collection will typically
be normal (Gaussian, bell-shaped). Some rigorous results about this exist in statistics.

This common law of nature does not work for many large-scale graphs!!!
Expected Value (Average) 𝝁 and the Standard Deviation 𝝈

The probability of finding the value outside the range 𝝁 − 𝟑𝝈, 𝝁 + 𝟑𝝈 is extremely
small. The density function decays very fast (faster than the exponential).

>68% of values belong in fact to 𝝁 − 𝝈, 𝝁 + 𝝈

>95% of values belong in fact to 𝝁 − 𝟐𝝈, 𝝁 + 𝟐𝝈
Key Characteristics of an Undirected Graph
• Numbers of nodes and edges. Notice the relation between edges and degrees:

• In network science, graph density is characterized by the average node degree

• Degree distribution: for each value k=0,1,2, …, find the proportion of nodes with degree k:

Regular graphs: distribution is trivial (P(k)=1 for some k, other P(j)=0).

Typical randomly generated large-scale graph: should look like a normal distribution (graph is large).

Real statistics of many graphs: P(k) decays polynomially as k is growing. Shocking discovery!
Distribution of the Degrees: Expectation vs. Reality (for many graphs)

Pathological (scale-free) distributions of degrees found in many real networks:

• Collaboration networks (e.g., actors casting in the same movie);
• WWW – graphs of hyperlikns
• Social media
• Financial networks (interbank payments)
• Biochemical networks (interaction between chemical substances – proteins, enzymes, RNA etc.)

Scale free: distribution not concentrated around the average value, depending on the size.
Key Characteristics of a Graph (continued)
Graph diameter: maximal length of the shortest path between all possible pairs of nodes.

The six degree of separation theory: all people are six or fewer social connections away from
each other. Real graph: this diameter is small indeed (graphs are irregular).

Clustering coefficients

• Among 𝑑(𝑣) neighbors, 𝑑(𝑣) [𝑑(𝑣) − 1]/2 links are possible (lead to triangles 𝑣, 𝑢, 𝑤)
• Which percentage of this exists in reality? This is measured by the clustering coefficient!

• Average clustering coefficient: the tendency of forming densely knit communities.

• Many other characteristics, e.g., sizes of connected components.

Where Network Science Starts: Non-trivial Statistical Properties

• Interesting observations (physical literature). Real big graphs are:

✓ Scale-free (polynomially decaying) distribution of the degrees;

✓ Diameter is small compared to the size of the graph (grows as log |𝑉|);

✓ Average clustering coefficient usually is not less than 0.1 (e.g., Barabasi estimates it as
0.1 for the network of scientific collaborations in Hungary), independent of the size.

✓ To create a synthetic network that has such properties is very difficult!

✓ Three most famous attempts are the ER (Erdos-Renyi), WS (small-world) and BA

(preferential attachment) models of random graphs.
Erdős–Rényi model (1)

Undirected graph with a fixed number

of nodes and random number of edges

Idea: organize an even with many people who

don’t know each other. Let people walk
around the hall and chat to each other,
establishing new connections.

With some probability, two people meet and

Paul Erdős (1913-1996) new social connection arises. Alfréd Rényi (1921 – 1970)

Assume for simplicity that the crowd is well

mixed, so this probability is same for every
two individuals. Then you get a ER graph.
Erdős–Rényi model (2)
• NEEDED: generator of independent and identically distributed (pseudo)random numbers with the
Bernoulli distribution

• In MATLAB: rand() gives you a random number uniformly sampled from [0,1]. Define
X=(rand() <= p);

• Generation of the graph: for each unordered pair {𝑖, 𝑗}, where 𝑖 = 1, … , 𝑛 − 1 and 𝑗 = 𝑖 + 1, … , 𝑛,
generate the random number 𝑿 and define the entry adjacency matrix as

• Notice: the graph is random; hence, its characteristics are also random. One can only speak about
their expected values. For brevity, we omit the word “expected” in the following properties:
❖ The average degree is 𝑑 = (𝑛 − 1)𝑝. Usually, we fix this value and consider the situation where
𝑛 is large, while 𝑝 = 𝑑/(𝑛 − 1) is small

❖ The degree distribution is not scale-free and is close to Poisson distribution

❖ For large n, looks approximately like the normal distribution
❖ The diameter is small, grows as log 𝑛
❖ Clustering coefficient goes to 0 as n grows
Watts-Strogatz model (small-world network)

Take a regular ring lattice and rewire each

edge with a given probability p.

The graph is random yet inherits many

arcs from the regular one.

Duncan T. Watts Steven Henry Strogatz

Watts-Strogatz model (2)
• NEEDED: generator of independent and identically distributed Bernoulli variables

• NEEDED: generator of independent uniformly distributed numbers 𝑆 = 1,2, … , 𝑛

• In MATLAB: randi(n) function

• For each node 𝑖 = 1, … , 𝑛 and each of the next nodes 𝑗 = 𝑖 + 1, … , 𝑖 + 𝑚 of the lattice, take arc (𝑖, 𝑗)
and generate X. If X=1, generate S and rewire (𝑖, 𝑗) to (𝑖, 𝑆). If such an arc already exists or 𝑆 = 𝑖,
regenerate S.

• Structural characteristics (expected):

❖ The average degree is 𝑑 = 2𝑚, because the number of edges remains unchanged. Here, the
probability of rewiring does not matter.
❖ The degree distribution is not scale-free, frequency decays exponentially with k
❖ The diameter is small, grows as log n
❖ Clustering coefficient is bounded from below by some constant, depending only on p
Barabasi-Albert Graphs
Model of a scale-free distribution,
with a small diameter yet
decaying clustering coefficient.

Important: growth process, nodes

do not appear simultaneously

The principle of preferential

attachment, or rich-gets-richer
(«Matthew effect, Bible verse
Albert-László Barabási Matthew 25:29») Réka Albert

Evolution (picture from the book Network

Science), a node with m=2 links added each time.
BA model (2)
• NEEDED: generator of independent non-uniformly distributed number 𝑆 = 1,2, … , 𝑁

• In MATLAB: read about datasample() function, may be, there are simpler ways.

• Start from some connected graph (e.g., complete) with 𝑚0 > 𝑚 nodes
• At each time, add one node and connect it with the existing nodes by 𝑚 links

• How do we decide to whom connect? Random choice from a predefined distribution: if the number of
nodes is 𝑁, the probability to connect with node 𝑖 is

• The more neighbors a node already has, the more attractive it will be!
• You should generate variable S several (m) times to choose m existing nodes independently. Repetitions
are not allowed: if the nodes repeat, regenerate. datasample() allows to exclude repeats.
• Structural characteristics (expected):
❖ The average degree approaches 2𝑚 (as the number of steps grows).
❖ The degree distribution is scale-free, frequency decays as
❖ The diameter is small, grows as log 𝑛
❖ Clustering coefficient goes to 0 as the graph growing.