expander graph [IZ89] Nii (NII) Lec. 11 October 22, / 16

Similar documents
Lecture 12. Properties of Expanders

/ n (M1) M (M2) n Λ A = {ϕ λ : U λ R n } λ Λ M (atlas) A (a) {U λ } λ Λ M (open covering) U λ M λ Λ U λ = M (b) λ Λ ϕ λ : U λ ϕ λ (U λ ) R n ϕ

‚åŁÎ“·„´Šš‡ðŠp‡¢‡½‹âfi`fiI…A…‰…S…−…Y…•‡ÌMarkovŸA“½fiI›ð’Í

ユニセフ表紙_CS6_三.indd

N cos s s cos ψ e e e e 3 3 e e 3 e 3 e

研修コーナー

パーキンソン病治療ガイドライン2002

untitled

untitled


untitled


学報22号

00学報42号最終色替え

LabFabChemicals2013Oct_ pdf


<8E6C969C8F5C8E738D4C95F131308C8E8D862E706466>

単ページ

kouhou_honbun_20_35_ pdf


‘¬”R.qx

ユニセフ表紙_CS6_三.indd

I z n+1 = zn 2 + c (c ) c pd L.V. K. 2

量子力学 問題

ii 3.,. 4. F. (), ,,. 8.,. 1. (75%) (25%) =7 20, =7 21 (. ). 1.,, (). 3.,. 1. ().,.,.,.,.,. () (12 )., (), 0. 2., 1., 0,.

I A A441 : April 15, 2013 Version : 1.1 I Kawahira, Tomoki TA (Shigehiro, Yoshida )

() x + y + y + x dy dx = 0 () dy + xy = x dx y + x y ( 5) ( s55906) 0.7. (). 5 (). ( 6) ( s6590) 0.8 m n. 0.9 n n A. ( 6) ( s6590) f A (λ) = det(a λi)

Gmech08.dvi

ii 3.,. 4. F. (), ,,. 8.,. 1. (75% ) (25% ) =9 7, =9 8 (. ). 1.,, (). 3.,. 1. ( ).,.,.,.,.,. ( ) (1 2 )., ( ), 0. 2., 1., 0,.


PDF

数学概論I

1. (8) (1) (x + y) + (x + y) = 0 () (x + y ) 5xy = 0 (3) (x y + 3y 3 ) (x 3 + xy ) = 0 (4) x tan y x y + x = 0 (5) x = y + x + y (6) = x + y 1 x y 3 (

( ) ( ) 1729 (, 2016:17) = = (1) 1 1


本文／目次（裏白）

II A A441 : October 02, 2014 Version : Kawahira, Tomoki TA (Kondo, Hirotaka )


基礎数学I

Z[i] Z[i] π 4,1 (x) π 4,3 (x) 1 x (x ) 2 log x π m,a (x) 1 x ϕ(m) log x 1.1 ( ). π(x) x (a, m) = 1 π m,a (x) x modm a 1 π m,a (x) 1 ϕ(m) π(x)

Œ{Ł¶/1ŒÊ −ªfiª„¾ [ 1…y†[…W ]

本文／扉１

プログラム


平成20年5月 協会創立50年の歩み　海の安全と環境保全を目指して 友國八郎 海上保安庁 長官 岩崎貞二 日本船主協会 会長 前川弘幸 JF全国漁業協同組合連合会 代表理事会長 服部郁弘 日本船長協会 会長 森本靖之 日本船舶機関士協会 会長 大内博文 航海訓練所 練習船船長 竹本孝弘 第二管区海上保安本部長 梅田宜弘

Program

ａｐｈｐ３７－１１＿プロ１／ｋｙ８６９５４３５４０４１０００５５９０


日本内科学会雑誌第96巻第11号

( [1]) (1) ( ) 1: ( ) 2 2.1,,, X Y f X Y (a mapping, a map) X ( ) x Y f(x) X Y, f X Y f : X Y, X f Y f : X Y X Y f f 1 : X 1 Y 1 f 2 : X 2 Y 2 2 (X 1

LCR e ix LC AM m k x m x x > 0 x < 0 F x > 0 x < 0 F = k x (k > 0) k x = x(t)

m dv = mg + kv2 dt m dv dt = mg k v v m dv dt = mg + kv2 α = mg k v = α 1 e rt 1 + e rt m dv dt = mg + kv2 dv mg + kv 2 = dt m dv α 2 + v 2 = k m dt d

国際会館ICC冊子2013.indd

,. Black-Scholes u t t, x c u 0 t, x x u t t, x c u t, x x u t t, x + σ x u t, x + rx ut, x rux, t 0 x x,,.,. Step 3, 7,,, Step 6., Step 4,. Step 5,,.

Ł\”ƒ-2005

第90回日本感染症学会学術講演会抄録（I）

A A = a 41 a 42 a 43 a 44 A (7) 1 (3) A = M 12 = = a 41 (8) a 41 a 43 a 44 (3) n n A, B a i AB = A B ii aa


ii 3.,. 4. F. ( ), ,,. 8.,. 1. (75% ) (25% ) =7 24, =7 25, =7 26 (. ). 1.,, ( ). 3.,...,.,.,.,.,. ( ) (1 2 )., ( ), 0., 1., 0,.

液晶の物理１：連続体理論（弾性，粘性）

Gmech08.dvi

II 2 II

BayesfiI‡É“ÅfiK‡È−w‘K‡Ì‡½‡ß‡ÌChow-Liu…A…‰…S…−…Y…•

「産業上利用することができる発明」の審査の運用指針（案）

III 1 (X, d) d U d X (X, d). 1. (X, d).. (i) d(x, y) d(z, y) d(x, z) (ii) d(x, y) d(z, w) d(x, z) + d(y, w) 2. (X, d). F X.. (1), X F, (2) F 1, F 2 F

y = x x R = 0. 9, R = σ $ = y x w = x y x x w = x y α ε = + β + x x x y α ε = + β + γ x + x x x x' = / x y' = y/ x y' =

u u u 1 1

30 (11/04 )

201711grade1ouyou.pdf

pdf

B ver B

1 variation 1.1 imension unit L m M kg T s Q C QT 1 A = C s 1 MKSA F = ma N N = kg m s 1.1 J E = 1 mv W = F x J = kg m s 1 = N m 1.

renshumondai-kaito.dvi

A = A x x + A y y + A, B = B x x + B y y + B, C = C x x + C y y + C..6 x y A B C = A x x + A y y + A B x B y B C x C y C { B = A x x + A y y + A y B B

LLG-R8.Nisus.pdf

50 2 I SI MKSA r q r q F F = 1 qq 4πε 0 r r 2 r r r r (2.2 ε 0 = 1 c 2 µ 0 c = m/s q 2.1 r q' F r = 0 µ 0 = 4π 10 7 N/A 2 k = 1/(4πε 0 qq

1 1 sin cos P (primary) S (secondly) 2 P S A sin(ω2πt + α) A ω 1 ω α V T m T m 1 100Hz m 2 36km 500Hz. 36km 1

プログラム

ω 0 m(ẍ + γẋ + ω0x) 2 = ee (2.118) e iωt x = e 1 m ω0 2 E(ω). (2.119) ω2 iωγ Z N P(ω) = χ(ω)e = exzn (2.120) ϵ = ϵ 0 (1 + χ) ϵ(ω) ϵ 0 = 1 +

2 1 x 2 x 2 = RT 3πηaN A t (1.2) R/N A N A N A = N A m n(z) = n exp ( ) m gz k B T (1.3) z n z = m = m ρgv k B = erg K 1 R =


I. (CREMONA ) : Cremona [C],., modular form f E f. 1., modular X H 1 (X, Q). modular symbol M-symbol, ( ) modular symbol., notation. H = { z = x

Gauss Gauss ɛ 0 E ds = Q (1) xy σ (x, y, z) (2) a ρ(x, y, z) = x 2 + y 2 (r, θ, φ) (1) xy A Gauss ɛ 0 E ds = ɛ 0 EA Q = ρa ɛ 0 EA = ρea E = (ρ/ɛ 0 )e

Onsager SOLUTION OF THE EIGENWERT PROBLEM (O-29) V = e H A e H B λ max Z 2 Onsager (O-77) (O-82) (O-83) Kramers-Wannier 1 1 Ons

医系の統計入門第 2 版 サンプルページ この本の定価 判型などは, 以下の URL からご覧いただけます. このサンプルページの内容は, 第 2 版 1 刷発行時のものです.

V 0 = + r pv (H) + qv (T ) = + r ps (H) + qs (T ) = S 0 X n+ (T ) = n S n+ (T ) + ( + r)(x n n S n ) = ( + r)x n + n (d r)s n = ( + r)v n + V n+(h) V

1 : f(z = re iθ ) = u(r, θ) + iv(r, θ). (re iθ ) 2 = r 2 e 2iθ = r 2 cos 2θ + ir 2 sin 2θ r f(z = x + iy) = u(x, y) + iv(x, y). (x + iy) 2 = x 2 y 2 +

I ( ) 2019

成長機構

独立性の検定・ピボットテーブル

R pdf

微分積分 サンプルページ この本の定価 判型などは, 以下の URL からご覧いただけます. このサンプルページの内容は, 初版 1 刷発行時のものです.

Z: Q: R: C: sin 6 5 ζ a, b

x 3 a (mod p) ( ). a, b, m Z a b m a b (mod m) a b m 2.2 (Z/mZ). a = {x x a (mod m)} a Z m 0, 1... m 1 Z/mZ = {0, 1... m 1} a + b = a +

SO(3) 7 = = 1 ( r ) + 1 r r r r ( l ) (5.17) l = 1 ( sin θ ) + sin θ θ θ ϕ (5.18) χ(r)ψ(θ, ϕ) l ψ = αψ (5.19) l 1 = i(sin ϕ θ l = i( cos ϕ θ l 3 = i ϕ

1 Tokyo Daily Rainfall (mm) Days (mm)

29


ｎｓｇ０２－１３／ｋｙ０４５０５９３０１６０００３３２１０

m(ẍ + γẋ + ω 0 x) = ee (2.118) e iωt P(ω) = χ(ω)e = ex = e2 E(ω) m ω0 2 ω2 iωγ (2.119) Z N ϵ(ω) ϵ 0 = 1 + Ne2 m j f j ω 2 j ω2 iωγ j (2.120)

Transcription:

Lecture 11: PSRGs via Random Walks on Graphs October 22, 2013 Nii (NII) Lec. 11 October 22, 2013 1 / 16

expander graph [IZ89] Nii (NII) Lec. 11 October 22, 2013 2 / 16

Expander Graphs Expander Graph ( ) : conductance expander family : (d, ϕ), s.t. d, conductance ϕ, ( d- expander ) expander expander λ i d < ϵd i 2 for constant ϵ µ i < ϵd i 2 for constant ϵ Nii (NII) Lec. 11 October 22, 2013 3 / 16

[ ] [ ] 1 2 Nii (NII) Lec. 11 October 22, 2013 4 / 16

(1 r ) (r t, t: ) ( r + 9t ) t t Nii (NII) Lec. 11 October 22, 2013 5 / 16

(1 r ) (r t, t: ) ( r + 9t ) t t Nii (NII) Lec. 11 October 22, 2013 5 / 16

(1 r ) (r t, t: ) ( r + 9t ) t t Nii (NII) Lec. 11 October 22, 2013 5 / 16

Random Walk Generator r : = {0, 1} r X {0, 1} r : Y {0, 1} r : V = {0, 1} r expander graph = expander graph : d- A : d = µ 1 > µ 2 µ n : µ i d 1/10 for all i 2?. Nii (NII) Lec. 11 October 22, 2013 6 / 16

Random Walk Generator d = 400 r log 2 400 9 9 2 r v i v i {0, 1} r d = r i i I promise you that... Nii (NII) Lec. 11 October 22, 2013 7 / 16

Random Walk Generator d = 400 r log 2 400 9 9 2 r v i v i {0, 1} r d = r i i I promise you that... Nii (NII) Lec. 11 October 22, 2013 7 / 16

Formalizing[ ] t + 1 v {0, 1} r v t X X 2 r /100 ( 99 ) t + 1 t + 1 X v 0 v 1,..., v t S = {i v i X} t + 1 (1 ) ( ) t+1 P r[ S > t/2] 2 5 Nii (NII) Lec. 11 October 22, 2013 8 / 16

Formalizing[ ] t + 1 v {0, 1} r v t X X 2 r /100 ( 99 ) t + 1 t + 1 X v 0 v 1,..., v t S = {i v i X} t + 1 (1 ) ( ) t+1 P r[ S > t/2] 2 5 Nii (NII) Lec. 11 October 22, 2013 8 / 16

Formalizing[ ] t + 1 v {0, 1} r v t X X 2 r /100 ( 99 ) t + 1 t + 1 X v 0 v 1,..., v t S = {i v i X} t + 1 (1 ) ( ) t+1 P r[ S > t/2] 2 5 Nii (NII) Lec. 11 October 22, 2013 8 / 16

Formalizing[ ] t + 1 v {0, 1} r v t X X 2 r /100 ( 99 ) t + 1 t + 1 X v 0 v 1,..., v t S = {i v i X} t + 1 (1 ) ( ) t+1 P r[ S > t/2] 2 5 Nii (NII) Lec. 11 October 22, 2013 8 / 16

p 0 = 1 n 1 = ( 1 n,..., 1 n )T χ X, χ Y X, Y (X,Y 1) D X = diag(χ X ), D Y = diag(χ Y ) W = 1 da G random walk ( lazy ) ω 1,..., ω n W ω i 1/10 ( i 2) p X χ T Xp = 1 T D X p D X p p X 0 R {0,..., t} i R X 1 T D Zt W D Zt 1 W D Z1 W D Z0 p 0 Z i i R X Y (2) 1 T D Zt W D Zt 1 W D Z1 W D Z0 p 0 (1/5) R Nii (NII) Lec. 11 October 22, 2013 9 / 16

p 0 = 1 n 1 = ( 1 n,..., 1 n )T χ X, χ Y X, Y (X,Y 1) D X = diag(χ X ), D Y = diag(χ Y ) W = 1 da G random walk ( lazy ) ω 1,..., ω n W ω i 1/10 ( i 2) p X χ T Xp = 1 T D X p D X p p X 0 R {0,..., t} i R X 1 T D Zt W D Zt 1 W D Z1 W D Z0 p 0 Z i i R X Y (2) 1 T D Zt W D Zt 1 W D Z1 W D Z0 p 0 (1/5) R Nii (NII) Lec. 11 October 22, 2013 9 / 16

p 0 = 1 n 1 = ( 1 n,..., 1 n )T χ X, χ Y X, Y (X,Y 1) D X = diag(χ X ), D Y = diag(χ Y ) W = 1 da G random walk ( lazy ) ω 1,..., ω n W ω i 1/10 ( i 2) p X χ T Xp = 1 T D X p D X p p X 0 R {0,..., t} i R X 1 T D Zt W D Zt 1 W D Z1 W D Z0 p 0 Z i i R X Y (2) 1 T D Zt W D Zt 1 W D Z1 W D Z0 p 0 (1/5) R Nii (NII) Lec. 11 October 22, 2013 9 / 16

p 0 = 1 n 1 = ( 1 n,..., 1 n )T χ X, χ Y X, Y (X,Y 1) D X = diag(χ X ), D Y = diag(χ Y ) W = 1 da G random walk ( lazy ) ω 1,..., ω n W ω i 1/10 ( i 2) p X χ T Xp = 1 T D X p D X p p X 0 R {0,..., t} i R X 1 T D Zt W D Zt 1 W D Z1 W D Z0 p 0 Z i i R X Y (2) 1 T D Zt W D Zt 1 W D Z1 W D Z0 p 0 (1/5) R Nii (NII) Lec. 11 October 22, 2013 9 / 16

p 0 = 1 n 1 = ( 1 n,..., 1 n )T χ X, χ Y X, Y (X,Y 1) D X = diag(χ X ), D Y = diag(χ Y ) W = 1 da G random walk ( lazy ) ω 1,..., ω n W ω i 1/10 ( i 2) p X χ T Xp = 1 T D X p D X p p X 0 R {0,..., t} i R X 1 T D Zt W D Zt 1 W D Z1 W D Z0 p 0 Z i i R X Y (2) 1 T D Zt W D Zt 1 W D Z1 W D Z0 p 0 (1/5) R Nii (NII) Lec. 11 October 22, 2013 9 / 16

p 0 = 1 n 1 = ( 1 n,..., 1 n )T χ X, χ Y X, Y (X,Y 1) D X = diag(χ X ), D Y = diag(χ Y ) W = 1 da G random walk ( lazy ) ω 1,..., ω n W ω i 1/10 ( i 2) p X χ T Xp = 1 T D X p D X p p X 0 R {0,..., t} i R X 1 T D Zt W D Zt 1 W D Z1 W D Z0 p 0 Z i i R X Y (2) 1 T D Zt W D Zt 1 W D Z1 W D Z0 p 0 (1/5) R Nii (NII) Lec. 11 October 22, 2013 9 / 16

(2) 1 T D Zt W D Zt 1 W D Z1 W D Z0 p 0 (1/5) R (1) P r[ S > t/2] P r[ S > t/2] ( 2 R >t/2 2 t+1 ( 1 5 5 ) t+1 P r[v i X i R] ) t+1 2 ( 2 5 ) t+1 Nii (NII) Lec. 11 October 22, 2013 10 / 16

(2) 1 T D Zt W D Zt 1 W D Z1 W D Z0 p 0 (1/5) R (1) P r[ S > t/2] P r[ S > t/2] ( 2 R >t/2 2 t+1 ( 1 5 5 ) t+1 P r[v i X i R] ) t+1 2 ( 2 5 ) t+1 Nii (NII) Lec. 11 October 22, 2013 10 / 16

(2-norm) : M = max v Mv v M M = max α: α ( v ) M 1 M 2 M 1 M 2 D X, D Y, W 1 1 1 3 2 Nii (NII) Lec. 11 October 22, 2013 11 / 16

(2) Lemma 1 T D Zt W D Z1 W D Z0 p 0 (1/5) R D X W 1 5 p 0 = W p 0 ( ) 1 T D Zt W D Z1 W D Z0 p 0 = 1 T (D Zt W ) (D Z0 W )p 0 { 1/5 for i R D Zi W 1 for i / R. (D Zt W ) (D Z0 W ) 1 5 R. Nii (NII) Lec. 11 October 22, 2013 12 / 16

(2) Lemma 1 T D Zt W D Z1 W D Z0 p 0 (1/5) R D X W 1 5 p 0 = W p 0 ( ) 1 T D Zt W D Z1 W D Z0 p 0 = 1 T (D Zt W ) (D Z0 W )p 0 { 1/5 for i R D Zi W 1 for i / R. (D Zt W ) (D Z0 W ) 1 5 R. Nii (NII) Lec. 11 October 22, 2013 12 / 16

(2) Lemma 1 T D Zt W D Z1 W D Z0 p 0 (1/5) R D X W 1 5 p 0 = W p 0 ( ) 1 T D Zt W D Z1 W D Z0 p 0 = 1 T (D Zt W ) (D Z0 W )p 0 { 1/5 for i R D Zi W 1 for i / R. (D Zt W ) (D Z0 W ) 1 5 R. Nii (NII) Lec. 11 October 22, 2013 12 / 16

(2) Lemma 1 T D Zt W D Z1 W D Z0 p 0 (1/5) R D X W 1 5 p 0 = W p 0 ( ) 1 T D Zt W D Z1 W D Z0 p 0 = 1 T (D Zt W ) (D Z0 W )p 0 { 1/5 for i R D Zi W 1 for i / R. (D Zt W ) (D Z0 W ) 1 5 R. Nii (NII) Lec. 11 October 22, 2013 12 / 16

(2) 1 T D Zt W D Z1 W D Z0 p 0 (1/5) R (D Zt W ) (D Z0 W ) 1 5 R p 0 = 1/ n, 1 = n 1 T (D Zt W ) (D Z0 W )p 0 1 T (D Zt W ) (D Z0 W ) p 0 = (1/5) R Nii (NII) Lec. 11 October 22, 2013 13 / 16

(2) 1 T D Zt W D Z1 W D Z0 p 0 (1/5) R (D Zt W ) (D Z0 W ) 1 5 R p 0 = 1/ n, 1 = n 1 T (D Zt W ) (D Z0 W )p 0 1 T (D Zt W ) (D Z0 W ) p 0 = (1/5) R Nii (NII) Lec. 11 October 22, 2013 13 / 16

Lemma ( ) x, D X W x (1/5) x [ ] x x = c 1 1 + y x = (c 1 n) 2 + y 2 max(c 1 n, y ) D X W x = c 1 D X W 1 + D X W y D X W x c 1 D X W 1 + D X W y (1 T y = 0) Nii (NII) Lec. 11 October 22, 2013 14 / 16

Lemma ( ) x, D X W x (1/5) x [ ] x x = c 1 1 + y x = (c 1 n) 2 + y 2 max(c 1 n, y ) D X W x = c 1 D X W 1 + D X W y D X W x c 1 D X W 1 + D X W y (1 T y = 0) Nii (NII) Lec. 11 October 22, 2013 14 / 16

Lemma ( ) x, D X W x (1/5) x [ ] x x = c 1 1 + y x = (c 1 n) 2 + y 2 max(c 1 n, y ) D X W x = c 1 D X W 1 + D X W y D X W x c 1 D X W 1 + D X W y (1 T y = 0) Nii (NII) Lec. 11 October 22, 2013 14 / 16

Lemma ( ) x, D X W x (1/5) x [ ] x x = c 1 1 + y x = (c 1 n) 2 + y 2 max(c 1 n, y ) D X W x = c 1 D X W 1 + D X W y D X W x c 1 D X W 1 + D X W y (1 T y = 0) Nii (NII) Lec. 11 October 22, 2013 14 / 16

Lemma ( ) x, D X W x (1/5) x [ ] x max(c 1 n, y ) D X W x c 1 D X W 1 + D X W y. Nii (NII) Lec. 11 October 22, 2013 15 / 16

Lemma ( ) x, D X W x (1/5) x [ ] x max(c 1 n, y ) D X W x c 1 D X W 1 + D X W y. W 1 = 1 D X W 1 = χ X c 1 D X W 1 = c 1 χ X = c 1 X c1 n 10 x 10 ( X n/100) Nii (NII) Lec. 11 October 22, 2013 15 / 16

Lemma ( ) x, D X W x (1/5) x [ ] x max(c 1 n, y ) D X W x c 1 D X W 1 + D X W y. W, ϕ 1 = 1 {ϕ 2,..., ϕ n } ( ω i ) y = i 2 c iϕ i (c i = ϕ T i y) W y = i 2 c iω i ϕ i = i 2 (c iω i ) 2 1 10 i 2 (c i) 2 = y 10 D X W y D X W y (1/10) y (1/10) x Nii (NII) Lec. 11 October 22, 2013 15 / 16

Lemma ( ) x, D X W x (1/5) x [ ] x max(c 1 n, y ) D X W x c 1 D X W 1 + D X W y. c 1 D X W 1 + D X W y (1/10) x + (1/10) x (1/5) x Nii (NII) Lec. 11 October 22, 2013 15 / 16

1 (r, t ) 2 (rt ) 3 4 expander graph 5 r + 9t, (2/ 5) t = (0.89) t Nii (NII) Lec. 11 October 22, 2013 16 / 16

2024 © docsplayer.net プライバシー | 利用規約 | フィードバック