New Resistance Distances with Global Information on Large Graphs
Loading...
Access rights
openAccess
publishedVersion
URL
Journal Title
Journal ISSN
Volume Title
A4 Artikkeli konferenssijulkaisussa
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
Authors
Date
2016-05
Major/Subject
Mcode
Degree programme
Language
en
Pages
Series
Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, pp. 639-647, JMLR: Workshop and Conference Proceedings ; Volume 51
Abstract
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.Description
Keywords
GRAPHS, Graph mining, Machine learning, Node distance
Other note
Citation
Nguyen, C H & Mamitsuka, H 2016, New Resistance Distances with Global Information on Large Graphs . in A Gretton & C C Robert (eds), Proceedings of the 19th International Conference on Artificial Intelligence and Statistics . JMLR: Workshop and Conference Proceedings, vol. 51, MIT Press, pp. 639-647, International Conference on Artificial Intelligence and Statistics, Cadiz, Spain, 09/05/2016 .