A Survey on Identification of Protein Complexes in Protein–protein Interaction Data: Methods and Evaluation - Computational Intelligence Techniques for Comparative Genomics - page 56

as the average of deg(u) for all u ϵ V, represented as Avdeg(G). The density of a
graph G denoted as den(G),

X

deg ð u Þ

ð Þ¼ ð Þ

Avdeg G 2

j V j

u 2 V

j
j V jðj V j

2 j E

ð Þ¼ ð Þ

den G 3

1 Þ

2.2 Algorithms

2.2.1 Markov Clustering Algorithm (MCL)

The MCL algorithm simulates random walks within a graph by alternation of two
operators called expansion and in ation. Expansion coincides with taking the

power of a stochastic matrix using the normal matrix product (i.e., matrix squaring).
In

fl

ation corresponds with taking the Hadamard power of a matrix, followed by
a scaling step, such that the resulting matrix is stochastic again, i.e., the matrix
elements (on each column) correspond to probability values [ 6 ].
Expansion and in

fl

ation represent different tidal forces which are alternated until
an equilibrium state is reached. An equilibrium state takes the form of a so-called
doubly idempotent matrix, i.e., a matrix that does not change with further expansion
of in

fl

nds the minimal cut which allows
separating the graph component into two clusters by minimizing the number of
inter-cluster edges. The process is repeated until a stop condition is reached.

fl ation steps. At each step, the algorithm

2.2.2 Cluster Breadth- rst Search

Given a weighted network, the objective of this algorithm is to output a set of
disjoint dense subgraphs. Model the network as an undirected graph G =(V, E) with
a con W u ; v

ð ; Þ2

dence score 0 \ 1, for every edge u v E. For any pair of vertices,

u and v without an edge between them, we set W u ; v ¼ 0. For each set of vertices

S ne its weighted density as the sum of the weights of the edges between

them divided by the total number of possible edges. In other words, the density of a
set is measure of how close the induced subgraph is to clique, varies from 0 to 1.

E,de

P ð u ; v Þ2 S x u ; v

D x ð S Þ¼ ð 4 Þ

j S jðj S j 1 Þ= 2

ClusterBFS assembles one cluster at a time, and every cluster is expanded from a
unique seed protein. The unclustered node is added if it has the highest edge weight,