Hierarchikus skálafüggetlen gráfok generálása fraktálokkal

Hierarchikus skálafüggetlen gráfok generálása fraktálokkal Komjáthy Júlia Simon Károly Sztochasztika Tanszék Matematika Intézet Budapesti Műszaki és Gazdaságtudományi Egyetem www.math.bme.hu/~komyju www.math.bme.hu/~simonk

2011 November 15. Jövő Internet technológiák és alkalmazások kutatása Magyarországon

Komjáthy Júlia, Simon Károly (BME)

Skálafüggetlen gráfok és fraktálok

Jövő Internet

1 / 22

1

Motiváció

2

A kiinduló modell

3

Graph directed leírás

4

Determinisztikus eset, tulajdonságok

5

Véletlen modell



Jövő Internet

2 / 22

Motiváció

Skálafüggetlen gráfok lépten nyomon



Jövő Internet

3 / 22

Motiváció

Skálafüggetlen gráfok lépten nyomon Hierarchikus gráfok sok helyen



Jövő Internet

3 / 22

Motiváció

Skálafüggetlen gráfok lépten nyomon Hierarchikus gráfok sok helyen modellünk segítséget nyújt ilyen hálózatok tesztelésére



Jövő Internet

3 / 22

A kiinduló modell 1 0

11 10

2

12

01 00

21 02

20

22

(a) G1 és G2 hurokélekkel

111 110

112

101 100

121 102

120

122

011 010

211 012

210

001 000

021 002

020

212

201 022

200

221 202

220

222

(b) G3

ábra: G1 , G2 , G3 a "Cseresznye" példára (Barabási-Ravasz-Vicsek, [2]). Komjáthy Júlia, Simon Károly (BME)


Jövő Internet

4 / 22

Adjacencia mátrix Λ1

Λ3

Λ2

ábra: Λ1 , Λ2 , Λ3 a "Cseresznye" esetében.

111 110

112

101 100

121 102

120

122

011 010

211 012

210

001 000

021 002


020

212

201 022

200

221 202


220

222

Jövő Internet

5 / 22

Általános eset: "Legyező" példán keresztül



Jövő Internet

6 / 22


0

3

1

2

5

0

3

1

2

4

5

4

(c) G és G1 20

21

23

22

00

01

02

03

05

04

25

40

24

10

43

42

11

12

41

13

15

30

14

31

32

33

45

44

35

34

50

51

52

53

55

54

(d) G2 (hurokélek nélkül). Komjáthy Júlia, Simon Károly (BME)


Jövő Internet

6 / 22


0

3

1

2

5

0

3

1

2

4

5

4

(e) G és G1 20

21

23

22

00

01

02

03

05

04

25

40

24

10

43

42

11

12

41

13

15

30

14

31

32

33

45

44

35

34

50

51

52

53

55

54

(f) G2 (hurokélek nélkül). Komjáthy Júlia, Simon Károly (BME)


Jövő Internet

6 / 22

Általános eset: "Legyező" példán keresztül A csúcsok 0

3

1

2

5

0

3

1

2

4

5

4

(g) G és G1 20

21

23

22

00

01

02

03

05

04

25

40

24

10

43

42

11

12

41

13

15

30

14

31

32

33

45

44

35

34

50

51

52

53

55

54

(h) G2 (hurokélek nélkül). Komjáthy Júlia, Simon Károly (BME)


Jövő Internet

6 / 22


3

1

2

5

0

1

3

2

4

5

az első jegyek: országok

4

(i) G és G1 20

21

23

22

00

01

02

03

05

04

25

40

24

10

42

11

12

41

13

15

30

14

31

32

33

43

45

44

35

34

50

51

52

53

55

54

(j) G2 (hurokélek nélkül). Komjáthy Júlia, Simon Károly (BME)


Jövő Internet

6 / 22


3

1

2

5

0

3

1

2

4

5

az első jegyek: országok a második jegyek: városok

4

(k) G és G1 20

21

23

22

00

01

02

03

05

04

25

40

24

10

42

