nach oben

Erschienen in:

2022 | OriginalPaper | Buchkapitel

A Simple Extension of the Bag-of-Paths Model Weighting Path Lengths by a Poisson Distribution

verfasst von : Sylvain Courtain, Marco Saerens

Erschienen in: Complex Networks & Their Applications X

Verlag: Springer International Publishing

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

This work extends the bag-of-paths model [14] by introducing a weighting of the length of the paths in the network, provided by a Poisson probability distribution. The main advantage of this approach is that it allows to tune the mean path length parameter which is most relevant for the application at hand. Various quantities of interest, such as the probability of drawing a path from the bag of paths, or the join probability of sampling any path connecting two nodes of interest, can easily be computed in closed form from this model. In this context, a new distance measure between nodes of a network, considering a weighting factor on the length of the paths, is defined. Experiments on semi-supervised classification tasks show that the introduced distance measure provides competitive results compared to other state-of-the-art methods. Moreover, a new interpretation of the logarithmic communicability similarity measure [17] is proposed in terms of the new model.

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 The Fréchet Mean of Inhomogeneous Random Graphs

Nächstes Kapitel Spectral Rank Monotonicity on Undirected Networks

If the graph G is undirected, each of its undirected edge \(i \leftrightarrow j\) is considered as a set of two different directed edges going in opposite directions, \(i \rightarrow j\) and \(j \rightarrow i\).

As, for instance, a simple bag-of-words model in information retrieval or a naive Bayes classification model in data science.

In general, this matrix is non-symmetric.

The communicability kernel is also related to the exponential diffusion kernel [22].

The communicability kernel has also been investigated, but we have not included its results as these are worse compared to its logarithmic version.

We use the LIBSVM library [3] with the options ‘-s 0’ and ‘-t 4’.

Note that the kernels obtained through this transformation are already centered.

We apply the centering transformation \(\mathbf {K}=\mathbf {H}\mathbf {K}\mathbf {H}\) to the Gaussian kernel where \(\mathbf {H} = \mathbf {I} - \mathbf {e} \mathbf {e}^{\mathrm {T}}/n\) is the centering matrix, \(\mathbf {e}\) is a column vector full of 1’s, \(\mathbf {I}\) is the identity matrix and n is the number of nodes.

Akamatsu, T.: Cyclic flows, Markov process and stochastic traffic assignment. Transp. Res. B 30(5), 369–386 (1996)CrossRef

Borg, I., Groenen, P.J.F.: Modern Multidimensional Scaling. SSS, Springer, New York (2005). https://doi.org/10.1007/0-387-28981-XCrossRefMATH

Chang, C.C., Lin, C.J.: LIBSVM: a library for support vector machines. ACM Trans. Intell. Syst. Technol. 2, 27:1–27:27 (2011)

Chebotarev, P., Shamis, E.: The matrix-forest theorem and measuring relations in small social groups. Autom. Remote Control 58(9), 1505–1514 (1997)MATH

Chebotarev, P.: A class of graph-geodetic distances generalizing the shortest-path and the resistance distances. Discret. Appl. Math. 159(5), 295–302 (2011)MathSciNetCrossRefMATH

Consul, P.C.: Generalized Poisson Distributions: Properties and Applications. Marcel Dekker (1989)

Courtain, S., Guex, G., Kivimaki, I., Saerens, M.: Relative entropy-regularized optimal transport on a graph: a new algorithm and an experimental comparison. ArXiv preprint arXiv:0912.0238v9 (2021)

Courtain, S., Leleux, P., Kivimaki, I., Guex, G., Saerens, M.: Randomized shortest paths with net flows and capacity constraints. Inf. Sci. 556, 341–360 (2020)MathSciNetCrossRefMATH

Courtain, S., Lebichot, B., Kivimäki, I., Saerens, M.: Graph-based fraud detection with the free energy distance. In: Cherifi, H., Gaito, S., Mendes, J.F., Moro, E., Rocha, L.M. (eds.) COMPLEX NETWORKS 2019. SCI, vol. 882, pp. 40–52. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-36683-4_4CrossRef

10.

Demšar, J.: Statistical comparisons of classifiers over multiple data sets. J. Mach. Learn. Res. 7, 1–30 (2006)MathSciNetMATH

11.

Devooght, R., Mantrach, A., Kivimäki, I., Bersini, H., Jaimes, A., Saerens, M.: Random walks based modularity: application to semi-supervised learning. In: Proceedings of the 23rd International World Wide Web Conference (WWW 2014), pp. 213–224 (2014)

12.

Estrada, E., Hatano, N.: Communicability in complex networks. Phys. Rev. E 77(3), 036111 (2008)MathSciNetCrossRef

13.

