New Resistance Distances with Global Information on Large Graphs

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussavertaisarvioitu

Tutkijat

Organisaatiot

  • Bioinformatics Center, Institute for Chemical Research, Kyoto University

Kuvaus

We consider the problem that on large random geometric graphs, random walk-based distances between nodes do not carry global information such as cluster structure. Instead, as the graphs become larger, the distances contain mainly the obsolete information of local density of the nodes. Many distances or similarity measures between nodes on a graph have been proposed but none are both proved to overcome this problem or computationally feasible even for small graphs. We propose new distance functions between nodes for this problem. The idea is to use electrical flows with different energy functions. Our proposed distances are proved analytically to be metrics in $L^p$ spaces, to keep global information, avoiding the problem, and can be computed efficiently for large graphs. Our experiments with synthetic and real data confirmed the theoretical properties and practical performances of our proposed distances.

Yksityiskohdat

AlkuperäiskieliEnglanti
OtsikkoProceedings of the 19th International Conference on Artificial Intelligence and Statistics
ToimittajatArthur Gretton, Christian C. Robert
TilaJulkaistu - toukokuuta 2016
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisuussa
TapahtumaInternational Conference on Artificial Intelligence and Statistics - Cadiz, Espanja
Kesto: 9 toukokuuta 201611 toukokuuta 2016
Konferenssinumero: 19
http://www.aistats.org/aistats2016/

Julkaisusarja

NimiJMLR: Workshop and Conference Proceedings
KustantajaThe MIT Press
Vuosikerta51
ISSN (elektroninen)1938-7228

Conference

ConferenceInternational Conference on Artificial Intelligence and Statistics
LyhennettäAISTATS
MaaEspanja
KaupunkiCadiz
Ajanjakso09/05/201611/05/2016
www-osoite

Lataa tilasto

Ei tietoja saatavilla

ID: 4127616