11

12

41

13

15

30

14

31

32

33

43

45

44

35

34

50

51

52

53

55

54

(l) G2 (hurokélek nélkül). Komjáthy Júlia, Simon Károly (BME)


Jövő Internet

6 / 22


3

1

2

5

0

3

1

2

4

5


4

(m) G és G1 20

21

23

22

00

01

02

03

05

04

25

Az élek 40

24

10

43

42

11

12

41

13

15

30

14

31

32

33

45

44

35

34

50

51

52

53

55

54

(n) G2 (hurokélek nélkül). Komjáthy Júlia, Simon Károly (BME)


Jövő Internet

6 / 22


3

1

2

5

0

3

1

2

4

5


4

(o) G és G1 20

21

23

22

00

01

02

03

05

04

25

Az élek 40

24

10

43

42

11

12

41

13

15

30

14

31

32

33

az első jegyek: csak testvérországba megy él

45

44

35

34

50

51

52

53

55

54

(p) G2 (hurokélek nélkül). Komjáthy Júlia, Simon Károly (BME)


Jövő Internet

6 / 22


3

1

2

5

0

3

1

2

4

5


4

(q) G és G1 20

21

23

22

25

Az élek 40

24

41

43

42


45

44

a második jegyek: csak testvérvárosba (testvérországon belül!) 00

01

02

03

05

04

10

11

12

13

15

30

14

31

32

33

35

34

50

51

52

53

55

54

(r) G2 (hurokélek nélkül). Komjáthy Júlia, Simon Károly (BME)


Jövő Internet

6 / 22


3

1

2

5

0

3

1

2

4

5


4

(s) G és G1 20

21

23

22

25

Az élek 40

24

41

43

42


45

44

a második jegyek: csak testvérvárosba (testvérországon belül!) 00

01

02

03

05

04

10

11

12

13

15

30

14

31

32

33

35

34

50

51

52

53

55

54

Következő szint (testvér)utcák is vannak

(t) G2 (hurokélek nélkül). Komjáthy Júlia, Simon Károly (BME)


Jövő Internet

6 / 22

A modell, általánosan



Jövő Internet

7 / 22

A modell, általánosan Alapgráf: páros gráf G a V = V1 csúcshalmazon.


S

V2 , V = {0, . . . , N − 1}


Jövő Internet

7 / 22


S

V2 , V = {0, . . . , N − 1}

G határozza meg az éleket



Jövő Internet

7 / 22


S

V2 , V = {0, . . . , N − 1}

G határozza meg az éleket Gn -ben N n csúcs, n hosszú kóddal: v ∈ Vn := {0, . . . , N − 1}n .



Jövő Internet

7 / 22


S

V2 , V = {0, . . . , N − 1}

G határozza meg az éleket Gn -ben N n csúcs, n hosszú kóddal: v ∈ Vn := {0, . . . , N − 1}n .

Testvér-viszonyok formálisan Két csúcs x, y ∈ Vn , kódjaik x = (x ∧ y )˜ x és y = (x ∧ y )˜ y (x, y ) ∈ E (Gn ) a.cs.a ha x˜ ∈ Vi , y˜ ∈ V¯i és (˜ xi , y˜i ) ∈ E (G )



Jövő Internet

7 / 22

Hierarchiák

Megjegyzés (Gn hierarchikus struktúrája)



Jövő Internet

8 / 22

Hierarchiák

Megjegyzés (Gn hierarchikus struktúrája) Wx jelölje azokat a (x1 . . . xn ) csúcsokat Gn -ben, akikre x1 = x (minden kezdeti x ∈ {0, . . . , N − 1} jegyre). A Wx -en feszített részgráf azonos Gn−1 -gyel.



Jövő Internet

8 / 22

Hierarchiák

Megjegyzés (Gn hierarchikus struktúrája) Wx jelölje azokat a (x1 . . . xn ) csúcsokat Gn -ben, akikre x1 = x (minden kezdeti x ∈ {0, . . . , N − 1} jegyre). A Wx -en feszített részgráf azonos Gn−1 -gyel. Ha az első n − k jegyet rögzítjük Vn -ben, akkor látjuk, hogy Gn N n−k db Gk másolatból áll.



