Все выпуски

Доказывается, что произвольная алгебраическая группа алгебраически изоморфна полной группе автоморфизмов некоторого топологического пространства (автобиекций, сохраняющих открытые множества) с нормальным типом отделимости (Т₄ + Т₁). Кроме того, любое непрерывное действие группы на нормальном топологическом пространстве может быть получено как действие полной группы автоморфизмов нормального топологического пространства на его подпространстве.

The famous fact [3, 5] of existence of an exact representation for any finite group in the form of the full automorphism group of a finite graph was generalize in [4]. For an arbitrary group exact representation exists in the form of the full automorphism group of Kolmogorov topological space (weak type of separability T₀). For a finite group a finite space may be chosen, thus allowing to restore a finite graph with the same number of vertices and having the same automorphism group. Such topological spaces and graphs are called topological imprints and graph imprints of a group (T-imprints and G-imprints, respectively). The question of maximum type of separability of a topological space for which T-imprint can be obtained for any group is open. The author proves that the problem can be solved for the class of normal topology (maximal type of separability T₄+T₀). Special finite T-imprint for a symmetric group may be obtained as a discrete topology; for any other group minimal cardinality of normal T-imprint is countable. There is a generic procedure to construct a T-imprint for any group. For a finite group this procedure allows finite space partitioning into subspaces having G-imprint of the original group as their connectivity graphs.

Рассмотрена задача нахождения инвариантной меры неприводимой цепи Маркова с дискретным временем и конечным пространством состояний. Для такой цепи Маркова существует и единственна инвариантная мера, определенная с точностью до умножения на константу. Для каждого состояния эта инвариантная мера получена в виде суммы $n^{n−2}$ неотрицательных слагаемых, где $n$ — число состояний. Каждое слагаемое является произведением $n − 1$ условных вероятностей перехода. В стандартном представлении цепи Маркова ориентированным графом каждому состоянию ставится в соответствие вершина графа, а условной вероятности перехода — ориентированное ребро. В этом представлении каждое слагаемое в рассматриваемом выражении для инвариантной меры некоторого состояния взаимно-однозначно соответствует обратно ориентированному дереву с корнем в вершине, являющейся образом рассматриваемого состояния. Ребра ориентированы по направлению к корню. Дерево включает все вершины — образы состояний. Каждое слагаемое является произведением всех тех и только тех условных вероятностей перехода, образами которых являются ориентированные ребра соответствующего дерева.

A problem of finding of an invariant measure of irreducible discrete-time Markov chain with a finite state space is considered. There is a unique invariant measure for such Markov chain that can be multiplied by an arbitrary constant. A representation of a Markov chain by a directed graph is considered. Each state is represented by a vertex, and each conditional transition probability is represented by a directed edge. It is proved that an invariant measure for each state is a sum of $n^{n−2}$ non-negative summands, where $n$ is a cardinality of state space. Each summand is a product of $n − 1$ conditional transition probabilities and is represented by an opposite directed tree that includes all vertices. The root represents the considered state. The edges are directed to the root. This result leads to methods of analyses and calculation of an invariant measure that is based on a graph theory.

Исследуется отказоустойчивость конечной вычислительной сети с произвольным графом, элементы которой имеют вероятность отказа и вероятность восстановления после отказа. Работа сети происходит по трехэтапным тактам (разрушение-восстановление-функционирование). Предлагается алгоритм наращивания сети в начале каждого такта ее работы. При этом граф увеличенной конфигурации сети формируется путем добавления новых экземпляров исходной сети и соединения их определенным образом с элементами старой конфигурации сети. Доказывается, что при достаточно быстром росте сеть имеет положительную вероятность неограниченной безотказной работы. Параметрическая оценка критической скорости роста сети имеет логарифмический порядок по числу тактов.

Fault-tolerance of a finite computing net with arbitrary graph, containing elements with certain probability of fault and restore, is analyzed. Algorithm for net growth at each work cycle is suggested. It is shown that if the rate of net increase is sufficiently big then the probability of infinity faultless work is positive. Estimated critical net increase rate is logarithmic over the number of work cycles.

