Material Detail

Graph complexity for structure and learning

Graph complexity for structure and learning

This video was recorded at 6th Slovenian International Conference on Graph Theory, Bled 2007. The talk will consider ways of bounding the complexity of a graph as measured by the number of partitions satisfying certain properties. The approach adopted uses Vapnik Chervonenkis dimension techniques. An example of such a bound was given by Kleinberg et al (2004) with an application to network failure detection. We describe a new bound in the same vein that depends on the eigenvalues of the graph Laplacian. We show an application of the result to transductive learning of a graph labelling from examples.


  • User Rating
  • Comments
  • Learning Exercises
  • Bookmark Collections
  • Course ePortfolios
  • Accessibility Info

More about this material


Log in to participate in the discussions or sign up if you are not already a MERLOT member.