RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Archive Impact factor Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Prikl. Diskr. Mat.: Year: Volume: Issue: Page: Find

 Prikl. Diskr. Mat., 2019, Number 45, Pages 64–77 (Mi pdm672)

Applied Graph Theory

Approximate algorithms for graph clustering problem

V. P. Il'eva, S. D. Il'evaa, A. V. Morshininb

a Dostoevsky Omsk State University, Omsk, Russia,
b Sobolev Institute of Mathematics SB RAS, Omsk, Russia

Abstract: In the paper, the graph clustering problem is studied. For the version of the problem when the number of clusters does not exceed $3$, we develop three approximate algorithms. The first algorithm uses as a procedure the known Coleman–Saunderson–Wirth algorithm which approximately solves the similar problem when the number of clusters does not exceed $2$, and repeatedly applies a local search. On the contrary, our second algorithm is based on an original idea and does not use a local search at all. The main difference between these algorithms is the following. The first algorithm looks over all vertices of a given graph, for each vertex forms the cluster involving this vertex and all its neighbors and on the rest of the vertices forms one or two clusters using the Coleman–Saunderson–Wirth algorithm. The second algorithm looks over all ordered pairs of vertices of a given graph and for every pair forms two clusters at once, each of which contains only one vertex of this pair with some of its neighbors, placing the rest of the vertices to the third cluster (the third cluster may be empty). Finally, the third algorithm applies the local search only once to the feasible solution returned by the second one. A priori performance guarantees of all approximate algorithms are obtained, the best is equal to $(6-12/n)$ for the second and the third algorithms, where $n$ is the number of vertices of a given graph. Also, experimental comparing of the developed algorithms was carried out. Experimental testing show that running time of our second and third algorithms is essentially less than running time of the first algorithm. At the same time the third algorithm demonstrated the best results in sense of accuracy of the solutions. Thus, the third algorithm has the best characterstics both from point of view of theoretical analysis and experimental study.

Keywords: graph, clustering, approximation algorithm, performance guarantee.

DOI: https://doi.org/10.17223/20710410/45/7

Full text: PDF file (762 kB)
References: PDF file   HTML file

Bibliographic databases:

UDC: 519.8

Citation: V. P. Il'ev, S. D. Il'eva, A. V. Morshinin, “Approximate algorithms for graph clustering problem”, Prikl. Diskr. Mat., 2019, no. 45, 64–77

Citation in format AMSBIB
\Bibitem{IleIleMor19} \by V.~P.~Il'ev, S.~D.~Il'eva, A.~V.~Morshinin \paper Approximate algorithms for~graph~clustering~problem \jour Prikl. Diskr. Mat. \yr 2019 \issue 45 \pages 64--77 \mathnet{http://mi.mathnet.ru/pdm672} \crossref{https://doi.org/10.17223/20710410/45/7}