A linear-time algorithm and analysis of graph relative Hausdorff distance

DOI10.1137/19M1248224MaRDI QIDQ5025764zbMATH OpenOpenAlexFDO

Authors

Publication date 3 February 2022

Published in SIAM Journal on Mathematics of Data Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1903.01682

zbMATH Keywords

degree distributiongraph similarity measurenetwork sciencerelative Hausdorff distance

Mathematics Subject Classification ID

Vertex degrees (05C07) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Graph algorithms (graph-theoretic aspects) (05C85) Network design and communication in computer systems (68M10) Deterministic network models in operations research (90B10)

Abstract: Graph similarity metrics serve far-ranging purposes across many domains in data science. As graph datasets grow in size, scientists need comparative tools that capture meaningful differences, yet are lightweight and scalable. Graph Relative Hausdorff (RH) distance is a promising, recently proposed measure for quantifying degree distribution similarity. In spite of recent interest in RH distance, little is known about its properties. Here, we conduct an algorithmic and analytic study of RH distance. In particular, we provide the first linear-time algorithm for computing RH distance, analyze examples of RH distance between pairs of real-world networks as well as structured families of graphs, and prove several analytic results concerning the range, density, and extremal behavior of RH distance values.

Recommendations

• Similarities on graphs: kernels versus proximity measures
• On efficient network similarity measures
• Properties of graph distance measures by means of discrete inequalities
• Measuring similarity between connected graphs: the role of induced subgraphs and complementarity eigenvalues
• Measuring closeness of graphs -- the Hausdorff distance

Cites work

• A distance measure between attributed relational graphs for pattern recognition
• A generative graph model for electrical infrastructure networks
• A graph distance metric combining maximum common subgraph and minimum common supergraph
• A linear time algorithm for the Hausdorff distance between convex polygons
• A Measure of Similarity between Graph Vertices: Applications to Synonym Extraction and Web Searching
• Authoritative sources in a hyperlinked environment
• Emergence of Scaling in Random Networks
• scientific article; zbMATH DE number 1555923 (Why is no real title available?)
• Power-law distributions in empirical data
• Relaxing the uniformity and independence assumptions using the concept of fractal dimension
• The Structure and Function of Complex Networks

Cited in

(8)

• A linear-space algorithm for distance preserving graph embedding
• On efficient network similarity measures
• Similarities on graphs: kernels versus proximity measures
• Similarity analysis of time interval data sets -- a graph theory approach
• Measuring similarity between connected graphs: the role of induced subgraphs and complementarity eigenvalues
• A descriptive tolerance nearness measure for performing graph comparison
• Statistical fidelity: a tool to quantify the similarity between multi-variable entities with application in complex networks
• Studying new classes of graph metrics

Describes a project that uses

Uses Software

• plfit
• SNAP
• GitHub

This page was built for publication: A linear-time algorithm and analysis of graph relative Hausdorff distance

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5025764)