• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site
Student
Title
Supervisor
Faculty
Educational Programme
Final Grade
Year of Graduation
Daria Komissarova
Biclustering for Complex Networks
Data Science
(Master’s programme)
2017
Networks are a natural representation for various kinds of complex systems in biology, economy, sociology, and other fields. In this research we study the problem of community detection for 2-mode network, i.e. a network with connections between objects and attributes or two sets of objects.

The main purpose of this work is to study object-attribute biclusters (OA-biclusters), as mathematical representation of communities in 2-mode network. The motivation for this approach lies in efficiency of bicluster search algorithms on large datasets, in compare to analogical algorithms in formal concept analysis. In this work we studied a possibility of estimating formal concepts by the subset of dense biclusters. In addition, we suggested a stochastic algorithm for computing density of large biclusters, studied a problem of covering initial context with a set of biclusters and applied different measures to compute the quality of such covering.

In the experimental part we obtained, that, to solve the problem of approximating formal concepts with biclusters, with high probability it is sufficient to study only biclusters with density no less than 0.6. The accuracy of estimating the approximate density of large biclusters was higher than 90%, and complexity costs were reduced by 100 times.

Based on the results of the work, it should be mentioned, that biclusters can be successfully used in the problem of formal concepts approximation and communities detection. Firstly, the algorithms of bicluster search are quick. Secondly, a set of only few biclusters can approximate formal concepts with high accuracy. Moreover, due to weak constraints on biclusters, they are more stable than formal concepts, and this property allows us to detect large well-defined communities, as was shown in the study.

Student Theses at HSE must be completed in accordance with the University Rules and regulations specified by each educational programme.

Summaries of all theses must be published and made freely available on the HSE website.

The full text of a thesis can be published in open access on the HSE website only if the authoring student (copyright holder) agrees, or, if the thesis was written by a team of students, if all the co-authors (copyright holders) agree. After a thesis is published on the HSE website, it obtains the status of an online publication.

Student theses are objects of copyright and their use is subject to limitations in accordance with the Russian Federation’s law on intellectual property.

In the event that a thesis is quoted or otherwise used, reference to the author’s name and the source of quotation is required.

Search all student theses