Teorie grafů a realistické modely sítí
Obsah
I
I
I
I
I
I
Problém mostů v Königsbergu
Problémy řešené pomocí teorie grafů
I
I I
I
Definice grafu
£=E-» VxV
Grafy ve světě okolo nás
I I
I I
I I I
I
Obecné vlastnosti sítí
I
I
Vlastnost malého světa

Vysoký klastrovací koeficient

Mocninné chování rozdělení konektivit
ii
1
li M
O)
o
c
s   >
to    >
o   *»
S   0
o   ■*
O-   3
"5  =
5   "Ö
0.     (A
a x + b
Konektivita (počet hran) v logaritmické škále
Mocninné chování rozdělení konektivit
I
I I
World wide web (WWW)
iou
10"
ltr
Q.° IQ"6
10"'
10
•10
Q.
ÍO"2  10°  io2  io4  106   10"2  10°  io2  io4  io6
Internet
•
iol
10
-2
Q.
10"
10
o..........	.......1    ........1
=   o !\ O o 5                                C -	)                   i 0                           E o                 : o o
	'   '   1 'I'll          1     '    ......1
10°    101    io2    io3
Sít sexuálních kontaktů - rozdělení po 1 roce
10
10                                10
Number of partners, k
Sít sexuálních kontaktů - úplné rozdělení
-v  ^o-
tí 10"'
o
'S 10
a:
■Ž io"3
cd
rl 10      -
^55Ľ

o Females a Males
_i_____i____i___i__i i i i I_________i______i____i___i__i  i i i I_________i_____i____i___i__i__i i i
10                     10                     10'
Total number of partners, k
tot
Sít spoluautorství v různých vědních oborech
ioL
10"
CL
10
-4
10
-6
				
<>0				
i	%			E
	O			
	X			
!		o	o	;
:			ooo	:
			0	
\	........1	........1	........1	O =
-I—I I 111111------1—lili I ■ 11------1—I I I llllj
_l__.......I____I__.......I____I__.......'
10°     101     102     10310°     101     102     103
Sít spolupráce filmových herců
ioL
10
-2     _

10
~4
10"
-1—I    I  I MIH-------1----lili lili------1—I    I   I I lili
\
%
%
~6    I_____i___.......l_____i___.......I_____i___i i' ""l
10°     101     102     103
Modely sítí
Edös-Renyi model
Watts-S trogatz model
Watts-S trogatz model - konstrukce
Regular              Small-world             Random
Increasing randomness
Watts-S trogatz model - výsledky
[H-----'D'    'Ů'11^------d     '  á "  n'1-------'      ■    ■  ■  ""I-------1—i-i-r-mj
0.2 -
•
»
C{p) / C(0)      °
□
L{p) / L(0)
D
*       •       p
_i___i__i__i ■ i ' I_______i____i___i__i__i > i fn
0.0001                 0.0O1                   0.01                    0.1                       1
P
Watts-S trogatz model - výsledky
Connectivity distribution
0.1   -
0.01
0.001
10
10'
I   ..   .

□
*   +
I
X      A
a + *
X      H
5«      El
+      X
m
p=0.1       + p=0.2 p=0.3       * p=0.5      □ p=0.7 p=0.B p=0.9       • Random graph      *
10                             15
Connectivity
20
25
Barabási-Albert model
Barabási-Albert model - konstrukce
Barabási-Albert model - výsledky
Conenctivity distribution
o
a 1a
10000
1000
100
0.01
0.001
Connectivity
Závěr
I
I
I
Literatura