Transcript differential geometry

Mathematical Analysis of Complex
Networks and Databases
Dima Volchenkov
What is a network/database?
A network Ν : E  K  R is any method of sharing information
E  V V
between systems consisting of many individual units V,
a measurable pattern of relationships between entities.
We suggest that these relationships can be expressed by large but finite matrices :
A: V×VR+ or at least ATA, AAT are positive, symmetric.
The main problem:
Being often embedded into Euclidean space, graphs/databases
nevertheless lack of a metric space structure.
Thus, we cannot acquire a comprehensive image of the whole network – it looks
confusing to us.
Symmetry
Symmetry (exact reflection of form on opposite side)
is a striking attribute of a shape or a relation.
GA (adjacency matrix of the graph)
Symmetry
Symmetry (exact reflection of form on opposite side)
is a striking attribute of a shape or a relation.
GA (adjacency matrix of the graph)

P: [P,A]=0, Automorphisms
A permutation matrix
Fractional/Stochastic symmetry
GA (adjacency matrix of the graph)

P: [P,A]=0, P =1, only trivial
automorphisms
Fractional/Stochastic symmetry
GA (adjacency matrix of the graph)

P: [P,A]=0, P =1, only trivial
automorphisms
A permutation matrix is a particular case of
stochastic matrix:
P
j
ij
= 1, P ij = 0,1
Fractional/Stochastic symmetry
GA (adjacency matrix of the graph)

P: [P,A]=0, P =1, only trivial
automorphisms
A permutation matrix is a particular case of
stochastic matrix:
P
ij
= 1, P ij = 0,1
j
Let us extend the notion of automorphisms
onto the class of stochastic matrices.

ij

j
T: [T, A]=0, Fractional automorphisms,
or stochastic automorphisms
T = 1,
There are infinitely many fractional automorphisms…
GA (adjacency matrix of the graph)

T: [T, A]=0 , Fractional automorphisms
Each T can be considered as a transition
matrix of some Markov chain, a “random
walk” defined on the graph/database.
Plan of my talk
Evolution of networks
Ricci-Hamilton flows
deforming a probabilistic
manifold
Example:
• Music: (the cyclic
group Z/12Z over
the set of
frequencies )
A variety of
stochastic
automorphisms
Which paths are taken
to be equi-probable?
From stochastic
symmetry to
metric geometry
Probabilistic differential
geometry
Probabilistic geometric
manifolds
(+/- ) Curvature  intelligible/
confusing environments.
Euclidean
metric
structure
Examples:
1. Nearest neighbor
random walks,
2. Electric resistance
networks,
3. Urban networks
The main idea in “two words”
The distance = “a Feynman path integral”
sensitive to the global structure of the graph.
The shortest-path distance, insensitive to
the structure of the graph:


d  i, j  = min
l Wˆ  i  j  .
ˆ
W 
The length of a walk
l W  v0 , v1 ,...vl   = l
Systems of weights are related to each other
in a geometric fashion.
A variety of fractional automorphisms
T
ij
= 1,
T, A  = 0,
T is a transition matrix of a random walk.
j
The central question: what types of path do we treat as equi-probable?
A variety of fractional automorphisms
T
ij
= 1,
T, A  = 0,
T is a transition matrix of a random walk.
j
The central question: what types of path do we treat as equi-probable?
One end is fixed:
“Nearest neighbor random walks”
Tij = Aij
 A , T , A = 0
ij
j
i
ALL paths to nearest neighbors of i are equi-probable
A variety of fractional automorphisms
T
ij
= 1,
T, A  = 0,
T is a transition matrix of a random walk.
j
The central question: what types of path do we treat as equi-probable?
One end is fixed:
“Nearest neighbor random walks”
Tij = Aij
 A , T , A = 0
ij
j
i
ℓ
Paths to ALL nearest neighbors of i are equi-probable
“ℓ - neighbor random walks”
T  ij = Aij


 

A
,
T
,A =0
ij

j
Paths to ALL neighbors of i at the distance ℓ are equiprobable
A variety of fractional automorphisms
T
ij
= 1,
T, A  = 0,
T is a transition matrix of a random walk.
j
The central question: what types of path do we treat as equi-probable?
Both ends are fixed:
“All paths between i and j of the length ℓ
are equi-probable”
ℓ
i
j

