{"id":298242,"date":"2020-02-05T15:00:09","date_gmt":"2020-02-05T15:00:09","guid":{"rendered":"http:\/\/savepearlharbor.com\/?p=298242"},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-29T21:00:00","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=298242","title":{"rendered":"\u0422\u0435\u043e\u0440\u0438\u044f \u0433\u0440\u0430\u0444\u043e\u0432 \u0432 \u043c\u0430\u0448\u0438\u043d\u043d\u043e\u043c \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u0438 \u0434\u043b\u044f \u0441\u0430\u043c\u044b\u0445 \u043c\u0430\u043b\u0435\u043d\u044c\u043a\u0438\u0445"},"content":{"rendered":"\n<div class=\"post__text post__text-html\" id=\"post-content-body\" data-io-article-url=\"https:\/\/habr.com\/ru\/post\/487138\/\">\n<p>\u0421\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u0434\u0430\u043d\u043d\u044b\u0445 \u0434\u043b\u044f \u0433\u043b\u0443\u0431\u043e\u043a\u043e\u0433\u043e \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044f \u0440\u0430\u0441\u0442\u0435\u0442 \u0441 \u043a\u0430\u0436\u0434\u044b\u043c \u0434\u043d\u0435\u043c. \u041d\u0435\u0439\u0440\u043e\u043d\u043d\u044b\u0435 \u0441\u0435\u0442\u0438 \u043d\u0430 \u043e\u0441\u043d\u043e\u0432\u0435 \u0434\u0430\u043d\u043d\u044b\u0445 \u0432 \u0432\u0438\u0434\u0435 \u0433\u0440\u0430\u0444\u0430 (Graph Neural Network, <strong>GNN<\/strong>) \u0441\u0442\u0430\u043b\u0438 \u043e\u0434\u043d\u0438\u043c \u0438\u0437 \u043f\u0440\u043e\u0440\u044b\u0432\u043e\u0432 \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0438\u0445 \u043b\u0435\u0442. \u041d\u043e \u043f\u043e\u0447\u0435\u043c\u0443 \u0438\u043c\u0435\u043d\u043d\u043e \u0433\u0440\u0430\u0444\u044b \u043d\u0430\u0431\u0438\u0440\u0430\u044e\u0442 \u0432\u0441\u0435 \u0431\u043e\u043b\u044c\u0448\u0443\u044e \u043f\u043e\u043f\u0443\u043b\u044f\u0440\u043d\u043e\u0441\u0442\u044c \u0432 \u043c\u0430\u0448\u0438\u043d\u043d\u043e\u043c \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u0438?<\/p>\n<p>  <\/p>\n<p>\u041a\u043e\u043d\u0435\u0447\u043d\u043e\u0439 \u0446\u0435\u043b\u044c\u044e \u043c\u043e\u0435\u0433\u043e \u043f\u043e\u0432\u0435\u0441\u0442\u0432\u043e\u0432\u0430\u043d\u0438\u044f \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043e\u0431\u0449\u0435\u0435 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u0435 \u0433\u0440\u0430\u0444\u043e\u0432 \u0432 \u043f\u0440\u0438\u0435\u043c\u0430\u0445 \u043c\u0430\u0448\u0438\u043d\u043d\u043e\u0433\u043e \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044f. \u0421\u0442\u0430\u0442\u044c\u044f <strong>\u043d\u0435<\/strong> \u043f\u0440\u0435\u0442\u0435\u043d\u0434\u0443\u0435\u0442 \u043d\u0430 \u043d\u0430\u0443\u0447\u043d\u0443\u044e \u0440\u0430\u0431\u043e\u0442\u0443, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u0432 \u043f\u043e\u043b\u043d\u043e\u0439 \u043c\u0435\u0440\u0435 \u043e\u043f\u0438\u0441\u044b\u0432\u0430\u0435\u0442 \u0432\u0441\u044e \u043c\u043e\u0449\u044c \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u0433\u0440\u0430\u0444\u043e\u0432, \u0430 \u043b\u0438\u0448\u044c \u0437\u043d\u0430\u043a\u043e\u043c\u0438\u0442 \u0447\u0438\u0442\u0430\u0442\u0435\u043b\u044f \u0441 \u044d\u0442\u0438\u043c \u0443\u0434\u0438\u0432\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u043c \u0438 \u0441\u043b\u043e\u0436\u043d\u044b\u043c \u043c\u0438\u0440\u043e\u043c. \u041f\u0443\u0431\u043b\u0438\u043a\u0430\u0446\u0438\u044f \u043e\u0442\u043b\u0438\u0447\u043d\u043e \u043f\u043e\u0434\u043e\u0439\u0434\u0435\u0442, \u043a\u0430\u043a \u0434\u043b\u044f \u0437\u0430\u043a\u0430\u043b\u0435\u043d\u043d\u044b\u0445 \u0432 \u0431\u043e\u044f\u0445 \u043f\u0440\u043e\u0444\u0435\u0441\u0441\u0438\u043e\u043d\u0430\u043b\u043e\u0432, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0435\u0449\u0435 \u043d\u0435 \u0437\u043d\u0430\u043a\u043e\u043c\u044b \u0441 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u0435\u043c \u0433\u0440\u0430\u0444\u043e\u0432 \u0432 \u0433\u043b\u0443\u0431\u043e\u043a\u043e\u043c \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u0438, \u0442\u0430\u043a \u0438 \u0434\u043b\u044f \u043d\u043e\u0432\u0438\u0447\u043a\u043e\u0432 \u0432 \u044d\u0442\u043e\u0439 \u0441\u0444\u0435\u0440\u0435.<\/p>\n<p><a name=\"habracut\"><\/a>  <\/p>\n<h1 id=\"vvedenie\">\u0412\u0432\u0435\u0434\u0435\u043d\u0438\u0435<\/h1>\n<p>  <\/p>\n<p>\u0410\u0432\u0442\u043e\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u043e\u0435 \u0432\u044b\u0434\u0435\u043b\u0435\u043d\u0438\u0435 \u0432\u0430\u0436\u043d\u044b\u0445 \u043f\u0440\u0438\u0437\u043d\u0430\u043a\u043e\u0432, \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u044b\u0445 \u0434\u043b\u044f \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0437\u0430\u0434\u0430\u0447\u0438 \u2014 \u043e\u0434\u043d\u0430 \u0438\u0437 \u0433\u043b\u0430\u0432\u043d\u044b\u0445 \u043f\u0440\u0438\u0447\u0438\u043d \u0443\u0441\u043f\u0435\u0448\u043d\u043e\u0433\u043e \u043f\u0440\u0438\u043c\u0435\u043d\u0435\u043d\u0438\u044f \u043c\u0430\u0448\u0438\u043d\u043d\u043e\u0433\u043e \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044f. \u041d\u043e \u0442\u0440\u0430\u0434\u0438\u0446\u0438\u043e\u043d\u043d\u043e \u043f\u0440\u0438 \u0440\u0430\u0431\u043e\u0442\u0435 \u0441 \u0433\u0440\u0430\u0444\u0430\u043c\u0438, \u043f\u043e\u0434\u0445\u043e\u0434\u044b \u043c\u0430\u0448\u0438\u043d\u043d\u043e\u0433\u043e \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044f \u043f\u043e\u043b\u0430\u0433\u0430\u043b\u0438\u0441\u044c \u043d\u0430 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u0435\u043c\u0443\u044e \u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u0435\u043b\u0435\u043c \u044d\u0432\u0440\u0438\u0441\u0442\u0438\u043a\u0443, \u0447\u0442\u043e\u0431\u044b \u0438\u0437\u0432\u043b\u0435\u0447\u044c \u043e\u0441\u043e\u0431\u0435\u043d\u043d\u043e\u0441\u0442\u0438 \u043a\u043e\u0434\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u043d\u043e\u0439 \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u0438 \u043e \u0433\u0440\u0430\u0444\u0435. \u0422\u0435\u043c \u043d\u0435 \u043c\u0435\u043d\u0435\u0435, \u0442\u0435\u043d\u0434\u0435\u043d\u0446\u0438\u044f \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0438\u0445 \u043b\u0435\u0442 \u0441\u043c\u0435\u043d\u0438\u043b\u0430\u0441\u044c: \u0432\u0441\u0435 \u0447\u0430\u0449\u0435 \u0441\u0442\u0430\u043b\u0438 \u043f\u043e\u044f\u0432\u043b\u044f\u0442\u044c\u0441\u044f \u043f\u043e\u0434\u0445\u043e\u0434\u044b, \u0432 \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u0430\u0432\u0442\u043e\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u0438 \u0443\u0447\u0430\u0442\u0441\u044f \u043a\u043e\u0434\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0443 \u0433\u0440\u0430\u0444\u0430 \u0432 \u043d\u0438\u0437\u043a\u043e\u0440\u0430\u0437\u043c\u0435\u0440\u043d\u044b\u0435 \u0432\u043b\u043e\u0436\u0435\u043d\u0438\u044f \u0441 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u0435\u043c \u043c\u0435\u0442\u043e\u0434\u043e\u0432 \u0433\u043b\u0443\u0431\u043e\u043a\u043e\u0433\u043e \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044f \u0438 \u043d\u0435\u043b\u0438\u043d\u0435\u0439\u043d\u043e\u0433\u043e \u0443\u043c\u0435\u043d\u044c\u0448\u0435\u043d\u0438\u044f \u0440\u0430\u0437\u043c\u0435\u0440\u043d\u043e\u0441\u0442\u0438.<\/p>\n<p>  <\/p>\n<p>\u0412 \u043c\u0430\u0448\u0438\u043d\u043d\u043e\u043c \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u0438 \u043d\u0430 \u0433\u0440\u0430\u0444\u0430\u0445 \u043c\u043e\u0436\u043d\u043e \u0432\u044b\u0434\u0435\u043b\u0438\u0442\u044c \u0434\u0432\u0435 \u0446\u0435\u043d\u0442\u0440\u0430\u043b\u044c\u043d\u044b\u0435 \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u044b: \u0432\u043a\u043b\u044e\u0447\u0435\u043d\u0438\u0435 \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u0438 \u043e \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0435 \u0433\u0440\u0430\u0444\u0430 \u0432 \u043c\u043e\u0434\u0435\u043b\u044c (\u0442.\u0435. \u043f\u0440\u043e\u0441\u0442\u043e\u0439 \u0441\u043f\u043e\u0441\u043e\u0431 \u043a\u043e\u0434\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f \u044d\u0442\u043e\u0439 \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u0438 \u0432 \u0432\u0435\u043a\u0442\u043e\u0440 \u043f\u0440\u0438\u0437\u043d\u0430\u043a\u043e\u0432) \u0438 \u0443\u043c\u0435\u043d\u044c\u0448\u0435\u043d\u0438\u0435 \u0440\u0430\u0437\u043c\u0435\u0440\u043d\u043e\u0441\u0442\u0438 \u0432\u0435\u043a\u0442\u043e\u0440\u0430 \u043f\u0440\u0438\u0437\u043d\u0430\u043a\u043e\u0432.<\/p>\n<p>  <\/p>\n<p>\u0414\u043b\u044f \u0438\u0437\u0432\u043b\u0435\u0447\u0435\u043d\u0438\u044f \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u043d\u043e\u0439 \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u0438 \u0438\u0437 \u0433\u0440\u0430\u0444\u043e\u0432 \u0442\u0440\u0430\u0434\u0438\u0446\u0438\u043e\u043d\u043d\u044b\u0435 \u043c\u0430\u0448\u0438\u043d\u043d\u044b\u0435 \u043f\u043e\u0434\u0445\u043e\u0434\u044b \u0447\u0430\u0441\u0442\u043e \u043e\u0441\u043d\u043e\u0432\u0430\u043d\u044b \u043d\u0430 \u0441\u0432\u043e\u0434\u043d\u043e\u0439 \u0441\u0442\u0430\u0442\u0438\u0441\u0442\u0438\u043a\u0435 \u0433\u0440\u0430\u0444\u043e\u0432 (\u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440 \u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442\u0430\u0445 \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u0438\u0437\u0430\u0446\u0438\u0438), \u0444\u0443\u043d\u043a\u0446\u0438\u044f\u0445 \u044f\u0434\u0440\u0430 \u0438\u043b\u0438 \u0442\u0449\u0430\u0442\u0435\u043b\u044c\u043d\u043e \u0440\u0430\u0437\u0440\u0430\u0431\u043e\u0442\u0430\u043d\u043d\u044b\u0445 \u0444\u0443\u043d\u043a\u0446\u0438\u044f\u0445 \u0434\u043b\u044f \u0438\u0437\u043c\u0435\u0440\u0435\u043d\u0438\u044f \u043b\u043e\u043a\u0430\u043b\u044c\u043d\u044b\u0445 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440 \u043e\u043a\u0440\u0435\u0441\u0442\u043d\u043e\u0441\u0442\u0438. \u041e\u0434\u043d\u0430\u043a\u043e \u044d\u0442\u0438 \u043f\u043e\u0434\u0445\u043e\u0434\u044b \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u044b, \u043f\u043e\u0442\u043e\u043c\u0443 \u0447\u0442\u043e \u044d\u0442\u0438 \u0438\u043d\u0436\u0435\u043d\u0435\u0440\u043d\u044b\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u043d\u0435 \u043c\u043e\u0433\u0443\u0442 \u0430\u0434\u0430\u043f\u0442\u0438\u0440\u043e\u0432\u0430\u0442\u044c\u0441\u044f \u0432 \u043f\u0440\u043e\u0446\u0435\u0441\u0441\u0435 \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044f, \u0430 \u0438\u0445 \u0440\u0430\u0437\u0440\u0430\u0431\u043e\u0442\u043a\u0430 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0442\u0440\u0443\u0434\u043e\u0435\u043c\u043a\u0438\u043c \u0438 \u0434\u043e\u0440\u043e\u0433\u043e\u0441\u0442\u043e\u044f\u0449\u0438\u043c \u043f\u0440\u043e\u0446\u0435\u0441\u0441\u043e\u043c.<\/p>\n<p>  <\/p>\n<h1 id=\"pochemu-grafy\">\u041f\u043e\u0447\u0435\u043c\u0443 \u0433\u0440\u0430\u0444\u044b?<\/h1>\n<p>  <\/p>\n<p>\u0413\u043e\u0432\u043e\u0440\u044f \u043e \u0433\u0440\u0430\u0444\u0430\u0445, \u043a\u0430\u043a \u043e \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u043d\u044b\u0445 \u0435\u0434\u0438\u043d\u0438\u0446\u0430\u0445 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u0434\u0430\u043d\u043d\u044b\u0445, \u043c\u043e\u0436\u043d\u043e \u0437\u0430\u0434\u0430\u0442\u044c \u0441\u0435\u0431\u0435 \u043f\u0440\u043e\u0441\u0442\u043e\u0439 \u0432\u043e\u043f\u0440\u043e\u0441: \u043f\u043e\u0447\u0435\u043c\u0443 \u0438\u043c\u0435\u043d\u043d\u043e \u0433\u0440\u0430\u0444\u044b?<\/p>\n<p>  <\/p>\n<p>\u0413\u0440\u0430\u0444\u044b \u2014 \u043e\u0434\u0438\u043d \u0438\u0437 \u0441\u0430\u043c\u044b\u0445 \u043c\u043e\u0449\u043d\u044b\u0445 \u0438 \u0433\u0438\u0431\u043a\u0438\u0445 \u0441\u043f\u043e\u0441\u043e\u0431\u043e\u0432 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u0434\u0430\u043d\u043d\u044b\u0445. \u041e\u043d\u0438 \u043e\u0431\u043b\u0430\u0434\u0430\u044e\u0442 \u0431\u043e\u043b\u044c\u0448\u043e\u0439 \u0432\u044b\u0440\u0430\u0437\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0439 \u0441\u0438\u043b\u043e\u0439, \u0442\u043e \u0435\u0441\u0442\u044c \u0433\u0440\u0430\u0444\u044b \u043c\u043e\u0433\u0443\u0442 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c\u0441\u044f \u043a\u0430\u043a \u043e\u0431\u043e\u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0431\u043e\u043b\u044c\u0448\u043e\u0433\u043e \u0447\u0438\u0441\u043b\u0430 \u0441\u0438\u0441\u0442\u0435\u043c \u0432 \u0440\u0430\u0437\u043b\u0438\u0447\u043d\u044b\u0445 \u043e\u0431\u043b\u0430\u0441\u0442\u044f\u0445, \u0432\u043a\u043b\u044e\u0447\u0430\u044f \u043e\u0431\u0449\u0435\u0441\u0442\u0432\u0435\u043d\u043d\u044b\u0435 \u043d\u0430\u0443\u043a\u0438 (\u0441\u043e\u0446\u0438\u0430\u043b\u044c\u043d\u044b\u0435 \u0441\u0435\u0442\u0438) [<a href=\"https:\/\/cs.stanford.edu\/people\/jure\/pubs\/graphsage-nips17.pdf\">1<\/a>], [<a href=\"https:\/\/arxiv.org\/pdf\/1609.02907.pdf\">2<\/a>], \u0435\u0441\u0442\u0435\u0441\u0442\u0432\u043e\u0437\u043d\u0430\u043d\u0438\u0435 (\u0444\u0438\u0437\u0438\u0447\u0435\u0441\u043a\u0438\u0435 \u0441\u0438\u0441\u0442\u0435\u043c\u044b [<a href=\"https:\/\/arxiv.org\/pdf\/1806.01242.pdf\">3<\/a>], [<a href=\"https:\/\/arxiv.org\/pdf\/1612.00222.pdf\">4<\/a>] \u0438 \u0441\u0435\u0442\u0438 \u043c\u0435\u0436\u0431\u0435\u043b\u043a\u043e\u0432\u043e\u0433\u043e \u0432\u0437\u0430\u0438\u043c\u043e\u0434\u0435\u0439\u0441\u0442\u0432\u0438\u044f [<a href=\"https:\/\/papers.nips.cc\/paper\/7231-protein-interface-prediction-using-graph-convolutional-networks.pdf\">5<\/a>]), \u0433\u0440\u0430\u0444\u044b \u0437\u043d\u0430\u043d\u0438\u0439 [<a href=\"https:\/\/www.ijcai.org\/Proceedings\/2017\/0250.pdf\">6<\/a>] \u0438 \u043c\u043d\u043e\u0433\u0438\u0435 \u0434\u0440\u0443\u0433\u0438\u0435 \u043e\u0431\u043b\u0430\u0441\u0442\u0438 \u0438\u0441\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u043d\u0438\u0439 [<a href=\"https:\/\/arxiv.org\/pdf\/1704.01665.pdf\">7<\/a>].<\/p>\n<p>  <\/p>\n<p>\u0412 \u0431\u043e\u043b\u044c\u0448\u0438\u043d\u0441\u0442\u0432\u0435 CV\/ML \u0441\u0438\u0441\u0442\u0435\u043c \u0434\u0430\u043d\u043d\u044b\u0435 \u043c\u043e\u0433\u0443\u0442 \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0442\u044c\u0441\u044f \u043a\u0430\u043a \u0433\u0440\u0430\u0444\u044b, \u043d\u0435\u0441\u043c\u043e\u0442\u0440\u044f \u043d\u0430 \u0442\u043e, \u0447\u0442\u043e \u043c\u044b \u043f\u0440\u0438\u0432\u044b\u043a\u043b\u0438 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u0438\u0445 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u0432 \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0435 \u0434\u0440\u0443\u0433\u0438\u0445 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440 \u0434\u0430\u043d\u043d\u044b\u0445. \u041e\u0442\u043e\u0431\u0440\u0430\u0436\u0435\u043d\u0438\u0435 \u0434\u0430\u043d\u043d\u044b\u0445 \u0432 \u0432\u0438\u0434\u0435 \u0433\u0440\u0430\u0444\u043e\u0432 \u0434\u0430\u0435\u0442 \u0431\u043e\u043b\u044c\u0448\u0443\u044e \u0433\u0438\u0431\u043a\u043e\u0441\u0442\u044c \u0438 \u043c\u043e\u0436\u0435\u0442 \u0434\u0430\u0442\u044c \u0441\u043e\u0432\u0435\u0440\u0448\u0435\u043d\u043d\u043e \u0434\u0440\u0443\u0433\u043e\u0439, \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u044b\u0439, \u0432\u0437\u0433\u043b\u044f\u0434 \u043d\u0430 \u0440\u0430\u0437\u043b\u0438\u0447\u043d\u044b\u0435 \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u044b [<a href=\"https:\/\/arxiv.org\/pdf\/1603.07063.pdf\">8<\/a>].<\/p>\n<p>  <\/p>\n<p>\u041f\u0440\u043e\u0449\u0435 \u0433\u043e\u0432\u043e\u0440\u044f, \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u0433\u0440\u0430\u0444\u0430 \u043c\u044b \u043c\u043e\u0436\u0435\u043c \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u0441\u043a\u043e\u043b\u044c \u0443\u0433\u043e\u0434\u043d\u043e \u0441\u043b\u043e\u0436\u043d\u044b\u0435 \u0434\u0430\u043d\u043d\u044b\u0435. \u0422\u0430\u043a\u0430\u044f \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430 \u043f\u043e\u0434\u0445\u043e\u0434\u0438\u0442 \u043d\u0430\u0447\u0438\u043d\u0430\u044f \u043e\u0442 \u0440\u0430\u0437\u0440\u0430\u0431\u043e\u0442\u043a\u0438 \u043b\u0435\u043a\u0430\u0440\u0441\u0442\u0432 \u0438 \u0437\u0430\u043a\u0430\u043d\u0447\u0438\u0432\u0430\u044f \u0440\u0435\u043a\u043e\u043c\u0435\u043d\u0434\u0430\u0446\u0438\u044f\u043c\u0438 \u043f\u043e \u0434\u0440\u0443\u0436\u0431\u0435 \u0432 \u0441\u043e\u0446\u0438\u0430\u043b\u044c\u043d\u044b\u0445 \u0441\u0435\u0442\u044f\u0445. \u041a\u0430\u043a \u0441\u043b\u0435\u0434\u0441\u0442\u0432\u0438\u0435 \u0438\u0445 \u043f\u043e\u0432\u0441\u0435\u043c\u0435\u0441\u0442\u043d\u043e\u0441\u0442\u0438 \u0432 \u043d\u0430\u0448\u0435\u0439 \u0436\u0438\u0437\u043d\u0438, \u043c\u044b \u0432\u0438\u0434\u0438\u043c, \u0447\u0442\u043e \u0433\u0440\u0430\u0444\u044b \u0441\u0442\u0430\u043b\u0438 \u044f\u0432\u043b\u044f\u0442\u044c\u0441\u044f \u043e\u0441\u043d\u043e\u0432\u043e\u0439 \u043c\u043d\u043e\u0433\u043e\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u044b\u0445 \u0441\u0438\u0441\u0442\u0435\u043c, \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u044e\u0449\u0438\u0445 \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u043e \u0445\u0440\u0430\u043d\u0438\u0442\u044c \u0438 \u043f\u043e\u043b\u0443\u0447\u0430\u0442\u044c \u0434\u043e\u0441\u0442\u0443\u043f \u043a \u0440\u0435\u043b\u044f\u0446\u0438\u043e\u043d\u043d\u044b\u043c \u0437\u043d\u0430\u043d\u0438\u044f\u043c \u043e \u0432\u0437\u0430\u0438\u043c\u043e\u0434\u0435\u0439\u0441\u0442\u0432\u0443\u044e\u0449\u0438\u0445 \u043e\u0431\u044a\u0435\u043a\u0442\u0430\u0445.<\/p>\n<p>  <\/p>\n<h1 id=\"kratkaya-istoriya\">\u041a\u0440\u0430\u0442\u043a\u0430\u044f \u0438\u0441\u0442\u043e\u0440\u0438\u044f<\/h1>\n<p>  <\/p>\n<p>\u0412 \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0435\u0435 \u0432\u0440\u0435\u043c\u044f \u043d\u0430\u0431\u043b\u044e\u0434\u0430\u0435\u0442\u0441\u044f \u0432\u0441\u043f\u043b\u0435\u0441\u043a \u043f\u043e\u0434\u0445\u043e\u0434\u043e\u0432, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0441\u0442\u0440\u0435\u043c\u044f\u0442\u0441\u044f \u0438\u0437\u0443\u0447\u0438\u0442\u044c \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u044f (<strong>embeddings<\/strong>), \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043a\u043e\u0434\u0438\u0440\u0443\u044e\u0442 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u043d\u0443\u044e \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u044e \u043e \u0433\u0440\u0430\u0444\u0438\u043a\u0435. \u0418\u0434\u0435\u044f, \u043b\u0435\u0436\u0430\u0449\u0430\u044f \u0432 \u043e\u0441\u043d\u043e\u0432\u0435 \u044d\u0442\u0438\u0445 \u043f\u043e\u0434\u0445\u043e\u0434\u043e\u0432 \u043a \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044e \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u044f, \u0441\u043e\u0441\u0442\u043e\u0438\u0442 \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e\u0431\u044b \u0438\u0437\u0443\u0447\u0438\u0442\u044c \u043e\u0442\u043e\u0431\u0440\u0430\u0436\u0435\u043d\u0438\u0435, \u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u0442 \u0443\u0437\u043b\u044b \u0438\u043b\u0438 \u0446\u0435\u043b\u044b\u0435 (\u043f\u043e\u0434)\u0433\u0440\u0430\u0444\u044b, \u043a\u0430\u043a \u0442\u043e\u0447\u043a\u0438 \u0432 \u043d\u0438\u0437\u043a\u043e\u0440\u0430\u0437\u043c\u0435\u0440\u043d\u043e\u043c \u0432\u0435\u043a\u0442\u043e\u0440\u043d\u043e\u043c \u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432\u0435 <math>$inline$R^d$inline$<\/math>. \u0426\u0435\u043b\u044c \u0441\u043e\u0441\u0442\u043e\u0438\u0442 \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e\u0431\u044b \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u044d\u0442\u043e \u043e\u0442\u043e\u0431\u0440\u0430\u0436\u0435\u043d\u0438\u0435 \u0442\u0430\u043a, \u0447\u0442\u043e\u0431\u044b \u0433\u0435\u043e\u043c\u0435\u0442\u0440\u0438\u0447\u0435\u0441\u043a\u0438\u0435 \u043e\u0442\u043d\u043e\u0448\u0435\u043d\u0438\u044f \u0432 \u044d\u0442\u043e\u043c \u0438\u0437\u0443\u0447\u0435\u043d\u043d\u043e\u043c \u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432\u0435 \u043e\u0442\u043e\u0431\u0440\u0430\u0436\u0430\u043b\u0438 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0443 \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u0433\u043e \u0433\u0440\u0430\u0444\u0430. \u041f\u043e\u0441\u043b\u0435 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0438 \u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432\u0430 \u043e\u0442\u043e\u0431\u0440\u0430\u0436\u0435\u043d\u0438\u044f, \u0438\u0437\u0443\u0447\u0435\u043d\u043d\u044b\u0435 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u043c\u043e\u0433\u0443\u0442 \u0431\u044b\u0442\u044c \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u044b \u0432 \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0435 \u0432\u0445\u043e\u0434\u043d\u044b\u0445 \u0434\u0430\u043d\u043d\u044b\u0445 \u0434\u043b\u044f \u043f\u043e\u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0445 \u0437\u0430\u0434\u0430\u0447 \u043c\u0430\u0448\u0438\u043d\u043d\u043e\u0433\u043e \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044f.<\/p>\n<p>  <\/p>\n<p>\u0420\u0430\u043d\u0435\u0435 \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u0430 \u0441\u0431\u043e\u0440\u0430 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u043d\u043e\u0439 \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u0438 \u043e \u0433\u0440\u0430\u0444\u0435 \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u043b\u0430\u0441\u044c \u043a\u0430\u043a \u0448\u0430\u0433 \u043f\u0440\u0435\u0434\u0432\u0430\u0440\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0439 \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u043a\u0438, \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044e\u0449\u0438\u0439 \u0432\u0440\u0443\u0447\u043d\u0443\u044e \u0441\u043f\u0440\u043e\u0435\u043a\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u0443\u044e \u0441\u0442\u0430\u0442\u0438\u0441\u0442\u0438\u043a\u0443 \u0434\u043b\u044f \u0438\u0437\u0432\u043b\u0435\u0447\u0435\u043d\u0438\u044f \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u043d\u043e\u0439 \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u0438. \u0421\u0435\u0439\u0447\u0430\u0441, \u043d\u0430\u043f\u0440\u043e\u0442\u0438\u0432, \u043f\u043e\u0434\u0445\u043e\u0434\u044b \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044f \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u0439 \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u044e\u0442 \u044d\u0442\u0443 \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u0443 \u043a\u0430\u043a \u0441\u0430\u043c\u0443 \u0437\u0430\u0434\u0430\u0447\u0443 \u043c\u0430\u0448\u0438\u043d\u043d\u043e\u0433\u043e \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044f. \u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b, \u043e\u0441\u043d\u043e\u0432\u0430\u043d\u043d\u044b\u0435 \u043d\u0430 \u0434\u0430\u043d\u043d\u044b\u0445, \u0441\u043e\u0437\u0434\u0430\u044e\u0442 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u044f, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043a\u043e\u0434\u0438\u0440\u0443\u044e\u0442 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0443 \u0433\u0440\u0430\u0444\u0430.<\/p>\n<p>  <\/p>\n<p>\u0411\u043e\u043b\u044c\u0448\u0438\u043d\u0441\u0442\u0432\u043e \u0441\u043e\u0432\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0445 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u0432 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u0443\u0437\u043b\u043e\u0432 \u043e\u043f\u0438\u0440\u0430\u044e\u0442\u0441\u044f \u043d\u0430 \u0442\u043e, \u0447\u0442\u043e \u043c\u044b \u043d\u0430\u0437\u044b\u0432\u0430\u0435\u043c <strong>\u043f\u0440\u044f\u043c\u044b\u043c \u043a\u043e\u0434\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435\u043c<\/strong> (<strong>direct encoding<\/strong>), \u043a\u043e\u0433\u0434\u0430 \u0442\u043e\u043f\u043e\u043b\u043e\u0433\u0438\u0447\u0435\u0441\u043a\u0430\u044f \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u044f \u0445\u0440\u0430\u043d\u0438\u0442\u0441\u044f \u0432 \u044f\u0432\u043d\u043e\u043c \u0432\u0438\u0434\u0435. \u042d\u0442\u0438 \u043f\u043e\u0434\u0445\u043e\u0434\u044b \u0432\u043e \u043c\u043d\u043e\u0433\u043e\u043c \u043e\u0441\u043d\u043e\u0432\u0430\u043d\u044b \u043d\u0430 \u043a\u043b\u0430\u0441\u0441\u0438\u0447\u0435\u0441\u043a\u0438\u0445 \u043c\u0435\u0442\u043e\u0434\u0430\u0445 \u0444\u0430\u043a\u0442\u043e\u0440\u0438\u0437\u0430\u0446\u0438\u0438 \u043c\u0430\u0442\u0440\u0438\u0446\u044b \u0434\u043b\u044f \u0443\u043c\u0435\u043d\u044c\u0448\u0435\u043d\u0438\u044f \u0440\u0430\u0437\u043c\u0435\u0440\u043d\u043e\u0441\u0442\u0438 \u0438 \u043c\u043d\u043e\u0433\u043e\u043c\u0435\u0440\u043d\u043e\u0433\u043e \u043c\u0430\u0441\u0448\u0442\u0430\u0431\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f. \u0414\u0435\u0439\u0441\u0442\u0432\u0438\u0442\u0435\u043b\u044c\u043d\u043e, \u043c\u043d\u043e\u0433\u0438\u0435 \u0438\u0437 \u044d\u0442\u0438\u0445 \u043f\u043e\u0434\u0445\u043e\u0434\u043e\u0432 \u0438\u0437\u043d\u0430\u0447\u0430\u043b\u044c\u043d\u043e \u0431\u044b\u043b\u0438 \u043c\u043e\u0442\u0438\u0432\u0438\u0440\u043e\u0432\u0430\u043d\u044b \u043a\u0430\u043a \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u0444\u0430\u043a\u0442\u043e\u0440\u0438\u0437\u0430\u0446\u0438\u0438, \u0430 \u0437\u0430\u0442\u0435\u043c \u0431\u044b\u043b\u0438 \u043f\u0435\u0440\u0435\u043e\u0441\u043c\u044b\u0441\u043b\u0435\u043d\u044b \u0432 \u0440\u0430\u043c\u043a\u0430\u0445 \u043a\u043e\u043d\u0446\u0435\u043f\u0446\u0438\u0438 <strong>\u043a\u043e\u0434\u0435\u0440-\u0434\u0435\u043a\u043e\u0434\u0435\u0440<\/strong>. \u0420\u0430\u0437\u043b\u0438\u0447\u0430\u044e\u0442 \u043f\u043e\u0434\u0445\u043e\u0434\u044b, \u043e\u0441\u043d\u043e\u0432\u0430\u043d\u043d\u044b\u0435 \u043d\u0430 <strong>\u043c\u0430\u0442\u0440\u0438\u0447\u043d\u043e\u0439 \u0444\u0430\u043a\u0442\u043e\u0440\u0438\u0437\u0430\u0446\u0438\u0438<\/strong>, \u0438 \u0431\u043e\u043b\u0435\u0435 \u0441\u043e\u0432\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0435 \u043f\u043e\u0434\u0445\u043e\u0434\u044b, \u043e\u0441\u043d\u043e\u0432\u0430\u043d\u043d\u044b\u0435 \u043d\u0430 <strong>\u0441\u043b\u0443\u0447\u0430\u0439\u043d\u044b\u0445 \u043f\u0440\u043e\u0433\u0443\u043b\u043a\u0430\u0445<\/strong>.<\/p>\n<p>  <\/p>\n<p>\u041e\u0434\u043d\u0438 \u0438\u0437 \u0445\u043e\u0440\u043e\u0448\u043e \u0438\u0437\u0432\u0435\u0441\u0442\u043d\u044b\u0445 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u0432 <a href=\"https:\/\/arxiv.org\/pdf\/1403.6652.pdf\">DeepWalk<\/a> \u0438 <a href=\"https:\/\/snap.stanford.edu\/node2vec\/\">node2vec<\/a> \u0442\u043e\u0436\u0435 \u043f\u043e\u043b\u0430\u0433\u0430\u044e\u0442\u0441\u044f \u043d\u0430 \u043f\u0440\u044f\u043c\u043e\u0435 \u043a\u043e\u0434\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435 \u0441 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u0435\u043c \u0441\u0432\u043e\u0435\u0433\u043e \u0441\u043e\u0431\u0441\u0442\u0432\u0435\u043d\u043d\u043e\u0433\u043e \u0434\u0435\u043a\u043e\u0434\u0435\u0440\u0430. \u0412 \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0435 \u043c\u0435\u0440\u044b \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0438 \u0443 \u043d\u0438\u0445 \u0432\u044b\u0441\u0442\u0443\u043f\u0430\u0435\u0442 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0438\u0440\u0443\u0435\u0442 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u0435 \u0434\u043b\u044f \u043a\u043e\u0434\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f \u0441\u0442\u0430\u0442\u0438\u0441\u0442\u0438\u043a\u0438 \u0441\u043b\u0443\u0447\u0430\u0439\u043d\u044b\u0445 \u043f\u0440\u043e\u0433\u0443\u043b\u043e\u043a. \u0411\u043b\u0430\u0433\u043e\u0434\u0430\u0440\u044f \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u044e \u0441\u043e\u0432\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0445 \u043f\u043e\u0434\u0445\u043e\u0434\u043e\u0432, \u044d\u0442\u0438 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u0441\u0447\u0438\u0442\u0430\u044e\u0442\u0441\u044f \u043d\u0430\u0438\u0431\u043e\u043b\u0435\u0435 \u0440\u0435\u043b\u0435\u0432\u0430\u043d\u0442\u043d\u044b\u043c\u0438 \u0441\u0440\u0435\u0434\u0438 \u043e\u0431\u0449\u0435\u0434\u043e\u0441\u0442\u0443\u043f\u043d\u044b\u0445 \u0440\u0435\u0448\u0435\u043d\u0438\u0439.<\/p>\n<p>  <\/p>\n<p>\u041f\u043e\u0441\u043b\u0435\u0434\u043d\u0438\u0435 \u0440\u0430\u0437\u0440\u0430\u0431\u043e\u0442\u043a\u0438 \u0432 \u0441\u0444\u0435\u0440\u0435 \u043c\u0435\u0442\u043e\u0434\u043e\u0432 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u0443\u0437\u043b\u043e\u0432 \u0441\u043f\u043e\u0441\u043e\u0431\u043d\u044b \u0440\u0435\u0448\u0438\u0442\u044c \u0440\u044f\u0434 \u0432\u0430\u0436\u043d\u044b\u0445 \u043f\u0440\u043e\u0431\u043b\u0435\u043c (\u043e \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u043c\u044b \u0433\u043e\u0432\u043e\u0440\u0438\u043c \u0447\u0443\u0442\u044c \u043f\u043e\u0437\u0436\u0435). \u042d\u0442\u043e \u0441\u0442\u0430\u043b\u043e \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b\u043c \u0431\u043b\u0430\u0433\u043e\u0434\u0430\u0440\u044f \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u044e <strong>\u0430\u0432\u0442\u043e\u044d\u043d\u043a\u043e\u0434\u0435\u0440\u0430 \u043e\u043a\u0440\u0435\u0441\u0442\u043d\u043e\u0441\u0442\u0435\u0439<\/strong> (<strong>DNGR<\/strong> \u0438 <strong>SDNE<\/strong>), <strong>\u0430\u0433\u0440\u0435\u0433\u0430\u0446\u0438\u0438 \u043e\u043a\u0440\u0435\u0441\u0442\u043d\u043e\u0441\u0442\u0435\u0439<\/strong>, <strong>\u043c\u0435\u0445\u0430\u043d\u0438\u0437\u043c\u043e\u0432 \u0432\u043d\u0438\u043c\u0430\u043d\u0438\u044f<\/strong> \u0438 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u0434\u0440\u0443\u0433\u0438\u0445 \u043f\u0440\u043e\u0434\u0432\u0438\u043d\u0443\u0442\u044b\u0445 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u0432 [<a href=\"https:\/\/arxiv.org\/pdf\/1901.00596.pdf\">9<\/a>].<\/p>\n<p>  <\/p>\n<h2 id=\"oboznacheniya-i-osnovnye-predpolozheniya\">\u041e\u0431\u043e\u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u0438 \u043e\u0441\u043d\u043e\u0432\u043d\u044b\u0435 \u043f\u0440\u0435\u0434\u043f\u043e\u043b\u043e\u0436\u0435\u043d\u0438\u044f<\/h2>\n<p>  <\/p>\n<p>\u0413\u0440\u0430\u0444\u043e\u043c \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043f\u0430\u0440\u0430 <math>$inline$G = (V, E)$inline$<\/math>, \u0433\u0434\u0435 <math>$inline$V$inline$<\/math> \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u0442 \u0441\u043e\u0431\u043e\u0439 \u043d\u0430\u0431\u043e\u0440, \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u043d\u0430\u0437\u044b\u0432\u0430\u044e\u0442\u0441\u044f <strong>\u0432\u0435\u0440\u0448\u0438\u043d\u0430\u043c\u0438<\/strong>, \u0430 <math>$inline$E$inline$<\/math> \u2014 \u044d\u0442\u043e \u043d\u0430\u0431\u043e\u0440 \u0438\u0437 \u0434\u0432\u0443\u0445 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432 (\u043d\u0430\u0431\u043e\u0440\u043e\u0432 \u0441 \u0434\u0432\u0443\u043c\u044f \u0440\u0430\u0437\u043b\u0438\u0447\u043d\u044b\u043c\u0438 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430\u043c\u0438) \u0432\u0435\u0440\u0448\u0438\u043d, \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u043d\u0430\u0437\u044b\u0432\u0430\u044e\u0442\u0441\u044f <strong>\u0440\u0435\u0431\u0440\u0430\u043c\u0438<\/strong>.<\/p>\n<p>  <\/p>\n<p>\u0420\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u043f\u0440\u043e\u0441\u0442\u0435\u0439\u0448\u0438\u0439 \u043d\u0435\u043e\u0440\u0438\u0435\u043d\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0439 \u0433\u0440\u0430\u0444 (\u0440\u0438\u0441.1). \u0414\u043b\u044f \u0442\u0430\u043a\u043e\u0433\u043e \u0433\u0440\u0430\u0444\u0430 \u0438\u043c\u0435\u0435\u043c: <math>$inline$V = \\\\{1,2,3,4,5,6\\\\}$inline$<\/math> \u0438 <math>$inline$E = \\\\{\\\\{1, 2\\\\},\\\\{1, 5\\\\},\\\\{2, 3\\\\},\\\\{2, 5\\\\},\\\\{3, 4\\\\},\\\\{4, 5\\\\},\\\\{4, 6\\\\}\\\\}$inline$<\/math><\/p>\n<p>  <\/p>\n<p><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/ei\/3v\/8m\/ei3v8mrl-yla85yq87pcfo5lqga.png\" alt=\"image\"\/><\/p>\n<p>  <\/p>\n<p>\u041d\u0435\u0441\u043c\u043e\u0442\u0440\u044f \u043d\u0430 \u0442\u043e, \u0447\u0442\u043e \u043c\u043d\u043e\u0433\u0438\u0435 \u0433\u0440\u0430\u0444\u044b \u0440\u0435\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u043c\u0438\u0440\u0430 \u0438\u043c\u0435\u044e\u0442 \u0441\u043b\u043e\u0436\u043d\u0443\u044e \u043c\u0443\u043b\u044c\u0442\u0438\u043c\u043e\u0434\u0430\u043b\u044c\u043d\u0443\u044e \u0438\u043b\u0438 \u043c\u043d\u043e\u0433\u043e\u0441\u043b\u043e\u0439\u043d\u0443\u044e \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0443, \u043c\u044b \u0434\u043b\u044f \u043f\u0440\u043e\u0441\u0442\u043e\u0442\u044b \u0441\u043e\u0441\u0440\u0435\u0434\u043e\u0442\u043e\u0447\u0438\u043c\u0441\u044f \u043d\u0430 \u043f\u0440\u043e\u0441\u0442\u044b\u0445, \u043d\u0435\u043e\u0440\u0438\u0435\u043d\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0445 \u0433\u0440\u0430\u0444\u0430\u0445 (\u0441\u0442\u043e\u0438\u0442 \u043e\u0442\u043c\u0435\u0442\u0438\u0442\u044c, \u0447\u0442\u043e \u0440\u044f\u0434 \u0441\u043e\u0432\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0445 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u0432 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u044f\u044e\u0442 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u0441\u043f\u0440\u0430\u0432\u043b\u044f\u0442\u044c\u0441\u044f \u0441 \u043d\u0435\u043e\u0434\u043d\u043e\u0440\u043e\u0434\u043d\u043e\u0439 \u0442\u043e\u043f\u043e\u043b\u043e\u0433\u0438\u0435\u0439 \u0433\u0440\u0430\u0444\u043e\u0432). \u041f\u043e\u0434\u0440\u043e\u0431\u043d\u0435\u0435 \u043f\u0440\u043e \u0442\u0435\u043e\u0440\u0438\u044e \u0433\u0440\u0430\u0444\u043e\u0432 \u043c\u043e\u0436\u043d\u043e \u043f\u043e\u0447\u0438\u0442\u0430\u0442\u044c <a href=\"https:\/\/function-x.ru\/graphs2_definitions_classes.html\">\u0442\u0443\u0442<\/a>.<\/p>\n<p>  <\/p>\n<p>\u041f\u0440\u0435\u0434\u043f\u043e\u043b\u043e\u0436\u0438\u043c, \u0447\u0442\u043e \u043e\u0441\u043d\u043e\u0432\u043d\u044b\u043c \u0432\u0445\u043e\u0434\u043d\u044b\u043c \u0441\u0438\u0433\u043d\u0430\u043b\u043e\u043c \u0434\u043b\u044f \u043d\u0430\u0448\u0435\u0433\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044f \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u0439 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043d\u0435\u043e\u0440\u0438\u0435\u043d\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0439 \u0433\u0440\u0430\u0444 <math>$inline$G = (V, E)$inline$<\/math> \u0441\u043e \u0441\u0432\u044f\u0437\u0430\u043d\u043d\u043e\u0439 \u0434\u0432\u043e\u0438\u0447\u043d\u043e\u0439 \u043c\u0430\u0442\u0440\u0438\u0446\u0435\u0439 \u0441\u043c\u0435\u0436\u043d\u043e\u0441\u0442\u0438 <math>$inline$A$inline$<\/math>. \u041c\u044b \u0442\u0430\u043a\u0436\u0435 \u043f\u0440\u0435\u0434\u043f\u043e\u043b\u0430\u0433\u0430\u0435\u043c, \u0447\u0442\u043e \u043c\u0435\u0442\u043e\u0434\u044b \u043c\u043e\u0433\u0443\u0442 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u0432\u0435\u0449\u0435\u0441\u0442\u0432\u0435\u043d\u043d\u0443\u044e \u043c\u0430\u0442\u0440\u0438\u0446\u0443 \u0430\u0442\u0440\u0438\u0431\u0443\u0442\u043e\u0432 \u0443\u0437\u043b\u0430 <math>$inline$X \u2208 R^{m*|V|}$inline$<\/math> (\u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u0435 \u0442\u0435\u043a\u0441\u0442\u0430 \u0438\u043b\u0438 \u043c\u0435\u0442\u0430\u0434\u0430\u043d\u043d\u044b\u0445, \u0441\u0432\u044f\u0437\u0430\u043d\u043d\u044b\u0445 \u0441 \u0443\u0437\u043b\u0430\u043c\u0438). \u0426\u0435\u043b\u044c \u0441\u043e\u0441\u0442\u043e\u0438\u0442 \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e\u0431\u044b \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u044e, \u0441\u043e\u0434\u0435\u0440\u0436\u0430\u0449\u0443\u044e\u0441\u044f \u0432 <math>$inline$A$inline$<\/math> \u0438 <math>$inline$X$inline$<\/math>, \u0447\u0442\u043e\u0431\u044b \u043e\u0442\u043e\u0431\u0440\u0430\u0437\u0438\u0442\u044c \u043a\u0430\u0436\u0434\u044b\u0439 \u0443\u0437\u0435\u043b \u0438\u043b\u0438 \u043f\u043e\u0434\u0433\u0440\u0430\u0444 \u043d\u0430 \u0432\u0435\u043a\u0442\u043e\u0440 <math>$inline$z \u2208 R^d$inline$<\/math>, \u0433\u0434\u0435 <math>$inline$d &lt;&lt; |V|$inline$<\/math>.<\/p>\n<p>  <\/p>\n<p>\u0411\u043e\u043b\u044c\u0448\u0438\u043d\u0441\u0442\u0432\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c\u044b\u0445 \u043c\u0435\u0442\u043e\u0434\u043e\u0432 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0438\u0440\u0443\u044e\u0442 \u044d\u0442\u043e \u043e\u0442\u043e\u0431\u0440\u0430\u0436\u0435\u043d\u0438\u0435 \u0431\u0435\u0437 \u0443\u0447\u0438\u0442\u0435\u043b\u044f, \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044f \u0442\u043e\u043b\u044c\u043a\u043e \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u044e \u0432 <math>$inline$A$inline$<\/math> \u0438 <math>$inline$X$inline$<\/math>, \u043d\u0435 \u0437\u043d\u0430\u044f \u043f\u043e\u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0439 \u0437\u0430\u0434\u0430\u0447\u0438 \u043c\u0430\u0448\u0438\u043d\u043d\u043e\u0433\u043e \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044f. \u0422\u0435\u043c \u043d\u0435 \u043c\u0435\u043d\u0435\u0435, \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u044e\u0442 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043f\u043e\u0434\u0445\u043e\u0434\u044b \u043a \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044e \u0440\u0435\u043f\u0440\u0435\u0437\u0435\u043d\u0442\u0430\u0442\u0438\u0432\u043d\u043e\u0433\u043e \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u044f, \u0433\u0434\u0435 \u043c\u043e\u0434\u0435\u043b\u0438 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044e\u0442 \u043a\u043b\u0430\u0441\u0441\u0438\u0444\u0438\u043a\u0430\u0446\u0438\u043e\u043d\u043d\u044b\u0435 \u0438\u043b\u0438 \u0440\u0435\u0433\u0440\u0435\u0441\u0441\u0438\u043e\u043d\u043d\u044b\u0435 \u043c\u0435\u0442\u043a\u0438 \u0434\u043b\u044f \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0438 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u0439. \u042d\u0442\u0438 \u043a\u043b\u0430\u0441\u0441\u0438\u0444\u0438\u043a\u0430\u0446\u0438\u043e\u043d\u043d\u044b\u0435 \u043c\u0435\u0442\u043a\u0438 \u043c\u043e\u0433\u0443\u0442 \u0431\u044b\u0442\u044c \u0441\u0432\u044f\u0437\u0430\u043d\u044b \u0441 \u043e\u0442\u0434\u0435\u043b\u044c\u043d\u044b\u043c\u0438 \u0443\u0437\u043b\u0430\u043c\u0438 \u0438\u043b\u0438 \u0446\u0435\u043b\u044b\u043c\u0438 \u043f\u043e\u0434\u0433\u0440\u0430\u0444\u0430\u043c\u0438 \u0438 \u044f\u0432\u043b\u044f\u044e\u0442\u0441\u044f \u0446\u0435\u043b\u044f\u043c\u0438 \u043f\u0440\u043e\u0433\u043d\u043e\u0437\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f \u0434\u043b\u044f \u043f\u043e\u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0445 \u0437\u0430\u0434\u0430\u0447 \u043c\u0430\u0448\u0438\u043d\u043d\u043e\u0433\u043e \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044f (\u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u043e\u043d\u0438 \u043c\u043e\u0433\u0443\u0442 \u043e\u0431\u043e\u0437\u043d\u0430\u0447\u0430\u0442\u044c \u0440\u043e\u043b\u0438 \u0431\u0435\u043b\u043a\u0430 \u0438\u043b\u0438 \u0442\u0435\u0440\u0430\u043f\u0435\u0432\u0442\u0438\u0447\u0435\u0441\u043a\u0438\u0435 \u0441\u0432\u043e\u0439\u0441\u0442\u0432\u0430 \u043c\u043e\u043b\u0435\u043a\u0443\u043b\u044b \u043d\u0430 \u043e\u0441\u043d\u043e\u0432\u0435 \u0435\u0435 \u0433\u0440\u0430\u0444\u0438\u0447\u0435\u0441\u043a\u043e\u0433\u043e \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u044f)<\/p>\n<p>  <\/p>\n<p>\u041f\u043e\u0434\u0445\u043e\u0434 <strong>\u043a\u043e\u0434\u0435\u0440-\u0434\u0435\u043a\u043e\u0434\u0435\u0440<\/strong> \u0437\u0430\u043a\u043b\u044e\u0447\u0430\u0435\u0442\u0441\u044f \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e \u0441\u043d\u0430\u0447\u0430\u043b\u0430 \u043a\u043e\u0434\u0435\u0440 \u043e\u0442\u043e\u0431\u0440\u0430\u0436\u0430\u0435\u0442 \u0443\u0437\u0435\u043b <math>$inline$v_i$inline$<\/math> \u0432 \u043d\u0438\u0437\u043a\u043e\u0440\u0430\u0437\u043c\u0435\u0440\u043d\u043e\u0435 \u0432\u0435\u043a\u0442\u043e\u0440\u043d\u043e\u0435 \u0432\u043b\u043e\u0436\u0435\u043d\u0438\u0435 <math>$inline$z_i$inline$<\/math> \u043d\u0430 \u043e\u0441\u043d\u043e\u0432\u0435 \u043f\u043e\u043b\u043e\u0436\u0435\u043d\u0438\u044f \u0443\u0437\u043b\u0430 \u0432 \u0433\u0440\u0430\u0444\u0435, \u0435\u0433\u043e \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u043b\u043e\u043a\u0430\u043b\u044c\u043d\u044b\u0445 \u043e\u043a\u0440\u0435\u0441\u0442\u043d\u043e\u0441\u0442\u0435\u0439 \u0438\/\u0438\u043b\u0438 \u0435\u0433\u043e \u0430\u0442\u0440\u0438\u0431\u0443\u0442\u043e\u0432. \u0417\u0430\u0442\u0435\u043c \u0434\u0435\u043a\u043e\u0434\u0435\u0440 \u0438\u0437\u0432\u043b\u0435\u043a\u0430\u0435\u0442 \u0443\u043a\u0430\u0437\u0430\u043d\u043d\u0443\u044e \u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u0435\u043b\u0435\u043c \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u044e \u0438\u0437 \u043d\u0438\u0437\u043a\u043e\u0440\u0430\u0437\u043c\u0435\u0440\u043d\u043e\u0433\u043e \u0432\u043d\u0435\u0434\u0440\u0435\u043d\u0438\u044f; \u044d\u0442\u043e \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u044f \u043e \u043b\u043e\u043a\u0430\u043b\u044c\u043d\u043e\u0439 \u043e\u043a\u0440\u0435\u0441\u0442\u043d\u043e\u0441\u0442\u0438 \u0433\u0440\u0430\u0444\u0430 <math>$inline$v_i$inline$<\/math> (\u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440 \u0438\u0434\u0435\u043d\u0442\u0438\u0444\u0438\u043a\u0430\u0446\u0438\u044f \u0435\u0433\u043e \u0441\u043e\u0441\u0435\u0434\u0435\u0439) \u0438\u043b\u0438 \u043c\u0435\u0442\u043a\u0430 \u043a\u043b\u0430\u0441\u0441\u0438\u0444\u0438\u043a\u0430\u0446\u0438\u0438, \u0441\u0432\u044f\u0437\u0430\u043d\u043d\u0430\u044f \u0441 <math>$inline$v_i$inline$<\/math> (\u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440 \u043c\u0435\u0442\u043a\u0430 \u0441\u043e\u043e\u0431\u0449\u0435\u0441\u0442\u0432\u0430). \u0421\u043e\u0432\u043c\u0435\u0441\u0442\u043d\u043e \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0438\u0440\u0443\u044f \u043a\u043e\u0434\u0435\u0440 \u0438 \u0434\u0435\u043a\u043e\u0434\u0435\u0440, \u0441\u0438\u0441\u0442\u0435\u043c\u0430 \u0443\u0447\u0438\u0442\u0441\u044f \u0441\u0436\u0438\u043c\u0430\u0442\u044c \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u044e \u043e \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0435 \u0433\u0440\u0430\u0444\u0430 \u0432 \u043d\u0438\u0437\u043a\u043e\u0440\u0430\u0437\u043c\u0435\u0440\u043d\u043e\u0435 \u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432\u043e \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u0439.<\/p>\n<p>  <\/p>\n<p><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/d6\/pw\/ax\/d6pwaxx-4batpq30ierl69ctohm.png\" alt=\"image\"\/><\/p>\n<p>  <\/p>\n<h1 id=\"predstavleniya-uzlov\">\u041f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u0443\u0437\u043b\u043e\u0432<\/h1>\n<p>  <\/p>\n<p>\u041c\u044b \u043d\u0430\u0447\u043d\u0435\u043c \u0441 \u043e\u0431\u0441\u0443\u0436\u0434\u0435\u043d\u0438\u044f \u043c\u0435\u0442\u043e\u0434\u043e\u0432 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u0443\u0437\u043b\u043e\u0432, \u0433\u0434\u0435 \u0446\u0435\u043b\u044c \u0441\u043e\u0441\u0442\u043e\u0438\u0442 \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e\u0431\u044b \u0437\u0430\u043a\u043e\u0434\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0443\u0437\u043b\u044b \u043a\u0430\u043a \u043d\u0438\u0437\u043a\u043e\u0440\u0430\u0437\u043c\u0435\u0440\u043d\u044b\u0435 \u0432\u0435\u043a\u0442\u043e\u0440\u044b, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0441\u0443\u043c\u043c\u0438\u0440\u0443\u044e\u0442 \u0438\u0445 \u043f\u043e\u043b\u043e\u0436\u0435\u043d\u0438\u0435 \u0432 \u0433\u0440\u0430\u0444\u0435 \u0438 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0443 \u043b\u043e\u043a\u0430\u043b\u044c\u043d\u043e\u0439 \u043e\u043a\u0440\u0435\u0441\u0442\u043d\u043e\u0441\u0442\u0438 \u0433\u0440\u0430\u0444\u0430. \u042d\u0442\u0438 \u043d\u0438\u0437\u043a\u043e\u0440\u0430\u0437\u043c\u0435\u0440\u043d\u044b\u0435 \u0432\u043b\u043e\u0436\u0435\u043d\u0438\u044f \u043c\u043e\u0436\u043d\u043e \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0442\u044c \u043a\u0430\u043a \u043a\u043e\u0434\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435 \u0438\u043b\u0438 \u043f\u0440\u043e\u0435\u0446\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435 \u0443\u0437\u043b\u043e\u0432 \u0432 \u0441\u043a\u0440\u044b\u0442\u043e\u0435 \u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432\u043e, \u0433\u0434\u0435 \u0433\u0435\u043e\u043c\u0435\u0442\u0440\u0438\u0447\u0435\u0441\u043a\u0438\u0435 \u043e\u0442\u043d\u043e\u0448\u0435\u043d\u0438\u044f \u0432 \u044d\u0442\u043e\u043c \u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432\u0435 \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u044e\u0442 \u0432\u0437\u0430\u0438\u043c\u043e\u0434\u0435\u0439\u0441\u0442\u0432\u0438\u044f\u043c (\u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0440\u0435\u0431\u0440\u0430\u043c) \u0432 \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u043c \u0433\u0440\u0430\u0444\u0435. \u041d\u0430 \u0440\u0438\u0441\u0443\u043d\u043a\u0435 2 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d \u043f\u0440\u0438\u043c\u0435\u0440 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u0441\u043e\u0446\u0438\u0430\u043b\u044c\u043d\u043e\u0439 \u0441\u0435\u0442\u0438, \u0433\u0434\u0435 \u0432\u043b\u043e\u0436\u0435\u043d\u0438\u044f \u0434\u0432\u0443\u043c\u0435\u0440\u043d\u044b\u0445 \u0443\u0437\u043b\u043e\u0432 \u043e\u0442\u0440\u0430\u0436\u0430\u044e\u0442 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0443 \u0441\u043e\u043e\u0431\u0449\u0435\u0441\u0442\u0432\u0430, \u043d\u0435\u044f\u0432\u043d\u0443\u044e \u0432 \u0441\u0435\u0442\u0438.<\/p>\n<p>  <\/p>\n<p><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/ey\/2b\/i2\/ey2bi2uuvz_ybk2ii0aj5iwnjny.png\" alt=\"image\"\/><\/p>\n<p>  <\/p>\n<p>\u041c\u043e\u0436\u043d\u043e \u0441\u043a\u0430\u0437\u0430\u0442\u044c, \u0447\u0442\u043e \u043a\u043e\u0434\u0438\u0440\u043e\u0432\u0449\u0438\u043a \u2014 \u044d\u0442\u043e \u0444\u0443\u043d\u043a\u0446\u0438\u044f, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u043e\u0442\u043e\u0431\u0440\u0430\u0436\u0430\u0435\u0442 \u0443\u0437\u043b\u044b \u043d\u0430 \u0432\u0435\u043a\u0442\u043e\u0440\u043d\u044b\u0435 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u044f, <math>$inline$z_i \u2208 R^d$inline$<\/math> (\u0433\u0434\u0435 <math>$inline$z_i$inline$<\/math> \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u0435\u0442 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u044e \u0434\u043b\u044f \u0443\u0437\u043b\u0430 <math>$inline$v_i \u2208 V$inline$<\/math>):<\/p>\n<p>  <\/p>\n<p><math>$$display$$\\textbf{ENC: } V \u2192 R^d$$display$$<\/math><\/p>\n<p>  <\/p>\n<p>\u0422\u043e\u0433\u0434\u0430 \u0434\u0435\u043a\u043e\u0434\u0435\u0440 \u2014 \u0444\u0443\u043d\u043a\u0446\u0438\u044f, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u043f\u0440\u0438\u043d\u0438\u043c\u0430\u0435\u0442 \u043d\u0430\u0431\u043e\u0440 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u0439 \u0443\u0437\u043b\u043e\u0432 \u0438 \u0434\u0435\u043a\u043e\u0434\u0438\u0440\u0443\u0435\u0442 \u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u0441\u043a\u0443\u044e \u0433\u0440\u0430\u0444\u043e\u0432\u0443\u044e \u0441\u0442\u0430\u0442\u0438\u0441\u0442\u0438\u043a\u0443 \u0438\u0437 \u044d\u0442\u0438\u0445 \u0432\u043b\u043e\u0436\u0435\u043d\u0438\u0439:<\/p>\n<p>  <\/p>\n<p><math>$$display$$\\textbf{DEC: } R^d * R^d \u2192 R^+$$display$$<\/math><\/p>\n<p>  <\/p>\n<p>\u0418\u0437 \u043e\u0431\u0448\u0438\u0440\u043d\u043e\u0433\u043e \u0447\u0438\u0441\u043b\u0430 \u0434\u0435\u043a\u043e\u0434\u0435\u0440\u043e\u0432 \u0447\u0430\u0449\u0435 \u0432\u0441\u0435\u0433\u043e \u043f\u0440\u0435\u0434\u043f\u043e\u0447\u0442\u0435\u043d\u0438\u0435 \u043e\u0442\u0434\u0430\u0435\u0442\u0441\u044f <strong>\u043f\u043e\u043f\u0430\u0440\u043d\u043e\u043c\u0443 \u0434\u0435\u043a\u043e\u0434\u0435\u0440\u0443<\/strong>. \u042d\u0442\u0430 \u0440\u0430\u0437\u043d\u043e\u0432\u0438\u0434\u043d\u043e\u0441\u0442\u044c \u0434\u0435\u043a\u043e\u0434\u0435\u0440\u043e\u0432, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u043e\u0442\u043e\u0431\u0440\u0430\u0436\u0430\u0435\u0442 \u043f\u0430\u0440\u044b \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u0439 \u0443\u0437\u043b\u043e\u0432 \u0432 \u0440\u0435\u0430\u043b\u044c\u043d\u0443\u044e \u043c\u0435\u0440\u0443 \u0431\u043b\u0438\u0437\u043e\u0441\u0442\u0438 \u0433\u0440\u0430\u0444\u0430, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0435\u043d\u043d\u043e \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u0435\u0442 \u0431\u043b\u0438\u0437\u043e\u0441\u0442\u044c \u0434\u0432\u0443\u0445 \u0443\u0437\u043b\u043e\u0432 \u0432 \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u043c \u0433\u0440\u0430\u0444\u0435. \u042d\u0442\u043e \u0437\u043d\u0430\u0447\u0438\u0442, \u0447\u0442\u043e \u043a\u043e\u0433\u0434\u0430 \u043c\u044b \u043f\u0440\u0438\u043c\u0435\u043d\u044f\u0435\u043c \u043f\u043e\u043f\u0430\u0440\u043d\u044b\u0439 \u0434\u0435\u043a\u043e\u0434\u0435\u0440 \u043a \u043f\u0430\u0440\u0435 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u0439 <math>$inline$(z_i, z_j)$inline$<\/math>, \u043c\u044b \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u043c \u0440\u0435\u043a\u043e\u043d\u0441\u0442\u0440\u0443\u043a\u0446\u0438\u044e \u0431\u043b\u0438\u0437\u043e\u0441\u0442\u0438 \u043c\u0435\u0436\u0434\u0443 <math>$inline$v_i$inline$<\/math> \u0438 <math>$inline$v_j$inline$<\/math> \u0432 \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u043c \u0433\u0440\u0430\u0444\u0435. \u0412 \u0442\u0430\u043a\u043e\u0439 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0435 \u0446\u0435\u043b\u044c\u044e \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u044f \u043e\u0442\u043e\u0431\u0440\u0430\u0436\u0435\u043d\u0438\u0439 \u043a\u043e\u0434\u0435\u0440\u0430 \u0438 \u0434\u0435\u043a\u043e\u0434\u0435\u0440\u0430 \u0434\u043b\u044f \u043c\u0438\u043d\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0438 \u043e\u0448\u0438\u0431\u043a\u0438 \u0438\u043b\u0438 \u043f\u043e\u0442\u0435\u0440\u0438 \u0442\u0430\u043a, \u0447\u0442\u043e\u0431\u044b:<\/p>\n<p>  <\/p>\n<p><math>$$display$$DEC(ENC(v_i), ENC(v_j)) = DEC(z_i, z_j ) \u2248 sG(v_i, v_j) \\textbf{ (1)}$$display$$<\/math><\/p>\n<p>  <\/p>\n<p>\u0413\u0434\u0435 <math>$inline$sG$inline$<\/math> \u2014 \u044d\u0442\u043e \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u0435\u043c\u0430\u044f \u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u0435\u043b\u0435\u043c \u043c\u0435\u0440\u0430 \u0431\u043b\u0438\u0437\u043e\u0441\u0442\u0438 \u043c\u0435\u0436\u0434\u0443 \u0443\u0437\u043b\u0430\u043c\u0438, \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u043d\u0430\u044f \u043d\u0430\u0434 \u0433\u0440\u0430\u0444\u043e\u043c <math>$inline$G$inline$<\/math>. \u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u043c\u043e\u0436\u043d\u043e \u0443\u0441\u0442\u0430\u043d\u043e\u0432\u0438\u0442\u044c <math>$inline$sG(z_i, z_i) \u225c A_i,_j$inline$<\/math> \u0438 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u0442\u044c \u0443\u0437\u043b\u044b \u0442\u0430\u043a, \u0447\u0442\u043e\u0431\u044b \u0441\u043c\u0435\u0436\u043d\u044b\u0435 \u043d\u043e\u0434\u044b \u0431\u044b\u043b\u0438 \u0431\u043b\u0438\u0437\u043a\u0438 \u043a 1, \u0430 \u0440\u0430\u0437\u0440\u043e\u0437\u043d\u0435\u043d\u043d\u044b\u0435 \u043a 0. \u0418\u043b\u0438 \u043c\u043e\u0436\u043d\u043e \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u0442\u044c <math>$inline$sG$inline$<\/math> \u0432 \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0438\u0438 \u0441 \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u044c\u044e \u043e\u0434\u043d\u043e\u0432\u0440\u0435\u043c\u0435\u043d\u043d\u043e\u0433\u043e \u043f\u043e\u044f\u0432\u043b\u0435\u043d\u0438\u044f <math>$inline$v_i$inline$<\/math> \u0438 <math>$inline$v_j$inline$<\/math> \u043f\u0440\u0438 \u0441\u043b\u0443\u0447\u0430\u0439\u043d\u043e\u0439 \u043f\u0440\u043e\u0433\u0443\u043b\u043a\u0435 \u0441 \u0444\u0438\u043a\u0441\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0439 \u0434\u043b\u0438\u043d\u043e\u0439 \u043f\u043e \u0433\u0440\u0430\u0444\u0438\u043a\u0443 <math>$inline$G$inline$<\/math>. \u041d\u0430 \u043f\u0440\u0430\u043a\u0442\u0438\u043a\u0435 \u0431\u043e\u043b\u044c\u0448\u0438\u043d\u0441\u0442\u0432\u043e \u043f\u043e\u0434\u0445\u043e\u0434\u043e\u0432 \u0440\u0435\u0430\u043b\u0438\u0437\u0443\u044e\u0442 \u0432\u043e\u0441\u0441\u0442\u0430\u043d\u043e\u0432\u043b\u0435\u043d\u0438\u0435 (\u0443\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0435 1) \u043f\u0443\u0442\u0435\u043c \u043c\u0438\u043d\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0438 \u044d\u043c\u043f\u0438\u0440\u0438\u0447\u0435\u0441\u043a\u0438\u0445 \u043f\u043e\u0442\u0435\u0440\u044c <math>$inline$L$inline$<\/math> \u043f\u043e \u043d\u0430\u0431\u043e\u0440\u0443 \u043f\u0430\u0440 \u043e\u0431\u0443\u0447\u0430\u044e\u0449\u0438\u0445 \u0443\u0437\u043b\u043e\u0432 <math>$inline$D$inline$<\/math>:<\/p>\n<p>  <\/p>\n<p><math>$$display$$L = \\sum_{(v_i, v_j) \u2208 D} \u2113 (DEC(z_i, z_j), sG(v_i, v_j))$$display$$<\/math><\/p>\n<p>  <\/p>\n<p>\u0413\u0434\u0435 <math>$inline$\u2113 = R * R \u2192 R$inline$<\/math> \u2014 \u0437\u0430\u0434\u0430\u043d\u043d\u0430\u044f \u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u0435\u043b\u0435\u043c \u0444\u0443\u043d\u043a\u0446\u0438\u044f \u043f\u043e\u0442\u0435\u0440\u044c, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u0438\u0437\u043c\u0435\u0440\u044f\u0435\u0442 \u0440\u0430\u0441\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u0435 \u043c\u0435\u0436\u0434\u0443 \u0434\u0435\u043a\u043e\u0434\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u043c\u0438 (\u0442.\u0435. \u043f\u0440\u0435\u0434\u043f\u043e\u043b\u0430\u0433\u0430\u0435\u043c\u044b\u043c\u0438) \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f\u043c\u0438 \u0431\u043b\u0438\u0437\u043e\u0441\u0442\u0438 <math>$inline$DEC(z_i, z_j)$inline$<\/math> \u0438 \u0438\u0441\u0442\u0438\u043d\u043d\u044b\u043c\u0438 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f\u043c\u0438 <math>$inline$sG(v_i, v_j)$inline$<\/math>.<\/p>\n<p>  <\/p>\n<p>\u041f\u043e\u0441\u043b\u0435 \u0442\u043e\u0433\u043e, \u043a\u0430\u043a \u043c\u044b \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u043b\u0438 \u0441\u0438\u0441\u0442\u0435\u043c\u0443 \u043a\u043e\u0434\u0435\u0440-\u0434\u0435\u043a\u043e\u0434\u0435\u0440, \u043c\u044b \u043c\u043e\u0436\u0435\u043c \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u043e\u0431\u0443\u0447\u0435\u043d\u043d\u044b\u0439 \u043a\u043e\u0434\u0435\u0440 \u0434\u043b\u044f \u0433\u0435\u043d\u0435\u0440\u0430\u0446\u0438\u0438 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u0439 \u0434\u043b\u044f \u0443\u0437\u043b\u043e\u0432, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0437\u0430\u0442\u0435\u043c \u043c\u043e\u0436\u043d\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u0432 \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0435 \u0432\u0445\u043e\u0434\u043d\u044b\u0445 \u0434\u0430\u043d\u043d\u044b\u0445 \u0434\u043b\u044f \u0437\u0430\u0434\u0430\u0447 \u043c\u0430\u0448\u0438\u043d\u043d\u043e\u0433\u043e \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044f \u0432 \u043d\u0438\u0441\u0445\u043e\u0434\u044f\u0449\u0435\u043c \u043d\u0430\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u0438\u0438. \u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u043c\u043e\u0436\u043d\u043e \u043f\u0435\u0440\u0435\u0434\u0430\u0442\u044c \u043f\u043e\u043b\u0443\u0447\u0435\u043d\u043d\u044b\u0435 \u0432\u043b\u043e\u0436\u0435\u043d\u0438\u044f \u0432 \u043a\u043b\u0430\u0441\u0441\u0438\u0444\u0438\u043a\u0430\u0442\u043e\u0440 \u043b\u043e\u0433\u0438\u0441\u0442\u0438\u0447\u0435\u0441\u043a\u043e\u0439 \u0440\u0435\u0433\u0440\u0435\u0441\u0441\u0438\u0438, \u0447\u0442\u043e\u0431\u044b \u043f\u0440\u0435\u0434\u0441\u043a\u0430\u0437\u0430\u0442\u044c \u0441\u043e\u043e\u0431\u0449\u0435\u0441\u0442\u0432\u043e, \u043a\u043e\u0442\u043e\u0440\u043e\u043c\u0443 \u043f\u0440\u0438\u043d\u0430\u0434\u043b\u0435\u0436\u0438\u0442 \u0443\u0437\u0435\u043b, \u0438\u043b\u0438 \u043c\u043e\u0436\u043d\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u044f \u043c\u0435\u0436\u0434\u0443 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u044f\u043c\u0438, \u0447\u0442\u043e\u0431\u044b \u0440\u0435\u043a\u043e\u043c\u0435\u043d\u0434\u043e\u0432\u0430\u0442\u044c \u0434\u0440\u0443\u0436\u0435\u0441\u043a\u0438\u0435 \u0441\u0441\u044b\u043b\u043a\u0438 \u0432 \u0441\u043e\u0446\u0438\u0430\u043b\u044c\u043d\u043e\u0439 \u0441\u0435\u0442\u0438.<\/p>\n<p>  <\/p>\n<p>\u0422\u0430\u043a\u043e\u0439 \u043f\u043e\u0434\u0445\u043e\u0434 \u0441\u0438\u043b\u044c\u043d\u043e \u043d\u0430\u043f\u043e\u043c\u0438\u043d\u0430\u0435\u0442 <a href=\"https:\/\/google.github.io\/seq2seq\/\">seq2seq<\/a> \u0441\u0435\u0442\u0438, \u0433\u0434\u0435 \u0432\u0445\u043e\u0434\u043d\u0430\u044f \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c \u0441\u043b\u043e\u0432 \u043a\u043e\u0434\u0438\u0440\u0443\u0435\u0442\u0441\u044f \u0432 \u043d\u0438\u0437\u043a\u043e\u0440\u0430\u0437\u043c\u0435\u0440\u043d\u043e\u0435 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u0435, \u0430 \u0437\u0430\u0442\u0435\u043c \u0434\u0435\u043a\u043e\u0434\u0438\u0440\u0443\u0435\u0442\u0441\u044f \u0434\u043b\u044f \u0440\u0430\u0437\u043b\u0438\u0447\u043d\u044b\u0445 \u043f\u0440\u0435\u0434\u0441\u043a\u0430\u0437\u0430\u043d\u0438\u0439. \u0412\u0441\u0435 \u043f\u0440\u0438\u0435\u043c\u044b, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043c\u043e\u0436\u043d\u043e \u043f\u0440\u0438\u043c\u0435\u043d\u0438\u0442\u044c \u0434\u043b\u044f \u0441\u0435\u0442\u0435\u0439 seq2seq, \u043c\u043e\u0433\u0443\u0442 \u0431\u044b\u0442\u044c \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u043d\u044b \u0438 \u0434\u043b\u044f GNN [<a href=\"https:\/\/arxiv.org\/abs\/1710.10903\">10<\/a>].<\/p>\n<p>  <\/p>\n<h1 id=\"algoritmy-pryamogo-kodirovaniya\">\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u043f\u0440\u044f\u043c\u043e\u0433\u043e \u043a\u043e\u0434\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f<\/h1>\n<p>  <\/p>\n<p>\u041e\u0441\u043d\u043e\u0432\u043d\u044b\u0435 \u043c\u0435\u0442\u043e\u0434\u043e\u043b\u043e\u0433\u0438\u0447\u0435\u0441\u043a\u0438\u0435 \u0440\u0430\u0437\u043b\u0438\u0447\u0438\u044f \u043c\u0435\u0436\u0434\u0443 \u0440\u0430\u0437\u043b\u0438\u0447\u043d\u044b\u043c\u0438 \u043f\u043e\u0434\u0445\u043e\u0434\u0430\u043c\u0438 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u0443\u0437\u043b\u043e\u0432 \u0441\u043e\u0441\u0442\u043e\u044f\u0442 \u0432 \u0442\u043e\u043c, \u043a\u0430\u043a \u043e\u043d\u0438 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u044e\u0442 \u0447\u0435\u0442\u044b\u0440\u0435 \u043a\u043e\u043c\u043f\u043e\u043d\u0435\u043d\u0442\u0430:<\/p>\n<p>  <\/p>\n<ol>\n<li>\u0424\u0443\u043d\u043a\u0446\u0438\u044f \u043f\u0430\u0440\u043d\u043e\u0439 \u0431\u043b\u0438\u0437\u043e\u0441\u0442\u0438 <math>$inline$sG$inline$<\/math>: <math>$inline$V * V \u2192 R^+$inline$<\/math>, \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u043d\u0430\u044f \u043d\u0430\u0434 \u0433\u0440\u0430\u0444\u043e\u043c <math>$inline$G$inline$<\/math>.<\/li>\n<li>\u0424\u0443\u043d\u043a\u0446\u0438\u044f \u043a\u043e\u0434\u0438\u0440\u043e\u0432\u0449\u0438\u043a\u0430 <strong>ENC<\/strong>, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u0433\u0435\u043d\u0435\u0440\u0438\u0440\u0443\u0435\u0442 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u0443\u0437\u043b\u043e\u0432. \u042d\u0442\u0430 \u0444\u0443\u043d\u043a\u0446\u0438\u044f \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442 \u0440\u044f\u0434 \u043e\u0431\u0443\u0447\u0430\u0435\u043c\u044b\u0445 \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u043e\u0432, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0438\u0440\u0443\u044e\u0442\u0441\u044f \u043d\u0430 \u044d\u0442\u0430\u043f\u0435 \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044f.<\/li>\n<li>\u0424\u0443\u043d\u043a\u0446\u0438\u044f \u0434\u0435\u043a\u043e\u0434\u0435\u0440\u0430 <strong>DEC<\/strong>, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u0432\u043e\u0441\u0441\u0442\u0430\u043d\u0430\u0432\u043b\u0438\u0432\u0430\u0435\u0442 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u043f\u043e\u043f\u0430\u0440\u043d\u043e\u0439 \u0431\u043b\u0438\u0437\u043e\u0441\u0442\u0438 \u0438\u0437 \u0441\u0433\u0435\u043d\u0435\u0440\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0445 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u0439. \u042d\u0442\u0430 \u0444\u0443\u043d\u043a\u0446\u0438\u044f \u043e\u0431\u044b\u0447\u043d\u043e \u043d\u0435 \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442 \u043e\u0431\u0443\u0447\u0430\u0435\u043c\u044b\u0445 \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u043e\u0432<\/li>\n<li>\u0424\u0443\u043d\u043a\u0446\u0438\u044f \u043f\u043e\u0442\u0435\u0440\u044c <math>$inline$\u2113$inline$<\/math>, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u0435\u0442, \u043a\u0430\u043a \u043e\u0446\u0435\u043d\u0438\u0432\u0430\u0435\u0442\u0441\u044f \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u043e \u043f\u0430\u0440\u043d\u044b\u0445 \u0440\u0435\u043a\u043e\u043d\u0441\u0442\u0440\u0443\u043a\u0446\u0438\u0439 \u0434\u043b\u044f \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044f \u043c\u043e\u0434\u0435\u043b\u0438.<\/li>\n<\/ol>\n<p>  <\/p>\n<p><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/tz\/c6\/zh\/tzc6zhn_s6bvlws0ujqsncnclq8.png\" alt=\"image\"\/><\/p>\n<p>  <\/p>\n<p><em>\u0412\u043e\u0442 \u0441\u0432\u043e\u0434\u043a\u0430 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u0438\u0437\u0432\u0435\u0441\u0442\u043d\u044b\u0445 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u0432 \u043f\u0440\u044f\u043c\u043e\u0433\u043e \u043a\u043e\u0434\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f. \u041e\u0431\u0440\u0430\u0442\u0438\u0442\u0435 \u0432\u043d\u0438\u043c\u0430\u043d\u0438\u0435, \u0447\u0442\u043e \u0434\u0435\u043a\u043e\u0434\u0435\u0440 \u0438 \u0444\u0443\u043d\u043a\u0446\u0438\u044f \u043f\u0440\u0438\u0431\u043b\u0438\u0436\u0435\u043d\u0438\u044f \u0434\u043b\u044f \u043c\u0435\u0442\u043e\u0434\u043e\u0432 \u043d\u0430 \u043e\u0441\u043d\u043e\u0432\u0435 \u0441\u043b\u0443\u0447\u0430\u0439\u043d\u043e\u0439 \u043f\u0440\u043e\u0433\u0443\u043b\u043a\u0438 \u0430\u0441\u0438\u043c\u043c\u0435\u0442\u0440\u0438\u0447\u043d\u044b. \u041f\u0440\u0438\u0447\u0435\u043c \u0444\u0443\u043d\u043a\u0446\u0438\u0438 \u043f\u0440\u0438\u0431\u043b\u0438\u0436\u0435\u043d\u0438\u044f <math>$inline$pG(v_j|v_i)$inline$<\/math> \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u0435\u0442 \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u044c \u043f\u043e\u0441\u0435\u0449\u0435\u043d\u0438\u044f <math>$inline$v_j$inline$<\/math> \u043f\u0440\u0438 \u0441\u043b\u0443\u0447\u0430\u0439\u043d\u043e\u0439 \u043f\u0440\u043e\u0433\u0443\u043b\u043a\u0435 \u0444\u0438\u043a\u0441\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0439 \u0434\u043b\u0438\u043d\u044b, \u043d\u0430\u0447\u0438\u043d\u0430\u044f \u0441 <math>$inline$v_i$inline$<\/math><\/em>.<\/p>\n<p>  <\/p>\n<p>\u041c\u043d\u043e\u0433\u0438\u0435 \u0443\u0441\u043f\u0435\u0448\u043d\u044b\u0435 \u0438\u0437 \u0441\u043e\u0432\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0445 \u043c\u0435\u0442\u043e\u0434\u043e\u0432, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0442\u0430\u043a\u0436\u0435 \u043f\u0440\u0438\u043d\u0430\u0434\u043b\u0435\u0436\u0430\u0442 \u043a \u043a\u043b\u0430\u0441\u0441\u0443 \u043f\u043e\u0434\u0445\u043e\u0434\u043e\u0432 \u043f\u0440\u044f\u043c\u043e\u0433\u043e \u043a\u043e\u0434\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f, \u0438\u0437\u0443\u0447\u0430\u044e\u0442 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u0443\u0437\u043b\u043e\u0432 \u043d\u0430 \u043e\u0441\u043d\u043e\u0432\u0435 \u0441\u0442\u0430\u0442\u0438\u0441\u0442\u0438\u043a\u0438 <strong>\u0441\u043b\u0443\u0447\u0430\u0439\u043d\u043e\u0433\u043e \u043e\u0431\u0445\u043e\u0434\u0430<\/strong>. \u0418\u0445 \u043a\u043b\u044e\u0447\u0435\u0432\u044b\u043c \u043d\u043e\u0432\u043e\u0432\u0432\u0435\u0434\u0435\u043d\u0438\u0435\u043c \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u044f, \u043f\u0440\u0438 \u043a\u043e\u0442\u043e\u0440\u043e\u0439 \u0443\u0437\u043b\u044b \u0438\u043c\u0435\u044e\u0442 \u043f\u043e\u0445\u043e\u0436\u0438\u0435 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u044f, \u0435\u0441\u043b\u0438 \u043e\u043d\u0438 \u0438\u043c\u0435\u044e\u0442 \u0442\u0435\u043d\u0434\u0435\u043d\u0446\u0438\u044e \u0441\u043e\u0441\u0443\u0449\u0435\u0441\u0442\u0432\u043e\u0432\u0430\u0442\u044c \u043f\u0440\u0438 \u043a\u043e\u0440\u043e\u0442\u043a\u0438\u0445 \u0441\u043b\u0443\u0447\u0430\u0439\u043d\u044b\u0445 \u043e\u0431\u0445\u043e\u0434\u0430\u0445 \u043f\u043e \u0433\u0440\u0430\u0444\u0438\u043a\u0443 (\u0440\u0438\u0441.3). \u0422\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c, \u0432\u043c\u0435\u0441\u0442\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u044f \u0434\u0435\u0442\u0435\u0440\u043c\u0438\u043d\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0439 \u043c\u0435\u0440\u044b \u0431\u043b\u0438\u0437\u043e\u0441\u0442\u0438 \u043a \u0433\u0440\u0430\u0444\u0443, \u0432 \u044d\u0442\u0438\u0445 \u043c\u0435\u0442\u043e\u0434\u0430\u0445 \u0441\u043b\u0443\u0447\u0430\u0439\u043d\u043e\u0439 \u043f\u0440\u043e\u0433\u0443\u043b\u043a\u0438 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f \u0433\u0438\u0431\u043a\u0430\u044f \u0441\u0442\u043e\u0445\u0430\u0441\u0442\u0438\u0447\u0435\u0441\u043a\u0430\u044f \u043c\u0435\u0440\u0430 \u0431\u043b\u0438\u0437\u043e\u0441\u0442\u0438 \u043a \u0433\u0440\u0430\u0444\u0443, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u043f\u0440\u0438\u0432\u0435\u043b\u0430 \u043a \u043f\u0440\u0435\u0432\u043e\u0441\u0445\u043e\u0434\u043d\u043e\u0439 \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438 \u0432 \u0440\u044f\u0434\u0435 \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u043e\u0432.<\/p>\n<p>  <\/p>\n<p><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/wv\/z6\/5b\/wvz65bhm7chru0vl5hexgvi2azu.png\" alt=\"image\"\/><\/p>\n<p>  <\/p>\n<p>\u041f\u043e\u0434\u0445\u043e\u0434\u044b DeepWalk \u0438 node2vec, \u0432 \u043e\u0442\u043b\u0438\u0447\u0438\u0435 \u043e\u0442 \u0434\u0440\u0443\u0433\u0438\u0445 \u043f\u043e\u0434\u0445\u043e\u0434\u043e\u0432 \u043c\u0430\u0442\u0440\u0438\u0447\u043d\u043e\u0439 \u0444\u0430\u043a\u0442\u043e\u0440\u0438\u0437\u0430\u0446\u0438\u0438, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0442\u043e\u0436\u0435 \u043f\u043e\u043b\u0430\u0433\u0430\u044e\u0442\u0441\u044f \u043d\u0430 \u043f\u0440\u044f\u043c\u043e\u0435 \u043a\u043e\u0434\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435, \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044e\u0442 \u0441\u0432\u043e\u0439 \u0441\u043e\u0431\u0441\u0442\u0432\u0435\u043d\u043d\u044b\u0439 \u0434\u0435\u043a\u043e\u0434\u0435\u0440. \u041a \u0442\u043e\u043c\u0443 \u0436\u0435 \u0432\u043c\u0435\u0441\u0442\u043e \u0442\u043e\u0433\u043e, \u0447\u0442\u043e\u0431\u044b \u043f\u044b\u0442\u0430\u0442\u044c\u0441\u044f \u0434\u0435\u043a\u043e\u0434\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0444\u0438\u043a\u0441\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u0443\u044e \u0434\u0435\u0442\u0435\u0440\u043c\u0438\u043d\u0438\u0441\u0442\u0438\u0447\u0435\u0441\u043a\u0443\u044e \u043c\u0435\u0440\u0443 \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u044f, \u043e\u043d\u0438 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0438\u0440\u0443\u044e\u0442 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u0434\u043b\u044f \u043a\u043e\u0434\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f \u0441\u0442\u0430\u0442\u0438\u0441\u0442\u0438\u043a\u0438 \u0441\u043b\u0443\u0447\u0430\u0439\u043d\u044b\u0445 \u043f\u0440\u043e\u0433\u0443\u043b\u043e\u043a. \u041e\u0441\u043d\u043e\u0432\u043d\u0430\u044f \u0438\u0434\u0435\u044f \u044d\u0442\u0438\u0445 \u043f\u043e\u0434\u0445\u043e\u0434\u043e\u0432 \u0441\u043e\u0441\u0442\u043e\u0438\u0442 \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e\u0431\u044b \u0438\u0437\u0443\u0447\u0438\u0442\u044c \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u0442\u0430\u043a, \u0447\u0442\u043e\u0431\u044b:<\/p>\n<p>  <\/p>\n<p><math>$$display$$ DEC(z\\_i, z\\_j) \u225c \\dfrac{e^{z\\_i^Tz\\_j}}{\\sum_{v_k\u2208V}e^{z_i^Tz_k}} \u2248 pG,T(v\\_j|v\\_i) \\textbf{ (2)} $$display$$<\/math><\/p>\n<p>  <\/p>\n<p>\u0413\u0434\u0435 <math>$inline$pG,T (v_j|v_i)$inline$<\/math> \u2014 \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u044c \u043f\u043e\u0441\u0435\u0449\u0435\u043d\u0438\u044f <math>$inline$v_j$inline$<\/math> \u0432 \u0441\u043b\u0443\u0447\u0430\u0439\u043d\u043e\u0439 \u043f\u0440\u043e\u0433\u0443\u043b\u043a\u0435 \u043f\u043e \u0434\u043b\u0438\u043d\u0435 <math>$inline$T$inline$<\/math>, \u043d\u0430\u0447\u0438\u043d\u0430\u044f \u0441 <math>$inline$v_i$inline$<\/math>, \u043f\u0440\u0438\u0447\u0435\u043c <math>$inline$T$inline$<\/math> \u043e\u0431\u044b\u0447\u043d\u043e \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u043e \u0432 \u0434\u0438\u0430\u043f\u0430\u0437\u043e\u043d\u0435 <math>$inline$T \u2208 \\\\{2, &#8230;, 10\\\\}$inline$<\/math>. \u041e\u0431\u0440\u0430\u0442\u0438\u0442\u0435 \u0432\u043d\u0438\u043c\u0430\u043d\u0438\u0435, \u0447\u0442\u043e <math>$inline$pG,T (v_j|v_i)$inline$<\/math> \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0441\u0442\u043e\u0445\u0430\u0441\u0442\u0438\u0447\u0435\u0441\u043a\u0438\u043c \u0438 \u0430\u0441\u0438\u043c\u043c\u0435\u0442\u0440\u0438\u0447\u043d\u044b\u043c. \u0411\u043e\u043b\u0435\u0435 \u0444\u043e\u0440\u043c\u0430\u043b\u044c\u043d\u043e, \u044d\u0442\u0438 \u043f\u043e\u0434\u0445\u043e\u0434\u044b \u043f\u044b\u0442\u0430\u044e\u0442\u0441\u044f \u043c\u0438\u043d\u0438\u043c\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0443\u044e \u043f\u043e\u0442\u0435\u0440\u044e \u043f\u0435\u0440\u0435\u043a\u0440\u0435\u0441\u0442\u043d\u043e\u0439 \u044d\u043d\u0442\u0440\u043e\u043f\u0438\u0438:<\/p>\n<p>  <\/p>\n<p><math>$$display$$\u2113=\\sum_{(v_i,v_j)\u2208D}\u2212log(DEC(z_i, z_j)) \\textbf{ (3)}$$display$$<\/math><\/p>\n<p>  <\/p>\n<p>\u0412 \u044d\u0442\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u043e\u0431\u0443\u0447\u0430\u044e\u0449\u0438\u0439 \u043d\u0430\u0431\u043e\u0440 <math>$inline$D$inline$<\/math> \u0433\u0435\u043d\u0435\u0440\u0438\u0440\u0443\u0435\u0442\u0441\u044f \u043f\u0443\u0442\u0435\u043c \u0432\u044b\u0431\u043e\u0440\u043a\u0438 \u0441\u043b\u0443\u0447\u0430\u0439\u043d\u044b\u0445 \u043f\u0440\u043e\u0433\u0443\u043b\u043e\u043a, \u043d\u0430\u0447\u0438\u043d\u0430\u044f \u0441 \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0443\u0437\u043b\u0430 (\u0442.\u0435. \u0433\u0434\u0435 <math>$inline$N$inline$<\/math> \u043f\u0430\u0440 \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0443\u0437\u043b\u0430 <math>$inline$v_i$inline$<\/math> \u0432\u044b\u0431\u0438\u0440\u0430\u044e\u0442\u0441\u044f \u0438\u0437 \u0440\u0430\u0441\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u044f <math>$inline$(v_i, v_j) \\sim pG,T(v_j|v_j)$inline$<\/math>. \u041e\u0434\u043d\u0430\u043a\u043e \u043d\u0430\u0438\u0432\u043d\u0430\u044f \u043e\u0446\u0435\u043d\u043a\u0430 \u044d\u0442\u043e\u0439 \u043f\u043e\u0442\u0435\u0440\u0438 \u043d\u0435\u043f\u043e\u043c\u0435\u0440\u043d\u043e \u0434\u043e\u0440\u043e\u0433\u0430 \u2014 <math>$inline$O(|D||V|)$inline$<\/math> (\u043f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 \u043e\u0446\u0435\u043d\u043a\u0430 \u0437\u043d\u0430\u043c\u0435\u043d\u0430\u0442\u0435\u043b\u044f \u0443\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044f (2) \u0438\u043c\u0435\u0435\u0442 \u0432\u0440\u0435\u043c\u0435\u043d\u043d\u0443\u044e \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c <math>$inline$O(|V|)$inline$<\/math>). \u0422\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c, DeepWalk \u0438 node2vec \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044e\u0442 \u0440\u0430\u0437\u043d\u044b\u0435 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0438 \u0438 \u043f\u0440\u0438\u0431\u043b\u0438\u0436\u0435\u043d\u0438\u044f \u0434\u043b\u044f \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f \u043f\u043e\u0442\u0435\u0440\u044c \u0432 \u0443\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0438 (3). DeepWalk \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442 \u043c\u0435\u0442\u043e\u0434 <strong>\u0438\u0435\u0440\u0430\u0440\u0445\u0438\u0447\u0435\u0441\u043a\u043e\u0433\u043e softmax<\/strong> \u0434\u043b\u044f \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f \u043d\u043e\u0440\u043c\u0430\u043b\u0438\u0437\u0443\u044e\u0449\u0435\u0433\u043e \u0444\u0430\u043a\u0442\u043e\u0440\u0430, \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044f \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0443 \u0434\u0432\u043e\u0438\u0447\u043d\u043e\u0433\u043e \u0434\u0435\u0440\u0435\u0432\u0430 \u0434\u043b\u044f \u0443\u0441\u043a\u043e\u0440\u0435\u043d\u0438\u044f \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u0439. \u041d\u0430\u043f\u0440\u043e\u0442\u0438\u0432, node2vec \u0430\u043f\u043f\u0440\u043e\u043a\u0441\u0438\u043c\u0438\u0440\u0443\u0435\u0442 \u0443\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0435 (3), \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044f <strong>\u043e\u0442\u0440\u0438\u0446\u0430\u0442\u0435\u043b\u044c\u043d\u0443\u044e \u0432\u044b\u0431\u043e\u0440\u043a\u0443<\/strong>: \u0432\u043c\u0435\u0441\u0442\u043e \u043d\u043e\u0440\u043c\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438 \u043f\u043e \u0432\u0441\u0435\u043c\u0443 \u043d\u0430\u0431\u043e\u0440\u0443 \u0432\u0435\u0440\u0448\u0438\u043d, \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0430\u043f\u043f\u0440\u043e\u043a\u0441\u0438\u043c\u0438\u0440\u0443\u0435\u0442 \u043d\u043e\u0440\u043c\u0438\u0440\u0443\u044e\u0449\u0438\u0439 \u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442, \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044f \u043d\u0430\u0431\u043e\u0440 \u0441\u043b\u0443\u0447\u0430\u0439\u043d\u044b\u0445 &quot;\u043e\u0442\u0440\u0438\u0446\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u0445 \u0432\u044b\u0431\u043e\u0440\u043e\u043a&quot;.<\/p>\n<p>  <\/p>\n<p>\u041f\u043e\u043c\u0438\u043c\u043e \u044d\u0442\u0438\u0445 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0438\u0447\u0435\u0441\u043a\u0438\u0445 \u0440\u0430\u0437\u043b\u0438\u0447\u0438\u0439, \u043a\u043b\u044e\u0447\u0435\u0432\u043e\u0435 \u0440\u0430\u0437\u043b\u0438\u0447\u0438\u0435 \u043c\u0435\u0436\u0434\u0443 node2vec \u0438 DeepWalk \u0437\u0430\u043a\u043b\u044e\u0447\u0430\u0435\u0442\u0441\u044f \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e \u043f\u0435\u0440\u0432\u044b\u0439 \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u0433\u0438\u0431\u043a\u043e \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u0442\u044c \u0441\u043b\u0443\u0447\u0430\u0439\u043d\u044b\u0435 \u043e\u0431\u0445\u043e\u0434\u044b, \u0442\u043e\u0433\u0434\u0430 \u043a\u0430\u043a \u0432\u0442\u043e\u0440\u043e\u0439 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442 \u043f\u0440\u043e\u0441\u0442\u044b\u0435 \u043d\u0435\u043f\u0440\u0435\u0434\u0432\u0437\u044f\u0442\u044b\u0435 \u0441\u043b\u0443\u0447\u0430\u0439\u043d\u044b\u0435 \u043e\u0431\u0445\u043e\u0434\u044b \u043f\u043e \u0433\u0440\u0430\u0444\u0443. \u0412 \u0447\u0430\u0441\u0442\u043d\u043e\u0441\u0442\u0438, node2vec \u0432\u0432\u043e\u0434\u0438\u0442 \u0434\u0432\u0430 \u0433\u0438\u043f\u0435\u0440\u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u0430 \u0441\u043b\u0443\u0447\u0430\u0439\u043d\u044b\u0445 \u043f\u0440\u043e\u0433\u0443\u043b\u043e\u043a: <math>$inline$p$inline$<\/math> \u0438 <math>$inline$q$inline$<\/math>, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u044e\u0442 \u043a\u043e\u043d\u0442\u0440\u043e\u043b\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0441\u043c\u0435\u0449\u0435\u043d\u0438\u0435 \u0432\u043e \u0432\u0440\u0435\u043c\u044f \u043f\u0440\u043e\u0433\u0443\u043b\u043e\u043a (\u0440\u0438\u0441.4). \u0413\u0438\u043f\u0435\u0440\u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440 <math>$inline$p$inline$<\/math> \u043a\u043e\u043d\u0442\u0440\u043e\u043b\u0438\u0440\u0443\u0435\u0442 \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u044c \u0432\u043e\u0437\u0432\u0440\u0430\u0442\u0430 \u043a \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0435\u043c\u0443 \u0443\u0437\u043b\u0443, \u0432 \u0442\u043e \u0432\u0440\u0435\u043c\u044f \u043a\u0430\u043a <math>$inline$q$inline$<\/math> \u0443\u043f\u0440\u0430\u0432\u043b\u044f\u0435\u0442 \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u044c\u044e \u0438\u0441\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u044c \u043d\u0435\u0438\u0437\u0443\u0447\u0435\u043d\u043d\u044b\u0435 \u0447\u0430\u0441\u0442\u0438 \u0433\u0440\u0430\u0444\u0430. \u0412\u0432\u043e\u0434\u044f \u044d\u0442\u0438 \u0433\u0438\u043f\u0435\u0440\u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u044b, node2vec \u043c\u043e\u0436\u0435\u0442 \u043f\u043b\u0430\u0432\u043d\u043e \u0438\u043d\u0442\u0435\u0440\u043f\u043e\u043b\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u043c\u0435\u0436\u0434\u0443 \u043e\u0431\u0445\u043e\u0434\u0430\u043c\u0438, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0431\u043e\u043b\u044c\u0448\u0435 \u043f\u043e\u0445\u043e\u0436\u0438 \u043d\u0430 \u043f\u043e\u0438\u0441\u043a \u0432 \u0448\u0438\u0440\u0438\u043d\u0443 \u0438\u043b\u0438 \u0432 \u0433\u043b\u0443\u0431\u0438\u043d\u0443.<\/p>\n<p>  <\/p>\n<p><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/nn\/iv\/ym\/nnivyminybfrwvrp8ennb1luqfo.png\" alt=\"image\"\/><\/p>\n<p>  <\/p>\n<p><em>A: \u0418\u043b\u043b\u044e\u0441\u0442\u0440\u0430\u0446\u0438\u044f \u0442\u043e\u0433\u043e, \u043a\u0430\u043a node2vec \u0441\u043c\u0435\u0449\u0430\u0435\u0442 \u043f\u0440\u043e\u0433\u0443\u043b\u043a\u0438, \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044f \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u044b p \u0438 q. \u041f\u0440\u0435\u0434\u043f\u043e\u043b\u0430\u0433\u0430\u044f, \u0447\u0442\u043e \u043f\u0440\u043e\u0433\u0443\u043b\u043a\u0430 \u0442\u043e\u043b\u044c\u043a\u043e \u0447\u0442\u043e \u043f\u0435\u0440\u0435\u0448\u043b\u0430 \u043e\u0442 <math>$inline$v\\_s$inline$<\/math> \u043a <math>$inline$v\\_\u2217$inline$<\/math>, \u043c\u0435\u0442\u043a\u0438 \u0440\u0435\u0431\u0435\u0440 (\u03b1) \u043f\u0440\u043e\u043f\u043e\u0440\u0446\u0438\u043e\u043d\u0430\u043b\u044c\u043d\u044b \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u0438 \u0442\u043e\u0433\u043e, \u0447\u0442\u043e \u043f\u0440\u043e\u0433\u0443\u043b\u043a\u0430 \u0432\u044b\u0431\u0435\u0440\u0435\u0442 \u0438\u043c\u0435\u043d\u043d\u043e \u044d\u0442\u043e \u0440\u0435\u0431\u0440\u043e \u043d\u0430 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u043c \u0448\u0430\u0433\u0435.<\/em><\/p>\n<p>  <\/p>\n<p><em>B: \u0420\u0430\u0437\u043d\u0438\u0446\u0430 \u043c\u0435\u0436\u0434\u0443 \u0441\u043b\u0443\u0447\u0430\u0439\u043d\u044b\u043c\u0438 \u043f\u0440\u043e\u0433\u0443\u043b\u043a\u0430\u043c\u0438, \u043e\u0441\u043d\u043e\u0432\u0430\u043d\u043d\u044b\u043c\u0438 \u043d\u0430 \u043f\u043e\u0438\u0441\u043a\u0435 \u043f\u043e \u0448\u0438\u0440\u0438\u043d\u0435 (BFS) \u0438 \u043f\u043e\u0438\u0441\u043a\u0435 \u043f\u043e \u0433\u043b\u0443\u0431\u0438\u043d\u0435 (DFS). \u0421\u043b\u0443\u0447\u0430\u0439\u043d\u044b\u0435 \u043f\u0440\u043e\u0433\u0443\u043b\u043a\u0438, \u043f\u043e\u0434\u043e\u0431\u043d\u044b\u0435 BFS, \u0432 \u043e\u0441\u043d\u043e\u0432\u043d\u043e\u043c \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0438\u0432\u0430\u044e\u0442\u0441\u044f \u0438\u0437\u0443\u0447\u0435\u043d\u0438\u0435\u043c \u043d\u0435\u043f\u043e\u0441\u0440\u0435\u0434\u0441\u0442\u0432\u0435\u043d\u043d\u044b\u0445 \u0441\u043e\u0441\u0435\u0434\u0435\u0439 \u0443\u0437\u043b\u0430 \u0438, \u043a\u0430\u043a \u043f\u0440\u0430\u0432\u0438\u043b\u043e, \u0431\u043e\u043b\u0435\u0435 \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u044b \u0434\u043b\u044f \u0437\u0430\u0445\u0432\u0430\u0442\u0430 \u043d\u0435\u043a\u0438\u0445 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u043d\u044b\u0445 \u0440\u043e\u043b\u0435\u0439. \u0422\u043e\u0433\u0434\u0430 \u043a\u0430\u043a, \u043f\u0440\u043e\u0433\u0443\u043b\u043a\u0438, \u043e\u0441\u043d\u043e\u0432\u0430\u043d\u043d\u044b\u0435 \u043d\u0430 DFS, \u0438\u0437\u0443\u0447\u0430\u044e\u0442 \u0431\u043e\u043b\u0435\u0435 \u043e\u0442\u0434\u0430\u043b\u0435\u043d\u043d\u044b\u0435 \u0443\u0437\u043b\u044b \u0438 \u043f\u0440\u0438\u043c\u0435\u043d\u044f\u044e\u0442\u0441\u044f \u0434\u043b\u044f \u0437\u0430\u0445\u0432\u0430\u0442\u0430 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440 \u0441\u043e\u043e\u0431\u0449\u0435\u0441\u0442\u0432\u0430 \u0432 \u0446\u0435\u043b\u043e\u043c.<\/em><\/p>\n<p>  <\/p>\n<h1 id=\"metod-avtoenkodera-okrestnostey\">\u041c\u0435\u0442\u043e\u0434 \u0430\u0432\u0442\u043e\u044d\u043d\u043a\u043e\u0434\u0435\u0440\u0430 \u043e\u043a\u0440\u0435\u0441\u0442\u043d\u043e\u0441\u0442\u0435\u0439<\/h1>\n<p>  <\/p>\n<p>\u0414\u043e \u0441\u0438\u0445 \u043f\u043e\u0440 \u0432\u0441\u0435 \u0440\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0435\u043d\u043d\u044b\u0435 \u043d\u0430\u043c\u0438 \u043c\u0435\u0442\u043e\u0434\u044b \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u0443\u0437\u043b\u043e\u0432 \u0431\u044b\u043b\u0438 \u043e\u0441\u043d\u043e\u0432\u0430\u043d\u044b \u043d\u0430 \u0442\u043e\u043c, \u0447\u0442\u043e \u043a\u043e\u0434\u0435\u0440 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u0442 \u0441\u043e\u0431\u043e\u0439 \u043f\u0440\u043e\u0441\u0442\u043e\u0439 \u043f\u043e\u0438\u0441\u043a \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u0439. \u041e\u0434\u043d\u0430\u043a\u043e \u044d\u0442\u0438 \u043f\u043e\u0434\u0445\u043e\u0434\u044b \u043f\u0440\u044f\u043c\u043e\u0433\u043e \u043a\u043e\u0434\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f \u043e\u0431\u0443\u0447\u0430\u044e\u0442 \u0443\u043d\u0438\u043a\u0430\u043b\u044c\u043d\u044b\u0435 \u0432\u0435\u043a\u0442\u043e\u0440\u044b \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u0439 \u043d\u0435\u0437\u0430\u0432\u0438\u0441\u0438\u043c\u043e \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0443\u0437\u043b\u0430, \u0447\u0442\u043e \u043f\u0440\u0438\u0432\u043e\u0434\u0438\u0442 \u043a \u0440\u044f\u0434\u0443 \u043d\u0435\u0434\u043e\u0441\u0442\u0430\u0442\u043a\u043e\u0432:<\/p>\n<p>  <\/p>\n<ol>\n<li>\u041d\u0438 \u043e\u0434\u0438\u043d \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440 \u043d\u0435 \u0440\u0430\u0441\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d \u043c\u0435\u0436\u0434\u0443 \u0443\u0437\u043b\u0430\u043c\u0438 \u0432 \u043a\u043e\u0434\u0435\u0440\u0435 (\u0442.\u0435. \u043a\u043e\u0434\u0435\u0440 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043f\u0440\u043e\u0441\u0442\u043e \u043f\u043e\u0438\u0441\u043a\u043e\u043c \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u0439 \u043d\u0430 \u043e\u0441\u043d\u043e\u0432\u0435 \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u043b\u044c\u043d\u044b\u0445 \u0438\u0434\u0435\u043d\u0442\u0438\u0444\u0438\u043a\u0430\u0442\u043e\u0440\u043e\u0432 \u0443\u0437\u043b\u043e\u0432). \u042d\u0442\u043e \u043d\u0435\u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u043e, \u043a\u0430\u043a \u0441\u0442\u0430\u0442\u0438\u0441\u0442\u0438\u0447\u0435\u0441\u043a\u0438, \u0442\u0430\u043a \u0438 \u0432\u044b\u0447\u0438\u0441\u043b\u0438\u0442\u0435\u043b\u044c\u043d\u043e.<\/li>\n<li>\u041f\u0440\u044f\u043c\u043e\u0435 \u043a\u043e\u0434\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435 \u0442\u0430\u043a\u0436\u0435 \u043d\u0435 \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u0430\u0442\u0440\u0438\u0431\u0443\u0442\u044b \u0443\u0437\u043b\u0430 \u0432\u043e \u0432\u0440\u0435\u043c\u044f \u043a\u043e\u0434\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f. \u0412\u043e \u043c\u043d\u043e\u0433\u0438\u0445 \u0431\u043e\u043b\u044c\u0448\u0438\u0445 \u0433\u0440\u0430\u0444\u0430\u0445 \u0443\u0437\u043b\u044b \u0438\u043c\u0435\u044e\u0442 \u0430\u0442\u0440\u0438\u0431\u0443\u0442\u0438\u0432\u043d\u0443\u044e \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u044e (\u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u043f\u0440\u043e\u0444\u0438\u043b\u0438 \u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u0435\u043b\u0435\u0439 \u0432 \u0441\u043e\u0446\u0438\u0430\u043b\u044c\u043d\u043e\u0439 \u0441\u0435\u0442\u0438), \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u0447\u0430\u0441\u0442\u043e \u043e\u0447\u0435\u043d\u044c \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0442\u0438\u0432\u043d\u0430 \u0432 \u043e\u0442\u043d\u043e\u0448\u0435\u043d\u0438\u0438 \u043f\u043e\u043b\u043e\u0436\u0435\u043d\u0438\u044f \u0438 \u0440\u043e\u043b\u0438 \u0443\u0437\u043b\u0430 \u0432 \u0433\u0440\u0430\u0444\u0435.<\/li>\n<li>\u041c\u0435\u0442\u043e\u0434\u044b \u043f\u0440\u044f\u043c\u043e\u0433\u043e \u043a\u043e\u0434\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f \u043f\u043e \u0441\u0432\u043e\u0435\u0439 \u043f\u0440\u0438\u0440\u043e\u0434\u0435 \u044f\u0432\u043b\u044f\u044e\u0442\u0441\u044f <strong>\u0442\u0440\u0430\u043d\u0441\u0434\u0443\u043a\u0442\u0438\u0432\u043d\u044b\u043c\u0438<\/strong>. \u042d\u0442\u043e \u0437\u043d\u0430\u0447\u0438\u0442, \u0447\u0442\u043e \u043e\u043d\u0438 \u043c\u043e\u0433\u0443\u0442 \u0433\u0435\u043d\u0435\u0440\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u0442\u043e\u043b\u044c\u043a\u043e \u0434\u043b\u044f \u0443\u0437\u043b\u043e\u0432, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043f\u0440\u0438\u0441\u0443\u0442\u0441\u0442\u0432\u043e\u0432\u0430\u043b\u0438 \u043d\u0430 \u044d\u0442\u0430\u043f\u0435 \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044f (\u0435\u0441\u043b\u0438 \u043d\u0435 \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u044e\u0442\u0441\u044f \u0434\u043e\u043f\u043e\u043b\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u0435 \u0443\u043b\u0443\u0447\u0448\u0430\u044e\u0449\u0438\u0435 \u0440\u0430\u0443\u043d\u0434\u044b, \u0447\u0442\u043e\u0431\u044b \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u0434\u043b\u044f \u043d\u043e\u0432\u044b\u0445 \u0443\u0437\u043b\u043e\u0432). \u042d\u0442\u043e \u043e\u0447\u0435\u043d\u044c \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u0430\u0442\u0438\u0447\u043d\u043e \u0434\u043b\u044f \u0440\u0430\u0437\u0432\u0438\u0432\u0430\u044e\u0449\u0438\u0445\u0441\u044f, \u043c\u0430\u0441\u0441\u0438\u0432\u043d\u044b\u0445 \u0433\u0440\u0430\u0444\u043e\u0432, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043d\u0435 \u043c\u043e\u0433\u0443\u0442 \u0431\u044b\u0442\u044c \u043f\u043e\u043b\u043d\u043e\u0441\u0442\u044c\u044e \u0441\u043e\u0445\u0440\u0430\u043d\u0435\u043d\u044b \u0432 \u043f\u0430\u043c\u044f\u0442\u0438, \u0438\u043b\u0438 \u043e\u0431\u043b\u0430\u0441\u0442\u0435\u0439, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0442\u0440\u0435\u0431\u0443\u044e\u0442 \u043e\u0431\u043e\u0431\u0449\u0435\u043d\u0438\u044f \u0434\u043b\u044f \u043d\u043e\u0432\u044b\u0445 \u0433\u0440\u0430\u0444\u043e\u0432 \u043f\u043e\u0441\u043b\u0435 \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044f.<\/li>\n<\/ol>\n<p>  <\/p>\n<p>\u041d\u0435\u0434\u0430\u0432\u043d\u043e \u0431\u044b\u043b \u043f\u0440\u0435\u0434\u043b\u043e\u0436\u0435\u043d \u0440\u044f\u0434 \u043f\u043e\u0434\u0445\u043e\u0434\u043e\u0432 \u0434\u043b\u044f \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0445\/\u0432\u0441\u0435\u0445 \u044d\u0442\u0438\u0445 \u043f\u0440\u043e\u0431\u043b\u0435\u043c. \u042d\u0442\u0438 \u043f\u043e\u0434\u0445\u043e\u0434\u044b \u0432\u0441\u0435 \u0435\u0449\u0435 \u043f\u0440\u043e\u0447\u043d\u043e \u0432\u0445\u043e\u0434\u044f\u0442 \u0432 \u0440\u0430\u043c\u043a\u0438 \u043a\u043e\u043d\u0446\u0435\u043f\u0446\u0438\u0438 \u043a\u043e\u0434\u0435\u0440-\u0434\u0435\u043a\u043e\u0434\u0435\u0440, \u043d\u043e \u043e\u043d\u0438 \u043e\u0442\u043b\u0438\u0447\u0430\u044e\u0442\u0441\u044f \u043e\u0442 \u043f\u0440\u044f\u043c\u044b\u0445 \u043c\u0435\u0442\u043e\u0434\u043e\u0432 \u043a\u043e\u0434\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e \u043e\u043d\u0438 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044e\u0442 \u0431\u043e\u043b\u0435\u0435 \u0441\u043b\u043e\u0436\u043d\u044b\u0435 \u043a\u043e\u0434\u0435\u0440\u044b, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0432 \u0446\u0435\u043b\u043e\u043c \u0437\u0430\u0432\u0438\u0441\u044f\u0442 \u043e\u0442 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u0438 \u0430\u0442\u0440\u0438\u0431\u0443\u0442\u0438\u043a\u0438 \u0433\u0440\u0430\u0444\u0430.<\/p>\n<p>  <\/p>\n<p>\u041e\u0442\u043e\u0431\u0440\u0430\u0436\u0435\u043d\u0438\u044f \u0432 \u0432\u0438\u0434\u0435 \u0433\u043b\u0443\u0431\u043e\u043a\u043e\u0433\u043e \u043d\u0435\u0439\u0440\u043e\u043d\u043d\u043e\u0433\u043e \u0433\u0440\u0430\u0444\u0430 (<strong>DNGR<\/strong>) \u0438 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u043d\u0430\u044f \u0433\u043b\u0443\u0431\u043e\u043a\u0430\u044f \u0441\u0435\u0442\u044c \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u0439 (<strong>SDNE<\/strong>) \u0440\u0435\u0448\u0430\u044e\u0442 \u043e\u0434\u043d\u0443 \u0438\u0437 \u043f\u0440\u043e\u0431\u043b\u0435\u043c, \u043e\u043f\u0438\u0441\u0430\u043d\u043d\u044b\u0445 \u0432\u044b\u0448\u0435: \u0432 \u043e\u0442\u043b\u0438\u0447\u0438\u0435 \u043e\u0442 \u043c\u0435\u0442\u043e\u0434\u043e\u0432 \u043f\u0440\u044f\u043c\u043e\u0433\u043e \u043a\u043e\u0434\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f, \u043e\u043d\u0438 \u043d\u0430\u043f\u0440\u044f\u043c\u0443\u044e \u0432\u043a\u043b\u044e\u0447\u0430\u044e\u0442 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0443 \u0433\u0440\u0430\u0444\u0430 \u0432 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043a\u043e\u0434\u0435\u0440\u0430. \u041e\u0441\u043d\u043e\u0432\u043d\u0430\u044f \u0438\u0434\u0435\u044f \u044d\u0442\u0438\u0445 \u043f\u043e\u0434\u0445\u043e\u0434\u043e\u0432 \u0441\u043e\u0441\u0442\u043e\u0438\u0442 \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e \u043e\u043d\u0438 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044e\u0442 \u0430\u0432\u0442\u043e\u044d\u043d\u043a\u043e\u0434\u0435\u0440\u044b \u2014 \u0445\u043e\u0440\u043e\u0448\u043e \u0438\u0437\u0432\u0435\u0441\u0442\u043d\u044b\u0439 \u043f\u043e\u0434\u0445\u043e\u0434 \u0433\u043b\u0443\u0431\u043e\u043a\u043e\u0433\u043e \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044f, \u0434\u043b\u044f \u0441\u0436\u0430\u0442\u0438\u044f \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u0438 \u043e \u043b\u043e\u043a\u0430\u043b\u044c\u043d\u043e\u0439 \u043e\u043a\u0440\u0435\u0441\u0442\u043d\u043e\u0441\u0442\u0438 \u0443\u0437\u043b\u0430 (\u0440\u0438\u0441.5). DNGR \u0438 SDNE \u0442\u0430\u043a\u0436\u0435 \u043e\u0442\u043b\u0438\u0447\u0430\u044e\u0442\u0441\u044f \u043e\u0442 \u0440\u0430\u043d\u0435\u0435 \u0440\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0435\u043d\u043d\u044b\u0445 \u043f\u043e\u0434\u0445\u043e\u0434\u043e\u0432 \u0442\u0435\u043c, \u0447\u0442\u043e \u043e\u043d\u0438 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044e\u0442 \u0443\u043d\u0430\u0440\u043d\u044b\u0439 \u0434\u0435\u043a\u043e\u0434\u0435\u0440 \u0432\u043c\u0435\u0441\u0442\u043e \u043f\u043e\u043f\u0430\u0440\u043d\u043e\u0433\u043e.<\/p>\n<p>  <\/p>\n<p><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/lo\/h3\/s6\/loh3s6kmxkof3po4jrfdz9rlphe.png\" alt=\"image\"\/><\/p>\n<p>  <\/p>\n<p>\u0412 \u044d\u0442\u0438\u0445 \u043f\u043e\u0434\u0445\u043e\u0434\u0430\u0445 \u043a\u0430\u0436\u0434\u044b\u0439 \u0443\u0437\u0435\u043b <math>$inline$v_i$inline$<\/math> \u0441\u0432\u044f\u0437\u0430\u043d \u0441 \u0432\u0435\u043a\u0442\u043e\u0440\u043e\u043c \u043e\u043a\u0440\u0435\u0441\u0442\u043d\u043e\u0441\u0442\u0438 <math>$inline$s_i \u2208 R^{|V|}$inline$<\/math>, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u0435\u0442 \u0441\u0442\u0440\u043e\u043a\u0435 <math>$inline$v_i$inline$<\/math> \u0432 \u043c\u0430\u0442\u0440\u0438\u0446\u0435 <math>$inline$S$inline$<\/math> (\u0433\u0434\u0435 <math>$inline$S$inline$<\/math> \u043e\u0442\u043e\u0431\u0440\u0430\u0436\u0430\u0435\u0442 \u0431\u043b\u0438\u0437\u043e\u0441\u0442\u044c \u043f\u0430\u0440\u043d\u044b\u0445 \u0443\u0437\u043b\u043e\u0432 \u2014 <math>$inline$S_i,_j = sG (v_i , v_j)$inline$<\/math>). \u0412\u0435\u043a\u0442\u043e\u0440 <math>$inline$s_i$inline$<\/math> \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442 \u043f\u0430\u0440\u043d\u0443\u044e \u0431\u043b\u0438\u0437\u043e\u0441\u0442\u044c \u0433\u0440\u0430\u0444\u0430 <math>$inline$v_i$inline$<\/math> \u043a\u043e \u0432\u0441\u0435\u043c \u043e\u0441\u0442\u0430\u043b\u044c\u043d\u044b\u043c \u0443\u0437\u043b\u0430\u043c \u0438 \u0444\u0443\u043d\u043a\u0446\u0438\u043e\u043d\u0438\u0440\u0443\u0435\u0442 \u043a\u0430\u043a \u043c\u043d\u043e\u0433\u043e\u043c\u0435\u0440\u043d\u043e\u0435 \u0432\u0435\u043a\u0442\u043e\u0440\u043d\u043e\u0435 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u0435 \u043e\u043a\u0440\u0435\u0441\u0442\u043d\u043e\u0441\u0442\u0438 <math>$inline$v_i$inline$<\/math>. \u0426\u0435\u043b\u044c \u0430\u0432\u0442\u043e\u044d\u043d\u043a\u043e\u0434\u0435\u0440\u0430 \u0434\u043b\u044f DNGR \u0438 SDNE \u0441\u043e\u0441\u0442\u043e\u0438\u0442 \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e\u0431\u044b \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u044f\u0442\u044c \u0443\u0437\u043b\u044b \u0441 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u0435\u043c <math>$inline$s_i$inline$<\/math> \u0432\u0435\u043a\u0442\u043e\u0440\u043e\u0432 \u0442\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c, \u0447\u0442\u043e \u043f\u043e\u0442\u043e\u043c \u0432\u0435\u043a\u0442\u043e\u0440\u044b <math>$inline$s_i$inline$<\/math> \u043c\u043e\u0436\u043d\u043e \u0431\u044b\u043b\u043e \u0431\u044b \u0432\u043e\u0441\u0441\u0442\u0430\u043d\u043e\u0432\u0438\u0442\u044c \u0438\u0437 \u044d\u0442\u0438\u0445 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u0439:<\/p>\n<p>  <\/p>\n<p><math>$$display$$DEC(ENC(s_i)) = DEC(z_i) \u2248 s_i$$display$$<\/math><\/p>\n<p>  <\/p>\n<p>\u0414\u0440\u0443\u0433\u0438\u043c\u0438 \u0441\u043b\u043e\u0432\u0430\u043c\u0438, \u043f\u043e\u0442\u0435\u0440\u044f \u0434\u043b\u044f \u044d\u0442\u0438\u0445 \u043c\u0435\u0442\u043e\u0434\u043e\u0432 \u043f\u0440\u0438\u043d\u0438\u043c\u0430\u0435\u0442 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0443\u044e \u0444\u043e\u0440\u043c\u0443:<\/p>\n<p>  <\/p>\n<p><math>$$display$$\u2113=\\sum_{v_i\u2208V} ||DEC(z_i) \u2212 s_i||^2_2$$display$$<\/math><\/p>\n<p>  <\/p>\n<p>\u041a\u0430\u043a \u0438 \u0432 \u0441\u043b\u0443\u0447\u0430\u0435 \u043f\u043e\u043f\u0430\u0440\u043d\u043e\u0433\u043e \u0434\u0435\u043a\u043e\u0434\u0435\u0440\u0430, \u0440\u0430\u0437\u043c\u0435\u0440\u043d\u043e\u0441\u0442\u044c \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u0439 <math>$inline$z_i$inline$<\/math> \u043d\u0430\u043c\u043d\u043e\u0433\u043e \u043c\u0435\u043d\u044c\u0448\u0435, \u0447\u0435\u043c <math>$inline$|V|$inline$<\/math> (\u0440\u0430\u0437\u043c\u0435\u0440\u043d\u043e\u0441\u0442\u044c \u0432\u0435\u043a\u0442\u043e\u0440\u043e\u0432), \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u0446\u0435\u043b\u044c \u0441\u043e\u0441\u0442\u043e\u0438\u0442 \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e\u0431\u044b \u0441\u0436\u0430\u0442\u044c \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u044e \u043e \u0441\u043e\u0441\u0435\u0434\u044f\u0445 \u0443\u0437\u043b\u0430 \u0432 \u043d\u0438\u0437\u043a\u043e\u0440\u0430\u0437\u043c\u0435\u0440\u043d\u044b\u0439 \u0432\u0435\u043a\u0442\u043e\u0440. \u041a\u0430\u043a \u0434\u043b\u044f SDNE, \u0442\u0430\u043a \u0438 \u0434\u043b\u044f DNGR, \u0444\u0443\u043d\u043a\u0446\u0438\u0438 \u043a\u043e\u0434\u0435\u0440\u0430 \u0438 \u0434\u0435\u043a\u043e\u0434\u0435\u0440\u0430 \u0441\u043e\u0441\u0442\u043e\u044f\u0442 \u0438\u0437 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u0438\u0445 \u0441\u043b\u043e\u0436\u0435\u043d\u043d\u044b\u0445 \u0441\u043b\u043e\u0435\u0432 \u043d\u0435\u0439\u0440\u043e\u043d\u043d\u043e\u0439 \u0441\u0435\u0442\u0438: \u043a\u0430\u0436\u0434\u044b\u0439 \u0443\u0440\u043e\u0432\u0435\u043d\u044c \u043a\u043e\u0434\u0435\u0440\u0430 \u0443\u043c\u0435\u043d\u044c\u0448\u0430\u0435\u0442 \u0440\u0430\u0437\u043c\u0435\u0440\u043d\u043e\u0441\u0442\u044c \u0435\u0433\u043e \u0432\u0445\u043e\u0434\u0430, \u0430 \u043a\u0430\u0436\u0434\u044b\u0439 \u0443\u0440\u043e\u0432\u0435\u043d\u044c \u0434\u0435\u043a\u043e\u0434\u0435\u0440\u0430 \u0443\u0432\u0435\u043b\u0438\u0447\u0438\u0432\u0430\u0435\u0442 \u0440\u0430\u0437\u043c\u0435\u0440\u043d\u043e\u0441\u0442\u044c \u0435\u0433\u043e \u0432\u0445\u043e\u0434\u0430 (\u0440\u0438\u0441.5).<\/p>\n<p>  <\/p>\n<p>SDNE \u0438 DNGR \u043e\u0442\u043b\u0438\u0447\u0430\u044e\u0442\u0441\u044f \u0444\u0443\u043d\u043a\u0446\u0438\u0435\u0439 \u043f\u043e\u0434\u043e\u0431\u0438\u044f, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044e\u0442\u0441\u044f \u0434\u043b\u044f \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u044f \u0432\u0435\u043a\u0442\u043e\u0440\u043e\u0432 \u043e\u043a\u0440\u0435\u0441\u0442\u043d\u043e\u0441\u0442\u0438 <math>$inline$s_i$inline$<\/math>, \u0430 \u0442\u0430\u043a\u0436\u0435 \u0432 \u0434\u0435\u0442\u0430\u043b\u044f\u0445 \u0442\u043e\u0433\u043e, \u043a\u0430\u043a \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0438\u0440\u0443\u0435\u0442\u0441\u044f \u0430\u0432\u0442\u043e\u044d\u043d\u043a\u043e\u0434\u0435\u0440. DNGR \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u0435\u0442 <math>$inline$s_i$inline$<\/math> \u0432 \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0438\u0438 \u0441 \u0442\u043e\u0447\u0435\u0447\u043d\u043e\u0439 \u0432\u0437\u0430\u0438\u043c\u043d\u043e\u0439 \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u0435\u0439 \u0434\u0432\u0443\u0445 \u0443\u0437\u043b\u043e\u0432, \u0441\u043e\u0432\u043c\u0435\u0441\u0442\u043d\u043e \u0432\u0441\u0442\u0440\u0435\u0447\u0430\u044e\u0449\u0438\u0445\u0441\u044f \u043f\u0440\u0438 \u0441\u043b\u0443\u0447\u0430\u0439\u043d\u044b\u0445 \u043f\u0440\u043e\u0433\u0443\u043b\u043a\u0430\u0445, \u0430\u043d\u0430\u043b\u043e\u0433\u0438\u0447\u043d\u043e DeepWalk \u0438 node2vec. SDNE \u043f\u0440\u043e\u0441\u0442\u043e \u0443\u0441\u0442\u0430\u043d\u0430\u0432\u043b\u0438\u0432\u0430\u0435\u0442 <math>$inline$s_i \u225c Ai$inline$<\/math>, \u0442\u043e \u0435\u0441\u0442\u044c \u0440\u0430\u0432\u043d\u044b\u043c \u0432\u0435\u043a\u0442\u043e\u0440\u0443 \u0441\u043c\u0435\u0436\u043d\u043e\u0441\u0442\u0438 <math>$inline$v_i$inline$<\/math>.<\/p>\n<p>  <\/p>\n<p>\u041d\u0435\u0441\u043c\u043e\u0442\u0440\u044f \u043d\u0430 \u0442\u043e, \u0447\u0442\u043e \u043c\u0435\u0442\u043e\u0434\u044b SDNE \u0438 DNGR \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u044e\u0442 \u0432\u043a\u043b\u044e\u0447\u0430\u0442\u044c \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u043d\u0443\u044e \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u044e \u043e \u043b\u043e\u043a\u0430\u043b\u044c\u043d\u043e\u0439 \u043e\u043a\u0440\u0435\u0441\u0442\u043d\u043e\u0441\u0442\u0438 \u0443\u0437\u043b\u0430 \u043d\u0435\u043f\u043e\u0441\u0440\u0435\u0434\u0441\u0442\u0432\u0435\u043d\u043d\u043e \u0432 \u043a\u043e\u0434\u0438\u0440\u043e\u0432\u0449\u0438\u043a \u0432 \u0432\u0438\u0434\u0435 \u0440\u0435\u0433\u0443\u043b\u044f\u0440\u0438\u0437\u0430\u0446\u0438\u0438, \u0447\u0442\u043e \u043d\u0435\u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e \u0434\u043b\u044f \u043f\u043e\u0434\u0445\u043e\u0434\u043e\u0432 \u043f\u0440\u044f\u043c\u043e\u0433\u043e \u043a\u043e\u0434\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f (\u043f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 \u0438\u0445 \u043a\u043e\u0434\u0438\u0440\u043e\u0432\u0449\u0438\u043a \u0437\u0430\u0432\u0438\u0441\u0438\u0442 \u0442\u043e\u043b\u044c\u043a\u043e \u043e\u0442 \u0438\u0434\u0435\u043d\u0442\u0438\u0444\u0438\u043a\u0430\u0442\u043e\u0440\u0430 \u0443\u0437\u043b\u0430), \u043e\u043d\u0438 \u043f\u043e-\u043f\u0440\u0435\u0436\u043d\u0435\u043c\u0443 \u043e\u0441\u0442\u0430\u044e\u0442\u0441\u044f \u043f\u043e\u0434\u0432\u0435\u0440\u0436\u0435\u043d\u044b \u0442\u0440\u0430\u043d\u0441\u0434\u0443\u043a\u0442\u0438\u0432\u043d\u043e\u0441\u0442\u0438. \u041a \u0442\u043e\u043c\u0443 \u0436\u0435 \u0432\u0445\u043e\u0434\u043d\u043e\u0435 \u0438\u0437\u043c\u0435\u0440\u0435\u043d\u0438\u0435 \u0434\u043b\u044f \u0430\u0432\u0442\u043e\u044d\u043d\u043a\u043e\u0434\u0435\u0440\u0430 \u0437\u0430\u0444\u0438\u043a\u0441\u0438\u0440\u043e\u0432\u0430\u043d\u043e \u043d\u0430 <math>$inline$|V|$inline$<\/math>, \u0447\u0442\u043e \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u0447\u0440\u0435\u0437\u0432\u044b\u0447\u0430\u0439\u043d\u043e \u0434\u043e\u0440\u043e\u0433\u043e\u0441\u0442\u043e\u044f\u0449\u0438\u043c \u0438 \u0434\u0430\u0436\u0435 \u043d\u0435\u0440\u0430\u0437\u0440\u0435\u0448\u0438\u043c\u044b\u043c \u0434\u043b\u044f \u0433\u0440\u0430\u0444\u043e\u0432 \u0441 \u043c\u0438\u043b\u043b\u0438\u043e\u043d\u0430\u043c\u0438 \u0443\u0437\u043b\u043e\u0432.<\/p>\n<p>  <\/p>\n<p>\u0421\u0442\u043e\u0438\u0442 \u043e\u0442\u043c\u0435\u0442\u0438\u0442\u044c, \u0447\u0442\u043e \u043d\u0430 \u0434\u0430\u043d\u043d\u044b\u0439 \u043c\u043e\u043c\u0435\u043d\u0442 \u0432 \u0441\u0444\u0435\u0440\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u0432 \u0433\u0440\u0430\u0444\u043e\u0432 \u043d\u0435 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 \u043f\u0430\u043d\u0430\u0446\u0435\u0438. \u041b\u044e\u0431\u043e\u0439 \u043c\u0435\u0442\u043e\u0434 \u0432 \u0442\u043e\u0439 \u0438\u043b\u0438 \u0438\u043d\u043e\u0439 \u0441\u0442\u0435\u043f\u0435\u043d\u0438 \u043f\u043e\u0434\u0432\u0435\u0440\u0436\u0435\u043d \u0441\u0435\u0440\u044c\u0435\u0437\u043d\u044b\u043c \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f\u043c. \u041e\u0441\u0442\u0430\u0432\u0448\u0438\u0435\u0441\u044f \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b, \u0442\u0430\u043a\u0438\u0435 \u043a\u0430\u043a <strong>\u0430\u0433\u0440\u0435\u0433\u0430\u0446\u0438\u044f \u043e\u043a\u0440\u0435\u0441\u0442\u043d\u043e\u0441\u0442\u0435\u0439<\/strong>, <strong>\u0441\u0432\u0435\u0440\u0442\u043e\u0447\u043d\u044b\u0435 \u043a\u043e\u0434\u0435\u0440\u044b<\/strong>, <strong>\u043c\u0435\u0445\u0430\u043d\u0438\u0437\u043c\u044b \u0432\u043d\u0438\u043c\u0430\u043d\u0438\u044f<\/strong> \u0438 \u043c\u043d\u043e\u0433\u0438\u0435 \u0434\u0440\u0443\u0433\u0438\u0435 [<a href=\"https:\/\/arxiv.org\/pdf\/1901.00596.pdf\">9<\/a>], \u043f\u044b\u0442\u0430\u044e\u0442\u0441\u044f \u0440\u0435\u0448\u0438\u0442\u044c \u043e\u0431\u043e\u0437\u043d\u0430\u0447\u0435\u043d\u043d\u044b\u0435 \u0432\u043e\u043f\u0440\u043e\u0441\u044b. \u041a \u0441\u043e\u0436\u0430\u043b\u0435\u043d\u0438\u044e, \u0440\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0435\u043d\u0438\u0435 \u044d\u0442\u0438\u0445 \u043c\u0435\u0442\u043e\u0434\u043e\u0432 \u0441\u0438\u043b\u044c\u043d\u043e \u0432\u044b\u0445\u043e\u0434\u0438\u0442 \u0437\u0430 \u0440\u0430\u043c\u043a\u0438 \u043e\u0437\u043d\u0430\u043a\u043e\u043c\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0433\u043e \u043a\u0443\u0440\u0441\u0430 \u0438 \u0431\u0443\u0434\u0435\u0442 \u0440\u0430\u0441\u043a\u0440\u044b\u0442\u043e \u0432 \u043e\u0442\u0434\u0435\u043b\u044c\u043d\u043e\u0439 \u0441\u0442\u0430\u0442\u044c\u0435.<\/p>\n<p>  <\/p>\n<h1 id=\"zaklyuchenie\">\u0417\u0430\u043a\u043b\u044e\u0447\u0435\u043d\u0438\u0435<\/h1>\n<p>  <\/p>\n<p>\u041f\u043e\u0434\u0445\u043e\u0434\u044b \u043a \u0440\u0435\u043f\u0440\u0435\u0437\u0435\u043d\u0442\u0430\u0442\u0438\u0432\u043d\u043e\u043c\u0443 \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044e \u0434\u043b\u044f \u043c\u0430\u0448\u0438\u043d\u043d\u043e\u0433\u043e \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044f \u043d\u0430 \u0433\u0440\u0430\u0444\u0430\u0445 \u043f\u0440\u0435\u0434\u043b\u0430\u0433\u0430\u044e\u0442 \u043c\u043e\u0449\u043d\u0443\u044e \u0430\u043b\u044c\u0442\u0435\u0440\u043d\u0430\u0442\u0438\u0432\u0443 \u0442\u0440\u0430\u0434\u0438\u0446\u0438\u043e\u043d\u043d\u043e\u043c\u0443 \u043f\u0440\u043e\u0435\u043a\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044e \u043e\u0431\u044a\u0435\u043a\u0442\u043e\u0432. \u041e\u0434\u043d\u0430\u043a\u043e \u043f\u0440\u0435\u0434\u0441\u0442\u043e\u0438\u0442 \u0435\u0449\u0435 \u043f\u0440\u043e\u0434\u0435\u043b\u0430\u0442\u044c \u0431\u043e\u043b\u044c\u0448\u0443\u044e \u0440\u0430\u0431\u043e\u0442\u0443, \u043a\u0430\u043a \u0432 \u043f\u043b\u0430\u043d\u0435 \u043f\u043e\u0432\u044b\u0448\u0435\u043d\u0438\u044f \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u043e\u0441\u0442\u0438 \u044d\u0442\u0438\u0445 \u043c\u0435\u0442\u043e\u0434\u043e\u0432, \u0442\u0430\u043a \u0438, \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e, \u0447\u0442\u043e \u0435\u0449\u0435 \u0431\u043e\u043b\u0435\u0435 \u0432\u0430\u0436\u043d\u043e, \u0432 \u0440\u0430\u0437\u0440\u0430\u0431\u043e\u0442\u043a\u0435 \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u0445 \u0442\u0435\u043e\u0440\u0435\u0442\u0438\u0447\u0435\u0441\u043a\u0438\u0445 \u043e\u0441\u043d\u043e\u0432, \u043d\u0430 \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u043c\u043e\u0433\u0443\u0442 \u043e\u0441\u043d\u043e\u0432\u044b\u0432\u0430\u0442\u044c\u0441\u044f \u0431\u0443\u0434\u0443\u0449\u0438\u0435 \u0438\u043d\u043d\u043e\u0432\u0430\u0446\u0438\u0438.<\/p>\n<p>  <\/p>\n<p>\u0412 \u0434\u043e\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u0435 \u043a \u043e\u0431\u0449\u0438\u043c \u0437\u0430\u0434\u0430\u0447\u0430\u043c, \u0438\u0437\u043b\u043e\u0436\u0435\u043d\u043d\u044b\u043c \u0432\u044b\u0448\u0435, \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 \u0440\u044f\u0434 \u043a\u043e\u043d\u043a\u0440\u0435\u0442\u043d\u044b\u0445 \u043e\u0442\u043a\u0440\u044b\u0442\u044b\u0445 \u043f\u0440\u043e\u0431\u043b\u0435\u043c, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0435\u0449\u0435 \u043f\u0440\u0435\u0434\u0441\u0442\u043e\u0438\u0442 \u0440\u0435\u0448\u0438\u0442\u044c \u0432 \u043e\u0431\u043b\u0430\u0441\u0442\u0438 \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044f \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u0439 \u043d\u0430 \u0433\u0440\u0430\u0444\u0430\u0445.<\/p>\n<p>  <\/p>\n<p><em>\u041c\u0430\u0441\u0448\u0442\u0430\u0431\u0438\u0440\u0443\u0435\u043c\u043e\u0441\u0442\u044c<\/em>. \u0425\u043e\u0442\u044f \u0431\u043e\u043b\u044c\u0448\u0438\u043d\u0441\u0442\u0432\u043e \u0441\u043e\u0432\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0445 \u0440\u0430\u0431\u043e\u0442 \u0442\u0435\u043e\u0440\u0435\u0442\u0438\u0447\u0435\u0441\u043a\u0438 \u0445\u043e\u0440\u043e\u0448\u043e \u043c\u0430\u0441\u0448\u0442\u0430\u0431\u0438\u0440\u0443\u044e\u0442\u0441\u044f (\u0442.\u0435 \u0432\u0440\u0435\u043c\u044f \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044f <math>$inline$O(|E|)$inline$<\/math>), \u0435\u0449\u0435 \u043f\u0440\u0435\u0434\u0441\u0442\u043e\u0438\u0442 \u043f\u0440\u043e\u0434\u0435\u043b\u0430\u0442\u044c \u0437\u043d\u0430\u0447\u0438\u0442\u0435\u043b\u044c\u043d\u0443\u044e \u0440\u0430\u0431\u043e\u0442\u0443 \u0432 \u043f\u043e\u0434\u0445\u043e\u0434\u0430\u0445 \u043c\u0430\u0441\u0448\u0442\u0430\u0431\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f \u0443\u0437\u043b\u043e\u0432 \u0438 \u0433\u0440\u0430\u0444\u0438\u043a\u043e\u0432 \u043a \u0434\u0435\u0439\u0441\u0442\u0432\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u043c\u0430\u0441\u0441\u0438\u0432\u043d\u044b\u043c \u043d\u0430\u0431\u043e\u0440\u0430\u043c \u0434\u0430\u043d\u043d\u044b\u0445 (\u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440 \u043c\u0438\u043b\u043b\u0438\u0430\u0440\u0434\u0430\u043c \u0443\u0437\u043b\u043e\u0432). \u0411\u043e\u043b\u044c\u0448\u0438\u043d\u0441\u0442\u0432\u043e \u043c\u0435\u0442\u043e\u0434\u043e\u0432 \u043e\u0441\u043d\u043e\u0432\u0430\u043d\u044b \u043d\u0430 \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u0438 \u0438 \u0445\u0440\u0430\u043d\u0435\u043d\u0438\u0438 \u0443\u043d\u0438\u043a\u0430\u043b\u044c\u043d\u044b\u0445 \u0432\u043b\u043e\u0436\u0435\u043d\u0438\u0439 \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u043e\u0442\u0434\u0435\u043b\u044c\u043d\u043e\u0433\u043e \u0443\u0437\u043b\u0430. \u0411\u043e\u043b\u0435\u0435 \u0442\u043e\u0433\u043e, \u0431\u043e\u043b\u044c\u0448\u0438\u043d\u0441\u0442\u0432\u043e \u0443\u0441\u0442\u0430\u043d\u043e\u0432\u043e\u043a \u043e\u0446\u0435\u043d\u043a\u0438 \u043f\u0440\u0435\u0434\u043f\u043e\u043b\u0430\u0433\u0430\u044e\u0442, \u0447\u0442\u043e \u0430\u0442\u0440\u0438\u0431\u0443\u0442\u044b, \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u0438 \u0441\u043f\u0438\u0441\u043a\u0438 \u0440\u0435\u0431\u0435\u0440 \u0432\u0441\u0435\u0445 \u0443\u0437\u043b\u043e\u0432, \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c\u044b\u0445 \u043a\u0430\u043a \u0434\u043b\u044f \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044f, \u0442\u0430\u043a \u0438 \u0434\u043b\u044f \u0442\u0435\u0441\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f, \u043c\u043e\u0433\u0443\u0442 \u0443\u043c\u0435\u0441\u0442\u0438\u0442\u044c\u0441\u044f \u0432 \u043e\u0441\u043d\u043e\u0432\u043d\u043e\u0439 \u043f\u0430\u043c\u044f\u0442\u0438 \u2014 \u043f\u0440\u0435\u0434\u043f\u043e\u043b\u043e\u0436\u0435\u043d\u0438\u0435, \u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u043f\u0440\u043e\u0442\u0438\u0432\u043e\u0440\u0435\u0447\u0438\u0442 \u0440\u0435\u0430\u043b\u044c\u043d\u043e\u0441\u0442\u0438 \u0431\u043e\u043b\u044c\u0448\u0438\u043d\u0441\u0442\u0432\u0430 \u043e\u0431\u043b\u0430\u0441\u0442\u0435\u0439 \u043f\u0440\u0438\u043c\u0435\u043d\u0435\u043d\u0438\u044f, \u0433\u0434\u0435 \u0433\u0440\u0430\u0444\u044b \u044f\u0432\u043b\u044f\u044e\u0442\u0441\u044f \u043c\u0430\u0441\u0441\u0438\u0432\u043d\u044b\u043c\u0438, \u0440\u0430\u0437\u0432\u0438\u0432\u0430\u044e\u0449\u0438\u043c\u0438\u0441\u044f \u0438 \u0447\u0430\u0441\u0442\u043e \u0445\u0440\u0430\u043d\u0438\u0442\u0441\u044f \u0432 \u0440\u0430\u0441\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u043d\u043e\u043c \u0432\u0438\u0434\u0435. \u0420\u0430\u0437\u0440\u0430\u0431\u043e\u0442\u043a\u0430 \u0440\u0430\u043c\u043e\u043a \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044f \u0440\u0435\u043f\u0440\u0435\u0437\u0435\u043d\u0442\u0430\u0446\u0438\u0438, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0434\u0435\u0439\u0441\u0442\u0432\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u043c\u0430\u0441\u0448\u0442\u0430\u0431\u0438\u0440\u0443\u044e\u0442\u0441\u044f \u0434\u043e \u0440\u0435\u0430\u043b\u044c\u043d\u044b\u0445 \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0441\u0442\u0432\u0435\u043d\u043d\u044b\u0445 \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u043e\u0432, \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u0430, \u0447\u0442\u043e\u0431\u044b \u043f\u0440\u0435\u0434\u043e\u0442\u0432\u0440\u0430\u0442\u0438\u0442\u044c \u0440\u0430\u0441\u0448\u0438\u0440\u0435\u043d\u0438\u0435 \u0440\u0430\u0437\u0440\u044b\u0432\u0430 \u043c\u0435\u0436\u0434\u0443 \u0441\u043e\u043e\u0431\u0449\u0435\u0441\u0442\u0432\u043e\u043c \u0430\u043a\u0430\u0434\u0435\u043c\u0438\u0447\u0435\u0441\u043a\u0438\u0445 \u0438\u0441\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u043d\u0438\u0439 \u0438 \u0440\u0435\u0430\u043b\u044c\u043d\u044b\u043c\u0438 \u043f\u043e\u0442\u0440\u0435\u0431\u0438\u0442\u0435\u043b\u044f\u043c\u0438 \u044d\u0442\u0438\u0445 \u043f\u043e\u0434\u0445\u043e\u0434\u043e\u0432.<\/p>\n<p>  <\/p>\n<p><em>\u0418\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u0435 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440 \u0432\u044b\u0441\u0448\u0435\u0433\u043e \u043f\u043e\u0440\u044f\u0434\u043a\u0430<\/em>. \u0425\u043e\u0442\u044f \u0432 \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0438\u0435 \u0433\u043e\u0434\u044b \u0431\u043e\u043b\u044c\u0448\u0430\u044f \u0440\u0430\u0431\u043e\u0442\u0430 \u0431\u044b\u043b\u0430 \u043f\u043e\u0441\u0432\u044f\u0449\u0435\u043d\u0430 \u0443\u0442\u043e\u0447\u043d\u0435\u043d\u0438\u044e \u0438 \u0441\u043e\u0432\u0435\u0440\u0448\u0435\u043d\u0441\u0442\u0432\u043e\u0432\u0430\u043d\u0438\u044e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u043a\u043e\u0434\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f, \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c\u043e\u0433\u043e \u0434\u043b\u044f \u0433\u0435\u043d\u0435\u0440\u0430\u0446\u0438\u0438 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u0439 \u0443\u0437\u043b\u043e\u0432, \u0431\u043e\u043b\u044c\u0448\u0438\u043d\u0441\u0442\u0432\u043e \u043c\u0435\u0442\u043e\u0434\u043e\u0432 \u043f\u043e-\u043f\u0440\u0435\u0436\u043d\u0435\u043c\u0443 \u043f\u043e\u043b\u0430\u0433\u0430\u044e\u0442\u0441\u044f \u043d\u0430 \u0431\u0430\u0437\u043e\u0432\u044b\u0435 \u043f\u043e\u043f\u0430\u0440\u043d\u044b\u0435 \u0434\u0435\u043a\u043e\u0434\u0435\u0440\u044b, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043f\u0440\u043e\u0433\u043d\u043e\u0437\u0438\u0440\u0443\u044e\u0442 \u043f\u0430\u0440\u043d\u044b\u0435 \u043e\u0442\u043d\u043e\u0448\u0435\u043d\u0438\u044f \u043c\u0435\u0436\u0434\u0443 \u0443\u0437\u043b\u0430\u043c\u0438 \u0438 \u0438\u0433\u043d\u043e\u0440\u0438\u0440\u0443\u044e\u0442 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u0433\u0440\u0430\u0444\u0430 \u0431\u043e\u043b\u0435\u0435 \u0432\u044b\u0441\u043e\u043a\u043e\u0433\u043e \u043f\u043e\u0440\u044f\u0434\u043a\u0430, \u0432\u043a\u043b\u044e\u0447\u0430\u044e\u0449\u0438\u0435 \u0431\u043e\u043b\u0435\u0435 \u0434\u0432\u0443\u0445 \u0443\u0437\u043b\u043e\u0432. \u0425\u043e\u0440\u043e\u0448\u043e \u0438\u0437\u0432\u0435\u0441\u0442\u043d\u043e, \u0447\u0442\u043e \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u043d\u044b\u0435 \u043c\u043e\u0442\u0438\u0432\u044b \u0432\u044b\u0441\u0448\u0435\u0433\u043e \u043f\u043e\u0440\u044f\u0434\u043a\u0430 \u0438\u043c\u0435\u044e\u0442 \u0432\u0430\u0436\u043d\u043e\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0434\u043b\u044f \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u0438 \u0444\u0443\u043d\u043a\u0446\u0438\u043e\u043d\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f \u0441\u043b\u043e\u0436\u043d\u044b\u0445 \u0441\u0435\u0442\u0435\u0439, \u0430 \u0440\u0430\u0437\u0440\u0430\u0431\u043e\u0442\u043a\u0430 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u0432 \u0434\u0435\u043a\u043e\u0434\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f, \u0441\u043f\u043e\u0441\u043e\u0431\u043d\u044b\u0445 \u0434\u0435\u043a\u043e\u0434\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0442\u0430\u043a\u0438\u0435 \u0441\u043b\u043e\u0436\u043d\u044b\u0435 \u043a\u043e\u043d\u0444\u0438\u0433\u0443\u0440\u0430\u0446\u0438\u0438, \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0432\u0430\u0436\u043d\u044b\u043c \u043d\u0430\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u0438\u0435\u043c \u0431\u0443\u0434\u0443\u0449\u0435\u0439 \u0440\u0430\u0431\u043e\u0442\u044b.<\/p>\n<p>  <\/p>\n<p><em>\u041c\u043e\u0434\u0435\u043b\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435 \u0434\u0438\u043d\u0430\u043c\u0438\u0447\u0435\u0441\u043a\u0438\u0445 \u0433\u0440\u0430\u0444\u043e\u0432<\/em>. \u041c\u043d\u043e\u0433\u0438\u0435 \u043e\u0431\u043b\u0430\u0441\u0442\u0438 \u043f\u0440\u0438\u043c\u0435\u043d\u0435\u043d\u0438\u044f \u0432\u043a\u043b\u044e\u0447\u0430\u044e\u0442 \u0432 \u0441\u0435\u0431\u044f \u0432\u044b\u0441\u043e\u043a\u043e\u0434\u0438\u043d\u0430\u043c\u0438\u0447\u043d\u044b\u0435 \u0433\u0440\u0430\u0444\u044b, \u0433\u0434\u0435 \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u044f \u043e \u0441\u0438\u043d\u0445\u0440\u043e\u043d\u0438\u0437\u0430\u0446\u0438\u0438 \u0438\u043c\u0435\u0435\u0442 \u0440\u0435\u0448\u0430\u044e\u0449\u0435\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435, \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0441\u0435\u0442\u0438 \u043e\u0431\u043c\u0435\u043d\u0430 \u043c\u0433\u043d\u043e\u0432\u0435\u043d\u043d\u044b\u043c\u0438 \u0441\u043e\u043e\u0431\u0449\u0435\u043d\u0438\u044f\u043c\u0438 \u0438\u043b\u0438 \u0433\u0440\u0430\u0444\u044b \u0444\u0438\u043d\u0430\u043d\u0441\u043e\u0432\u044b\u0445 \u0442\u0440\u0430\u043d\u0437\u0430\u043a\u0446\u0438\u0439. \u041e\u0434\u043d\u0430\u043a\u043e \u043d\u0430\u043c \u043d\u0435 \u0445\u0432\u0430\u0442\u0430\u0435\u0442 \u043f\u043e\u0434\u0445\u043e\u0434\u043e\u0432 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u0439, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043c\u043e\u0433\u0443\u0442 \u0441\u043f\u0440\u0430\u0432\u0438\u0442\u044c\u0441\u044f \u0441 \u0443\u043d\u0438\u043a\u0430\u043b\u044c\u043d\u044b\u043c\u0438 \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u0430\u043c\u0438, \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u043d\u044b\u043c\u0438 \u0434\u0438\u043d\u0430\u043c\u0438\u0447\u0435\u0441\u043a\u0438\u043c\u0438 \u0433\u0440\u0430\u0444\u0430\u043c\u0438, \u0442\u0430\u043a\u0438\u043c\u0438 \u043a\u0430\u043a \u0437\u0430\u0434\u0430\u0447\u0430 \u0432\u043a\u043b\u044e\u0447\u0435\u043d\u0438\u044f \u0432\u0440\u0435\u043c\u0435\u043d\u043d\u043e\u0439 \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u0438 \u043e \u0440\u0435\u0431\u0440\u0430\u0445. \u0412\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0435 \u0433\u0440\u0430\u0444\u044b \u0441\u0442\u0430\u043d\u043e\u0432\u044f\u0442\u0441\u044f \u0432\u0441\u0435 \u0431\u043e\u043b\u0435\u0435 \u0432\u0430\u0436\u043d\u044b\u043c \u043e\u0431\u044a\u0435\u043a\u0442\u043e\u043c \u0438\u0441\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u043d\u0438\u044f, \u0438 \u0440\u0430\u0441\u0448\u0438\u0440\u0435\u043d\u0438\u0435 \u043c\u0435\u0442\u043e\u0434\u043e\u0432 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u0433\u0440\u0430\u0444\u043e\u0432 \u0434\u043b\u044f \u0440\u0430\u0431\u043e\u0442\u044b \u043d\u0430\u0434 \u043d\u0438\u043c\u0438 \u043e\u0442\u043a\u0440\u043e\u0435\u0442 \u0448\u0438\u0440\u043e\u043a\u0438\u0439 \u0441\u043f\u0435\u043a\u0442\u0440 \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u044b\u0445 \u043f\u0440\u0438\u043a\u043b\u0430\u0434\u043d\u044b\u0445 \u043e\u0431\u043b\u0430\u0441\u0442\u0435\u0439.<\/p>\n<p>  <\/p>\n<p><em>\u0423\u043b\u0443\u0447\u0448\u0435\u043d\u0438\u0435 \u0438\u043d\u0442\u0435\u0440\u043f\u0440\u0435\u0442\u0438\u0440\u0443\u0435\u043c\u043e\u0441\u0442\u0438<\/em>. \u041e\u0431\u0443\u0447\u0435\u043d\u0438\u0435 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u0439 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043f\u0440\u0438\u0432\u043b\u0435\u043a\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0439 \u043e\u0431\u043b\u0430\u0441\u0442\u044c\u044e, \u043f\u043e\u0442\u043e\u043c\u0443 \u0447\u0442\u043e \u043e\u043d\u043e \u043e\u0441\u0432\u043e\u0431\u043e\u0436\u0434\u0430\u0435\u0442 \u0431\u043e\u043b\u044c\u0448\u0443\u044e \u0447\u0430\u0441\u0442\u044c \u0431\u0440\u0435\u043c\u0435\u043d\u0438 \u0440\u0443\u0447\u043d\u044b\u0445 \u0444\u0443\u043d\u043a\u0446\u0438\u0439 \u043f\u0440\u043e\u0435\u043a\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f, \u043d\u043e \u043e\u043d\u043e \u0442\u0430\u043a\u0436\u0435 \u0438\u043c\u0435\u0435\u0442 \u043e\u0431\u0449\u0435\u0438\u0437\u0432\u0435\u0441\u0442\u043d\u0443\u044e \u0441\u0442\u043e\u0438\u043c\u043e\u0441\u0442\u044c \u0438\u043d\u0442\u0435\u0440\u043f\u0440\u0435\u0442\u0438\u0440\u0443\u0435\u043c\u043e\u0441\u0442\u0438. \u041c\u044b \u0437\u043d\u0430\u0435\u043c, \u0447\u0442\u043e \u043f\u043e\u0434\u0445\u043e\u0434\u044b \u043d\u0430 \u043e\u0441\u043d\u043e\u0432\u0435 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u0439 \u043e\u0431\u0435\u0441\u043f\u0435\u0447\u0438\u0432\u0430\u044e\u0442 \u0441\u043e\u0432\u0440\u0435\u043c\u0435\u043d\u043d\u0443\u044e \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c, \u043d\u043e \u0444\u0443\u043d\u0434\u0430\u043c\u0435\u043d\u0442\u0430\u043b\u044c\u043d\u044b\u0435 \u0438\u043c\u0438\u0442\u0430\u0446\u0438\u0438 \u0438 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b\u0435 \u043e\u0441\u043d\u043e\u0432\u043d\u044b\u0435 \u043e\u0442\u043a\u043b\u043e\u043d\u0435\u043d\u0438\u044f \u044d\u0442\u0438\u0445 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u0432 \u0434\u043e \u043a\u043e\u043d\u0446\u0430 \u043d\u0435 \u0438\u0437\u0443\u0447\u0435\u043d\u044b. \u0427\u0442\u043e\u0431\u044b \u0434\u0432\u0438\u0433\u0430\u0442\u044c\u0441\u044f \u0432\u043f\u0435\u0440\u0435\u0434, \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u043f\u043e\u0437\u0430\u0431\u043e\u0442\u0438\u0442\u044c\u0441\u044f \u043e \u0440\u0430\u0437\u0440\u0430\u0431\u043e\u0442\u043a\u0435 \u043d\u043e\u0432\u044b\u0445 \u043c\u0435\u0442\u043e\u0434\u043e\u0432, \u0443\u043b\u0443\u0447\u0448\u0430\u044e\u0449\u0438\u0445 \u0438\u043d\u0442\u0435\u0440\u043f\u0440\u0435\u0442\u0438\u0440\u0443\u0435\u043c\u043e\u0441\u0442\u044c \u0438\u0437\u0443\u0447\u0435\u043d\u043d\u044b\u0445 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u0439, \u043f\u043e\u043c\u0438\u043c\u043e \u0432\u0438\u0437\u0443\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438 \u0438 \u043e\u0446\u0435\u043d\u043a\u0438 \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438. \u0423\u0447\u0438\u0442\u044b\u0432\u0430\u044f \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u0438 \u0438 \u0440\u0435\u043f\u0440\u0435\u0437\u0435\u043d\u0442\u0430\u0442\u0438\u0432\u043d\u044b\u0435 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e\u0441\u0442\u0438 \u044d\u0442\u0438\u0445 \u043f\u043e\u0434\u0445\u043e\u0434\u043e\u0432, \u0438\u0441\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u0438 \u0434\u043e\u043b\u0436\u043d\u044b \u0432\u0441\u0435\u0433\u0434\u0430 \u043f\u0440\u043e\u044f\u0432\u043b\u044f\u0442\u044c \u0431\u0434\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c, \u0447\u0442\u043e\u0431\u044b \u0433\u0430\u0440\u0430\u043d\u0442\u0438\u0440\u043e\u0432\u0430\u0442\u044c, \u0447\u0442\u043e \u0438\u0445 \u043c\u0435\u0442\u043e\u0434\u044b \u0434\u0435\u0439\u0441\u0442\u0432\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u0443\u0447\u0430\u0442\u0441\u044f \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u044f\u0442\u044c \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u044e\u0449\u0443\u044e \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u044e \u0433\u0440\u0430\u0444\u0430, \u0430 \u043d\u0435 \u043e\u0431\u043e\u0431\u0449\u0430\u044e\u0442 \u0441\u0442\u0430\u0442\u0438\u0441\u0442\u0438\u0447\u0435\u0441\u043a\u0438\u0435 \u0442\u0435\u043d\u0434\u0435\u043d\u0446\u0438\u0438.<\/p>\n<p>  <\/p>\n<p>\u0412 \u0437\u0430\u043a\u043b\u044e\u0447\u0435\u043d\u0438\u0438 \u043c\u043d\u0435 \u0431\u044b \u0445\u043e\u0442\u0435\u043b\u043e\u0441\u044c \u0441\u043a\u0430\u0437\u0430\u0442\u044c, \u0447\u0442\u043e \u0441\u0435\u0439\u0447\u0430\u0441 \u0442\u0435\u043e\u0440\u0438\u044f \u0433\u0440\u0430\u0444\u043e\u0432 \u2014 \u043e\u0434\u043d\u043e \u0438\u0437 \u043d\u0430\u0438\u0431\u043e\u043b\u0435\u0435 \u043f\u0435\u0440\u0441\u043f\u0435\u043a\u0442\u0438\u0432\u043d\u044b\u0445 \u043d\u0430\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u0438\u0439 \u0432 \u043c\u0430\u0448\u0438\u043d\u043d\u043e\u043c \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u0438. \u041e\u0431\u0443\u0437\u0434\u0430\u0432 \u0432\u0441\u044e \u043c\u043e\u0449\u044c, \u043a\u043e\u0442\u043e\u0440\u0443\u044e \u043c\u043e\u0433\u0443\u0442 \u0434\u0430\u0442\u044c \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u0433\u0440\u0430\u0444\u043e\u0432, \u0447\u0435\u043b\u043e\u0432\u0435\u0447\u0435\u0441\u0442\u0432\u043e \u0441\u0434\u0435\u043b\u0430\u0435\u0442 \u043e\u0433\u0440\u043e\u043c\u043d\u044b\u0439 \u0448\u0430\u0433 \u043d\u0430 \u043f\u0443\u0442\u0438 \u043a \u0441\u043e\u0437\u0434\u0430\u043d\u0438\u044e \u043f\u0435\u0440\u0432\u043e\u0433\u043e \u043f\u0440\u043e\u0442\u043e\u0442\u0438\u043f\u0430 \u0438\u0441\u043a\u0443\u0441\u0441\u0442\u0432\u0435\u043d\u043d\u043e\u0433\u043e \u0438\u043d\u0442\u0435\u043b\u043b\u0435\u043a\u0442\u0430.<\/p>\n<p>  <\/p>\n<h1 id=\"ssylki\">\u0421\u0441\u044b\u043b\u043a\u0438<\/h1>\n<p>  <\/p>\n<p>[1] \u2014 W. L. Hamilton, Z. Ying, and J. Leskovec, &quot;Inductive representation learning on large graphs,&quot; NIPS 2017, pp. 1024\u20131034, 2017.<br \/>  [2] \u2014 T. N. Kipf and M. Welling, &quot;Semi-supervised classification with graph convolutional networks,&quot; ICLR 2017, 2017.<br \/>  [3] \u2014 A. Sanchez-Gonzalez, N. Heess, J. T. Springenberg, J. Merel, M. Riedmiller, R. Hadsell, and P. Battaglia, &quot;Graph networks as learnable physics engines for inference and control,&quot; arXiv<br \/>  preprint arXiv:1806.01242, 2018.<br \/>  [4] \u2014 P. Battaglia, R. Pascanu, M. Lai, D. J. Rezende et al., &quot;Interaction networks for learning about objects, relations and physics,&quot; in NIPS 2016, 2016, pp. 4502\u20134510.<br \/>  [5] \u2014 A. Fout, J. Byrd, B. Shariat, and A. Ben-Hur, &quot;Protein interface prediction using graph convolutional networks,&quot; in NIPS 2017, 2017, pp. 6530\u20136539.<br \/>  [6] \u2014 T. Hamaguchi, H. Oiwa, M. Shimbo, and Y. Matsumoto, &quot;Knowledge transfer for out-of-knowledge-base entities: A graph neural network approach,&quot; in IJCAI 2017, 2017, pp. 1802\u20131808.<br \/>  [7] \u2014 H. Dai, E. B. Khalil, Y. Zhang, B. Dilkina, and L. Song, &quot;Learning combinatorial optimization algorithms over graphs,&quot; arXiv preprint arXiv:1704.01665, 2017.<br \/>  [8] \u2014 X. Liang, X. Shen, J. Feng, F. Lin, S. Yan, &quot;Semantic Object Parsing with Graph LSTM&quot;, arXiv:1603.07063v1 [cs.CV] 23 Mar 2016.<br \/>  [9] \u2014 Z. Wu, S. Pan, F. Chen, G. Long, C. Zhang, Philip S. Yu, &quot;A Comprehensive Survey on Graph Neural Networks&quot;, arXiv:1901.00596v4 [cs.LG] 4 Dec 2019.<br \/>  [10] \u2014 P. Veli\u010dkovi\u0107, G. Cucurull, A. Casanova, A. Romero, P. Li\u00f2, Y. Bengio, &quot;Graph Attention Networks&quot;, arXiv:1710.10903v3 [stat.ML] 4 Feb 2018.<\/p>\n<p>  <\/p>\n<h1 id=\"ispolzovannaya-literatura\">\u0418\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u043d\u0430\u044f \u043b\u0438\u0442\u0435\u0440\u0430\u0442\u0443\u0440\u0430<\/h1>\n<p>  <\/p>\n<p><a href=\"https:\/\/arxiv.org\/pdf\/1812.08434.pdf\">Graph Neural Networks: A Review of Methods and Applications<\/a><br \/>  <a href=\"https:\/\/www-cs.stanford.edu\/people\/jure\/pubs\/graphrepresentation-ieee17.pdf\">Representation Learning on Graphs: Methods and Applications<\/a><\/p>\n<p><cut\/><\/div>\n<p> \u0441\u0441\u044b\u043b\u043a\u0430 \u043d\u0430 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b \u0441\u0442\u0430\u0442\u044c\u0438 <a href=\"https:\/\/habr.com\/ru\/post\/487138\/\"> https:\/\/habr.com\/ru\/post\/487138\/<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"\n<div class=\"post__text post__text-html\" id=\"post-content-body\" data-io-article-url=\"https:\/\/habr.com\/ru\/post\/487138\/\">\n<p>\u0421\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u0434\u0430\u043d\u043d\u044b\u0445 \u0434\u043b\u044f \u0433\u043b\u0443\u0431\u043e\u043a\u043e\u0433\u043e \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044f \u0440\u0430\u0441\u0442\u0435\u0442 \u0441 \u043a\u0430\u0436\u0434\u044b\u043c \u0434\u043d\u0435\u043c. \u041d\u0435\u0439\u0440\u043e\u043d\u043d\u044b\u0435 \u0441\u0435\u0442\u0438 \u043d\u0430 \u043e\u0441\u043d\u043e\u0432\u0435 \u0434\u0430\u043d\u043d\u044b\u0445 \u0432 \u0432\u0438\u0434\u0435 \u0433\u0440\u0430\u0444\u0430 (Graph Neural Network, <strong>GNN<\/strong>) \u0441\u0442\u0430\u043b\u0438 \u043e\u0434\u043d\u0438\u043c \u0438\u0437 \u043f\u0440\u043e\u0440\u044b\u0432\u043e\u0432 \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0438\u0445 \u043b\u0435\u0442. \u041d\u043e \u043f\u043e\u0447\u0435\u043c\u0443 \u0438\u043c\u0435\u043d\u043d\u043e \u0433\u0440\u0430\u0444\u044b \u043d\u0430\u0431\u0438\u0440\u0430\u044e\u0442 \u0432\u0441\u0435 \u0431\u043e\u043b\u044c\u0448\u0443\u044e \u043f\u043e\u043f\u0443\u043b\u044f\u0440\u043d\u043e\u0441\u0442\u044c \u0432 \u043c\u0430\u0448\u0438\u043d\u043d\u043e\u043c \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u0438?<\/p>\n<p>  <\/p>\n<p>\u041a\u043e\u043d\u0435\u0447\u043d\u043e\u0439 \u0446\u0435\u043b\u044c\u044e \u043c\u043e\u0435\u0433\u043e \u043f\u043e\u0432\u0435\u0441\u0442\u0432\u043e\u0432\u0430\u043d\u0438\u044f \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043e\u0431\u0449\u0435\u0435 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u0435 \u0433\u0440\u0430\u0444\u043e\u0432 \u0432 \u043f\u0440\u0438\u0435\u043c\u0430\u0445 \u043c\u0430\u0448\u0438\u043d\u043d\u043e\u0433\u043e \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044f. \u0421\u0442\u0430\u0442\u044c\u044f <strong>\u043d\u0435<\/strong> \u043f\u0440\u0435\u0442\u0435\u043d\u0434\u0443\u0435\u0442 \u043d\u0430 \u043d\u0430\u0443\u0447\u043d\u0443\u044e \u0440\u0430\u0431\u043e\u0442\u0443, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u0432 \u043f\u043e\u043b\u043d\u043e\u0439 \u043c\u0435\u0440\u0435 \u043e\u043f\u0438\u0441\u044b\u0432\u0430\u0435\u0442 \u0432\u0441\u044e \u043c\u043e\u0449\u044c \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u0433\u0440\u0430\u0444\u043e\u0432, \u0430 \u043b\u0438\u0448\u044c \u0437\u043d\u0430\u043a\u043e\u043c\u0438\u0442 \u0447\u0438\u0442\u0430\u0442\u0435\u043b\u044f \u0441 \u044d\u0442\u0438\u043c \u0443\u0434\u0438\u0432\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u043c \u0438 \u0441\u043b\u043e\u0436\u043d\u044b\u043c \u043c\u0438\u0440\u043e\u043c. \u041f\u0443\u0431\u043b\u0438\u043a\u0430\u0446\u0438\u044f \u043e\u0442\u043b\u0438\u0447\u043d\u043e \u043f\u043e\u0434\u043e\u0439\u0434\u0435\u0442, \u043a\u0430\u043a \u0434\u043b\u044f \u0437\u0430\u043a\u0430\u043b\u0435\u043d\u043d\u044b\u0445 \u0432 \u0431\u043e\u044f\u0445 \u043f\u0440\u043e\u0444\u0435\u0441\u0441\u0438\u043e\u043d\u0430\u043b\u043e\u0432, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0435\u0449\u0435 \u043d\u0435 \u0437\u043d\u0430\u043a\u043e\u043c\u044b \u0441 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u0435\u043c \u0433\u0440\u0430\u0444\u043e\u0432 \u0432 \u0433\u043b\u0443\u0431\u043e\u043a\u043e\u043c \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u0438, \u0442\u0430\u043a \u0438 \u0434\u043b\u044f \u043d\u043e\u0432\u0438\u0447\u043a\u043e\u0432 \u0432 \u044d\u0442\u043e\u0439 \u0441\u0444\u0435\u0440\u0435.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[],"tags":[],"class_list":["post-298242","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/298242","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=298242"}],"version-history":[{"count":0,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/298242\/revisions"}],"wp:attachment":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=298242"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=298242"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=298242"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}