Sadrˇ
zaj
Kontekst
Osobine simplicijalnih kompleksa
Simplicijalni kompleksi iz kompleksnih mreˇ
za
Rezultati
Simplicijalni kompleksi kao kompleksni sistemi
Slobodan Maleti´c, Milan Rajkovi´c
Institut za nuklearne nauke ”Vinˇ
ca”
Univerzitet u Beogradu
TINKOS2013
Septembar, 2013
Slobodan Maleti´
c, Milan Rajkovi´
c
Simplicijalni kompleksi kao kompleksni sistemi
Zakljuˇ
cci
Sadrˇ
zaj
Kontekst
Osobine simplicijalnih kompleksa
Simplicijalni kompleksi iz kompleksnih mreˇ
za
1
Kontekst
Kompleksni sistemi
Zaˇsto simplicijalni kompleksi?
Primeri simpleksa
2
Osobine simplicijalnih kompleksa
Definicija simplicijalnog kompleksa
Karakterizacija simplicijalnih kompleksa
3
Simplicijalni kompleksi iz kompleksnih mreˇza
Klika kompleks
Kompleks susedstva
Simplicijalne zajednice
4
Rezultati
5
Zakljuˇcci
Slobodan Maleti´
c, Milan Rajkovi´
c
Rezultati
Simplicijalni kompleksi kao kompleksni sistemi
Zakljuˇ
cci
Sadrˇ
zaj
Kontekst
Osobine simplicijalnih kompleksa
Simplicijalni kompleksi iz kompleksnih mreˇ
za
Rezultati
Zakljuˇ
cci
Kompleksni sistemi
Nepostojanje jedinstvene definicije kompleksnog sistema
Osnovne osobine kompleksnih sistema (koje sluˇze kao polazna
osnova za istraˇzivanje predstavljeno u radu):
1
2
3
organizovana kompleksnost
kvalitativne osobine grupe elemenata su drugaˇcije od
kvalitativnih osobina svakog elementa posebno
unutraˇsnja hijerarhijska organizacija
Kompleksne mreˇze su veliki podskup kompleksnih sistema
→ zadovoljavaju osnovne osobine
Iznalaˇzenje adekvatnog matematiˇckog aparata za opis i
karakterizaciju kompleksnih mreˇza
Slobodan Maleti´
c, Milan Rajkovi´
c
Simplicijalni kompleksi kao kompleksni sistemi
Sadrˇ
zaj
Kontekst
Osobine simplicijalnih kompleksa
Simplicijalni kompleksi iz kompleksnih mreˇ
za
Rezultati
Zaˇsto simplicijalni kompleksi?
Neophodnost deskripcije (pod)struktura viˇseg reda u
kompleksnim sistemima
Da bi se detektovale kvalitativne osobine strukture mreˇze
Teorija mreˇza nema dovoljno fleksibilnosti za predstavljanje
agregacija viˇseg reda, gde nekoliko agenata interaguju kao
grupa, pre nego kao kolekcija parova
Simplicijalni kompleksi su kombinatorne verzije topoloˇskih
prostora koji se mogu analizirati kombinatornim, topoloˇskim i
algebarskim metodama ...
kombinatorna algebarska topologija
Slobodan Maleti´
c, Milan Rajkovi´
c
Simplicijalni kompleksi kao kompleksni sistemi
Zakljuˇ
cci
Sadrˇ
zaj
Kontekst
Osobine simplicijalnih kompleksa
Simplicijalni kompleksi iz kompleksnih mreˇ
za
Rezultati
Primeri simpleksa
Intuitivni nagoveˇstaj 1: kapu´cino
šećer
mleko
mlevena
kafa
voda
kapu´cino 6= mlevena kafa + voda + mleko + ˇse´cer
nije samo kolekcija delova
Slobodan Maleti´
c, Milan Rajkovi´
c
Simplicijalni kompleksi kao kompleksni sistemi
Zakljuˇ
cci
Sadrˇ
zaj
Kontekst
Osobine simplicijalnih kompleksa
Simplicijalni kompleksi iz kompleksnih mreˇ
za
Rezultati
Primeri simpleksa
Intuitivni nagoveˇstaj 2: pet osoba se nalaze na sastanku
Sluˇ
caj 1: svaka osoba moˇze da ˇsapne na uvo drugoj osobi
→ 5-klika
Sluˇ
caj 2: svaka osoba moˇze da ˇcuje svaku drugu osobu
→ pentaedar
Slobodan Maleti´
c, Milan Rajkovi´
c
Simplicijalni kompleksi kao kompleksni sistemi
Zakljuˇ
cci
Sadrˇ
zaj
Kontekst
Osobine simplicijalnih kompleksa
Simplicijalni kompleksi iz kompleksnih mreˇ
za
Rezultati
Primeri simpleksa
Intuitivni nagoveˇstaj 3: bliski prijatelji
zelena osoba ima ˇ
cetiri bliska prijatelja
Slobodan Maleti´
c, Milan Rajkovi´
c
→
tetraedar
Simplicijalni kompleksi kao kompleksni sistemi
Zakljuˇ
cci
Sadrˇ
zaj
Kontekst
Osobine simplicijalnih kompleksa
Simplicijalni kompleksi iz kompleksnih mreˇ
za
Rezultati
Definicija simplicijalnog kompleksa
q-dimenzionalni simpleks ili q-simpleks je (ne)uredeni
skup
ˇcvorova:
σq = hv1 , v2 , ..., vq , vq+1 i
na primer: ˇcvor, ivica, trougao, tetraedar, itd
0-simplex
1-simplex
2-simplex
3-simplex
Slobodan Maleti´
c, Milan Rajkovi´
c
Simplicijalni kompleksi kao kompleksni sistemi
Zakljuˇ
cci
Sadrˇ
zaj
Kontekst
Osobine simplicijalnih kompleksa
Simplicijalni kompleksi iz kompleksnih mreˇ
za
Rezultati
Zakljuˇ
cci
Definicija simplicijalnog kompleksa
p-lice q-simpleksa σq je svaki podsimpleks od σq definisan sa p + 1
ˇcvorom
na primer: 3-lica od σ4 (a) su tetraedri, 2-lica od σ4 (a) su trouglovi, itd
Definition
Simplicijalni kompleks je skup svih simpleksa zajedno sa
svim njihovim licima
14
14
s(g)
5
5
13
s(g)
5
13
11
11
s(b)
s(a)
4
6
3
3
6
12
s(c)
8
1
2
2
2
s(d)
s(f)
7
Slobodan Maleti´
c, Milan Rajkovi´
c
s(b)
s(a)
8
s(e)
7
12
10
8
6
s(c)
3
4
s(f)
s(e)
9
9
10
8
1
2
s(d)
7
Simplicijalni kompleksi kao kompleksni sistemi
9
Sadrˇ
zaj
Kontekst
Osobine simplicijalnih kompleksa
Simplicijalni kompleksi iz kompleksnih mreˇ
za
Rezultati
Definicija konjugovanog kompleksa
Menjanjem uloga simpleksima i ˇcvorovima dobijamo dualni
kompleks poˇcetnog simplicijalnog kompleksa: konjugovani
kompleks
b
s(6)
s(3), s(5)
s(10)
c
s(8)
s(2)
a
s(1), s(4)
s(9)
e
d
f
s(7)
g
s(11), s(12)
s(13), s(14)
Slobodan Maleti´
c, Milan Rajkovi´
c
Simplicijalni kompleksi kao kompleksni sistemi
Zakljuˇ
cci
Sadrˇ
zaj
Kontekst
Osobine simplicijalnih kompleksa
Simplicijalni kompleksi iz kompleksnih mreˇ
za
Rezultati
Karakterizacija simplicijalnih kompleksa
q-povezanost
(a)
(b)
Slobodan Maleti´
c, Milan Rajkovi´
c
Simplicijalni kompleksi kao kompleksni sistemi
Zakljuˇ
cci
Sadrˇ
zaj
Kontekst
Osobine simplicijalnih kompleksa
Simplicijalni kompleksi iz kompleksnih mreˇ
za
Rezultati
Zakljuˇ
cci
Strukturni vektor
q=4
- simpleksa
q-povezanost izmedu
indukuje relaciju ekvivalencije
q=3
→ generiˇse particiju simplicijalnog
kompleksa na klase q-povezanosti
Broj razliˇcitih q-povezanih klasa je
zapisan u q-tom mestu u
q=2
Q-vektoru (ili strukturnom
vektoru)
q=1
q=0
Slobodan Maleti´
c, Milan Rajkovi´
c
Simplicijalni kompleksi kao kompleksni sistemi
Sadrˇ
zaj
Kontekst
Osobine simplicijalnih kompleksa
Simplicijalni kompleksi iz kompleksnih mreˇ
za
Rezultati
Zakljuˇ
cci
Kombinatorni Laplasijan
q-ti kombinatorni laplasijan Lq je generalizacija laplasijana grafa na
viˇse-dimenzionalne strukture (simplekse) koje su ugradene
u
kompleksnu mreˇzu
0-dimenzionalni kombinatorni laplasijan ↔ laplasijan grafa
multiplicitet svojstvenih vrednosti jednakih nuli q − tog
kombinatornog laplasijana jednak je broju q-dimenzionalnih rupa u
simplicijalnom kompleksu
Slobodan Maleti´
c, Milan Rajkovi´
c
Simplicijalni kompleksi kao kompleksni sistemi
Sadrˇ
zaj
Kontekst
Osobine simplicijalnih kompleksa
Simplicijalni kompleksi iz kompleksnih mreˇ
za
Rezultati
Zakljuˇ
cci
Od kompleksnih mreˇza do simplicijalnih kompleksa i
simplicijalnih zajednica
Graf ↔ Klika kompleks
ˇ
Cvorovi
klika kompleksa su node osnovnog grafa, a simpleksi su sve
maksimalne klike (zajedno sa svim njihovim podklikama)
Slobodan Maleti´
c, Milan Rajkovi´
c
Simplicijalni kompleksi kao kompleksni sistemi
Sadrˇ
zaj
Kontekst
Osobine simplicijalnih kompleksa
Simplicijalni kompleksi iz kompleksnih mreˇ
za
Rezultati
Zakljuˇ
cci
Od kompleksnih mreˇza do simplicijalnih kompleksa i
simplicijalnih zajednica
Graf ↔ Kompleks susedstva
ˇ
Cvorovi
su node osnovnog grafa G i svakoj nodi iz G odgovara
simpleks koji sadrˇzi sve njene susede
6
9
6
2
5
4
7
8
7
1
1
4
8
3
2
5
3
deg
Slobodan Maleti´
c, Milan Rajkovi´
c
=dim
+1
Simplicijalni kompleksi kao kompleksni sistemi
9
Sadrˇ
zaj
Kontekst
Osobine simplicijalnih kompleksa
Simplicijalni kompleksi iz kompleksnih mreˇ
za
Rezultati
Od kompleksnih mreˇza do simplicijalnih kompleksa i
simplicijalnih zajednica
q-simplicijalne zajednice:
agregacije simpleksa dobijene iz kompleksne mreˇze na q-nivou
→ klase q-povezanosti
Razliˇciti naˇcini da sagradimo simplicijalni kompleks iz kompleksne
mreˇze → razliˇcite simplicijalne zajednice
U naˇsem sluˇcaju:
simplicijalne zajednice klika
simplicijalne zajednice susedstva
Slobodan Maleti´
c, Milan Rajkovi´
c
Simplicijalni kompleksi kao kompleksni sistemi
Zakljuˇ
cci
Sadrˇ
zaj
Kontekst
Osobine simplicijalnih kompleksa
Simplicijalni kompleksi iz kompleksnih mreˇ
za
Rezultati
Zakljuˇ
cci
Primeri simplicijalnih zajednica
Mreˇza mozga (node-delovi mozga,
- delova
linkovi-komunikacija izmedu
mozga): Kompleks susedstva
Mreˇza koautora
Klika kompleks
q=4
Shenorr, S
Chklovskii, D
Milo, R
Kashtan, N
22
22
q=9
16
Ziv, G
17
18
9
Alon, U
21
Sheffer, M
Milo, R
Itzkovitz, S
Ayzenshtat, I
21
2
Itzkovitz, S
12
7
15
20
2
4
10
14
5
19
7
15
20
Levitt, R
9
14
5
19
Alon, U
q=8
16
17
18
Kashtan, N
12
4
10
23
q=3
24
Shenorr, S
3
13
23
1
24
3
13
1
25
25
6
Chklovskii, D
Kashtan, N
11
26
8
Shenorr, S
6
11
26
8
Pajek
Pajek
Mangan, S
q=7
22
Alon, U
Sheffer, M
Milo, R
Ziv, G
16
Alon, U
17
18
18
9
21
Levitt, R
9
14
5
19
21
7
15
20
q=2
2
12
7
15
2
4
10
14
5
19
20
Mangan, S
Shenorr, S
16
17
Milo, R
Ayzenshtat, I
Itzkovitz, S
q=6
22
12
4
10
23
Kashtan, N
Chklovskii, D
24
3
13
1
23
24
3
13
1
25
25
6
Alon, U
8
Milo, R
Ziv, G
Sheffer, M
Ayzenshtat, I
Itzkovitz, S
Levitt, R
Slobodan Maleti´
c, Milan Rajkovi´
c
26
6
11
Pajek
8
26
11
Pajek
1-Anterior Cingulate; 2-Superior Frontal Gyrus; 3-Middle Frontal Gyrus; 4-Inferior Frontal
Gyrus; 5-Medial Frontal Gyrus; 6-Insular Cortex; 7-Parahippocampnal Gyrus; 8-Superior Temporal
Gyrus; 9-Inferior Temporal Gyrus; 10- Middle Temporal Gyrus; 11-Cingulate Gyrus; 12-Postcentral
Gyrus; 13- Precentral Gyrus; 14-Inferior Parietal Lobule; 15-Superior Parietal Lobule; 16-Precuneus;
17-Cuneus; 18-Lingual Gyrus; 19-Fusiform Gyrus; 20-Inferior Occipital Gyrus; 21-Middle Occipital
Gyrus; 22-Posterior Cingulate; 23-Unicate Fasciculus; 24-Lenticular Nucleus; 25-Thalamus; 26-Caudal
Simplicijalni kompleksi kao kompleksni sistemi
Sadrˇ
zaj
Kontekst
Osobine simplicijalnih kompleksa
Simplicijalni kompleksi iz kompleksnih mreˇ
za
Rezultati
Statistiˇcka invarijantnost
Q-vektor za Barab´
asi-Albert scale-free mreˇzu
Klika kompleks
Slobodan Maleti´
c, Milan Rajkovi´
c
Konjugovani klika kompleks i
kompleks susedstva
Simplicijalni kompleksi kao kompleksni sistemi
Zakljuˇ
cci
Sadrˇ
zaj
Kontekst
Osobine simplicijalnih kompleksa
Simplicijalni kompleksi iz kompleksnih mreˇ
za
Rezultati
Statistiˇcka invarijantnost
Mreˇza protein-proteinske interakcije u kvascu
Klika kompleks
Slobodan Maleti´
c, Milan Rajkovi´
c
Konjugovani klika kompleks i
kompleks susedstva
Simplicijalni kompleksi kao kompleksni sistemi
Zakljuˇ
cci
Sadrˇ
zaj
Kontekst
Osobine simplicijalnih kompleksa
Simplicijalni kompleksi iz kompleksnih mreˇ
za
Rezultati
Zakljuˇ
cci
Klika kompleks
Mreˇza: Zachary karate klub
Kombinatorni laplasijan
Q-vektor
40
q=4
q=4
35
4
3
30
25
3
8
s(2)
s(1)
4
f(x)
2
20
15
10
1
1
2
14
5
0
0
2
4
6
8
λ
10
12
14
16
18
10
12
14
16
18
250
q=3
q=3
200
4
8
s(1)
33
f(x)
150
34
3
s(2)
34
33
50
s(20)
1
2
100
14
9
s(31)
31
24
Slobodan Maleti´
c, Milan Rajkovi´
c
30
0
0
2
4
6
8
λ
Simplicijalni kompleksi kao kompleksni sistemi
Sadrˇ
zaj
Kontekst
Osobine simplicijalnih kompleksa
Simplicijalni kompleksi iz kompleksnih mreˇ
za
Rezultati
Zakljuˇ
cci
Klika kompleks
Mreˇza: Zachary karate klub
Q-vektor
4
q=2
20
18
8
3
s(2)
s(1)
s(3)
14
s(4)
2
1
1
1
2
2
s(5)
2
1
3
11
s(8)
s(7)
s(6)
1
1
400
q=2
4
7
Kombinatorni laplasijan
7
13
9
22
5
1
11
350
33
300
5
1
s(11)
s(10)
1
6
34
17
1
6
33
9
15
21
33
32
23
33
34
s(32)
30
34
25
24
s(34)
26
27
0
0
s(30)
33
s(31)
50
34
s(28)
33
33
16
34
s(27)
33
s(24)
100
31
34
s(25)
24
200
150
34
19
34
s(23)
s(20)
7
34
250
9
3
34
s(19)
6
s(15)
f(x)
s(9)
2
4
6
8
λ
10
12
28
34
s(35)
30
29
32
s(36)
32
33
Slobodan Maleti´
c, Milan Rajkovi´
c
Simplicijalni kompleksi kao kompleksni sistemi
14
16
18
Sadrˇ
zaj
Kontekst
Osobine simplicijalnih kompleksa
Simplicijalni kompleksi iz kompleksnih mreˇ
za
Rezultati
Zakljuˇ
cci
Klika kompleks
Mreˇza: Zachary karate klub
Q-vektor
23
q=1
Kombinatorni laplasijan
28
27
21
s(28)
s(27)
34
s(25)
s(24)
19
16
400
s(30)
s(34)
300
s(31)
s(23)
15
30
33
4
s(20)
s(36) s(35)
s(15)
s(7)
s(2)
3
8
250
29
31
f(x)
13
q=1
350
24
9
s(1) s(6)
200
150
100
32
14
50
2
1
s(3)
0
0
2
4
6
8
λ
10
12
14
16
q=0
180
20
22
160
s(16)
3
s(19)
6
7
1
10
3
34
10
s(8)
32
2
31
s(18)
28
3
29
s(17)
s(22)
s(21)
s(10)
s(11) 1
12
14
140
s(14)
s(13)
s(12)
1
17
34
34
24
11
s(33)
s(29)
5
s(32)
26
25
80
40
20
32
s(9)
100
60
s(26)
20
120
f(x)
18
18
200
s(4) s(5)
25
0
0
28
2
4
6
8
λ
10
12
26
Slobodan Maleti´
c, Milan Rajkovi´
c
Simplicijalni kompleksi kao kompleksni sistemi
14
16
18
Sadrˇ
zaj
Kontekst
Osobine simplicijalnih kompleksa
Simplicijalni kompleksi iz kompleksnih mreˇ
za
Rezultati
Zakljuˇ
cci
Zakljuˇcci
Razliˇciti simplicijalni kompleksi se mogu dobiti iz jedne mreˇze
→ mogu se detektovati razliˇciti skriveni organizacioni obrasci
koje formiraju simplicijalne zajednice unutar kompleksne mreˇze
Analiza kompleksa susedstva pokazuje oˇcuvanje statistiˇckih
osobina prilikom prelaska sa kompleksne mreˇze na
simplicijalnu reprezentaciju
Analiza klika kompleksa ukazuje na korisnost simplicijalnih
kompleksa u modelovanju kvalitativnih osobina kompleksnih
mreˇza
Spektar kombinatornog laplasijana je duboko povezan sa
osobinama povezanosti simplicijalnog kompleksa, a samim tim
i osobinama povezanosti podstruktura kompleksnih mreˇza iz
kojih se oni dobijaju
Slobodan Maleti´
c, Milan Rajkovi´
c
Simplicijalni kompleksi kao kompleksni sistemi
Sadrˇ
zaj
Kontekst
Osobine simplicijalnih kompleksa
Simplicijalni kompleksi iz kompleksnih mreˇ
za
Rezultati
Zakljuˇ
cci
S. Maleti´c, M. Rajkovi´c, D. Vasiljevi´c, Simplicial Complexes of Networks
and Their Statistical Properties, Lecture Notes in Computational Science
5102(II), 568-575, 2008
D. Horak, S. Maleti´c, M. Rajkovi´c, Persistent Homology of Complex
Networks, J. of Stat. Mech. 03, P03034, 2009
S. Maleti´c, M. Rajkovi´c, Simplicial Complex of Opinions on Scale-Free
Networks, Studies in Computational Intelligence, Springer 207, 127, 2009
S. Maleti´c, L. Stameni´c, M. Rajkovi´c, Statistical mechanics on simplicial
complexes, Atti Semin. Mat. Fis. Univ. Modena Reggio Emilia 58, 23,
2011
S. Maleti´c, D. Horak, M. Rajkovi´c, Cooperation, conflict and higher-order
structures of complex networks, Advances in Complex Systems 15,
1250055, 2012
S. Maleti´c and M. Rajkovi´c, Combinatorial Laplacian and entropy of
simplicial complexes associated with complex networks, Eur. Phys. J.
Special Topics 212, 7797, 2012
Slobodan Maleti´
c, Milan Rajkovi´
c
Simplicijalni kompleksi kao kompleksni sistemi
Sadrˇ
zaj
Kontekst
Osobine simplicijalnih kompleksa
Simplicijalni kompleksi iz kompleksnih mreˇ
za
Rezultati
Hvala
Slobodan Maleti´
c, Milan Rajkovi´
c
Simplicijalni kompleksi kao kompleksni sistemi
Zakljuˇ
cci
Download

Simplicijalni kompleksi kao kompleksni sistemi