User menu

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

Modularity-driven kernel k-means for community detection

Primary tabs

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

The k-means algorithm is probably the most well-known and most popular clustering method in existence today. This work evaluates if a new, autonomous, kernel k-means approach for graph node clustering coupled with the modularity criterion can rival, e.g., the well-established Louvain method. We test the algorithm on social network datasets of various sizes and types. The new method estimates the optimal kernel or distance parameters as well as the natural number of clusters in the dataset based on modularity. Results indicate that this simple black-box algorithm manages to perform on par with the Louvain method given the same input.

Document type Article de périodique (Journal article) – Article de recherche
Access type Accès libre
Publication date 2017
Language Anglais
Journal information "Lecture Notes in Computer Science - ICANN 2017 International Conference on Artificial Neural Networks" - Vol. 10614, p. 423-433 (2017)
Peer reviewed yes
Publisher Springer (Heidelberg)
issn 0302-9743
e-issn 1611-3349
Publication status Publié
Affiliations UCL - SSH/LouRIM - Louvain Research Institute in Management and Organizations
UCL - SST/ICTM - Institute of Information and Communication Technologies, Electronics and Applied Mathematics
UCL - SST/ICTM/INGI - Pôle en ingénierie informatique
Keywords Clustering ; Graph theory ; Modularity ; Kernel k-means ; Community detection
Links
  1. Berkhin P., A Survey of Clustering Data Mining Techniques, Grouping Multidimensional Data ISBN:354028348X p.25-71, 10.1007/3-540-28349-8_2
  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. Bolla Marianna, Penalized versions of the Newman-Girvan modularity and their relation to normalized cuts andk-means clustering, 10.1103/physreve.84.016108
  4. Borg Ingwer, Groenen Patrick, Modern Multidimensional Scaling, ISBN:9781475727135, 10.1007/978-1-4757-2711-1
  5. Brandes U., Delling D., Gaertler M., Gorke R., Hoefer M., Nikoloski Z., Wagner D., On Modularity Clustering, 10.1109/tkde.2007.190689
  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. Chebotarev Pavel, The walk distances in graphs, 10.1016/j.dam.2012.02.015
  9. Chebotarev, P., Shamis, E.: The matrix-forest theorem and measuring relations in small social groups. Autom. Remote Control 58(9), 1505–1514 (1997)
  10. Chebotarev Pavel, Shamis Elena, The Forest Metrics for Graph Vertices, 10.1016/s1571-0653(04)00058-7
  11. Chung, F., Yau, S.T.: Coverings, heat kernels and spanning trees. J. Comb. 6, 163–184 (1998)
  12. 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)
  13. Cormen, T., Leiserson, C., Rivest, R., Stein, C.: Introduction to Algorithms, 3rd edn. The MIT Press, Cambridge (2009)
  14. Daniel, W.W.: Applied Non-parametric Statistics. The Duxbury Advanced Series in Statistics and Decision Sciences. PWS-Kent Publishing Company, Boston (1990)
  15. Demšar, J.: Statistical comparisons of classifiers over multiple data sets. J. Mach. Learn. Res. 7, 1–30 (2006)
  16. Devooght Robin, Mantrach Amin, Kivimäki Ilkka, Bersini Hugues, Jaimes Alejandro, Saerens Marco, Random walks based modularity : application to semi-supervised learning, 10.1145/2566486.2567986
  17. Duda, R.O., Hart, P.E.: Pattern Classification and Scene Analysis. Wiley, Hoboken (1973)
  18. Estrada Ernesto, The communicability distance in graphs, 10.1016/j.laa.2012.01.017
  19. Fortunato S., Barthelemy M., Resolution limit in community detection, 10.1073/pnas.0605965104
  20. Fouss Francois, Saerens Marco, Shimbo Masashi, Algorithms and Models for Network Data and Link Analysis, ISBN:9781316418321, 10.1017/cbo9781316418321
  21. Fouss Francois, Yen Luh, Pirotte Alain, Saerens Marco, An Experimental Investigation of Graph Kernels on a Collaborative Recommendation Task, 10.1109/icdm.2006.18
  22. Françoisse Kevin, Kivimäki Ilkka, Mantrach Amin, Rossi Fabrice, Saerens Marco, A bag-of-paths framework for network data analysis, 10.1016/j.neunet.2017.03.010
  23. Girvan M., Newman M. E. J., Community structure in social and biological networks, 10.1073/pnas.122653799
  24. Hubert Lawrence, Arabie Phipps, Comparing partitions, 10.1007/bf01908075
  25. Ito Takahiko, Shimbo Masashi, Kudo Taku, Matsumoto Yuji, Application of kernels to link analysis, 10.1145/1081870.1081941
  26. Ivashkin, V., Chebotarev, P.: Do logarithmic proximity measures outperform plain ones in graph clustering? In: Proceedings of 6th International Conference on Network Analysis (2016)
  27. Kandola, J., Cristianini, N., Shawe-Taylor, J.: Learning semantic similarity. In: Advances in Neural Information Processing Systems (NIPS 2002), vol. 15, pp. 657–664 (2002)
  28. Katz Leo, A new status index derived from sociometric analysis, 10.1007/bf02289026
  29. 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
  30. 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)
  31. Krebs, V.: New political patterns (2008). http://www.orgnet.com/divided.html
  32. Lancichinetti Andrea, Fortunato Santo, Limits of modularity maximization in community detection, 10.1103/physreve.84.066122
  33. Lancichinetti Andrea, Fortunato Santo, Radicchi Filippo, Benchmark graphs for testing community detection algorithms, 10.1103/physreve.78.046110
  34. Lang, K.: 20 newsgroups dataset. http://bit.ly/lang-newsgroups
  35. Newman M. E. J., Finding community structure in networks using the eigenvectors of matrices, 10.1103/physreve.74.036104
  36. Newman M. E. J., Modularity and community structure in networks, 10.1073/pnas.0601602103
  37. Newman Mark, Networks, ISBN:9780199206650, 10.1093/acprof:oso/9780199206650.001.0001
  38. Newman M. E. J., Girvan M., Finding and evaluating community structure in networks, 10.1103/physreve.69.026113
  39. Reichardt Jörg, Bornholdt Stefan, Detecting Fuzzy Community Structures in Complex Networks with a Potts Model, 10.1103/physrevlett.93.218701
  40. Saerens Marco, Achbany Youssef, Fouss François, Yen Luh, Randomized Shortest-Path Problems: Two Related Models, 10.1162/neco.2009.11-07-643
  41. Siegel, S.: Non-parametric Statistics for the Behavioral Sciences. McGraw-Hill, New York city (1956)
  42. Smola Alexander J., Kondor Risi, Kernels and Regularization on Graphs, Learning Theory and Kernel Machines (2003) ISBN:9783540407201 p.144-158, 10.1007/978-3-540-45167-9_12
  43. Sommer Felix, Fouss François, Saerens Marco, Comparison of Graph Node Distances on Clustering Tasks, Artificial Neural Networks and Machine Learning – ICANN 2016 (2016) ISBN:9783319447773 p.192-201, 10.1007/978-3-319-44778-0_23
  44. 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)
  45. Xu R., WunschII D., Survey of Clustering Algorithms, 10.1109/tnn.2005.845141
  46. 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
  47. 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
  48. 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
  49. 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. Modularity-driven kernel k-means for community detection. In: Lecture Notes in Computer Science - ICANN 2017 International Conference on Artificial Neural Networks, Vol. 10614, p. 423-433 (2017)
Permanent URL http://hdl.handle.net/2078.1/196187