Fouss, F., Pirotte, A., Renders, J.M., Saerens, M.: Random-walk computation of similarities between nodes of a graph, with application to collaborative recommendation. IEEE Trans. Knowl. Data Eng. 19(3), 355–369 (2007)CrossRef

14.

Francoisse, K., Kivimki, I., Mantrach, A., Rossi, F., Saerens, M.: A bag-of-paths framework for network data analysis. Neural Netw. 90, 90–111 (2017)CrossRefMATH

15.

Guex, G., Courtain, S., Saerens, M.: Covariance and correlation Kernels on a graph in the generalized bag-of-paths formalism. J. Complex Netw. 8(6), 1–46 (2021)

16.

Guex, G., Kivimäki, I., Saerens, M.: Randomized optimal transport on a graph: framework and new distance measures. Netw. Sci. 7(1), 88–122 (2019)CrossRef

17.

Ivashkin, V., Chebotarev, P.: Do logarithmic proximity measures outperform plain ones in graph clustering? In: Kalyagin, V.A., Nikolaev, A.I., Pardalos, P.M., Prokopyev, O.A. (eds.) NET 2016. SPMS, vol. 197, pp. 87–105. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-56829-4_8CrossRef

18.

Ivashkin, V., Chebotarev, P.: Dissecting graph measures performance for node clustering in LFR parameter space (2021). Preprint available at https://openreview.net/forum?id=HkUfnZFt1Rw

19.

Kivimäki, I., Lebichot, B., Saramäki, J., Saerens, M.: Two betweenness centrality measures based on randomized shortest paths. Sci. Rep. 6(1), 1–15 (2016)CrossRef

20.

Kivimäki, I., Shimbo, M., Saerens, M.: Developments in the theory of randomized shortest paths with a comparison of graph node distances. Physica A 393, 600–616 (2014)CrossRefMATH

21.

Klein, D.J., Randic, M.: Resistance distance. J. Math. Chem. 12(1), 81–95 (1993)MathSciNetCrossRef

22.

Kondor, R.I., Lafferty, J.: Diffusion kernels on graphs and other discrete structures. In: Proceedings of the 19th International Conference on Machine Learning (ICML 2002), pp. 315–322 (2002)

23.

Leleux, P., Courtain, S., Guex, G., Saerens, M.: Sparse randomized shortest paths routing with Tsallis divergence regularization. Data Min. Knowl. Disc. 35(3), 986–1031 (2021). https://doi.org/10.1007/s10618-021-00742-yMathSciNetCrossRefMATH

24.

Leleux, P., Courtain, S., Françoisse, K., Saerens, M.: Design of biased random walks on a graph with application to collaborative recommendation. Submitted for publication (2020)

25.

Lichman, M.: UCI machine learning repository (2013)

26.

Macskassy, S.A., Provost, F.: Classification in networked data: a toolkit and a univariate case study. J. Mach. Learn. Res. 8, 935–983 (2007)

27.

Saerens, M., Achbany, Y., Fouss, F., Yen, L.: Randomized shortest-path problems: two related models. Neural Comput. 21(8), 2363–2404 (2009)MathSciNetCrossRefMATH

28.

Schölkopf, B., Smola, A.: Learning with Kernels. MIT Press, Cambridge (2002)

29.

Sommer, F., Fouss, F., Saerens, M.: Comparison of graph node distances on clustering tasks. In: Villa, A.E.P., Masulli, P., Pons Rivero, A.J. (eds.) ICANN 2016. LNCS, vol. 9886, pp. 192–201. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-44778-0_23CrossRef

30.

Sommer, F., Fouss, F., Saerens, M.: Modularity-driven Kernel k-means for community detection. In: Lintas, A., Rovetta, S., Verschure, P.F.M.J., Villa, A.E.P. (eds.) ICANN 2017. LNCS, vol. 10614, pp. 423–433. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-68612-7_48CrossRef

31.

von Luxburg, U., Radl, A., Hein, M.: Getting lost in space: Large sample analysis of the commute distance. In: Advances in Neural Information Processing Systems: Proceedings of the NIPS 2010 Conference, vol. 23, pp. 2622–2630 (2010)

32.

Yen, L., Fouss, F., Decaestecker, C., Francq, P., Saerens, M.: Graph nodes clustering with the sigmoid commute-time kernel: a comparative study. Data Knowl. Eng. 68(3), 338–361 (2009)CrossRef

33.

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

Titel: A Simple Extension of the Bag-of-Paths Model Weighting Path Lengths by a Poisson Distribution
verfasst von: Sylvain Courtain
Marco Saerens
Verlag: Springer International Publishing
Buch: Complex Networks & Their Applications X
Print ISBN: 978-3-030-93408-8

Electronic ISBN: 978-3-030-93409-5

Copyright-Jahr: 2022
DOI: https://doi.org/10.1007/978-3-030-93409-5_19

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"

Premium Partner