~   A ij j
T ij = 
, A = max 
max i
A variety of fractional automorphisms
T
ij
= 1,
T, A  = 0,
T is a transition matrix of a random walk.
j
The central question: what types of path do we treat as equi-probable?
“All paths between i and j of the length ℓ
are equi-probable”
i
j

~   A ij j
T ij = 
, A = max 
max i
“All paths between i and j are equi-probable”
j  A
~  
T ij =  
 =0  i  max

A = max 

  max   j
 = 
  ,
  max 1  A ij i
General transition operator
The generalized transition operator must contain all possible transitions that can
take place by the moment t:
 n 
 1    2 




,

Τ =
~
=T , T
t = 1   2  n 
 
Tij =
Aij
N

A
 is
~  
, T ij =
Aij j
 i

max
Τ, A  = 0
, A = max 
s =1
This is not just any path in a connected graph acquires a statistical weight,
but also all strategies of choosing a neighborhood (in which all paths are equi-probable)
are characterized by certain probabilities.
Properties of flows defined by different stochastic
automorphisms are very different
Nearest neighbor RW
J. K. Ochab, Z. Burda
Tij = Aij
A
ij
j
“Maximal entropy” RW
Aij j
~1
T ij =
, A = max 
max i
Properties of flows defined by different stochastic
automorphisms are very different
Nearest neighbor RW
J. K. Ochab, Z. Burda
Tij = Aij
A
ij
j
“Maximal entropy” RW
Aij j
~1
T ij =
, A = max 
max i
Properties of flows defined by different stochastic
automorphisms are very different
Nearest neighbor RW
J. K. Ochab, Z. Burda
Tij = Aij
A
ij
j
“Maximal entropy” RW
Aij j
~1
T ij =
, A = max 
max i
Properties of flows defined by different stochastic
automorphisms are very different
Nearest neighbor RW
J. K. Ochab, Z. Burda
Tij = Aij
A
ij
j
“Maximal entropy” RW
Aij j
~1
T ij =
, A = max 
max i
Properties of flows defined by different stochastic
automorphisms are very different
Nearest neighbor RW
J. K. Ochab, Z. Burda
Tij = Aij
A
ij
j
“Maximal entropy” RW
Aij j
~1
T ij =
, A = max 
max i
Properties of flows defined by different stochastic
automorphisms are very different
Nearest neighbor RW
J. K. Ochab, Z. Burda
Tij = Aij
A
ij
j
“Maximal entropy” RW
Aij j
~1
T ij =
, A = max 
max i
Properties of flows defined by different stochastic
automorphisms are very different
Nearest neighbor RW
J. K. Ochab, Z. Burda
Tij = Aij
A
ij
j
“Maximal entropy” RW
Aij j
~1
T ij =
, A = max 
max i
Properties of flows defined by different stochastic
automorphisms are very different
Nearest neighbor RW
J. K. Ochab, Z. Burda
Tij = Aij
A
ij
j
“Maximal entropy” RW
Aij j
~1
T ij =
, A = max 
max i
Properties of flows defined by different stochastic
automorphisms are very different
Nearest neighbor RW
J. K. Ochab, Z. Burda
Tij = Aij
A
ij
j
Maximal entropy RW
Aij j
~1
T ij =
, A = max 
max i
Properties of flows defined by different stochastic
automorphisms are very different
Nearest neighbor RW
J. K. Ochab, Z. Burda
Tij = Aij
A
ij
j
“Maximal entropy” RW
Aij j
~1
T ij =
, A = max 
max i
Properties of flows defined by different stochastic
automorphisms are very different
Nearest neighbor RW
J. K. Ochab, Z. Burda
Tij = Aij
A
ij
j
Homogeneous covering
“Maximal entropy” RW
Aij j
~1
T ij =
, A = max 
max i
Localization in the best connected
places
From stochastic symmetry to metric geometry
Graph A  P: [P,A]=0, Automorphisms

T: [T, A]=0   T n = 1 =" L1" , the Green function
n 
1 T

We can define a scalar product:
x, x'T
= x, " L1"  x, x '  x'
Metric Structure
From stochastic symmetry to metric geometry
Graph A  P: [P,A]=0, Automorphisms

