• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Article

Комбинированный алгоритм выделения сообществ в графах взаимодействующих объектов

Бизнес-информатика. 2017. Т. 42. № 4. С. 64-73.
Чеповский А. А., Лобанова С. Ю.

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 offvertices 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.