Vietoris-Ripsa komplexum

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2022. február 10-én felülvizsgált verziótól ; az ellenőrzések 8 szerkesztést igényelnek .

A Vietoris-Rips komplexum , amelyet Vietoris-komplexumnak vagy Rips -komplexumnak is neveznek , egy módja annak, hogy egy ponthalmazban lévő távolságokból topológiai teret alkossunk . Ez egy absztrakt egyszerűsített komplex , amely bármely M metrikus térből és távolságból meghatározható úgy, hogy szimplexet képez bármely véges ponthalmazhoz , amelynek átmérője nem haladja meg a . Vagyis ez az M metrikus tér véges részhalmazainak családja, amely k pontból álló részhalmazként értendő, mint egy ( k − 1)-dimenziós szimplex (egy él két ponthoz, egy háromszög három, egy tetraéder az négy stb.). Ha egy véges S halmaznak az a tulajdonsága, hogy az S -beli pontpárok távolsága nem haladja meg a -t , akkor S szimplexként szerepel a komplexben.

Történelem

A Vietoris-Rips komplexumot eredetileg Vietoris komplexumnak nevezték Leopold Vietoris tiszteletére, aki a homológiaelmélet kiterjesztésének eszközeként vezette be a metrikus terek egyszerű komplexeiből [1] [2] [3] [4] . Miután Ilja Aronovics Rips néhány komplexet használt a hiperbolikus csoportok tanulmányozására , alkalmazásukat Mihail Leonidovics Gromov [5] népszerűsítette , aki Rips-komplexeknek [3] [4] nevezte el őket . A "Vietoris-Rips Complex" név Houseman [3] [4] nevéhez fűződik .

Kapcsolat Cech komplexekkel

A Vietoris–Rips komplexum szorosan összefügg a golyók halmazának Cech komplexével (vagy idegével ) , amelynek szimplexe van a golyók bármely véges részhalmazára, ahol a metszéspont nem nulla. Geodéziailag konvex térben Y bármely altér Vietoris-Rips komplexuma egy adott távolságra ugyanazokkal a pontokkal és élekkel rendelkezik, mint az Y sugarú golyók halmazának Cech komplexe, amelynek középpontja X -ben van . A Cech-komplexussal ellentétben azonban az X Vietoris-Rips komplexe csak X belső geometriájától függ, és nem az X beágyazódásától valamely nagyobb térben .

Példaként vegyünk egy homogén M 3 metrikus teret , amely három pontból áll, amelyek mindegyike egy távolságra van a többitől. Az M 3 -hoz tartozó Vietoris-Rips komplexum tartalmazza az M 3 pontjainak bármely részhalmazának szimplexét , beleértve magát az M 3 háromszöget is . Ha M 3 - at szabályos háromszögként ágyazzuk be az euklideszi síkba , akkor az 1/2 sugarú golyókból álló Cech-komplexus, amelynek középpontja az M 3 pontjaiban van, tartalmazza a Vietoris-Rips komplex összes többi egyszerűségét, de nem tartalmaz egy háromszög, mivel a síkban nincs olyan pont, amely mindhárom golyóhoz tartozna. Ha azonban M 3 ehelyett egy metrikus térbe van beágyazva, amely egy negyedik pontot tartalmaz az M 3 minden egyes pontjától 1/2 távolságra , akkor az 1/2 sugarú golyók Cech komplexe ebben a térben egy háromszöget tartalmaz. Így az M 3 középpontú golyók rögzített sugarú Cech komplexe attól a tértől függ, amelybe M 3 beágyazható, míg a Vietoris-Rips komplex változatlan marad.

Ha egy X metrikus teret beágyazunk egy Y injektív metrikus térbe , akkor a Vietoris-Rips-komplexus a távolságra és az X halmazra egybeesik az Y -ben X -ben középre állított sugarú golyók Cech komplexével . Így bármely M metrikus tér Vietoris-Rips komplexe egyenlő az M tér injektív testében lévő golyók rendszerének Cech komplexével .

Kapcsolódás egységkör grafikonokkal és klikkkomplexusokkal

A Vietoris-Rips komplexum tartalmaz egy élt bármely olyan pontpárhoz, amely egy adott metrikus térben egységnyi távolságra vagy annál kisebb távolságra van. És akkor annak 1-váza a pontjainak egységköreinek grafikonja . Tartalmaz egy szimplexet az egységkör gráf bármely klikkjére , tehát ez az egységkör gráf zászlókomplexuma (vagy klikk komplexuma) [6] . Általánosabban fogalmazva, bármely G gráf klikkkomplexuma a Vietoris-Rips komplexum egy olyan metrikus térhez, amelynek G csúcsai pontok , és G -ben a legrövidebb utak hossza a távolság.

Egyéb eredmények

Ha M egy zárt Riemann-féle sokaság , akkor kellően kis értékek esetén az M -hez tartozó Vietoris-Rips komplex vagy az M -hez kellően közeli terek homotópia ekvivalens magával M -mel [3] [7] .

Chambers, Erickson és Vora [6] hatékony algoritmusokat írt le annak meghatározására, hogy egy adott ciklus összehúzható-e az euklideszi sík bármely véges halmazának Rips komplexében .

Alkalmazások

Mint az egységlemezes gráfok esetében, a Vietoris-Rips komplexumot a számítástechnikában használják a vezeték nélküli ad-hoc hálózatok topológiájának modellezésére . A Vietoris-Rips komplexum egyik előnye ebben az alkalmazásban, hogy csak a kölcsönhatásban lévő csomópontok közötti távolság alapján állítható be anélkül, hogy ismerni kellene a fizikai elhelyezkedésüket. Hátránya, hogy a Cech-komplexussal ellentétben a Vietoris-Rips komplexum nem ad közvetlenül információt a kommunikációs lefedettség hiányosságairól, de ez a hátrány csökkenthető, ha a Cech-komplexumot két Vietoris-Rips komplexum közé helyezzük különböző értékekre . 8] [9] . A Vietoris-Rips komplexek megvalósítása a TDAstats R csomagban található [10] .

A Vietoris-Rips komplexeket a képek jellemzőinek kiemelésére is használják. Ebben az alkalmazásban a komplexum egy nagy dimenziójú metrikus térben épül fel, amelyben a pontok alacsony rendű képi jellemzőket képviselnek [11] .

Jegyzetek

  1. ↑ Vietoris, 1927 .
  2. ↑ Lefschetz, 1942 .
  3. ↑ 1 2 3 4 Hausmann, 1995 .
  4. ↑ 1 2 3 Reitberger, 2002 .
  5. ↑ Gromov, 1987 .
  6. ↑ 12 Chambers, Erickson, Worah, 2008 .
  7. ↑ Latschev, 2001 .
  8. ↑ de Silva, Ghrist, 2006 .
  9. ↑ Muhammad, Jadbabaie, 2007 .
  10. ↑ Wadhwa, Williamson, Dhawan, Scott, 2018 .
  11. ↑ Carlsson, Carlsson, de Silva, 2006 .

Irodalom