Material Detail
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.
Quality
- User Rating
- Comments
- Learning Exercises
- Bookmark Collections
- Course ePortfolios
- Accessibility Info
More about this material
- Mobile Compatibility:
- Not specified at this time
- Language:
- English
- Cost Involved:
- No
- Source Code Available:
- No
- Accessibility Information Available:
- Unknown
- Creative Commons:
-
This work is licensed under a Attribution-NonCommercial-NoDerivs 3.0 United States
