Generalized entropy as network metrics
Joseph E. Johnson
University of South Carolina, Physics Dept.
Full text:
PDF
Last modified: August 15, 2006
Abstract
Networks can be exactly described by a matrix of n2–n nonnegative values representing the connection weights among the n nodes. When a network is large and changing every second such as the Internet, then 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.
More technically expressed, 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 groups: (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.


