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




Applied Graph Theory
Approximate algorithms for graph clustering problem
V. P. Il'ev^{a}, S. D. Il'eva^{a}, A. V. Morshinin^{b} ^{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 $(612/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 6477
\mathnet{http://mi.mathnet.ru/pdm672}
\crossref{https://doi.org/10.17223/20710410/45/7}
Linking options:
http://mi.mathnet.ru/eng/pdm672 http://mi.mathnet.ru/eng/pdm/y2019/i3/p64
Citing articles on Google Scholar:
Russian citations,
English citations
Related articles on Google Scholar:
Russian articles,
English articles

Number of views: 
This page:  95  Full text:  43  References:  6 
