FIT1016 &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.