Исследование зависимостей и распределений в случайных сетях для смешанных моделей эволюции и при удалении узлов

Автор(ы): Маркович Н.М., Рыжов М.С., Кулик М.Р.

Название статьи: Исследование зависимостей и распределений в случайных сетях для смешанных моделей эволюции и при удалении узлов

Выпуск: 109

Рубрика: Сетевые модели в управлении

Год: 2024

Библиография: Маркович Н.М., Рыжов М.С., Кулик М.Р. Исследование зависимостей и распределений в случайных сетях для смешанных моделей эволюции и при удалении узлов // Управление большими системами. Выпуск 109. М.: ИПУ РАН, 2024. С.89-121. DOI: https://doi.org/10.25728/ubs.2024.109.5

Дата опубликования: 31.05.2024

Ключевые слова: эволюция сети, предпочтительное и кластерное присоединения, смешанное присоединение, число связей узла, число треугольников узла, удаление узла, кластерный коэффициент

Аннотация: Изучается эволюция случайной сети моделями предпочтительного (preferential attachment), кластерного (clustering attachment) и смешанного присоединений для формирования связей вновь присоединенных узлов с существующими узлами. Рассматриваются стратегии удаления узла на каждом шаге эволюции сети: 1) без удаления узлов и связей; 2) удаление наименее влиятельного узла среди наиболее "старых", где в качестве меры влиятельности узла используется его пейджранг; 3) удаление узла с вероятностью, обратно пропорциональной числу его связей. Для этих стратегий удаления моделированием сравниваются зависимости двух характеристик случайных сетей: числа связей узлов и числа их треугольников (т.е. троек связанных узлов, в которые узел вовлечен) и поведение кластерных коэффициентов узлов. Оценивается тяжесть хвоста распределения для числа связей и треугольников. Смешанное кластерно-предпочтительное присоединение предлагается впервые.

Author(s): Markovich N., Ryzhov M., Kulik i.

Article title: Investigation of dependencies and distributions in random networks evolved by mixed models of the evolution and node deletion

Issue: 109

Year: 2024

Keywords: network evolution, preferential and clustering attachment, mixed clustering-preferential attachment, node degree, triangle counts, node deletion, clustering coefficient

Abstract: The evolution of a random network by models of preferential, clustering and mixed attachments to form links between newly appending nodes and existing nodes is studied. Strategies of node deletion at each step of network evolution are considered: 1) without node and edge deletion;~2) deletion the least influential node among the most 'old', where the node's PageRank is used as a measure of the node's influence;~3) deletion a node with a probability inversely proportional to the node degree. For these deletion strategies the dependence of two characteristics of random networks, namely, the node degrees and node triangle counts (that is, the triples of interconnected nodes in which the node is involved), and the behavior of clustering coefficients of nodes are compared by simulation. The heaviness of the distribution tails for the node degrees and the node triangle counts is estimated. The mixed clustering-preferential attachment is proposed here for the first time.

в формате PDF

Просмотров: 149; загрузок: , за месяц: .

Назад