T: [T, A]=0   T n = 1 =" L1" , the Green function
1 T
n 

We can define a scalar product:
(a generalized inverse)
The problem is that
T , max = 1 
x, x'T
1
1
 =
1 T 0
As being a member of a multiplicative
group under the ordinary matrix
multiplication, the Laplace operator
possesses a group inverse (a special
case of Drazin inverse) with respect to
this group, L◊, which satisfies the
conditions:
LL L = L,
L LL = L
L , L = 0

= x, " L1"  x, x '  x'
Metric Structure
The Drazin inverse corresponds to the eigenprojection of the matrix L w.r.t. to the
eigenvalue λ1 = 1−μ1 = 0
L = L  Z   Z , Z =  1  L i , i = 1  i
1
i 0
where the product in the idempotent matrix Z is taken over all nonzero eigenvalues of L.
Probabilistic Euclidean metric structure
Every stochastic automorphism T: [T,A]=0 induces a Euclidean metric structure with the
inner product
ξ, ς T
= ξ, Lς 
between any two vectors of the projective space
ξ, ς  PR  N 1
Probabilistic Euclidean metric structure
Every stochastic automorphism T: [T,A]=0 induces a Euclidean metric structure with the
inner product
ξ, ς T
= ξ, Lς 
between any two vectors of the projective space
The (squared) norm of a vector
ξ
2
T
= ξ, L ξ 
and an angle
 ξ, ς T 

 ξ ς 
 T T
 = arccos 
The Euclidean distance
ξ  ς T = ξ T  ς T  2ξ, ς T
2
2
2
ξ, ς  PR  N 1
Probabilistic Euclidean metric structure
Every stochastic automorphism T: [T,A]=0 induces a Euclidean metric structure with the
inner product
ξ, ς T
= ξ, Lς 
between any two vectors of the projective space
ξ, ς  PR  N 1
Example 1: Nearest neighbor random walks
The (squared) norm of a vector
ξ
2
T
= ξ, L ξ 
and an angle
 ξ, ς T 

 ξ ς 
 T T
 = arccos 
The Euclidean distance
ξ  ς T = ξ T  ς T  2ξ, ς T
2
2
2
GA
T = D1A
Probabilistic Euclidean metric structure
Every stochastic automorphism T: [T,A]=0 induces a Euclidean metric structure with the
inner product
ξ, ς T
= ξ, Lς 
ξ, ς  PR  N 1
between any two vectors of the projective space
Example 1: Nearest neighbor random walks
The (squared) norm of a vector
ξ
2
T
= ξ, L ξ 
Aij
A
is

s
N
L =

and an angle
 ξ, ς T 

 ξ ς 
 T T
 = arccos 
The Euclidean distance
ξ  ς T = ξ T  ς T  2ξ, ς T
2
Tˆij =
2
2
s =2

A
s
ˆ =  ,  = 1   , 1 =     
,  lT
l l
l
l
1
N
js
e i  PR  N 1
1  s ,i  s , j
s  1,i  1, j
The spectral representation of the (mean) first passage time, the expected
number of steps required to reach the node i for the first time starting from
a node randomly chosen among all nodes of the graph accordingly to the
stationary distribution π.
The commute time, the expected number of steps required for a random
walker starting at i ∈ V to visit j ∈ V and then to return back to i,
Probabilistic Euclidean metric structure
Every stochastic automorphism T: [T,A]=0 induces a Euclidean metric structure with the
inner product
ξ, ς T
= ξ, Lς 
between any two vectors in the projective space
ξ, ς  PR  N 1
Example 2: Electric Resistance Networks, Resistance distance
The (squared) norm of a vector
ξ
2
T
= ξ, L ξ 
An electrical network is considered as an
interconnection of resistors.
and an angle
 ξ, ς T 

 = arccos 
 ξ ς 
 T T