С 50-х годов XX века транспортное моделирование крупных мегаполисов стало усиленно развиваться. Появились первые модели равновесного распределения потоков по путям. Наиболее популярной (и использующейся до сих пор) моделью была модель Бэкмана и др. 1955 г. В основу этой модели положены два принципа Вардропа. На современном теоретико-игровом языке можно кратко описать суть модели как поиск равновесия Нэша в популяционной игре загрузки, в которой потери игроков (водителей) рассчитываются исходя из выбранного пути и загрузках на этом пути, при фиксированных корреспонденциях. Загрузки (затраты) на пути рассчитываются как сумма затрат на различных участках дороги (ребрах графа транспортной сети). Затраты на ребре (время проезда по ребру) определяется величиной потока автомобилей на этом ребре. Поток на ребре, в свою очередь, определяется суммой потоков по всем путям, проходящим через заданное ребро. Таким образом, затраты на проезд по пути определяются не только выбором пути, но и тем, какие пути выбрали остальные водители. Таким образом, мы находимся в стандартной теоретико-игровой постановке. Специфика формирования функций затрат позволяет сводить поиск равновесия к решению задачи оптимизации (игра потенциальная). Эта задача оптимизации будет выпуклой, если функции затрат монотонно неубывающие. Собственно, различные предположения о функциях затрат формируют различные модели. Наиболее популярной моделью является модель с функцией затрат BPR. Такие функции используются при расчетах реальных городов повсеместно. Однако в начале XXI века Ю. Е. Нестеровым и А. де Пальмой было показано, что модели типа Бэкмана имеют серьезные недостатки. Эти недостатки можно исправить, используя модель, которую авторы назвали моделью стабильной динамики. Поиск равновесия в такой модели также сводится к задаче оптимизации. Точнее, даже задаче линейного программирования. В 2013 г. А. В. Гасниковым было обнаружено, что модель стабильной ди- намики может быть получена предельным переходом, связанным с поведением функции затрат, из модели Бэкмана. Однако обоснование упомянутого предельного перехода было сделано в нескольких важных (для практики), но все- таки частных случаях. В общем случае вопрос о возможности такого предельного перехода, насколько нам известно, остается открытым. Данная работа закрывает данный зазор. В статье в общем случае приводится обоснование возможности отмеченного предельного перехода (когда функция затрат на проезд по ребру как функция потока по ребру вырождается в функцию, равную постоянным затратам до достижения пропускной способности, и равна плюс бесконечности, при превышении пропускной способности).

Since 1950s the field of city transport modelling has progressed rapidly. The first equilibrium distribution models of traffic flow appeared. The most popular model (which is still being widely used) was the Beckmann model, based on the two Wardrop principles. The core of the model could be briefly described as the search for the Nash equilibrium in a population demand game, in which losses of agents (drivers) are calculated based on the chosen path and demands of this path with correspondences being fixed. The demands (costs) of a path are calculated as the sum of the demands of different path segments (graph edges), that are included in the path. The costs of an edge (edge travel time) are determined by the amount of traffic on this edge (more traffic means larger travel time). The flow on a graph edge is determined by the sum of flows over all paths passing through the given edge. Thus, the cost of traveling along a path is determined not only by the choice of the path, but also by the paths other drivers have chosen. Thus, it is a standard game theory task. The way cost functions are constructed allows us to narrow the search for equilibrium to solving an optimization problem (game is potential in this case). If the cost functions are monotone and non-decreasing, the optimization problem is convex. Actually, different assumptions about the cost functions form different models. The most popular model is based on the BPR cost function. Such functions are massively used in calculations of real cities. However, in the beginning of the XXI century, Yu. E. Nesterov and A. de Palma showed that Beckmann-type models have serious weak points. Those could be fixed using the stable dynamics model, as it was called by the authors. The search for equilibrium here could be also reduced to an optimization problem, moreover, the problem of linear programming. In 2013, A.V.Gasnikov discovered that the stable dynamics model can be obtained by a passage to the limit in the Beckmann model. However, it was made only for several practically important, but still special cases. Generally, the question if this passage to the limit is possible remains open. In this paper, we provide the justification of the possibility of the above-mentioned passage to the limit in the general case, when the cost function for traveling along the edge as a function of the flow along the edge degenerates into a function equal to fixed costs until the capacity is reached and it is equal to plus infinity when the capacity is exceeded.

