User menu

Accès à distance ? S'identifier sur le proxy UCLouvain

Comparison of Graph Node Distances on Clustering Tasks

Primary tabs

download
  • Open access
  • PDF
  • 245.82 K
Sommer, Félix [UCL] Fouss, François [UCL] Saerens, Marco [UCL]

This work presents recent developments in graph node distances and tests them empirically on social network databases of various sizes and types. We compare two versions of a distance-based kernel k-means algorithm with the well-established Louvain method. The first version is a classic kernel k-means approach, the second version additionally makes use of node weights with the Sum-over-Forests density index. Both kernel k-means algorithms employ a variety of classic and modern distances. We compare the results of all three algorithms using statistical measures and an overall rank-comparison to ascertain their capabilities in community detection. Results show that two recently introduced distances outperform the others, on our tested datasets.

Document type Article de périodique (Journal article) – Article de recherche
Access type Accès libre
Publication date 2016
Language Anglais
Journal information "Lecture Notes in Computer Science - ICANN 2016 International Conference on Artificial Neural Networks" - Vol. 9886, p. 192-201 (2016)
Peer reviewed yes
Publisher Springer (Switzerland)
issn 0302-9743
e-issn 1611-3349
Publication status Publié
Affiliations UCL - SST/ICTM - Institute of Information and Communication Technologies, Electronics and Applied Mathematics
UCL - SSH/LouRIM - Louvain Research Institute in Management and Organizations
UCL - SST/ICTM/INGI - Pôle en ingénierie informatique
Keywords Clustering ; Graph theory ; Kernel k-means ; Communtiy detection
Links
  1. Bavaud François, Guex Guillaume, Interpolating between Random Walks and Shortest Paths: A Path Functional Approach, Lecture Notes in Computer Science (2012) ISBN:9783642353857 p.68-81, 10.1007/978-3-642-35386-4_6
  2. Blondel Vincent D, Guillaume Jean-Loup, Lambiotte Renaud, Lefebvre Etienne, Fast unfolding of communities in large networks, 10.1088/1742-5468/2008/10/p10008
  3. Borg Ingwer, Groenen Patrick, Modern Multidimensional Scaling, ISBN:9781475727135, 10.1007/978-1-4757-2711-1
  4. Celeux, G., Diday, E., Govaert, G., Lechevallier, Y., Ralambondrainy, H.: Classification Automatique des Données. Dunod, Paris (1989)
  5. Chebotarev, P., Shamis, E.: The matrix-forest theorem and measuring relations in small social groups. Autom. Remote Control 58(9), 1505–1514 (1997)
  6. Chebotarev Pavel, A class of graph-geodetic distances generalizing the shortest-path and the resistance distances, 10.1016/j.dam.2010.11.017
  7. Chebotarev Pavel, The graph bottleneck identity, 10.1016/j.aam.2010.11.001
  8. Collignon, A., Maes, F., Delaere, D., Vandermeulen, D., Suetens, P., Marchal, G.: Automated multi-modality image registration based on information theory. Inf. Process. Med. Imaging 3, 263–274 (1995)
  9. Cormen, T., Leiserson, C., Rivest, R., Stein, C.: Introduction to Algorithms, 3rd edn. The MIT Press, Cambridge (2009)
  10. Daniel, W.: Applied Nonparametric Statistics. The Duxbury Advanced Series in Statistics and Decision Sciences. PWS-Kent Publications, Boston (1990)
  11. Demšar, J.: Statistical comparisons of classifiers over multiple data sets. J. Mach. Learn. Res. 7, 1–30 (2006)
  12. Duda, R.O., Hart, P.E.: Pattern Classification and Scene Analysis. Wiley, New York (1973)
  13. Fouss, F., Saerens, M., Shimbo, M.: Algorithms for Exploratory Link Analysis. Cambridge University Press (2016, to appear)
  14. Françoisse, K., Kivimäki, I., Mantrach, A., Rossi, F., Saerens, M.: A bag-of-paths framework for network data analysis, pp. 1–36 (2013). arXiv:1302.6766
  15. Girvan M., Newman M. E. J., Community structure in social and biological networks, 10.1073/pnas.122653799
  16. Grady, L., Schwartz, E.: The graph analysis toolbox: image processing on arbitrary graphs. CAS/CNS Technical report Series (021) (2010)
  17. Hashimoto, T., Sun, Y., Jaakkola, T.: From random walks to distances on unweighted graphs. In: Cortes, C., Lawrence, N.D., Lee, D.D., Sugiyama, M., Garnett, R. (eds.) Advances in Neural Information Processing Systems, vol. 28, pp. 3411–3419. Curran Associates, Inc. (2015)
  18. Hubert Lawrence, Arabie Phipps, Comparing partitions, 10.1007/bf01908075
  19. Finding Groups in Data, ISBN:9780470316801, 10.1002/9780470316801
  20. Kivimäki Ilkka, Shimbo Masashi, Saerens Marco, Developments in the theory of randomized shortest paths with a comparison of graph node distances, 10.1016/j.physa.2013.09.016
  21. Krebs, V.: New political patterns (2008). http://www.orgnet.com/divided.html
  22. Lancichinetti Andrea, Fortunato Santo, Radicchi Filippo, Benchmark graphs for testing community detection algorithms, 10.1103/physreve.78.046110
  23. Lang, K.: 20 newsgroups dataset. http://bit.ly/lang-newsgroups
  24. Newman Mark, Networks, ISBN:9780199206650, 10.1093/acprof:oso/9780199206650.001.0001
  25. Newman M. E. J., Finding community structure in networks using the eigenvectors of matrices, 10.1103/physreve.74.036104
  26. Newman M. E. J., Modularity and community structure in networks, 10.1073/pnas.0601602103
  27. Newman M. E. J., Girvan M., Finding and evaluating community structure in networks, 10.1103/physreve.69.026113
  28. Saerens Marco, Achbany Youssef, Fouss François, Yen Luh, Randomized Shortest-Path Problems: Two Related Models, 10.1162/neco.2009.11-07-643
  29. Schölkopf, B., Smola, A.: Learning with Kernels. The MIT Press, Cambridge (2002)
  30. Senelle Mathieu, Garcia-Diez Silvia, Mantrach Amin, Shimbo Masashi, Saerens Marco, Fouss Francois, The Sum-over-Forests Density Index: Identifying Dense Regions in a Graph, 10.1109/tpami.2013.227
  31. Siegel, S.: Nonparametric Statistics for the Behavioral Sciences. McGraw-Hill, New York (1956)
  32. Sommer, F., Fouss, F., Saerens, M.: Clustering using a Sum-Over-Forests weighted kernel k-means approach. LSM Working Paper 22 (2015)
  33. von Luxburg, U., Radl, A., Hein, M.: Getting lost in space: large sample analysis of the commute distance. In: Proceedings of the 23th Neural Information Processing Systems Conference (NIPS 2010), pp. 2622–2630 (2010)
  34. von Luxburg, U., Radl, A., Hein, M.: Hitting and commute times in large random neighborhood graphs. J. Mach. Learn. Res. 15, 1751–1798 (2014)
  35. Yen Luh, Fouss Francois, Decaestecker Christine, Francq Pascal, Saerens Marco, Graph Nodes Clustering Based on the Commute-Time Kernel, Advances in Knowledge Discovery and Data Mining ISBN:9783540717003 p.1037-1045, 10.1007/978-3-540-71701-0_117
  36. Yen Luh, Fouss Francois, Decaestecker Christine, Francq Pascal, Saerens Marco, Graph nodes clustering with the sigmoid commute-time kernel: A comparative study, 10.1016/j.datak.2008.10.006
  37. Yen Luh, Saerens Marco, Mantrach Amin, Shimbo Masashi, A family of dissimilarity measures between nodes generalizing both the shortest-path and the commute-time distances, 10.1145/1401890.1401984
  38. Zachary Wayne W., An Information Flow Model for Conflict and Fission in Small Groups, 10.1086/jar.33.4.3629752
Bibliographic reference Sommer, Félix ; Fouss, François ; Saerens, Marco. Comparison of Graph Node Distances on Clustering Tasks. In: Lecture Notes in Computer Science - ICANN 2016 International Conference on Artificial Neural Networks, Vol. 9886, p. 192-201 (2016)
Permanent URL http://hdl.handle.net/2078.1/187106