The Euclidean distance
ξ  ς T = ξ T  ς T  2ξ, ς T
2
2
2
can be described by the Kirchhoff circuit law,
Probabilistic Euclidean metric structure
Every stochastic automorphism T: [T,A]=0 induces a Euclidean metric structure with the
inner product
ξ, ς T
= ξ, Lς 
between any two vectors in the projective space
ξ, ς  PR  N 1
Example 2: Electric Resistance Networks, Resistance distance
The (squared) norm of a vector
ξ
2
T
= ξ, L ξ 
Given an electric current from a to b of
amount 1 A, the effective resistance of a
network is the potential difference between
a and b,
and an angle
 ξ, ς T 

 ξ ς 
 T T
 = arccos 
The Euclidean distance
ξ  ς T = ξ T  ς T  2ξ, ς T
2
2
2
The effective resistance allows for the
spectral representation:
Tax assessment value of land ($)
The (mean) first-passage time in cities
Manhattan, 2005
Neubeckum, Germany, 2012
(Mean) First passage time
Cities are the biggest editors of our life: built environments constrain our visual space and determine our
ability to move thorough by structuring movement space.
Some places in urban environments are easily accessible, others are not;
well accessible places are more favorable to public,
while isolated places are either abandoned, or misused.
In a long time perspective, inequality in accessibility results in disparity of land prices:
the more isolated a place is, the less its price would be.
In a lapse of time, structural isolation would cause social isolation, as a host society occupies the structural
focus of urban environments, while the guest society would typically reside in outskirts, where the land price
is relatively cheap.
Federal Hall
Times Square
SoHo
East Village
(Mean) first-passage times
in the city graph of
Manhattan
East Harlem
Bowery
Probabilistic Riemannian geometry
Small changes to data in a database/weights of nodes would rise small changes to the
probabilistic geometric representation of database/graph. We can think of them as of smooth
manifolds endowed with a Riemannian metric.
Given a function defined at a node x, we can
extend it to a vicinity of the node.
ui
p
x
uj
Probabilistic Riemannian geometry
Small changes to data in a database/weights of nodes would rise small changes to the
probabilistic geometric representation of database/graph. We can think of them as of smooth
manifolds endowed with a Riemannian metric.
Given a function defined at a node x, we can
extend it to a vicinity of the node.
ui
x
uj
TxM RN-1
p
We can determine a node/entry dependent basis of
vector fields on the tangential probabilistic manifold:
i x  =
ui  x T
ui  x T
 Tx M , ui , x  PRp
N 1
Probabilistic Riemannian geometry
Small changes to data in a database/weights of nodes would rise small changes to the
probabilistic geometric representation of database/graph. We can think of them as of smooth
manifolds endowed with a Riemannian metric.
Given a function defined at a node x, we can
extend it to a vicinity of the node.
ui
x
uj
TxM RN-1
p
We can determine a node/entry dependent basis of
vector fields on the tangential probabilistic manifold:
i x  =
ui  x T
ui  x T
 Tx M , ui , x  PRp
N 1
For the group of translations, the shift operator is given by
the exponential map of the differential operator:
S f x  = exp   i x  f x  = f x   
Probabilistic Riemannian geometry
The node/entry dependent basis of vector fields on
the tangential probabilistic manifold:
ui
x
uj
i x  =
TxM RN-1
ui  x T
ui  x T
 Tx M , ui , x  PRp
N 1
… and then define the metric tensor at each node/entry
(of the database) by
p

u  x, u
g x  =
i
ij
The standard calculus of differential geometry…
The definition of the Levi-Civita connection derived above is equivalent to a
definition of the Christoffel symbols in terms of the metric as
j
 x T
