Wavelets on Graphs: a Tool for Multiscale Community Mining in Graphs

Nicolas Tremblay

Jeudi 11 avril 2013 à 11h, salle 25-26/101


For data represented by networks, the community structure of the underlying graph is of great interest. A classical clustering problem is to uncover the overall best partition of nodes in communities. We work on a more elaborate description in which community structures are identified at different scales. To this end, we take advantage of the local and scale-dependent information encoded in graph wavelets. We classify nodes according to their wavelets or scaling functions, using, for instance, a scale-dependent modularity function. I will give an introduction on spectral graph wavelets and scaling functions, and talk about our recent advances. I will show results obtained on a graph benchmark having hierarchical structure and on real social networks. This is joint work with my supervisor Pierre Borgnat.