TY - JOUR TI - Combined method to detect communities in graphs of interacting objects T2 - IS - KW - graph KW - graph analysis KW - community detection KW - graph structure KW - social network analysis KW - Big Data AB - Sofiya Y. Lobanova - BSc Program Student, Tikhonov Moscow Institute of Electronics and Mathematics, National Research University Higher School of EconomicsAddress: 20, Myasnitskaya Street, Moscow, 101000, Russian FederationE-mail: s.lobanova@usabilitylab.netAlexander A. Chepovskiy - Associate Professor, School of Applied Mathematics, Tikhonov Moscow Institute of Electronics and Mathematics, National Research University Higher School of EconomicsAddress: 20, Myasnitskaya Street, Moscow, 101000, Russian FederationE-mail: aachepovsky@hse.ru      In this paper, we propose and implement a method for detecting intersecting and nested communities in graphs of interacting objects of different natures. For this, two classical algorithms are taken: a hierarchical agglomerate and one based on the search for k-cliques. The combined algorithm presented is based on their consistent application. In addition, parametric options are developed that are responsible for actions with communities whose sizes are smaller than the given k, and also with single vertices. Varying these parameters allows us to take into account differences in the topology of the original graph and thus to correct the algorithm.      The testing was carried out on real data, including on a group of graphs of a social network, and the qualitative content of the resulting partition was investigated. To assess the differences between the integrated method and the classical algorithms of community detections, a common measure of similarity was used. As a result, it is clearly shown that the resulting partitions are significantly different. We found that for the approach proposed in the article the index of the numerical characteristic of the partitioning accuracy, modularity, can be lower than the corresponding value for other approaches. At the same time, the result of an integrated method is often more informative due to intersections and nested community structure.      A visualization of the partition obtained for one of the examples by an integrated method at the first and last steps is presented. Along with the successfully found set of parameters of the integrated method for small communities and cut off vertices in the case of social networks, some shortcomings of the proposed model are noted. Proposals are made to develop this approach by using a set of parametric algorithms.This work was supported by the Russian Foundation for Basic Research (projects No. №16-29-09546 and №16-07-00641)  AU - Sofiya Lobanova AU - Alexander Chepovskiy UR - https://bijournal.hse.ru/en/2017--4 (42)/216770576.html PY - 2017 SP - 64-73 VL -