In [ ]:
%%HTML
<style>
.output_png {
display: table-cell;
text-align: center;
vertical-align: middle;
}
body:after {
background-image: url('lincs.png');
background-size: 200px 100px;
position: fixed;
bottom: 1em;
right: 8em;
width: 200px;
height: 100px;
content:"";
}
</style>
In [ ]:
%pylab inline
xkcd()
rcParams['figure.facecolor'] = (0,0,0,0)
Planet Earth has never been as *tiny* as it is now. It shrunk - relatively speaking of course - due to the quickening pulse of both physical and verbal communication. This topic has come up before, but we had never framed it quite this way. We never talked about the fact that anyone on Earth, at my or anyone's will, can now learn in just a few minutes what I think or do, and what I want or what I would like to do. If I wanted to convince myself of the above fact: in couple of days I could be - *Hocus pocus!* - where I want to be.
One of us suggested performing the following experiment to prove that the population of the Earth is closer together now than they have ever been before. We should select any person from the 1.5 billion inhabitants of the Earth - anyone, anywhere at all. He bet us that, using no more than five individuals, one of whom is a personal acquaintance, he could contact the selected individual using nothing except the network of personal acquaintances.
In [ ]:
%%HTML
<iframe width="560" height="315" src="https://www.dailymotion.com/embed/video/xak9gu" frameborder="0" allowfullscreen></iframe>'
In [ ]:
fig = figure(figsize=(7.0,5))
ax = axes()
ax.patch.set_alpha(0)
n = arange(12)
c = [0, 2, 3, 8, 14, 8, 16, 6, 2, 2, 3, 0]
plot(n, c, "k-o")
title("Travers & Milgram, 1969")
xlabel("Number of Intermediaries")
ylabel("Number of Chains")
ylim([0, 20])
show()
I read somewhere that everybody on this planet is separated by only six other people. Six degrees of separation between us and everyone else on this planet. The President of the United States, a gondolier in Venice, just fill in the names. I find it
- extremely comforting that we're so close
- like Chinese water torture that we're so close because you have to find the right six people to make the right connection
Rule: find People with low (finite) sum of
Surprising results
End of 90's, Watts & Strogatz revived small-world studies
We hope that our work will stimulate further studies of small-world networks (...). Although small-world architecture has not received much attention, we suggest that it will probably turn out to be widespread in biological, social and made-made systems, often with important dynamical consequences.
Graphs representing social interactions (local choices)
Graphs from real networks (biology, infrastructures, CS)
Graphs with properties that have been observed in most social networks (and in some real-world graphs)
All graphs are not small-worlds
Six properties characterize small-worlds:
Degree distribution is Heavy-Tail:
Six properties characterize small-worlds:
Clustering coefficient: probability of triangles in the graph
Six properties characterize small-worlds:
Not all are required to qualify as a small-world:
Remark: Average degree is $ D=\sum_{d\geq 1} dP(d) $
(Will be detailed in the Power Law course.)
In [ ]:
%reload_ext tikzmagic
In [ ]:
%%tikz -l calc --scale 4 --size 1000,500
\tikzset{every node/.style={scale=4}}
\foreach \an in {0,...,19}
{
\draw let
\n1={int(mod(\an+1,20))},
\n2={int(mod(\an+2,20))}
in
(18*\an:2) node[circle, fill, scale = .6]{}
edge (18*\n1:2)
edge[bend left = 60] (18*\n2:2);
\pgfmathtruncatemacro{\nun}{ifthenelse(mod(\an+2,9),int(mod(\an+1,20)),int(mod(\an+8,20)))}%
\pgfmathtruncatemacro{\ndeux}{ifthenelse(mod(\an,13),int(mod(\an+2,20)),int(mod(\an+5,20)))}%
\draw
(5,0) +(18*\an:2) node[circle, fill, scale = .6]{}
edge +(18*\nun:2)
edge[bend left = 60] +(18*\ndeux:2);
\draw let
\n1={int(mod(\an * \an,20))},
\n2={int(mod(\an * \an * \an,20))}
in
(10,0) +(18*\an:2) node[circle, fill, scale = .6]{}
edge +(18*\n1:2)
edge[bend left = 10] +(18*\n2:2);
}
\draw (0,2.5) node {Regular}
++(5,0) node {Small-World?}
++(5,0) node {Random};
\node (p1) at (0,-2.5) {$ p = 0 $};
\node (p2) at (10,-2.5) {$ p = 1 $};
\draw (p1) edge[->,>=latex,thick] node[below] {Chaos} (p2);
We hope that our work will stimulate further studies of small-world networks (\ldots). Although small-world architecture has not received much attention, we suggest that it will probably turn out to be widespread in biological, social and made-made systems, often with important dynamical consequences.
In [ ]:
%%tikz -l calc,arrows,positioning --scale 4 --size 300,300
\tikzset{every node/.style={scale=4, thick}}
\foreach \x in {0,...,5}
\foreach \y in {0,...,5}
{\pgfmathtruncatemacro{\label}{\x - 5 * \y +21}
\node [draw, circle, fill, black] (\x\y) at (1.5*\x,1.5*\y) {};}%{\label};}
\foreach \x in {0,...,5}
\foreach \y [count=\yi] in {0,...,4}
\draw (\x\y) edge[<->, line width=2mm] (\x\yi) (\y\x) edge[<->, line width=2mm] (\yi\x) ;
\node [draw, fill, circle, blue] (s) at (32) {};
\draw[->, thick, line width=2mm, blue] (s) edge (31)
edge (33) edge (22) edge (42) edge[bend right] (04);
In [ ]:
xl = linspace(0,2,100)
xh = linspace(2, 4, 100)
figure(1)
clf()
ax = axes()
ax.patch.set_alpha(0)
plot(xl, (2-xl)/3, 'b')
plot(xh, (2-xh)/(1-xh), 'b')
xlabel('$r$')
ylabel('$\\alpha$')
ylim([0,1 ])
show()
In [ ]:
xl = linspace(0,2,100)
xh = linspace(2, 4, 100)
figure(1)
clf()
ax = axes()
ax.patch.set_alpha(0)
plot(xl, (2-xl)/3, 'b')
plot(xh, (2-xh)/(1-xh), 'b')
xlabel('$r$')
ylabel('$\\alpha$')
ylim([0,1 ])
show()
$\rightarrow$ Most social networks are small-worlds, but most small-world simple models only focus on specific properties.