Transcript Morse structure of first

Is it possible to geometrize
infinite graphs?
(Diffusion metrics and geometrization of finite graphs and relational databases)
D. Volchenkov
Motivation
1. Data interpretation
X
m* = ?
m
Y
Motivation
1. Data interpretation
X
m* = ?
Y
Monge – Kantorovich transport problem
K  X , Y  = inf  cost x, y dL
L
-- the transportation plan L;
m
-- X , Y probability measures on
a compact (metrizable) space;
K → the transportation metric
Motivation
1. Data interpretation
X
m* = ?
Y
Monge – Kantorovich transport problem
K  X , Y  = inf  cost x, y dL
L
-- the transportation plan L;
m
2. Data “coordinates”
-- X , Y probability measures on
a compact (metrizable) space;
K → the transportation metric
“0”
Resistor networks
I
i
Vj
Vi
rij
j
rij is the measure of the opposition
that a conductor presents to a current
when a voltage is applied.
(an “empirical distance” between i and j )
Ohm's law:
I=
V j  Vi
r ij
The current through a conductor between two
points is directly proportional to the voltage
across the two points.
Resistor networks
i = 1,, N
I1
1
rij = rji
V1
r12 V
2
r13
3
I3
2 I2
V3
r 23
The (effective) resistance
between nodes  and  :
Kirchhoff's current law:
N
I
i =1
i
The algebraic sum of currents in a
network of conductors meeting at
a point is zero.
=0
cij = rij1, conductanc e
Ohm's law:
 c V  V  = I
N
ij
j =1( j i )
R =
i
j
V  V
I
i
=?
I i = I  i   i 
The current through a
conductor between two points
is directly proportional to the
voltage across the two points.
?
rij  Rij
Resistor networks
i = 1,, N
I1
1
I3
ij
j =1( j i )
V1
r12 V
2
2 I2
V3
 c V  V  = I
N
rij = rji
r13
3
Ohm's law:
r 23
i
i
In the matrix form:


I = LV
 c12
 c1

c2
c
L =  21



  cN 1  cN 2
(L – the Kirchhoff matrix)
  c1N 

  c2 N 
  

 cN 
(f all rij =1 W, L is the graph Laplacian operator)
R
j
1
the Green function
"
=
"
L


cij = c ji = 1 rij
ci =
N
 c
j =1 j i
ij
Resistor networks
i = 1,, N
I1
1
rij = rji
V1
r12 V
2
r13
3
I3
2 I2
V3
r 23
N
I
i =1
i
=0
 c12
 c1

c2
c
L =  21



  cN 1  cN 2
  c1N 

  c2 N 

 

 cN 
cij = c ji = 1 rij
ci =
N
c
ij
j =1 j i 
Let Yi and li be the eigenvectors and
eigenvalues of L:
LYi = li Yi
L = L : Yi* , Yj  =  is* js =  ij
s
The sum of all columns (or rows) of L is identically
zero:
l1 = 0, 1 = 1 N , = 1,2,, N .
L has no inverse!
Resistor networks
i = 1,, N
I1
1
rij = rji
I3
I
i =1
V1
i
=0
 c12
 c1

c2
c
L =  21



  cN 1  cN 2
  c1N 

  c2 N 

 

 cN 
ci =
N
c
ij
j =1 j i 
2 I2
N
L( ) = L    1,   0, G( ) = L ( ), Vi =  Gij  I j
1
V3
cij = c ji = 1 rij
How can we calculate the Green function?
r12 V
2
r13
3
N
j =1
r 23
U : U LU = Λ, U L( )U = Λ( )
LYi = li Yi
U ij =  ji ,  ii ( ) = (li   ) ij
UG( )U = Λ 1 ( ),
G( ) = UΛ1 ( )U
N
 i i*
 1  *
1
U i =
G ( ) = Ui 
 g ( ), g ( ) = 
l


N

i =1
i =2 li  
 i

N
Resistor networks
i = 1,, N
rij = rji
I1
1
I3
I
i =1
V1
i
=0
 c12
 c1

c2
c
L =  21



  cN 1  cN 2
  c1N 

  c2 N 

 

 cN 
ci =
N
c
ij
j =1 j i 
2 I2
N
L( ) = L    1,   0, G( ) = L ( ), Vi =  Gij  I j
1
V3
cij = c ji = 1 rij
How can we calculate the Green function?
r12 V
2
r13
3
N
j =1
r 23
U : U LU = Λ, U L( )U = Λ( )
LYi = li Yi
U ij =  ji ,  ii ( ) = (li   ) ij
N
Vi ( ) =  Gij ( ) I j =
j =1
1
=
N
N
N
I  g
j =1
j
j =1
0
ij
( ) I j
UG( )U = Λ 1 ( ),
G( ) = UΛ1 ( )U
N
 i i*
 1  *
1
U i =
G ( ) = Ui 
 g ( ), g ( ) = 
l


N

i =1
i =2 li  
 i

