title: A modified two-stage Markov clustering algorithm for large and sparse networks.
abstract: BACKGROUND
  Graph-based hierarchical clustering algorithms become prohibitively costly in both execution time and storage space, as the number of nodes approaches the order of millions.
  
  
  OBJECTIVE
  A fast and highly memory efficient Markov clustering algorithm is proposed to perform the classification of huge sparse networks using an ordinary personal computer.
  
  
  METHODS
  Improvements compared to previous versions are achieved through adequately chosen data structures that facilitate the efficient handling of symmetric sparse matrices. Clustering is performed in two stages: the initial connected network is processed in a sparse matrix until it breaks into isolated, small, and relatively dense subgraphs, which are then processed separately until convergence is obtained. An intelligent stopping criterion is also proposed to quit further processing of a subgraph that tends toward completeness with equal edge weights. The main advantage of this algorithm is that the necessary number of iterations is separately decided for each graph node.
  
  
  RESULTS
  The proposed algorithm was tested using the SCOP95 and large synthetic protein sequence data sets. The validation process revealed that the proposed method can reduce 3-6 times the processing time of huge sequence networks compared to previous Markov clustering solutions, without losing anything from the partition quality.
  
  
  CONCLUSIONS
  A one-million-node and one-billion-edge protein sequence network defined by a BLAST similarity matrix can be processed with an upper-class personal computer in 100 minutes. Further improvement in speed is possible via parallel data processing, while the extension toward several million nodes needs intermediary data storage, for example on solid state drives.
authors: Faculty of Technical and Human Sciences, Sapientia University of Transylvania,Şoseaua Sighişoarei 1/C, 540485 Tîrgu Mureş, Romania; Department of Informatics, Petru Maior University, Str. N. Iorga Nr. 1, 540088 Tîrgu Mureş, Romania.
authors: László
authors: L
authors: Szilágyi
authors: Budapest University of Technology and Economics, Department of Control Engineering and Information Technology, Magyar tudósok krt. 2, H-1117 Budapest, Hungary; Department of Informatics, Petru Maior University, Str. N. Iorga Nr. 1, 540088 Tîrgu Mureş, Romania. Electronic address: sandor.szilagyi@science.upm.ro.
authors: Sándor M
authors: SM
authors: Szilágyi
mesh_terms: D000465:Algorithms; D016000:Cluster Analysis; D008390:Markov Chains
keywords: Efficient computing; Hierarchical clustering; Markov clustering; Protein sequence networks; Sparse matrix