Evaluation of clustering algorithms for protein-protein interaction networks

Sylvain Brohée and Jacques van Helden

MCL : Separation and Accuracy as a function of the inflation

Figures with legend

% removed \ % added

0

5

10

20

40

80

100

0

5

10

20

40

80

MCL : Separation and Accuracy as a function of the inflation

Figures without legend

% removed \ % added

0

5

10

20

40

80

100

0

5

10

20

40

80

MCL : Separation and Accuracy as a function of the inflation

Figures in black and white with legend

% removed \ % added

0

5

10

20

40

80

100

0

5

10

20

40

80

MCL : Number of clusters as a function of the inflation parameter

% removed \ % added

0

5

10

20

40

80

100

0

5

10

20

40

80

RNSC : Cluster vs Complex Separation and (weighted) Sensitivity versus (weighted) PPV

With legend

% removed \ % added

0

5

10

20

40

80

100

0

5

10

20

40

80

RNSC : Cluster vs Complex Separation and (weighted) Sensitivity versus (weighted) PPV

Without legend

% removed \ % added

0

5

10

20

40

80

100

0

5

10

20

40

80

Algorithms robustness comparaison

Geometric accuracy as a function of the percentage of added edges with optimal accuracy parameters

	Weighted accuracy		Unweighted accuracy
% of removed edges	No legend	Legend	No legend	Legend
0	Rdm graph permuted clusters	randomized graphs permuted clusters	randomized graphs permuted clusters	randomized graphs permuted clusters
5	Rdm graph permuted clusters	randomized graphs permuted clusters	randomized graphs permuted clusters	randomized graphs permuted clusters
10	Rdm graph permuted clusters	randomized graphs permuted clusters	randomized graphs permuted clusters	randomized graphs permuted clusters
20	Rdm graph permuted clusters	randomized graphs permuted clusters	randomized graphs permuted clusters	randomized graphs permuted clusters
40	Rdm graph permuted clusters	randomized graphs permuted clusters	randomized graphs permuted clusters	randomized graphs permuted clusters
80	Rdm graph permuted clusters	randomized graphs permuted clusters	randomized graphs permuted clusters	randomized graphs permuted clusters

Geometric accuracy as a function of the percentage of removed edges with optimal accuracy parameters

	Weighted accuracy		Unweighted accuracy
% of added edges	No legend	Legend	No legend	Legend
0	Rdm graph permuted clusters	randomized graphs permuted clusters	randomized graphs permuted clusters	randomized graphs permuted clusters
5	Rdm graph permuted clusters	randomized graphs permuted clusters	randomized graphs permuted clusters	randomized graphs permuted clusters
10	Rdm graph permuted clusters	randomized graphs permuted clusters	randomized graphs permuted clusters	randomized graphs permuted clusters
20	Rdm graph permuted clusters	randomized graphs permuted clusters	randomized graphs permuted clusters	randomized graphs permuted clusters
40	Rdm graph permuted clusters	randomized graphs permuted clusters	randomized graphs permuted clusters	randomized graphs permuted clusters
80	Rdm graph permuted clusters	randomized graphs permuted clusters	randomized graphs permuted clusters	randomized graphs permuted clusters
100	Rdm graph permuted clusters	randomized graphs permuted clusters	randomized graphs permuted clusters	randomized graphs permuted clusters

Geometric accuracy as a function of the percentage of added edges with optimal separation parameters

	Weighted accuracy		Unweighted accuracy
% of removed edges	No legend	Legend	No legend	Legend
0	Rdm graph permuted clusters	randomized graphs permuted clusters	randomized graphs permuted clusters	randomized graphs permuted clusters
5	Rdm graph permuted clusters	randomized graphs permuted clusters	randomized graphs permuted clusters	randomized graphs permuted clusters
10	Rdm graph permuted clusters	randomized graphs permuted clusters	randomized graphs permuted clusters	randomized graphs permuted clusters
20	Rdm graph permuted clusters	randomized graphs permuted clusters	randomized graphs permuted clusters	randomized graphs permuted clusters
40	Rdm graph permuted clusters	randomized graphs permuted clusters	randomized graphs permuted clusters	randomized graphs permuted clusters
80	Rdm graph permuted clusters	randomized graphs permuted clusters	randomized graphs permuted clusters	randomized graphs permuted clusters