Jövő Internet

8 / 22

Adjacencia mátrix: egy fraktál

0 First approximation of Λ12

2

4

6

1

3

5

7

A fenti alapgráf G

7 |E| = 9 és |V| = 8. Azonos színû élek 5 azonos színû négyzeteknek felelnek meg.

3

⇐ ezek a négyzetek generálják a Λ12 fraktált. Λ12 -t a Λ fraktál atomjának nevezzük

1 0 Komjáthy Júlia, Simon Károly (BME)

log 9

dimH (Λ12 ) = log 8 > 1. Skálafüggetlen gráfok és fraktálok

Jövő Internet

9 / 22


0

2

4

6

1

3

5

7

First approximation of Λ12

Second approximation of Λ12

7

5

3



Jövő Internet

9 / 22


0

2

4

6

1

3

5

7

First approximation of Λ12 ∪ Λ21

Second approximation of Λ12

7

5

3



Jövő Internet

9 / 22


0

2

4

6

1

3

5


Second approximation of Λ12 ∪ Λ21

7

7

5

5

3

3

1

1

0 Komjáthy Júlia, Simon Károly (BME)

7

0 Skálafüggetlen gráfok és fraktálok

Jövő Internet

9 / 22


0

2

4

6

1

3

5


Second approximation of Λ12 ∪ Λ21

7

7

5

5

3

3

1

1


7


Jövő Internet

9 / 22


0

2

4

6

1

3

5

7


Second approximation of Λ

7

7

5

5

3

3

1

1



Jövő Internet

9 / 22

Λn

∞ n=1

graph-directed struktúrája

A "Cseresznyére" definiáljuk az ábrán látható G gráfot. Gn minden éle megfelel egy n hosszú útnak G-ben.

¡1 ¢ 0

¡1 ¢ 1

¡0 ¢ 1


¡1 ¢

−−−−−−→ K |E|(V12)

¡2 ¢

−−−−−−→ K |N|(Vd d )

¡2 ¢

−−−−−−→ K |E|(V21)

2

¡0 ¢ 0

2

1


Jövő Internet

10 / 22

Az adjacencia mátrix: fraktálhoz tart

Minden G-beli (v1 , v2 ) él egy homotéciának (hasonlóságnak) felel meg: 1 1 fe : Qv2 → Qv1 , fe (a, b) := (a, b) + (x1 , y1 ) N N vi = (xi , yi ) ahol Qv := Q(x,y ) első szintű négyzet v = (x, y ) ∈ V (G).



Jövő Internet

11 / 22

Az adjacencia mátrix: fraktálhoz tart

Minden G-beli (v1 , v2 ) él egy homotéciának (hasonlóságnak) felel meg: 1 1 fe : Qv2 → Qv1 , fe (a, b) := (a, b) + (x1 , y1 ) N N vi = (xi , yi ) ahol Qv := Q(x,y ) első szintű négyzet v = (x, y ) ∈ V (G). Λn azokat az n. szintű négyzeteket tartalmazza, akiket az n hosszú utak kódolnak G-ben (függvénykompozícióval).



Jövő Internet

11 / 22

Az adjacencia mátrix limesze Λ Λn+1 ⊂ Λn kompakt, így


T∞

n=1 Λn

= lim Λn := Λ nemüres. n→∞


Jövő Internet

12 / 22


T∞

n=1 Λn


Két Iterált Függvényrendszer (IFS) V12 ill. V21 -en határozza meg a Λ12 ill. Λ21 attraktorokat [0, 1]n -en.



Jövő Internet

12 / 22


T∞

n=1 Λn


Két Iterált Függvényrendszer (IFS) V12 ill. V21 -en határozza meg a Λ12 ill. Λ21 attraktorokat [0, 1]n -en. Λ ezen attraktorok hasonló képeiből áll, mégpedig



Jövő Internet

