Metriska grafer är allmänt förekommande inom vetenskap och teknik. Till exempel är många data hämtade från dolda utrymmen som är grafliknande, såsom den kosmiska webben. En metriska graf erbjuder ett av de enklaste men ändå meningsfulla sätten att representera den icke-linjära struktur som döljs bakom data. I det här dokumentet föreslår vi ett nytt avstånd mellan två finita metriska grafer, så kallade persistens-förvrängningsavstånd, som bygger på en topologisk idé. Detta topologiska perspektiv tillsammans med den metriska rymdsynvinkeln ger en ny vinkel till grafens matchande problem. Vår persistens-förvrängning avstånd har två egenskaper som inte delas med tidigare metoder: För det första är det stabilt mot perturbations av indata grafen mätvärden. För det andra är det ett kontinuerligt avståndsmått, i den meningen att det definieras på en justering av de underliggande utrymmena för inmatningsgrafer, i stället för bara deras noder. Detta gör vår persistent-distortion avstånd robust mot, till exempel, olika diskretizations av samma underliggande graf. Trots att inmatningsgraferna betraktas som kontinuerliga utrymmen, det vill säga att ta alla punkter i beaktande, visar vi att vi kan beräkna persistens-förvrängning avstånd i polynom tid. Tiden komplexitet för det diskreta fallet där endast graf noder anses är mycket snabbare. Vi tillhandahåller också några preliminära experimentella resultat för att visa användningen av den nya avståndsmätaren.
I REF visar Dey, Shi och Wang att distorsionsavståndet för persistens är stabilt med avseende på förändringar i indatametriska grafer mätt med Gromov-Hausdorff-avståndet.
Comparing Graphs via Persistence Distortion
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}