Professor
Joseph Johnson
University of South Carolina
Full text:
Not available
Last modified: May 26, 2006
Abstract
1.0 Abstract
A network of N nodes can be exactly described by a matrix of N2–N nonnegative offdiagonal values representing the connection weights among the N nodes. When a network is large and changing every second such as the Internet, the resulting system has tens of millions of values every second. We have found a method for reducing this vast data into a few (2N and fewer) representative values (network entropy spectral functions, or metrics) in order to track the changing topology for attacks, failures and malicious processes.
Our previous work showed that the general linear group, of transformations that are continuously connected to the identity in n dimensions GL(n,R), can be decomposed into two Lie groups1: (1) an n(n1)dimensional Markovtype Lie group M(n) that is defined by preserving the sum of the components of a vector, and (2) the ndimensional Abelian Lie group, A(n), of scaling transformations of the coordinates. With the restriction of the Markovtype Lie algebra parameters to nonnegative values, one obtains exactly all Markov transformations in n dimensions that are continuously connected to the identity. More precisely, this system is now a Markov Monoid (MM) as it is a group without an inverse.
In our current work we show that every network, as defined by its connection matrix Cij, is in one to one correspondence to a single element of the MM Lie algebra of the same dimensionality. It follows that any network matrix, C, is the generator of a continuous Markov transformation that can be interpreted as producing an irreversible flow of a conserved substance among the nodes of the corresponding network. The exponentiation of the MM algebra provides a continuous transformation with rows and columns that constitute normed probability distributions that encapsulate the topology of the network in all orders of expansion. This allows Shannon and generalized (Renyi) entropy functions to be defined on the column and row probability distributions. These (2N) generalized entropies (along with derivatives and functions of these entropies) for these Markov transformations become metrics for the topology of the corresponding network encapsulating all of the network topology in a more hierarchical way. Thus we have tightly connected the fields of Lie groups and algebras, Markov transformations, conserved flows, diffusion transformations, and generalized entropies, on the one hand, to network theory and network topology. We are specifically interested in applying these generalized entropies as metrics for the tracking of network topological changes such as one would expect under attacks and intrusions on internets. We will show our experimental results of monitoring these entropy spectral distributions using two internet tracking applications.


