×

Bootstrap clustering for graph partitioning. (English) Zbl 1238.05116

Summary: 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.

MSC:

05C22 Signed and weighted graphs
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C85 Graph algorithms (graph-theoretic aspects)
90C35 Programming involving graphs or networks
62F40 Bootstrap, jackknife and other resampling methods

Software:

bootlib
PDF BibTeX XML Cite
Full Text: DOI EuDML Link

References:

[1] D. Aloise, S. Cafieri, G. Caporossi, P. Hansen, L. Liberti and S. Perron, Column generation algorithms for exact modularity maximization in networks. Phys. Rev. E82 (2010) 046112.
[2] J.B. Angelelli, A. Baudot, C. Brun and A. Guénoche, Two local dissimilarity measures for weighted graph with application to biological networks. Adv. Data Anal. Classif.2 (2008) 3-16. · Zbl 1146.05019
[3] J.P. Barthélemy and B. Leclerc, The median procedure for partitions. DIMACS series in Discrete Mathematics and Theoretical Computer Science19 (1995) 3-34. · Zbl 0814.62031
[4] V. Blondel, J.-L. Guillaume, R. Lambiotte and E. Lefebvre, Fast unfolding of communities in large networks. J. Stat. Mech. Theor. Exp. (2008) P10008.
[5] U. Brandes, D. Delling, M. Gaertler, R. Görke, M. Hoefer, Z. Nikoloski and D. Wagner, On modularity - NP-completeness and beyond. Proceedings of WG 2007. Lett. Notes Comput. Sci.4769 (2007) 121-132.
[6] S.V. Dale and C.J. StoeckertJr., Computational modeling of the Plasmodium falciparum interactome reveals protein function on a genome-wide scale. Gen. Res.16 (2006) 542-549.
[7] A.C. Davison and D.V. Hinkley, Bootstrap methods and their application. Cambridge University Press (1997). · Zbl 0886.62001
[8] L.R. Dice, Measures of the amount of ecologic association between species. Ecology26 (1945) 297-302.
[9] J. Duch and A. Arenas, Community detection in complex networks using extremal optimization. Phys. Rev. E72 (2005) 027104.
[10] J. Felsenstein, Inferring Phylogenies. Sunderland (MA), Sinauer Associates Inc. (2003).
[11] S. Fortunato, Community detection in graphs. Phys. Rep.486 (2010) 75-174.
[12] A. Guénoche, Comparison of algorithms in graph partitioning. RAIRO42 (2008) 469-484. · Zbl 1198.90379
[13] A. Guénoche, Consensus of partitions : a constructive approach. Adv. Data Anal. Classif.5 (2011) 215-229. · Zbl 1253.68258
[14] L. Hubert and P. Arabie, Comparing partitions, J. Classif.2 (1985) 193-218. · Zbl 0587.62128
[15] A.K. Jain and J.V. Moreau, Bootstrap technique in cluster analysis. Pattern Recogn.20 (1987) 547-568.
[16] M.E.J. Newman, Modularity and community structure in networks. PNAS103 (2006) 8577-8582.
[17] M.E.J. Newman and M. Girvan, Finding and evaluating community structure in networks. Phys. Rev. E69 (2004) 026133.
[18] A. Noack and R. Rotta, Multi-level algorithms for modularity clustering, Proceedings of SEA’2009, edited by J. Vahrenhold. Lett. Notes Comput. Sci.5526 (2009) 257-268.
[19] S. Régnier, Sur quelques aspects mathématiques des problèmes de classification automatique. I.C.C. Bulletin4 (1965) 175-191. Reprint, Math. Sci. Hum.82 (1983) 13-29. Zbl0548.62040 · Zbl 0548.62040
[20] C.T. Zahn, Approximating symmetric relations by equivalence relations. SIAM J. Appl. Math.12 (1964) 840-847. Zbl0129.16003 · Zbl 0129.16003
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.