Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Modernising Official Statistics: A Complex Challenge Read chapter Read first chapter

2015 | OriginalPaper | Chapter

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

Authors : Guillaume Guex, François Bavaud

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

Publisher: Springer Berlin Heidelberg

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

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.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now
previous chapter Similarity Measures of Concept Lattices
next chapter Resampling Techniques in Cluster Analysis: Is Subsampling Better Than Bootstrapping?
Literature
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
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).
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.
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).
Metadata
Title
Flow-Based Dissimilarities: Shortest Path, Commute Time, Max-Flow and Free Energy
Authors
Guillaume Guex
François Bavaud
Copyright Year
2015
Publisher
Springer Berlin Heidelberg
Book
Data Science, Learning by Latent Structures, and Knowledge Discovery

Print ISBN: 978-3-662-44982-0

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

Copyright Year: 2015

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

Premium Partner

    Image Credits