Grafer och nätverksdata är allmänt förekommande inom ett brett spektrum av vetenskapliga områden och tillämpningsområden. Ofta i praktiken kan en inmatningskurva betraktas som en observerad ögonblicksbild av en (potentiellt kontinuerlig) dold domän eller process. Efterföljande analys, bearbetning och slutsatser utförs sedan på denna observerade graf. I detta papper förespråkar vi perspektivet att en observerad graf ofta är en bullrig version av några diskretized 1-skelett av en dold domän, och särskilt kommer vi att överväga följande naturliga nätverksmodell: Vi antar att det finns en sann graf G * som är en viss närhet graf för punkter som samplas från en dold domän X ; medan den observerade grafen G är en Erdös-Rényi typ perturbed version av G *. Vår nätverksmodell är relaterad till, och något generaliserar, den mycket hyllade småskaliga nätverksmodellen som ursprungligen föreslogs av Watts och Strogatz. Den huvudsakliga frågan vi vill besvara är dock ortogonal till de vanliga studierna av nätverksmodeller (som ofta fokuserar på att karakterisera / förutsäga beteenden och egenskaper i verkliga nätverk). Specifikt siktar vi på att återställa den metriska strukturen av G * (som speglar det dolda utrymmet X som vi kommer att visa) från den observerade grafen G. Vårt huvudresultat är att en enkel filtreringsprocess baserad på Jaccard-indexet kan återställa detta metriska inom en multiplikativ faktor på 2 under vår nätverksmodell. Vårt arbete tar ett steg mot den allmänna frågan om att sluta sig till strukturen av ett dolt utrymme från dess observerade bullriga graf representation. Dessutom ger våra resultat också en teoretisk förståelse för Jaccard-Index-baserade denoiserande metoder.
Vårt arbete liknar Parthasarathy et al. REF i att de använder Jaccard-indexet i en observerad graf för att uppskatta den underliggande grafens geodesiska avstånd.
A quest to unravel the metric structure behind perturbed networks
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}