Abstrakt. Detta arbete presenterar ett nytt förfarande för beräkning (1) avstånd mellan noder av en viktad, oriktad graf, kallad Euclidean Communte Time Distance (ECTD), och (2) en subrymdsprojicering av noderna i grafen som bevarar så mycket varians som möjligt, i termer av ECTD - en huvudkomponent analys av grafen. Det är baserat på en Markov-kedja modell av slumpmässig promenad genom grafen. Modellen tilldelar övergångssannolikheter till länkarna mellan noder, så att en slumpmässig gångare kan hoppa från nod till nod. En kvantitet, som kallas den genomsnittliga pendla tiden, beräknar den genomsnittliga tid som tas av en slumpmässig vandrare för att nå node j för första gången när man börjar från node i, och kommer tillbaka till node i. Kvadratroten av denna mängd, ECTD, är ett avståndsmått mellan två noder, och har den trevliga egenskapen att minska när antalet vägar som förbinder två noder ökar och när "längden" av varje väg minskar. ECTD kan beräknas från pseudoinversen av Laplacian-matrisen i grafen, som är en kärna. Vi definierar slutligen huvudkomponentanalysen (PCA) av en graf som den subrymdsprojicering som bevarar så mycket varians som möjligt, i termer av ECTD. Denna graf PCA har några intressanta länkar med spektral grafteori, särskilt spektral klustring.
En annan metod är tolkningen av Principal Component Analysis (PCA) på grafer REF, som återigen länkar grafstrukturen till en subrymd som spänns över av de översta eigenvectors av grafen Laplacian.
The principal components analysis of a graph, and its relationships to spectral clustering
{'venue': 'Proceedings of the 15th European Conference on Machine Learning (ECML 2004). Lecture Notes in Artificial Intelligence', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}