ui  x T u j  x
, ui , x  PRp
N 1
T
The Riemann curvature tensor:
The Ricci curvature tensor & the scalar curvature:
Probabilistic manifolds of negative curvature R  0
Traps: (Mean) First Passage Time > Recurrence Time
.
.
.
i1
ik
i2
(mean) first passage time
.
.
i3
i4
.
.
.
Mazes and labyrinths
It might be difficult to reach a place, but we return to the place quite often
provided we reached that.
“Confusing environments”
Probabilistic manifolds of positive curvature
R0
Landmarks: (Mean) First Passage Time < Recurrence Time
.
.
i1
i2
i3
ik
i4
.
.
.
.
.
.
Landmarks establishes a wayguiding structure that facilitates understanding of the
environment.
“Intelligible environments”
Probabilistic manifolds of positive curvature
An example:
Music = the cyclic group
Z/12Z over the discrete space of notes:
Motivated by the logarithmic pitch perception in humans, music theorists represent pitches using a
numerical scale based on the logarithm of fundamental frequency.
The resulting linear pitch space in which octaves have size 12, semitones have size 1, and the number 69 is
assigned to the note "A4".
A discrete model of music (MIDI) as a simple
Markov chain
In a musical dice game, a piece is generated by patching notes Xt taking values from the set of pitches
that sound good together into a temporal sequence.
First passage times to notes resolve tonality
In music theory, the hierarchical pitch relationships are introduced based on a tonic key, a pitch which is the
lowest degree of a scale and that all other notes in a musical composition gravitate toward. A successful tonal
piece of music gives a listener a feeling that a particular (tonic) chord is the most stable and final.
R0
R0
Tonality structure
of music
The basic pitches for the E minor
scale are "E", "F", "G", "A", "B",
"C", and "D".
The E major scale is based on "E", "F", "G",
"A", "B", "C", and "D".
The A major scale consists of "A", "B", "C",
"D", "E", "F", and "G".
The recurrence time vs. the first passage time
over 804 compositions of 29 Western
composers.
Namely, every pitch in a musical piece is characterized with respect to the entire structure of the Markov chain by its level of accessibility
estimated by the first passage time to it that is the expected length of the shortest path of a random walk toward the pitch from any other
pitch randomly chosen over the musical score. The values of first passage times to notes are strictly ordered in accordance to their role in
the tone scale of the musical composition.
Evolution of networks: Ricci-Hamilton flows
We consider the metric tensor to be functions of a variable which is usually called
"time”, then we obtain the geometric evolution equation (which preserves the
volume of the metric):
R
g ij =  Rij 
gij
N  1
The Ricci flow tends to expand negatively curved regions of the manifold, and
contract positively curved regions
Evolution of networks: Ricci-Hamilton flows
We consider the metric tensor to be functions of a variable which is usually called
"time”, then we obtain the geometric evolution equation (which preserves the
volume of the metric):
R
g ij =  Rij 
gij
N  1
The Ricci flow tends to expand negatively curved regions of the manifold, and
contract positively curved regions
R0
R0
N 1
1
S
“Contraction” of
a “probabilistic
manifold”
“Densification” of
the network of
“positive curvature”
A “collapse” and
decomposition
of the network
of “negative
curvature”
The scalar curvature for ℓ - neighbor random walks
Paths to ALL
neighbors of i at
the distance ℓ are
equi-probable
T  ij = Aij

A
 ij
j
ℓ
R0
ℓ
“Densification” of the
network of “positive
curvature”
R0
A collapse and
decomposition of the
network;
localization of walkers
in the best connected
places
The scalar curvature for ℓ - neighbor random walks
Paths to ALL
neighbors of i at
the distance ℓ are
equi-probable
T  ij = Aij

A
 ij
j
t
R0
t
ℓ
“Densification” of the
network of “positive
curvature”
“time” in the RicciHamilton flow
ℓ
R0
A collapse and
decomposition of the
network;
localization of walkers
in the best connected
places
The scalar curvature for ℓ - neighbor random walks
Paths to ALL
neighbors of i at
the distance ℓ are
equi-probable
T  ij = Aij

A
 ij
j
t
R0
t
ℓ
“time” in the RicciHamilton flow
 
Τ =
R0
A collapse and
decomposition of the
network;
localization of walkers
in the best connected
places
  2     n  ,
1 
~
 =T , T
t = 1   2  n 
Aij
 
Tij =
“Densification” of the
network of “positive
curvature”
ℓ
N
A
s =1

is
Aij j
~  
, T ij = 
max i
The Ricci-Hamilton flow passes through a variety of configurations of the stochastic
automorphisms of the graph.
Conclusion
Evolution by Ricci-Hamilton flow
expanding negatively curved regions
and contracting positively curved
regions
Stochastic automorphisms
of graphs/databases/groups
“For unto every one that
hath shall be given, and he
shall have abundance: but
from him that hath not shall
be taken away even that
which he hath.”
Probabilistic
differential geometry
Matthew 25:29
Euclidean
metric
structure
Probabilistic
geometric
manifolds