Computer Laboratory

Technical reports

On joint diagonalisation for dynamic network analysis

Damien Fay, Jérôme Kunegis, Eiko Yoneki

October 2011, 12 pages

Abstract

Joint diagonalisation (JD) is a technique used to estimate an average eigenspace of a set of matrices. Whilst it has been used successfully in many areas to track the evolution of systems via their eigenvectors; its application in network analysis is novel. The key focus in this paper is the use of JD on matrices of spanning trees of a network. This is especially useful in the case of real-world contact networks in which a single underlying static graph does not exist. The average eigenspace may be used to construct a graph which represents the `average spanning tree' of the network or a representation of the most common propagation paths. We then examine the distribution of deviations from the average and find that this distribution in real-world contact networks is multi-modal; thus indicating several modes in the underlying network. These modes are identified and are found to correspond to particular times. Thus JD may be used to decompose the behaviour, in time, of contact networks and produce average static graphs for each time. This may be viewed as a mixture between a dynamic and static graph approach to contact network analysis.

Full text

PDF (0.8 MB)

BibTeX record

@TechReport{UCAM-CL-TR-806,
  author =	 {Fay, Damien and Kunegis, J{\'e}r{\^o}me and Yoneki, Eiko},
  title = 	 {{On joint diagonalisation for dynamic network analysis}},
  year = 	 2011,
  month = 	 oct,
  url = 	 {http://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-806.pdf},
  institution =  {University of Cambridge, Computer Laboratory},
  number = 	 {UCAM-CL-TR-806}
}