12 / 22


T∞

n=1 Λn





Jövő Internet

12 / 22


T∞

n=1 Λn



Tétel Λ = Diag ∪ | {z } Λdd

[

fv (Λ12 ) ∪ fv (Λ21 ) ,

∗ v ∈Vdd

ahol Diag = {(x, x) : x ∈ [0, 1]}.



Jövő Internet

12 / 22

Tulajdonságok

0

2

4

6

1

3

5

7

Fokszámeloszlás hatványlecsengésű, a kitevő γ = 1 +

log(N/n1 ) log d

(N

a csúcsok száma, n1 a felső csúcsok száma, d a kapcsolataik száma)



Jövő Internet

13 / 22

Tulajdonságok

0

2

4

6

1

3

5

7


log(N/n1 ) log d

(N

a csúcsok száma, n1 a felső csúcsok száma, d a kapcsolataik száma) Átmérője Gn -nek arányos |Gn | logaritmusával



Jövő Internet

13 / 22

Tulajdonságok

0

2

4

6

1

3

5

7


log(N/n1 ) log d

(N

a csúcsok száma, n1 a felső csúcsok száma, d a kapcsolataik száma) Átmérője Gn -nek arányos |Gn | logaritmusával Átlagos legrövidebb út két pont közt Gn -ben szintén ∼ log(|Gn |)



Jövő Internet

13 / 22

Tulajdonságok

0

2

4

6

1

3

5

7


log(N/n1 ) log d

(N

a csúcsok száma, n1 a felső csúcsok száma, d a kapcsolataik száma) Átmérője Gn -nek arányos |Gn | logaritmusával Átlagos legrövidebb út két pont közt Gn -ben szintén ∼ log(|Gn |) Lokális klaszterezettségi együttható a csúcs fokszámával fordítottan ∼ (deg)−1 arányos. Komjáthy Júlia, Simon Károly (BME)


Jövő Internet

13 / 22

Fokszámeloszlás Feltevés Minden fenti csúcs foka azonos, és nagyobb, mint a lentieké: deg(x) := d ,

∀x ∈ V1

max deg(y ) ≤ d − 1, j∈V2


(A1)

∀y ∈ V2


Jövő Internet

14 / 22


∀x ∈ V1



(A1)

∀y ∈ V2


Jövő Internet

14 / 22


∀x ∈ V1


(A1)

∀y ∈ V2

Ekkor az alábbi hatványlecsengést kapjuk P(deg(X ) > t) = c(d ) · t

−

log(N/n1 ) log d

A hatványkitevő γ = 1 + γ˜ = 1 +


log(N/n1 ) log d


Jövő Internet

14 / 22


∀x ∈ V1


(A1)

∀y ∈ V2

Ekkor az alábbi hatványlecsengést kapjuk P(deg(X ) > t) = c(d ) · t

−

log(N/n1 ) log d

A hatványkitevő

0

γ = 1 + γ˜ = 1 +


2

4

6

1

3

5

7

log(N/n1 ) log d


Jövő Internet

14 / 22

Fraktáldimenziós kapcsolat I. Az egységnégyzetben az attraktor Λ megszámlálható db hasonló másolata Λ12 -nek. Így a fraktáldimenziója HD = dimH (Λ) =

log |E | log N .

A kapcsolat a hatványkitevő γ˜ és a HD közt: (ha HD > 1), majdnem bizotsan H (`rand ∩Λ12 ) 1 − γ˜ = dim dimH (`vert ∩Λ12 ) . számláló: Λ12 -nek véletlen szögű egyenessel vett metszete



Jövő Internet

15 / 22

Fraktáldimenziós kapcsolat I. Az egységnégyzetben az attraktor Λ megszámlálható db hasonló másolata Λ12 -nek. Így a fraktáldimenziója HD = dimH (Λ) =

log |E | log N .

A kapcsolat a hatványkitevő γ˜ és a HD közt: (ha HD > 1), majdnem bizotsan H (`rand ∩Λ12 ) 1 − γ˜ = dim dimH (`vert ∩Λ12 ) . számláló: Λ12 -nek véletlen szögű egyenessel vett metszete nevező: Λ12 -nek függőleges egyenessel vett metszete



Jövő Internet

15 / 22

Fraktáldimenziós kapcsolat II. Λ12 7

2

4

6

1

3

5

5

3

0

7 1

ábra: 1 − γ˜ = Komjáthy Júlia, Simon Károly (BME)

2

4

dimH (`rand ∩Λ12 ) dimH (`vert ∩Λ12 )


`vert

`ra

nd

0 6

, Jövő Internet

16 / 22

Átmérő, tipikus távolság

Átmérő A csúcsok kódolását felhasználva x ∈ {0, . . . N − 1}n konstruálhatunk legrövidebb utakat, amiből: Diam(Gn ) =


2 log N

log(|Gn |) + O(1).


Jövő Internet

17 / 22

Átmérő, tipikus távolság

Átmérő A csúcsok kódolását felhasználva x ∈ {0, . . . N − 1}n konstruálhatunk legrövidebb utakat, amiből: Diam(Gn ) =

2 log N

log(|Gn |) + O(1).

Átlagos legrövidebb út Két egyenletesen választott csúcs X , Y ∈ Gn közti távolság várható értéke pedig 4n1 n2 log |Gn | < E(|P(X , Y )|) < N + 4nN12n2 log |Gn |. N2



Jövő Internet

17 / 22

Lokális klaszterezettségi együttható (LCC)



Jövő Internet

18 / 22

Lokális klaszterezettségi együttható (LCC) G 3

1

1

0

5

2

b G

3

0

5

4

2

4

b1 (c) G és G 21

23

41

20

25

22

01

04

13

31

10

15

12

45

42

11 05

02

24

03

00

43

40

14

44

33

51

30

35

32

34

53

50

55

52

54

b2 , ahol G2 és G b2 élei csak a legalsó hie(d) G rarchikus szinten különböznek. Komjáthy Júlia, Simon Károly (BME)


Jövő Internet

18 / 22


1

1

0

5

2

b G

3

0

5

4

2

4

b1 (e) G és G 21

23

41

20

25

22

01

04

13

31

10

15

12

45

42

11 05

02

24

03

00

43

40

14

44

33

51

30

35

32

34

53

50

55

52

54

b2 , ahol G2 és G b2 élei csak a legalsó hie(f) G rarchikus szinten különböznek. Komjáthy Júlia, Simon Károly (BME)


Jövő Internet

18 / 22


1

1

0

5

2

b G

Tétel 3

0

K1 , K2 > 0 konstansok, hogy egy ˆn csúcs Cx tetszőleges x ∈ G LCC-jére:

5

4

2

4

b1 (g) G és G 21

23

41

20

25

22

01

03 05

04

13

31

10

15

12

45

42

11

00

02

24

14

51 35

34

≤ Cx ≤

K2 . d deg(x)

44

33

30

32

K1 d deg(x)

43

40

53

50

55

52

54

b2 , ahol G2 és G b2 élei csak a legalsó hie(h) G rarchikus szinten különböznek. Komjáthy Júlia, Simon Károly (BME)


Jövő Internet

18 / 22


1

1

0

5

2

b G

Tétel 3

0


5

4

2

4

b1 (i) G és G 21

23

41

20

25

22

01

03 05

04

13

31

10

15

12

45

42

11

00

02

24

14

51 35

34

≤ Cx ≤

K2 . d deg(x)

44

33

30

32

K1 d deg(x)

43

40

53

50

55

52

54

b2 , ahol G2 és G b2 élei csak a legalsó hie(j) G rarchikus szinten különböznek. Komjáthy Júlia, Simon Károly (BME)


Jövő Internet

18 / 22


1

1

0

5

2

b G

Tétel 3

0


5

4

2

4

b1 (k) G és G 21

23

41

20

25

22

01

03 05

04

13

31

10

15

12

45

42

11

00

02

24

14

51 35

34

53

50

55

52

54

b2 , ahol G2 és G b2 élei csak a legalsó hie(l) G rarchikus szinten különböznek. Komjáthy Júlia, Simon Károly (BME)

≤ Cx ≤

K2 . d deg(x)

¯ (G ˆn ), az átlagos LCC-je G ˆn -nek C pedig alulról-felülről korlátos, vagyis

44

33

30

32

K1 d deg(x)

43

40

2n1 n2 N2

ˆmin ≤ C ¯ (G ˆn ) ≤ C ¯ (G ˆ ), ·C

ˆmin := min Cx > 0. ahol C


ˆ x∈G

Jövő Internet

18 / 22

Véletlen modell Urnákkal, golyókkal Urnák vannak a determinisztikus modell minden v ∈ Gn csúcsában.



Jövő Internet

19 / 22

Véletlen modell Urnákkal, golyókkal Urnák vannak a determinisztikus modell minden v ∈ Gn csúcsában.



Jövő Internet

19 / 22

Véletlen modell Urnákkal, golyókkal Urnák vannak a determinisztikus modell minden v ∈ Gn csúcsában. Dobjunk le Mn + 1 db golyót függetlenül és egyenletesen az urnákba.



Jövő Internet

19 / 22

Véletlen modell Urnákkal, golyókkal Urnák vannak a determinisztikus modell minden v ∈ Gn csúcsában. Dobjunk le Mn + 1 db golyót függetlenül és egyenletesen az urnákba. A random gráfban két csúcs közt (i, j) ∈ E (Gnr ) a.cs.a. ha a csúcsoknak megfelelő i és j golyók éllel összekötött urnában landoltak (Gn -ben).

Fraktállal ekvivalens:

X (i)

Mn i=1

∼ U[0, 1] iid.

E (Gnr ) = (i, j)|Λn (X (i) , X (j) ) = 1 .



Jövő Internet

19 / 22



X (i)

Mn i=1

∼ U[0, 1] iid.

E (Gnr ) = (i, j)|Λn (X (i) , X (j) ) = 1 .



Jövő Internet

19 / 22



X (i)

Mn i=1

∼ U[0, 1] iid.

E (Gnr ) = (i, j)|Λn (X (i) , X (j) ) = 1 .



Jövő Internet

19 / 22

Fokszámeloszlás A fokszámeloszlás lecsengése most is hatványlecsengésű.

Tétel Legyen γ := 1 +

log( nN ) 1

log d

γ ∈ 1, 1 +

log 3 . log 2

Akkor a véletlen gráf fokszámeloszlásának lecsengése: P(deg(V ) > t) = t −γ+1 · L(t), ahol L(t) korlátos: n1 N ≤ L(t) ≤ . N n1 Bizonyítás Centrális Határeloszlás tétellel és Nagyeltérés Tétellel.



Jövő Internet

20 / 22

R. Albert, A.-L. Barabási, Hierarchical organization in complex networks. Rev. Mod. Phys. 74, 47 (2002).



Jövő Internet

21 / 22

R. Albert, A.-L. Barabási, Hierarchical organization in complex networks. Rev. Mod. Phys. 74, 47 (2002). A.-L. Barabási, E. Ravasz, T. Vicsek, Deterministic Scale-Free Networks. Physica A: Statistical Mechanics and its Applications 299, Issues 3-4, 559-564 (2001).



Jövő Internet

21 / 22

R. Albert, A.-L. Barabási, Hierarchical organization in complex networks. Rev. Mod. Phys. 74, 47 (2002). A.-L. Barabási, E. Ravasz, T. Vicsek, Deterministic Scale-Free Networks. Physica A: Statistical Mechanics and its Applications 299, Issues 3-4, 559-564 (2001). G. Palla, L. Lovász and T. Vicsek, Multifractal network generator. PNAS 107 , 7640-7645.



Jövő Internet

21 / 22

Vége Köszönöm a figyelmet!



Jövő Internet

22 / 22

Hierarchikus skálafüggetlen gráfok generálása fraktálokkal

Recommend Documents