Det andra eigenvärdet av Laplacia-matrisen och dess tillhörande eigenvektor är grundläggande drag i en oriktad graf, och som sådan har de funnit en utbredd användning inom vetenskaplig databehandling, maskininlärning och dataanalys. I många tillämpningar har dock grafer som uppstår flera lokala regioner av intresse, och den andra eigenvector kommer vanligtvis att misslyckas med att ge information finjusterad till varje lokal region. I detta dokument introducerar vi en lokalt objektiv analog till den andra eigenvektorn, och vi visar dess användbarhet när det gäller att lyfta fram lokala egenskaper hos datagrafer på ett halvövervakat sätt. För att göra det, ser vi först den andra eigenvector som lösningen på ett begränsat optimeringsproblem, och vi införlivar den lokala informationen som en ytterligare begränsning; vi karakteriserar sedan den optimala lösningen på detta nya problem och visar att det kan tolkas som en generalisering av en Personaliserad PageRank vektor; och slutligen, som en följd av detta, visar vi att lösningen kan beräknas i nästan linjär tid. Dessutom visar vi att denna lokalt biased vektor kan användas för att beräkna en approximation till den bästa partitionen nära ett ingångsfrö som sätts på ett liknande sätt som det sätt på vilket den andra eigenvector av Laplacian kan användas för att få en approximation till den bästa partitionen i hela inmatningskurvan. En sådan primitiv är användbar för att identifiera och förfina kluster lokalt, eftersom det gör det möjligt för oss att fokusera på en lokal region av intresse på ett halvövervakat sätt. Slutligen ger vi en detaljerad empirisk utvärdering av vår metod genom att visa hur den kan tillämpas på att hitta lokalt opartiska sparse skär runt ett input vertex frö som finns i sociala nätverk och informationsnätverk.
Mahoney, Orecchia och Vishnoi REF introducerar en lokalt objektiv analog till den andra eigenvektorn för att extrahera lokala egenskaper hos datagrafer nära ett inmatningsfrö som sätts genom att hitta ett glest snitt, och tillämpa metoden för halvövervakad bildsegmentering och lokal samhällsextraktion.
A Local Spectral Method for Graphs: with Applications to Improving Graph Partitions and Exploring Data Graphs Locally
{'venue': None, 'journal': 'arXiv: Data Structures and Algorithms', 'mag_field_of_study': ['Mathematics', 'Computer Science']}