nach oben

Erschienen in:

2015 | OriginalPaper | Buchkapitel

Flow-Based Dissimilarities: Shortest Path, Commute Time, Max-Flow and Free Energy

verfasst von : Guillaume Guex, François Bavaud

Erschienen in: Data Science, Learning by Latent Structures, and Knowledge Discovery

Verlag: Springer Berlin Heidelberg

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Random-walk based dissimilarities on weighted networks have demonstrated their efficiency in clustering algorithms. This contribution considers a few alternative network dissimilarities, among which a new max-flow dissimilarity, and more general flow-based dissimilarities, freely mixing shortest paths and random walks in function of a free parameter—the temperature. Their geometrical properties and in particular their squared Euclidean nature are investigated through their power indices and multidimensional scaling properties. In particular, formal and numerical studies demonstrate the existence of critical temperatures, where flow-based dissimilarities cease to be squared Euclidean. The clustering potential of medium range temperatures is emphasized.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Similarity Measures of Concept Lattices

Nächstes Kapitel Resampling Techniques in Cluster Analysis: Is Subsampling Better Than Bootstrapping?

Alamgir, M., & Von Luxburg, U. (2011). Phase transition in the family of p-resistances. In Neural Information Processing Systems (NIPS 2011) (pp. 379–387).

Bavaud, F. (2010). Euclidean distances, soft and spectral clustering on weighted graphs. In Proceedings of ECML-PKDD 2010. Lecture notes in computer science (Vol. 6321, pp. 103–118).

Bavaud, F., & Guex, G. (2012). Interpolating between random walks and shortest paths: A path functional approach. In Proceedings of SocInfo 2012. Lecture notes in computer science (Vol. 7710, pp. 68–81).

Bavaud, F., & Xanthos, A. (2005). Markov associativities. Journal of Quantitative Linguistics, 12, 123–137.CrossRef

Berger, J., & Snell, J. L. (1957). On the concept of equal exchange. Behavioral Science, 2, 111–118.CrossRefMathSciNet

Boley, D., Ranjan, G., & Zhang, Z.-L. (2011). Commute times for a directed graph using an asymmetric Laplacian. Linear Algebra and its Applications, 435, 224–242.CrossRefMATHMathSciNet

Chandra, A. K., Raghavan, P., Ruzzo, W. L., Smolensky, R., & Tiwari, P. (1989). The electrical resistance of a graph captures its commute and cover times. In Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing (STOC ’89) (pp. 574–586).

Chebotarev, P. (2010). A class of graph-geodetic distances generalizing the shortest-path and the resistance distances. Discrete Applied Mathematics, 159, 295–302.CrossRefMathSciNet

Critchley, F., & Fichet (1994) The partial order by inclusion of the principal classes of dissimilarity on a finite set, and some of their basic properties. In B. van Cutsem (Ed.), Classification and dissimilarity analysis. LNS (Vol. 93, pp. 5–65).

Deza, M., & Deza, E. (2009). Encyclopedia of distances. New York: Springer.CrossRefMATH

Deza, M., & Laurent, M. (1997). Geometry of cuts and metrics. New York: Springer.CrossRefMATH

Doyle, P., & Snell, J. (1984). Random walks and electric networks. Washington, DC: Mathematical Association of America.MATH

Françoisse, K., Kivimäki, I., Mantrach, A. Rossi, F., & Saerens, M. (2013). A bag-of-paths framework for network data analysis. arXiv:1302.6766.

Gastner, M. T., & Newman, M. E. J. (2006). The spatial structure of networks. The European Physical Journal B, 49, 247–252.CrossRef

Joly, S., & Le Calvé, G. (1986). Etude des puissances d’une distance. Statistique et analyse des donnes, 11, 30–50.MATH

Kivimäki, I., Shimbo, M., & Saerens, M. (2012). Developments in the theory of randomized shortest paths with a comparison of graph node distances. arXiv:1212.1666.

Klein, D. J., & Zhu, H. Y. (1998). Distances and volumina for graphs. Journal of Mathematical Chemistry, 23, 179–195.CrossRefMATHMathSciNet

Lew, J. S. (1978). Some counterexamples in multidimensional scaling. Journal of Mathematical Psychology, 17, 247–254.CrossRefMATHMathSciNet

Li, Y., Zhang, Z.-L., & Boley, D. (2011). The routing continuum from shortest-path to all-path: A unifying theory. 31st International Conference on Distributed Computing Systems (ICDCS) (pp. 847–856).

Liu, S., Matzavinos, A., & Sethuraman, S. (2013). Random walk distances in data clustering and applications. Advances in Data Analysis and Classification, 7, 83–108.CrossRefMATHMathSciNet

Meila, M. (2003). Comparing clusterings by the variation of information. In Proceedings of the Sixteenth Annual Conference of Computational Learning Theory (COLT). New York: Springer.

Saerens, M., Achbany, Y., Fouss, F., & Yen, L. (2009). Randomized shortest-path problems: Two related models. Neural Computation, 21, 2363–2404.CrossRefMATHMathSciNet

Torgeson, W. S. (1958). Theory and methods of scaling. New York: Wiley.

Yen, L., Saerens, M., Mantrach, A., & Shimbo, M. (2008). A family of dissimilarity measures between nodes generalizing both the shortest-path and the commute-time distances. In Proceedings of the 14th SIGKDD International Conference on Knowledge Discovery and Data Mining (pp. 785–793).

Titel: Flow-Based Dissimilarities: Shortest Path, Commute Time, Max-Flow and Free Energy
verfasst von: Guillaume Guex
François Bavaud
Verlag: Springer Berlin Heidelberg
Buch: Data Science, Learning by Latent Structures, and Knowledge Discovery
Print ISBN: 978-3-662-44982-0

Electronic ISBN: 978-3-662-44983-7

Copyright-Jahr: 2015
DOI: https://doi.org/10.1007/978-3-662-44983-7_9

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"