The similarity distance on graphs and graphons

Channel:
Microsoft Research
Subscribers:
344,000
Published on ● Video Link: https://www.youtube.com/watch?v=pWpzUz0x3EM


Duration: 1:04:14
2,359 views
31

The similarity distance measures how "similar" two nodes in a dense graph are. Selecting an epsilon-net with respect to this metric is a useful tool in algorithms for very large graphs. For example, the Voronoi cells of such a set form a weak regularity partition. One can introduce the same distance on graph limits (graphons). This defines a compact metric space, whose dimension is an important complexity measure of the graphon and of any graph sequence converging to it. Graphons for which this dimension is finite have polynomial-size weak regularity partitions. We will state some sufficient conditions, some proven and some conjectured, for this dimension to be finite.



Other Videos By Microsoft Research


2016-08-04Faculty Summit 2016 - Computing with exotic technologies and platforms
2016-08-01Programming Devices and Services with P - Lecture 2
2016-08-01Practical Statically-checked Deterministic Parallelism
2016-08-01Real-time Air Quality Monitoring Network Using Low-Cost Devices
2016-08-01Experiments in Indoor Localization and Vehicle Classification
2016-08-01Achieving Household Energy Breakdown at Scale
2016-08-01Verifying Constant-Time Implementations
2016-07-28Quantum Computation for Quantum Chemistry: Status, Challenges, and Prospects - Session 3
2016-07-28Asymptotic behavior of the Cheeger constant of super-critical percolation in the square lattice
2016-07-28Recovering Washington’s Wolves & Preserving the Critical Link
2016-07-28The similarity distance on graphs and graphons
2016-07-28Neural Acceleration for General-Purpose Approximate Programs
2016-07-28Snow Hydrology at the Scale of Mountain Ranges
2016-07-28Vote Privacy, Revisited: New Definitions, Tools and Constructions
2016-07-28Dispelling an Old Myth about an Ancient Algorithm
2016-07-28Behavior Based Authentication using Gestures and Signatures
2016-07-28Approximating the Expansion Profile and Almost Optimal Local Graph Clustering
2016-07-28Stochastic Dual Coordinate Ascent and its Proximal Extension for Regularized Loss Minimization
2016-07-28A Practical Approach to Reduce the Power Consumption of LCD Displays
2016-07-28CryptDB: Processing Queries on an Encrypted Database
2016-07-28Performing Time, Space and Light


Tags:
microsoft research