Abstract | ||
---|---|---|
Given a simple undirected weighted or unweighted graph, we try to cluster the vertex set into communities and also to quantify the robustness of these clusters. For that task, we propose a new method, called bootstrap clustering which consists in (i) defining a new clustering algorithm for graphs, (ii) building a set of graphs similar to the initial one, (iii) applying the clustering method to each of them, making a profile (set) of partitions, (iv) computing a consensus partition for this profile, which is the final graph partitioning. This allows to evaluate the robustness of a cluster as the average percentage of partitions in the profile joining its element pairs; this notion can be extended to partitions. Doing so, the initial and consensus partitions can be compared. A simulation protocol, based on random graphs structured in communities is designed to evaluate the efficiency of the Bootstrap Clustering approach. |
Year | DOI | Venue |
---|---|---|
2011 | 10.1051/ro/2012001 | RAIRO-OPERATIONS RESEARCH |
Keywords | Field | DocType |
Graph partitioning,clustering,modularity,consensus of partitions,bootstrap | Combinatorics,Random graph,Vertex (geometry),Correlation clustering,Robustness (computer science),Partition (number theory),Cluster analysis,Graph partition,Bootstrapping (electronics),Mathematics | Journal |
Volume | Issue | ISSN |
45 | 4 | 0399-0559 |
Citations | PageRank | References |
5 | 0.54 | 4 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Philippe Gambette | 1 | 77 | 9.61 |
A. Guénoche | 2 | 229 | 41.64 |