Несмотря на многочисленные достижения современной науки, до сих пор остается нераскрытой проблема зарождения молниевого разряда в безэлектродном грозовом облаке, максимальная напряженность электрического поля в котором примерно на порядок меньше диэлектрической прочности воздуха. Хотя не вызывает сомнений тот факт, что развитие разряда начинается с появления в облаке положительных стримеров, развитие которых становится возможным при примерно вдвое меньших значениях электрического поля по сравнению с отрицательными, на настоящий момент остается неизученным вопрос о том, каким образом холодные слабопроводящие стримерные системы объединяются в горячий хорошо проводящий лидерный канал, способный к самостоятельному распространению за счет эффективной поляризации в относительно слабом внешнем поле. В данной работе представлена самоорганизующаяся транспортная модель, реализованная на примере формирования фрактального древа электрического разряда в грозовом облаке и направленная на численное моделирование процесса начальной стадии развития молниевого разряда. Среди инновационных особенностей нашего подхода, отсутствующих в других численных моделях развития молнии, можно выделитьот сутствие привязки элементов проводящей структуры графа к узлам пространственной решетки, высокое пространственно-временное разрешение и учет временной эволюции электрических параметров транспортных каналов. Кроме того, модельучи тывает известную из многочисленных экспериментов асимметрию полей развития положительных и отрицательных стримеров. В рамках используемого подхода результирующий хорошо проводящий лидерный канал формируется за счет коллективного эффекта объединения токов десятков тысяч взаимодействующих между собой стримеров, каждый из которых изначально обладает пренебрежимо малой проводимостью и температурой, не отличающейся от температуры окружающей среды. Модельное биполярное древо представляет собой направленный граф (имеет положительную и отрицательную части) и имеет морфологические и электро-динамические характеристики, промежуточные между лабораторной длинной искрой и развитой молнией. Модель имеет универсальный характер, что при необходимости позволяет использовать ее в рамках других задач, связанных с исследованием транспортных (в широком смысле слова) сетей.

Despite numerous achievements of modern science the problem of lightning initiation in an electrodeless thundercloud, the maximum electric field strength inside which is approximately an order of magnitude lower than the dielectric strength of air, remains unsolved. Although there is no doubt that discharge activity begins with the appearance of positive streamers, which can develop under approximately half the threshold electric field as compared to negative ones, it remains unexplored how cold weakly conducting streamer systems unite in a joint hot well-conducting leader channel capable of self-propagation due to effective polarization in a relatively small external field. In this study, we present a self-organizing transport model which is applied to the case of electric discharge tree formation in a thundercloud. So, the model is aimed at numerical simulation of the initial stage of lightning discharge development. Among the innovative features of the model are the absence of grid spacing, high spatiotemporal resolution, and consideration of temporal evolution of electrical parameters of transport channels. The model takes into account the widely known asymmetry between threshold fields needed for positive and negative streamers development. In our model, the resulting well-conducting leader channel forms due to collective effect of combining the currents of tens of thousands of interacting streamer channels each of which initially has negligible conductivity and temperature that does not differ from the ambient one. The model bipolar tree is a directed graph (it has both positive and negative parts). It has morphological and electrodynamic characteristics which are intermediate between laboratory long spark and developed lightning. The model has universal character which allows to use it in other tasks related to the study of transport (in the broad sense of the word) networks.