N
Resistor networks
N
I
i = 1,, N
I1
1
rij = rji
r12 V
2
I3
ci =
N
c
ij
j =1 j i 
0
R =
r 23
V  V
I
Ii = I
=
 
i  i

g (0)  g  (0)  g (0)  g  (0)
N

 *
 LYi = li Yi , g ( ) =  i i

i = 2 li  

N


cij = c ji = 1 rij
N
1 N
Vi =
I j  lim  gij ( ) I j

 0
N j =1
j =1



2 I2
V3
=0
  c1N 

  c2 N 

 

 cN 
V1
r13
3
i =1
i
 c12
 c1

c2
c
L =  21



  cN 1  cN 2
R = 
1
i = 2 li
R



  i 
2
i
  2

=
,, N
lN
 l2


 
=   i  i 

li 
i = 2  li
N
2
    2 

,, N
,  = 
lN

 l2







Resistor networks
 N 1

1  1
L= 

r

 1
 1
1 



 
 N 1 1 

  1 N  1
l1 = 0, l2 = lN = N r
 n
A complete graph
R

1 2i
=
e
N
r
=
N
N
n 1
N
, n,  = 1, N (Fourier harmonics)
  n  n =
n =1
r
=
N
2
2r
N
(an equidistant set of
nodes)
n 1
2i

 (a superposition of
N
,
, e

 standing waves)
Optimization problems
In the context of electrical
networks, the OP
corresponds to allocating
conductance to the
branches of a circuit so as to
achieve the lowest net
resistance between nodes.
A probabilistic interpretation
i = 1,, N
rij = rji
1
Pr i  j  =
r12
r13
2
r 23
3
P =
1 1
c R
cij = c ji = 1 rij
cij
ci
ci =

cij
cj
c12 c1
 0

0
 c21 c1
T=



 cN 1 cN cN 2 cN
N
 c
j =1 j i
ij
= Pr  j  i 
 c1N c1 

 c2 N c2 

 


0 
Let Pαβ be the probability that the walker starting
from node α will reach node β before returning
to α, which is the probability of first passage.
Study of finite connected graphs by the nearest neighbor random walks
Graph  A  T = D 1 A, D = diag deg(1), deg( N )
ˆ = D1 2 AD 1 2 ,  T
ˆ = m  ,   N ,
T
l
l l
l
1  s ,i  s , j
Gij = 
s = 2 1  m s  1,i  1, j
N

i
2
T

 2 ,i

   1,i 1  m 2
= 

 
N ,i

   1,i 1  m N

2
1  k ,i
=  i , G i  = 
2
k =2 1  mk  1,i
 
Kij = i  j
N
2
T

 k, j
 k ,i
= 


 1, j 1  mk
k = 2   1,i 1  mk
N




2
1 = m1    m N ,  12,i =  i =
 2, j
 
 
   1, j 1  m 2
 , 

   N, j
 
   1, j 1  m N
 
degi 
2E



 

= i, j T



  PR N 1
 
Study of finite connected graphs by the nearest neighbor random walks
The matrix of the access (hitting) time
from i to j:
(with no return to i )
1

H
=
1

H vj
 ij i  j

deg( i ) v i 


H ii = 0

(the first step takes us to a neighbor v of i, and then we have to reach j from there)
N
1
H ji  H ij = 
k = 2 1  mk
  kj2  ki  kj 
 2 



 1 j  1i  1 j 

 k, j
 k ,i
Kij = H ij  H ji =  


 1, j 1  mk
k =2   1,i 1  mk
N
2
1  k ,i
=  i H ij = 
2
i =1
k =2 1  mk  1,i
N
Pi
N




2
The commute time from i to j and back
The first-passage time to i from any
other node chosen randomly wrt to the
stationary probability of rand walks.
All possible (self-avoiding) paths between the nodes contribute into the “diffusion” distance
accordingly their weights (the probability to be chosen by a random walker).
Study of finite connected graphs by the nearest neighbor random walks
Graph  A  T = D 1 A, D = diag deg(1), deg( N )
ˆ = D1 2 AD 1 2 ,  T
ˆ = m  ,   N ,
T
l
l l
l
1  s ,i  s , j
Gij = 
s = 2 1  m s  1,i  1, j
N
1 = m1    m N ,  12,i =  i =
 2, j
 
 
   1, j 1  m 2
 , 

   N, j
 
   1, j 1  m N
 

 2 ,i

   1,i 1  m 2
= 

 
N ,i

   1,i 1  m N

First-passage time:

i
2
T
1 
k =2 1  mk 
N
=  i , G i  = 
2
k ,i
2
1,i
N
=   i H ij
1
Commute time:
 
Kij = i  j
2
T

i =1

 k, j
 k ,i
= 


 1, j 1  mk
k = 2   1,i 1  mk
N




2

2 ,i
2, j
, 3, j 
degi 
2E



 

= i, j T



  PR N 1
 

j
, 3,i 

