Transcript A High Security Information System | Joe Johnson

DARPA
Oasis PI Meeting
Hilton Head, SC
March 2002
Network
Classifications & Flows as
Markov Lie Algebra
Transformations
DARPA OASIS PI Meeting
Hilton Head SC
Tuesday March 12, 2002
Joseph E. Johnson, PhD
Introduction to
Lie Groups & Algebras
Lie Groups and Lie Algebras
1.
2.
3.
Group theory provides a representation of
both exact and approximate symmetries using
continuous and discrete transformations.
Groups have a multiplication operation with
closure, associatively, a unit, and an inverse.
Lie Groups / Lie Algebras represent
transformations that are continuously
connected to the identity (thus infinite
dimensional).
Examples:






Rotation Group x2 + y2 + z2 is invariant
Lorentz Group c2t2 - x2 - y2 - z2 is invariant (relativity).
Poincare Group c2dt2 - dx2 - dy2 - dz2 is invariant thus
allowing translations.
Unitary Group x*x + y*y + …. Or <a|b> invariant
including SU3, SUn (quantum mechanics)
Heisenberg Lie Algebra [x,p] = I
Harmonic Oscillator Algebra a+, a , N, I
Introduction to
Markov Processes
Markov Transformations




A Markov matrix transformation M preserves the sum of the
non-negative components of a vector upon which it acts with
no negative transformed components (thus x + y + z + w +…
is invariant) .
It follows that a Markov transformation must itself have nonnegative components with the sum of elements in each column
equal to 1.
Markov transformations have no inverse and thus they do not
form a group.
Markov transformations are useful in a variety of problems: such
as economic and population redistribution.
Markov Type Lie Groups
(Johnson J.E., Jour. Math. Phys.1985)





In the paper above, I suggested relaxing the non-negative condition to get a
‘Markov like’ Lie Group that preserves Sum xi but which allows for
unphysical components.
A careful choice of the associated Lie Algebra generators Lij gives Markov
transformations when non-negative combinations of Lij are used to generate
the transformation.
Thus the term: Markov-Type Lie Algebra or Group
One can see the connection to diffusion. The lack of an inverse results in a
loss of ‘information’.
Lij along with Lii diagonal generators form a basis of GL(n,R) = Markov
Subgroup M(n,R) + an Abelian Scale (growth) group A(n,r) – a new
decomposition of GL(n,R).
Network or Graph Theory
Adjacency (or Connectivity)
Matrix for a Network (graph)





An undirected graph consists of a set of points or
nodes (numbered 1, 2, …) connected by lines.
If node i is connected to node j then we represent this
with a matrix Lij = 1 else =0. Thus Lij contains the
topological connectivity of the graph.
The diagonal Lii is taken as 0 or 1 if a node is
considered to be (or not to be) connected to itself.
It also contains the superfluous numbering of nodes.
It is an unsolved problem to tell, from Lij, if two graphs
are topologically equivalent.
A Network as a MarkovDynamical Informational Flow




If we take the diagonal elements of the connectivity matrix so
that the sum over each column is ‘0’ then Lij is a Markov Lie
algebra generator for a transformation that preserves a vector
sum xi.
We could take this vector to be the information stored at the
node xi or water or electrical charge or whatever.
This gives us a dynamical system where information is moved
from node to node by equal bandwidth by all connections. L is
the time evolution operator with x(t) = exp(tL).
The eigenvectors are linear combinations of nodes with
information content decreasing at the rate of exp(tz) where z is
the associated eigenvalue. There is a strong analogy with exp(tH)
in quantum theory.
Network Dynamics



This work extends the customary graph theory
with the associated model of information (or
water or population) flow of a conserved
quantity.
Thus one now has a dynamical physical model
and interpretation for the connectivity matrix as
well as the power of Lie group theory that can
be applied to network dynamics and topology.
The choice of 0 or 1 as diagonal elements can
also be achieved within this theory and
represents exponential growth or decay of the
quantity at that node.
Asymmetric & Directed Graphs &
Information Nonconservation


We can readily extend this work to dynamical problems on:
 Different data transfer rates between nodes where Lij is not
equal to 1 but is still symmetric.
 Directed graphs where Lij is not symmetric (but rather has
the values 0 and 1 indicating flow direction).
 Graphs which allow for the creation and annihilation of
information at the nodal points.
With these collective generalizations, one obtains the
transformations of GL(n,R) with a restricted Lie algebra
parameter space.
An Approach to
Network Classification
Self Connectivity Defined




It is known that these eigenvalue sets are almost but not
quite isomorphic to the topologically different graphs
as some graphs are isospectral.
Define L1ij = 1 or 0 as before when i and j are not
equal.
Save the diagonal vector and reset the diagonal terms
=0 because we do not want to allow a transition from a
node back to itself.
Now define L2 = L1 L1 via normal matrix multiplication
and set the diagonal terms =0. Then define L3 = L1 L2
+ L2 L1 , etc up to L2n-2 where n is the number of
nodes.


This gives a sequence of 2n-2 matrices. We
require 2n-2 possible transitions to ‘feel out’ the
paths from a node and back to that node again.
We now extract the diagonal components to
construct an (2n-2) x n matrix with columns
labeled by node number and the rows labeled by
the power of the matrix.
Self-Connectivity Matrix Defined



We now reorder the columns by sorting the values (ascending) in
order of the first row. Then for each set of identical values in
the first row, we resort the columns in the second row
(ascending).
The final matrix gives a relatively unique order to the nodes but
it is not proven that it is unique. To the extent that the new
column order is unique, one obtains a natural numbering of the
nodes.
This matrix will constitute the first part of identification of the
topology. We call this the Self-Connectivity Matrix.
Interconnectivity Matrices
Defined





Return now to the first n powers of L including the
first power.
Note that each power is a symmetrized product of
matrices and thus is symmetric and has real eigenvalues.
We call this the n^2 matrix of eigenvalues, the
interconnectivity eigenvalue matrix as it describes
interconnectivities.
It is independent of the numbering of the nodes.
Each of the eigenvalue sets represents the normal
nodes of a Markov transformation that takes n steps as
an infinitesimal motion.



Set all diagonal values equal to the negative of the sum
of the remaining column elements in that matrix thus
giving a set of Markov Lie generators.
Find the eigenvalues and eigenvectors of these matrices
and group these n eigenvectors as rows in a new matrix
and sort each row by ascending associated eigenvalues
(placed in an associated column ‘0’) for each power.
This gives an (n+1) x n^2 matrix of the eigenvalues and
eigenvectors that correspond to dynamic evolution of
the system when one dynamically evolves with multiple
node connectivity.
Graph Description




Neither the n x (2n-1) self connectivity matrix nor the n x n interconnectivity
eigenvalues are dependent upon the ordering of the nodes but only on the
topology.
It is our hope that this removes much of the isospectral aspects of a graphs
description.
We would adjoin the sequence of eigenvector matrices at each of the n levels
where one sorts the rows by ascending order of the associated eigenvalues,
for each power, and sorts the columns by the node ordering prescribed by the
final ordering that results from the self connectivity matrix as described
above.
Any degeneracy that remains from the self-connectivity matrix is to be
resolved by ordering the components of the eigenvectors by the lowest order
values that differ.


We are studying the extent to which this method
removes the degeneracy's and identifies the
topology of the graph.
We are also studying the utility of the
connectivity matrix as a Lie generator for
transformation flows of information on a
network.

Thank You