**FIT****1016 &FIT2044 Advanced Project **

## Semester 2, 2010

### Measuring the complexity of Networks

### Supervisor: Dr. Peter Tischer

Networks
turn up everywhere from gene regulatory networks in bioinformatics, social
interaction networks in studying the spread of disease (and FaceBook), networks
representing the interactions in complex ecologies, to Bayesian Networks in
Machine Learning. How do we compare two networks to say that
one network is either simpler more complex than the other?

One way of doing this is to say that the
complexity of a network depends on how many bits we need to describe the
network. Working out the

smallest
number of bits needed to store some information is known as Data Compression. This project will apply some basic data compression
approaches to the problem of

encoding
networks. The project will not need to produce a program for encoding or decoding
networks. It will be possible to
estimate accurately how many bits would be

needed without actually producing a compressed file.