i
Tax assessment value of land ($)
Can we see the first-passage times?
Manhattan, 2005
(Mean) First passage time
(Mean) first-passage times in the city graph of Manhattan
SoHo
Federal Hall
10
East Village
100
1,000
Bowery
East Harlem
5,000
10,000
Why are mosques located close to railways?
NEUBECKUM:
Social isolation vs. structural isolation
Connection to dynamical systems (Ulam): Music as a time series
G major is based on the pitches
G, A, B, C, D, E, and F♯.
W.A. Mozart, Eine Kleine Nachtmusik
T
G=
 Tn = 1-T  =" L1" ,
1
n 
C, “do”:
first-passage
times
“
recurrence
times
1
0
“ =
First-passage time (
Recurrence time (
) T2 =
(
) =1/
,
,G
)
0 =  G
“Ricci curvature”:
First - passage time
 = 1
Recurrence time
Anticipation is possible within the data neighborhood of positive “Ricci curvature”
Is it possible to geometrize
infinite graphs?
May be, the resolvent of some (self-adjoint)
“transfer operators” would be helpful ??
Negative result is a result
(Complex electrical impedance)
I

V
V

z = z = r  ix
the resistance
r = r  0
z is the measure of the opposition
that an element presents to a current
when a voltage is applied.
the negative reactance:
the positive reactance:
x = x  0, capacitanc es
x = x  0, inductance s
Capacitance is a measure of
the capacity of storing
electric charge for a given
potential difference.
Inductance is the property of an
electrical conductor by which a
change in current through it
induces an electromotive force in
both the conductor itself and in any
nearby conductors by mutual
inductance.
An electrical impedance network
 ,  = 1,, N
1
z12
z13
2
z 23
3
The effective impedance
between nodes p and q :
Z pq =
V p  Vq
I
=?
I = I  p   q 
An electrical impedance network
N
Kirchhoff's current law:
 ,  = 1,, N
1
z12


I = LV
2
z 23
3
y =
=1
 y12
 y1

y2
 y
L =  21



  yN 1  yN 2
y = y = 1 z
z13
I = 0


N
y

   
=1 
  y1N 

  y2 N 

 

 y N 
UT LU = ,  = diag 0, l2 ,lN 
The effective impedance
between nodes p and q :
Z pq =
V p  Vq
I
=?
I = I  p   q 
N
Z pq = 
 =2
1
l
u
p  uq  , if l  0,   2
2
= , if  : l = 0,   2.
resonances
Electrical resonances occur at a particular
resonance frequency when the imaginary parts of
impedances of circuit elements cancel each other.
Electrical resonance


I = LV
R = 0
 1  1
,
L = y12 
 1 1 
y12 = iC  1 iL = iC  1 L 

L* L   1 = 0,  2 = 4 y12
l1 = 0, l2 = 2 y12


=1
Z12 = 1 y12


=1
2

0
LC

LC
The collapsing magnetic field of the inductor generates an electric current in its windings
that charges the capacitor, and then the discharging capacitor provides an electric current
that builds the magnetic field in the inductor. This process is repeated continually.
If edges of an infinite graph have
complex weights, what might be its
resonances?
(Resonance bands?)
Morse structure of first-passage manifolds
Tˆij =
Aij
A
is
s

A
ˆ = m  ,   O N , l = 1  m , 1 = m    m
,  lT
l l
l
l
l
1
N
js
s
The first-passage time to a node is calculated as the mean of all first access
(hitting) times:
2
f j =  1,i H ij
i 1
with respect to the stationary distribution of random walks
 i =  12,i
For any given starting distribution that differs from the stationary one, we can
calculate the analogous quantity,
We call it the first attaining time to the node j by the random walks starting at
the distribution defined by ϕ1.
Morse structure of first-passage manifolds
k are the direction cosines
f j =  12,i H ij = q j , q j PR N 1
i 1
A manifold locally homeomorphic to Euclidean space
First
Morse
attaining
structure
times
ofmanifold.
first-passage
The manifolds
Morse eory
At a vicinity of the stationary distribution (k ≈0),
each node j is a critical point of the manifold of first attaining
times, and the first passage times fj are the correspondent
critical values:
Morse structure of first-passage manifolds
Following the ideas of the Morse theory, we
can perform the standard classification of
the critical points, introducing the index g j of
the critical point j as the number of
negative eigenvalues of H at j.
The index of a critical point is the dimension of the largest subspace of
the tangent space to the manifold at j on which the Hessian is negative
definite).
Morse structure of first-passage manifolds
The Euler characteristic c is an intrinsic
property of a manifold that describes its
topological space’s shape regardless of
the way it is bent.
It is known that the Euler characteristic can be calculated
as the alternating sum of Cg , the numbers of critical points
of index c of the Hessian function,
Morse structure of first-passage manifolds
Amsterdam (57 canals)
The negative Euler characteristics could
either come from a pattern of symmetry in
the hyperbolic surfaces, or from a manifold
homeomorphic multiple tori.
Venice (96 canals)
The large positive value of the Euler
characteristic can arise due to the wellknown product property of Euler
characteristics
for any product space M ×N, or, more generally, from a fibration, when one topological
space (a fiber) is being ”parameterized” by another topological space (a base).
Thank you!