Geometric accuracy as a function of the percentage of removed edges with optimal separation parameters

	Weighted accuracy		Unweighted accuracy
% of added edges	No legend	Legend	No legend	Legend
0	Rdm graph permuted clusters	randomized graphs permuted clusters	randomized graphs permuted clusters	randomized graphs permuted clusters
5	Rdm graph permuted clusters	randomized graphs permuted clusters	randomized graphs permuted clusters	randomized graphs permuted clusters
10	Rdm graph permuted clusters	randomized graphs permuted clusters	randomized graphs permuted clusters	randomized graphs permuted clusters
20	Rdm graph permuted clusters	randomized graphs permuted clusters	randomized graphs permuted clusters	randomized graphs permuted clusters
40	Rdm graph permuted clusters	randomized graphs permuted clusters	randomized graphs permuted clusters	randomized graphs permuted clusters
80	Rdm graph permuted clusters	randomized graphs permuted clusters	randomized graphs permuted clusters	randomized graphs permuted clusters
100	Rdm graph permuted clusters	randomized graphs permuted clusters	randomized graphs permuted clusters	randomized graphs permuted clusters

Separation as a function of the percentage of added edges with optimal separation parameters

% of removed edges	No legend	Legend
0	permuted graph permuted clusters	randomized graphs permuted clusters
5	permuted graph permuted clusters	randomized graphs permuted clusters
10	permuted graph permuted clusters	randomized graphs permuted clusters
20	permuted graph permuted clusters	randomized graphs permuted clusters
40	permuted graph permuted clusters	randomized graphs permuted clusters
80	permuted graph permuted clusters	randomized graphs permuted clusters

Separation as a function of the percentage of removed edges with optimal separation parameters

% of added edges	No legend	Legend
0	permuted graph permuted clusters	randomized graphs permuted clusters
5	permuted graph permuted clusters	randomized graphs permuted clusters
10	permuted graph permuted clusters	randomized graphs permuted clusters
20	permuted graph permuted clusters	randomized graphs permuted clusters
40	permuted graph permuted clusters	randomized graphs permuted clusters
80	permuted graph permuted clusters	randomized graphs permuted clusters
100	permuted graph permuted clusters	randomized graphs permuted clusters

Separation as a function of the percentage of added edges with optimal accuracy parameters

% of removed edges	No legend	Legend
0	permuted graph permuted clusters	randomized graphs permuted clusters
5	permuted graph permuted clusters	randomized graphs permuted clusters
10	permuted graph permuted clusters	randomized graphs permuted clusters
20	permuted graph permuted clusters	randomized graphs permuted clusters
40	permuted graph permuted clusters	randomized graphs permuted clusters
80	permuted graph permuted clusters	randomized graphs permuted clusters

Separation as a function of the percentage of removed edges with optimal accuracy parameters

% of added edges	No legend	Legend
0	permuted graph permuted clusters	randomized graphs permuted clusters
5	permuted graph permuted clusters	randomized graphs permuted clusters
10	permuted graph permuted clusters	randomized graphs permuted clusters
20	permuted graph permuted clusters	randomized graphs permuted clusters
40	permuted graph permuted clusters	randomized graphs permuted clusters
80	permuted graph permuted clusters	randomized graphs permuted clusters
100	permuted graph permuted clusters	randomized graphs permuted clusters

Accuracy and Separation bar plot

Negative control

Weighted accuracy

Sensitivity

PPV

Separation

Complex-wise separation

Cluster-wise separation

Legend

No legend

Legend

No legend

Legend

No legend

Legend

No legend

Legend

No legend

Legend

No legend

Randomized graph

Permuted clusters

Graphical representation of large scale experiment

Dataset	Real graph	Randomized graph	MCL clusters	MCODE clusters	RNSC clusters	SPC clusters
gavin_2002	PDF	PDF	PDF	PDF	PDF	PDF
gavin_2006	PDF	PDF	PDF	PDF	PDF	PDF
ho_2002	PDF	PDF	PDF	PDF	PDF	PDF
ito_2001	PDF	PDF	PDF	PDF	PDF	PDF
krogan_2006	PDF	PDF	PDF	PDF	PDF	PDF
uetz_2000	PDF	PDF	PDF	PDF	PDF	PDF