What is a Complex Network? A New Approach to Deciphering Complex Relationships
A complex network will be a network with a very complex structure, in which a large number of elements are interconnected with each other. Such networks are composed of nonlinear interactions that cannot be explained by simple regularities alone, and are characterized by scale-free, small-world, and hierarchical properties. Scale-free property indicates that some nodes have a very large number of links while many other nodes have only a few links, and small-world property indicates that many nodes can be reached in a short distance.
The study of complex networks helps to understand phenomena in which many elements interact with each other, and methods such as graph theory, statistical mechanics, information theory, and network science are used to analyze complex networks and applied to fields such as social networks, physics, biology, and information science.
In this issue, we present reading notes from “What is a Complex Network? A New Approach to Reading Complex Relationships,” an introductory book on such complex network techniques.
Preface
Chapter 1: The Beginning of Networks: The Birth of Graph Theory
1.1 Königsberg, the City of Bridges
Euler the Great Mathematician
The Beginnings of Graph Theory
After graph theory
1.2 Harary, the father of graph theory
The genesis of modern graphs
Strengths and Weaknesses of Graph Theory
1.3 Networks are Complex
Understanding Small Networks
The Concept of Network Science
Chapter 2: Lattice Patterns in Networks: The Grid and Its Companions
2.1 Tree Graphs
Cury tree
Bete lattice
Tree
2-2 Grids in a grid
square lattice
crystal lattice
Various lattices
hexagonal lattice
Triangular grid
Kagome Lattice
2-3 Games and Grids
Board Games and Grids
Diamond game
Computer Games and Grids
2-4 Reality and lattices
A square lattice has no shortcut
Chapter 3 Distance in Networks: Bacon and Erdesh Numbers
3-1 Bacon and Erdesh
Bacon number
Arriving at a coactor
Erdesh number
Sum of co-authorship of a paper
3-2 The Baseball Oracle
Network of baseballs
Distance of network
Average vertex distance of the network
Minimum distance between vertices at all vertices
Average of the distances of all vertex pairs
There are 7 vertices and 21 vertex pairs
1 x 10/20 + 2 x 9/21 + 3 x 2/21 =34/21
In a square lattice, the average distance is too large to be realistic
In realistic cases, the average distance will be small
Trees have a small enough average distance
3-3 Random Graphs
The Tree Challenge
There is only one way to get from one vertex to another
Random network
With randomness
Place a branch between each two points (n(n-1)/2) with probability p, but not with probability 1-p
When p is small, the network is fragmented, but when p is large, all points are connected.
Average distance is small
Far from reality
Network Comparison
Chapter 4: The World is Small! Small World
4-1 Small World Experiment
It’s a Small World
Distance between people
Milgram’s Small World Experiment
Experiment with letters
Difficulties with Milgram’s experiment
Not many letters actually arrived
Watts’ Small World Experiment
Experiment on the Web (email)
Message of the Small World Experiment
Shortcuts exist that connect people to each other
People’s curiosity is a motivation
4-2 Socializing on the inside
Watts and Stroganoff
Focus on clustered nature
Common friends
Clustered nature
Relatively small number of people and close relationships
Measuring clusteredness
The elementary unit of a cluster is a triangle
Size of clusteredness (cluster coefficient)
Don’t use too many branches
Cluster coefficient 1
Order is too large
4-3 Small World Nature
Small World Revisited
Square lattices can be viewed as clusters when transformed
Network Comparison
4-4 Small World Network
Watts and Strogatz ideas.
Introducing Shortcuts
Adding a few shortcuts dramatically reduces the average distance of the network
Clustering remains the same
Small average distance + high clustering = small world
One-dimensional lattice
Start with a one-dimensional lattice and generate a Watts-Strogatz model
How to create a small-world network
Randomly cut and add branches (reconnect branches)
4-5 Banquet game
Yamanote Line Game
One-dimensional lattice with no shortcuts
Large average distance
Few surprises
Dobin Chagon Hage Chabin game
Network Representation
Shortcuts bring stimulation
Mitsuo Senda Game
Shortcuts everywhere
4-6 Backgammon and Life
Old time backgammon
Abstraction
Backgammon as a Random Graph
Backgammon is a directed graph
Make the average distance small (Example 4)
Backgammon like a one-dimensional grid
Traditional board game
Chapter 5: The World is Unequal! Scale Free
5.1 The Beki Rule
Barabash
Focus on irregularities and clutter in the network
Variation in the degree of vertices
Degree distribution follows the Bechi rule
What is the Beki rule?
1/k to the power of γ
Beki rule and exponential rule
As K increases, both values decrease, but the exponential rule is by far the largest decrease.
Pareto’s law
Example of a distribution becoming a Beki work
5-2 Scale-Free Networks
Bechy rule for networks
Order distribution becomes Beki rule
Scale-free nature
Beki rule for order
No characteristic scale (free)
Characteristic scale
Mean and variance in bell-shaped distribution
Real World Examples
Random networks and small-world networks where the order follows a bell-shaped or exponential rule
How Networks Work
Internet Networks
A growing network
Networks in which only the branches change
Unchanging (static) network
BA (Barabashi-Albert) Model
Growing Network
Recreational Selection
Growth and preferential waterfall selection
New vertices are created
Vertices enter with branches
Branch connections are randomly assigned by “preferential selection
Preferential Selection
The vertex with the highest degree among the previously existing vertices is given priority to receive the new branch.
Growth Behavior
Generalized Random Graphs
Tree-like scale-free networks
How to create a generalized random graph
Vertex placement rules
Computer directory structure
Also known as:Gordon-Watson tree
Configuration model
Preconfigured model (order distribution)
Structured free scalability
5-3 Hubs
What is a hub?
A vertex with a very large degree
Scale-free networks have hubs, while networks with bell-shaped or exponential degree do not have hubs.
Small-world networks do not have hubs
Scale-free is not everything.
The combination of small average distance and high clustering (small world) is what most real-world networks have
Free-scaling is not universal.
Network Comparison
5-4 Order Correlation
Variation in order
Positive correlation
Hubs are easily associated with hubs
Example
Friendships
Collaborative business relationships
Negative correlation
Hubs and hubs are difficult to connect
Example
Internet
WWW
Electric circuits
Chemical reactions in proteins
Networks in the brain
Predation and prey in ecosystems
Order correlation is 0
BA model
Small world network
Random graph
5-5 Community
Human community
Decide from community networks
Networking Community
Example of analysis of a network community
Chapter 6 Protecting Against Infectious Diseases: Infection Routes and Vaccination
6-1 Fighting Human Infectious Diseases
What is Infectious Disease?
6-2 Conventional Models of Infectious Disease
SIR model ignoring the network
Healthy S-group
I group of sick people
R-group who were sick but recovered and became immune
Square lattice SIR model
Bond percolation
Simpler networked infection model than SIR
Bond (branch)
Some probability p determines whether a branch will pass or not
Site Percolation
Each vertex has a potential patient with probability p
If p is above a certain level, it becomes a large scale spectacle
SIS Model
A model that goes back and forth between S and I without R
6-3 Network model of infectious diseases
Small World Now
Infection on a small network
Differences in infection by model
Scale-Free Networks and Infection
Hubs and Super Spreaders
Hubs punish infections for the first time
Network Modernization and Infection Modernization
6-4 Public Health and Network Ethics
Vaccines and Immunization Policies
Hub priority policy
Technical aspects of hub priority
Chapter 7 Communication Networks – Internet and Mobile Phones
7.1 Computer Viruses
Infections on the Internet
The Internet is a typical free-scale network
It also has small-world characteristics
The critical probability is small, and the spread of viruses is likely to occur
Accidental Failures and Percolation
The mix of broken computers and yesterday’s computers can be replaced by the problem of site percolation.
Centralized systems are vulnerable to failure
Decentralized networks are fault tolerant, but the average distance is longer
Scale-free networks have smaller average distances and are less concentrated in hubs
Robustness of Free-Scale Networks
Intentional attacks and percolation
Free-scale networks are weak against intentional attacks
7.2 Wireless and Cellular
Advances in Mobile Phones
Mobile Phone Networks
Mobile Phone = Relay Station
7.3 Mixi
Social Networking Service
Mixi
Mixi is a small world
Mixi is scale-free
Versatility of Network Science
Chapter 8 Supporting Life: Neurons and Proteins
8.1 Neural Networks
Neuron
Computation on a neuron
Chemical synapses, a way of connecting
Gap Junction, a way to connect
Chemical synapses, where the axon is like a thin thread covered with a sheath, so it can pass through other cells and contact distant ones.
Chemical synapses are shortcuts in the network.
Gap junction interactions do not allow signals to flow freely from one side to the other
They work to close the gap between the internal states of two neighboring neurons.
Chapter 9: Surviving Business: The Society of Masterminds and Elites
Appendix: Drawing a Network
References
コメント