Information Technology Reference
In-Depth Information
Networks, Markov Lie Monoids, and
Generalized Entropy
Joseph E. Johnson
University of South Carolina,
Department of Physics,
Columbia, South Carolina 29208
jjohnson@sc.edu
Abstract.
The continuous general linear group in n dimensions can be
decomposed into two Lie groups: (1) an n(n-1) dimensional 'Markov type' Lie
group that is defined by preserving the sum of the components of a vector, and
(2) the n dimensional Abelian Lie group, A(n), of scaling transformations of the
coordinates. With the restriction of the first Lie algebra parameters to non-
negative values, one obtains exactly all Markov transformations in n
dimensions that are continuously connected to the identity. In this work we
show that every network, as defined by its C matrix, is in one to one
correspondence to one element of the Markov monoid 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 among the nodes of the corresponding network.
1 Introduction
There is a broad spectrum of mathematical problems that involve the general theory
of networks and the associated classification, optimization, and potentially even their
dynamical evolution. By a network we mean a set of n nodes (points), some pairs of
which are connected with a representative non-negative weight or strength of
connection. Such a network can be represented by a connection (or connectivity, or
adjancy) matrix C
ij
whose off-diagonal elements give the non-negative 'strength' of
the connection between nodes i and j in the network. Often that 'strength' or 'weight'
is as simple as a '1' for a connection and a '0' otherwise. A network can be
'undirected' or 'directed' depending upon whether C
ij
is symmetric or not thus
indicating respectively a symmetric or asymmetrical connection between i and j.
There may or may not exist a well defined 'metric distance' between the nodes or,
equivalently, positions for the points in a metric space of some dimensionality, such
as airports for airline networks, or substations for power or utility distribution
networks. It is well known that the classification of different network topologies
cannot be accomplished with just the eigenvalue spectra of the connectivity matrix as
there are topologically different networks with as few as five nodes that have the
same eigenvalue spectra. One root of the network problem is that although the
network is exactly defined by the C matrix, there are n! different C matrices that
correspond to the same topology because different C matrices result from different
