Complex Networks Lecture 1: Basic Concepts
EE 6605
Instructor: G Ron Chen
Most pictures on this ppt were taken from un-copyrighted websites on the web with thanks
Some Background and Motivation
Between two randomly selected persons in the world, how many friends are there connecting them together?
When searching from one webpage to another through the World Wide Web (WWW), how many clicks are needed on average?
Where to locate data centres on the Internet to be more efficient and effective for data traffic?
How could computer viruses propagate so fast and so wide through the Internet?
Why were people being infected so easily by diseases such as COVID-19, SARS and Flu, all over the world?
How did rumors spread out in human societies?
How did electric power blackout emerge from a small
local system failure through the huge power grid?
How did financial crisis spread out over the world?
We are living in a networked world today
The influence of various complex and dynamical networks is currently pervading all kinds of sciences, ranging from physical to biological, even to social sciences. Its impact on modern engineering and technology is prominent and will be far-reaching.
On the one hand, networks bring us with benefits and convenience, improve our efficiency of work and quality of life, and create tremendous opportunities that we never had before.
On the other hand, however, networks also generate harms and damages to humans and societies, typically through epidemic spreading, computer virus propagation, power blackout, and the like.
Development of network science studies
For a long time in the history, studies of communication networks, power networks, transportation networks, biological networks, economic networks, social networks, etc., were carried out separately and independently.
Recently, there were some rethinking of the general theory of complex dynamical networks towards a better understanding of the intrinsic relations, common properties and shared features of different kinds of networks in the real world.
The new intention of studying fundamental properties and dynamical behaviors of complex networks, both qualitatively and quantitatively, is important and timely, although very challenging technically.
The current research along this line has been recognized as a whole as “network science and engineering”, and has indeed become overwhelming.
Network Complexity (I) Structural complexity:
A network appears to be complicated in structure, which are seemingly messy and disordered.
The network topology (i.e., structure) may vary in time.
The connections (i.e., edges) among systems (i.e., nodes) may be weighted, directed, time- varying, and even with noise and uncertainties.
Network Complexity (II) Node-dynamical
complexity:
A network may have
different kinds of nodes.
A node in the network can be a dynamical system, which may have complex dynamics such as bifurcating and even chaotic behaviors.
Network Complexity (III) Mutual interactions among
various complex factors:
A real-world network is affected by many internal and external factors.
The close relations between sub-networks make the already-complicated behaviors of each of them become even more complex.
Network of Networks Internet of Things
Brief History of Network Research
Leonhard Euler (1707-1783)
Viewed the problem as a graph with 4 nodes and 7 edges
From
7 to
Solvable if and only if Every node has an even degree
N
“Eulerian Graph”
Fractals
Sierpinski Triangle
Wacław Sierpińsk
(1882 – 1969)
?
Dragon Curve
More Examples of Fractals
Sierpinski Triangle (Fractal Network)
You can always start from any node, go through every edge once and once only, and finally return to the starting node, no matter how big the Sierpinski triangle is.
Four Color Problem
Q: Given any map, can the regions be colored by using at most four different colors, so that no two adjacent regions have the same color?
Terminology:
Two regions are called adjacent if they share a common boundary that is not a corner, where a corner is a point shared by more than two regions.
Convention:
All corners, and points that belong to more than two regions, are ignored. A region has to be a simply connected (i.e., contiguous).
Bizarre maps (e.g. using regions of finite area but infinite perimeter) are ignored (which may require many different colors)
Map Coloring as a Network Problem
Q: Given any map, can the regions be colored by using at most four colors, so that no two adjacent regions have the same color?
Four Color Conjecture (Theorem): Yes, four colors are sufficient
Brief History:
Heawood (1890): Five colors are sufficient (proved mathematically) Appel and Haken (1976): Four colors are sufficient (proved by
computer programming: 1200 machine hours; 10 billion decisions)
Robertson, Sanders, Seymour and Thomas (1997): Simplified the above computer-aided proof
Gonthier (2005): proved by using a general purpose theorem-proving software
Graph Theory
provides a basic tool for studying complex networks
Some inferential historical markers in network science
Year
People
Event
1736
Euler
Seven-bridge problem
1936
König
First graph theory book
1959
Erdös and Rényi
Random graph theory
1967
Milgram
Small-world experiment
1973
Granovetter
Strength of weak ties
1998
Watts and Strogatz
Small-world network model
1999
Barabási and Albert
Scale-free network model
Inter-Personal Ties
Johann Wolfgang von Goethe (歌德) (Germany, 1809) discussed the “marriage tie”
Anatol Rapoport (Russia, 1954): “the likely contacts of two individuals who are closely acquainted tend to be more overlapping than those of two arbitrarily selected individuals” (became a cornerstone of social network theory)
…
Mark Granovetter (USA, 1973): “The Strength of Weak Ties”
(1943 –)
Stanford University
(one of the most influential sociology papers, cited by > 57,600 times)
Granovetter observed that most jobs were found through “weak ties” (distant acquaintances)
80-20 Rule
Vilfredo Pareto (Italy, 1906): Observed that about 80% of the land in Italy was owned by about 20% of the population
He then carried out some surveys on a number of other countries and found that all the distributions are quite similar
He further observed that 20% of the pea pods contained 80% of the peas in his garden
Microsoft: By fixing the top 20% most reported bugs, 80% of the errors and crashes would be eliminated
Business: Roughly 80% of profits come from 20% of buyers; 80% of complaints come from 20% of customers; 80% of sales come from 20% of products; 80% of the sales come from 20% of the clients, …
1992 United Nations Development Program Report:
The richest 20% of population control 82.7% of the world’s global income
According to a report in the 2012 BBC online briefing, about 83% of the population could properly be classified as lurkers, while 17% of the population could be classified as intense contributors
李嘉誠:
一件衣服被我穿上了，80%的人都說好看，那我一定會買;一個生意 機會被我遇上了，80%的人都說可以做，那我絕對不會去做。
我深信世界上的 2/8定律，爲什麽世界上80%是窮人，20%是富人? 因爲20%的人做了別人看不懂的事，而80%的人不會堅持正確的選擇。
Generalized 80-20 Rule and Pareto Distribution
USA 2014:
One Report
The top 1% of people own 40% of nation’s wealth The bottom 80% own only 7%
Another Report (4 December 2015)
CNBC = Consumer News and Business Channel
One More (13 December 2016)
What about China?
Top 1% Families worth as much as 1/3 of China
1% Rule (90-9-1 Rule)
1% rule (known also as 90-9-1 rule): hypothesizing that more people will lurk (沉默) than will participate in a virtual community (WeChat, Facebook, etc.)
Internet: 1% of people create content; 9% edit/modify the content; 90% only view the content without contributing anything to it
Blog: For every blog posted by 1 blogger, 9 people make some comments to follow; 99 other people only view the blog without posting comments
The first 90 percent of the code accounts for the first 10 percent of the development time. The remaining 10 percent of the code accounts for the other 90 percent of the development time.
— Tom Cargill, Bell Labs
Still yet, one more report (1% vs 90%)
Brain Science
The weight of the brain accounts for only 2% of the human body but it consumes 20% of the total energy
90% of the energy consumption (dark energy) in the brain has not been well understood
M. D. Fox, M. E. Raichle, Spontaneous fluctuations in brain activity observed with functional magnetic resonance imaging, Nature, 8: 710-711, 2007
BREAK
10 minutes
Network Topology A network is a set of nodes
interconnected via edges
Examples:
Internet: Nodes – routers Edges – optical fibers WWW: Nodes – document files Edges – hyperlinks Scientific Citation Network:
Nodes – papers Edges – citation Social Networks:
Nodes – individuals Edges – relations
An Brief Introduction to Graphs Theory
Some typical graphs:
(a) (b) (c) (d)
(a) undirected and unweighted network with same type of nodes
(b) undirected and unweighted network with different types of nodes and edges (c) undirected but weighted network with weights on both nodes and edges
(d) directed but unweighted network with same type of nodes
(e) … …
In this course: Nodes: all identical
Edges: undirected or directed, with no multi-connections and self-loops
Some Basics
Only connected(連通)graphs ae considered
graph with self-loop or multiple edges
are not allowed Convention: not allowed
When a node is removed, all its edges will also be removed
A graph of N nodes has N(N-1)/2 edges
Some Basic Concepts
Degree and Degree Distribution
Distance and Average Path Length Clustering Coefficient
Coreness
Betweenness
Assortativeness
Degree and Degree Distribution Degree ki of node i
= total number of its edges
Average Degree k over the network
1N
k Nki
i 1
The spread of node degrees over a network
is characterized by a distribution function: P(k) = probability that a randomly selected
node has exactly degree k
k k P ( k ) k0
histogram
Example:
Degree:
node1 = 3, node2 = 3, node3 = 2,
node4 = 1, node5 = 1
Average Degree:
k = (3 + 3 + 2 + 1 + 1) / 5 = 2
Degree Distribution:
01234
(probability mass function)
Example: Poisson Degree Distribution
Power-Law Degree Distribution
P(k) ~ k
ln[P(k)] ln[k] Y X
P(k) ~ k
slope
Distance and Average Path Length
Distance di,j between two nodes i and j
= the number of edges along the shortest path
connecting them
Diameter D = max{di,j}
Average path length L = average over all di,j
For many large and complex networks: small L is a small-world feature
(For example, most social networks)
Example:
A network having N = 5 nodes and 5 edges:
.
L 1 dij 1 N ( N 1) i j
d12 1 d13 1 d23 1
d34 2 Average: L = 16 / 10 = 1.6
2
Total = 16
d14 2 d24 1
d15 1 d25 2
d35 2 d45 3
Clustering Coefficient
Among all your friends, how many of them are also friends?
Clustering Coefficient
Clustering Coefficient C of a network:
How many of your friends are also friends each other?
Consider a node, i
Supposethatnodeihaski edges(soithaskineighbors)
E(i) = number of existing edges of these ki neighbors actually have T(i) = number of possible edges of these ki neighbors can have
= ki(ki 1)/2
C(i) = E(i) / T(i) — Clustering coefficient of node i
C = average over all C(i) — Clustering coefficient of the network
Usually,0
L – average path length; r – power-law exponent; C – clustering coefficient
Mostly assortative
Statistical Properties of Some Real-World Complex Networks
Mostly disassortative
Statistical Properties of Some Real-World Complex Networks
Various types
Common Features:
Small L and Small C Random-Graph Networks Small L but Large C Small-World Networks Power-Law ~ k Scale-Free Networks
Present studies of complex networks
Discovering: Trying to reveal the global statistical properties of a network and to develop measures for these properties.
Modeling: Trying to establish a mathematical model of a given network, enabling better understanding of the network statistical properties and the causes of their appearance.
Analysis: Trying to find out the basic characteristics and essential features of nodes, edges, and the whole network in a certain topology, to develop fundamental mathematical theories that can describe and predict the network dynamical behaviors.
Control: Trying to develop effective methods and techniques that can be used to modify and improve network properties and performances, suggesting new and possibly optimal network designs and utilizations, particularly in the regards of network stability, synchronizability, controllability and data-traffic management.
Applications: Trying to apply and utilize some special and fundamental properties and characteristics of complex networks to facilitate the design and applications of network-related problems, such as data-flow congestion control on the Internet and traffic control for city transportations, optimal integrated circuit design for chip fabrication, better decision-making of policy and strategy for commercial trading and financial management, etc.
End