Local clustering of large graphs by approximate Fiedler vectors

Reference:

Pekka Orponen and Satu Elisa Schaeffer. Local clustering of large graphs by approximate Fiedler vectors. In S. Nikoletseas, editor, Proceedings of the 4th International Workshop on Efficient and Experimental Algorithms (WEA'05, Santorini, Greece, May 2005), volume 3503 of Lecture Notes in Computer Science, pages 524–533, Berlin Heidelberg, 2005. Springer-Verlag.

Abstract:

We address the problem of determining the natural neighbourhood of a given node in a large nonunifom network in a way that uses only local computations, i.e. without recourse to the full adjacency matrix of . We view the problem as that of computing potential values in a diffusive system where node is fixed at zero potential, and the potentials at the other nodes are then induced by the adjacency relation of . This point of view leads to a constrained spectral clustering approach. We observe that a gradient method for computing the respective Fiedler vector values at each node can be implemented in a local manner, leading to our eventual algorithm. The algorithm is evaluated experimentally using two types of nonuniform networks: randomised ``caveman graphs'' and a scientific collaboration network.

Keywords:

nonuniform networks, clustering, spectral methods, Fiedler vectors

Suggested BibTeX entry:

@inproceedings{OrSc05,
    address = {Berlin Heidelberg},
    author = {Pekka Orponen and Satu Elisa Schaeffer},
    booktitle = {Proceedings of the 4th International Workshop on Efficient and Experimental Algorithms (WEA'05, Santorini, Greece, May 2005)},
    editor = {S. Nikoletseas},
    pages = {524--533},
    publisher = {Springer-Verlag},
    series = {Lecture Notes in Computer Science},
    title = {Local clustering of large graphs by approximate {F}iedler vectors},
    volume = {3503},
    year = {2005},
}