Задача поиска PageRank вектора представляет большой научный и практический интерес ввиду своей применимости к работе современных поисковых систем. Несмотря на то, что данная задача сводится к поиску собственного вектора стохастической матрицы $P$, потребность в новых алгоритмах для ее решения обусловлена большими размерами входных данных. Для достижения не более чем линейного времени работы применяются различные рандомизированные методы, возвращающие ожидаемый ответ лишь с некоторой достаточно близкой к единице вероятностью. Нами рассматриваются два таких способа, сводящие задачу поиска вектора PageRank к задаче поиска равновесия в антагонистической матричной игре, которая затем решается с помощью алгоритма Григориадиса – Хачияна. При этом данная реализация эффективно работает в предположении о разреженности матрицы, подаваемой на вход. Насколько нам известно, до сих пор не было ни одной успешной реализации ни алгоритма Григориадиса – Хачияна, ни его применения к задаче поиска вектора PageRank. Данная статья ставит перед собой задачу восполнить этот пробел. В работе приводится описание двух версий алгоритма с псевдокодом и некоторые детали их реализации. Кроме того, в работе рассматривается другой вероятностный метод поиска вектора PageRank, а именно Markov chain Monte Carlo (MCMC), с целью сравнения результатов работы указанных алгоритмов на матрицах с различными значениями спектральной щели. Последнее представляет особый интерес, поскольку значение спектральной щели сильно влияет на скорость сходимости MCMC, и не оказывает никакого влияния на два других подхода. Сравнение проводилось на сгенерированных графах двух видов: цепочках и $d$-мерных кубах. Проведенные эксперименты, как и предсказывает теория, демонстрируют эффективность алгоритма Григориадиса – Хачияна по сравнению с MCMC для разреженных графов с маленьким значением спектральной щели. Весь код находится в открытом доступе, так чтобы все желающие могли воспроизвести полученные результаты самостоятельно, или же использовать данную реализацию в своих нуждах. Работа имеет чисто практическую направленность, никаких теоретических результатов авторами получено не было.

Finding PageRank vector is of great scientific and practical interest due to its applicability to modern search engines. Despite the fact that this problem is reduced to finding the eigenvector of the stochastic matrix $P$, the need for new algorithms is justified by a large size of the input data. To achieve no more than linear execution time, various randomized methods have been proposed, returning the expected result only with some probability close enough to one. We will consider two of them by reducing the problem of calculating the PageRank vector to the problem of finding equilibrium in an antagonistic matrix game, which is then solved using the Grigoriadis – Khachiyan algorithm. This implementation works effectively under the assumption of sparsity of the input matrix. As far as we know, there are no successful implementations of neither the Grigoriadis – Khachiyan algorithm nor its application to the task of calculating the PageRank vector. The purpose of this paper is to fill this gap. The article describes an algorithm giving pseudocode and some details of the implementation. In addition, it discusses another randomized method of calculating the PageRank vector, namely, Markov chain Monte Carlo (MCMC), in order to compare the results of these algorithms on matrices with different values of the spectral gap. The latter is of particular interest, since the magnitude of the spectral gap strongly affects the convergence rate of MCMC and does not affect the other two approaches at all. The comparison was carried out on two types of generated graphs: chains and $d$-dimensional cubes. The experiments, as predicted by the theory, demonstrated the effectiveness of the Grigoriadis – Khachiyan algorithm in comparison with MCMC for sparse graphs with a small spectral gap value. The written code is publicly available, so everyone can reproduce the results themselves or use this implementation for their own needs. The work has a purely practical orientation, no theoretical results were obtained.

Предложена имитационная модель коррупционного поведения в иерархических системах, учитывающая индивидуальные стратегии отдельных элементов и позволяющая описывать коллективное поведение достаточно больших групп. Были рассмотрены зависимости различных характеристик системы, таких как уровень коррумпированности и доля коррупционеров в иерархии, от управляющих параметров. Численный анализ позволил исследовать эффективность различных антикоррупционных стратегий.

Simulation model of corruption in hierarchical systems which takes into account individual strategies of elements and collective behavior of large groups is proposed. Evolution of various characteristics like level of corruption or ratio of corrupted elements and their dependence on external parameters are discussed. The effectiveness of various anticorruptional strategies is examined by means of numeric analysis.