@inproceedings{
    OrSc05,
    editor = "Nikoletseas, S.",
    author = "Orponen, Pekka and Schaeffer, Satu Elisa",
    volume = "3503",
    title = "Local clustering of large graphs by approximate {F}iedler vectors",
    url = "http://dx.doi.org/10.1007/11427186_45",
    series = "Lecture Notes in Computer Science",
    booktitle = "Proceedings of the 4th International Workshop on Efficient and Experimental Algorithms (WEA'05, Santorini, Greece, May 2005)",
    publisher = "Springer-Verlag",
    abstract = "We address the problem of determining the natural neighbourhood of a given node $i$ in a large nonunifom network $G$ in a way that uses only local computations, i.e.\ without recourse to the full adjacency matrix of $G$. We view the problem as that of computing potential values in a diffusive system where node $i$ is fixed at zero potential, and the potentials at the other nodes are then induced by the adjacency relation of $G$. 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.",
    note = "",
    flags = "public",
    year = "2005",
    keywords = "nonuniform networks, clustering, spectral methods, Fiedler vectors",
    pages = "524--533",
    address = "Berlin Heidelberg"
}