Investigation of Triangle Counts in Graphs Evolved by Clustering Attachment

Модель кластерного присоединения (КП), предложенная Багроу и Брокманном (2013 г.), может быть использована как инструмент эволюции ненаправленных случайных сетей. В статье вводится обобщенное определение модели КП. Теоретические результаты получены для новой модели КП, которую можно рассматривать как предел прежней, когда параметр модели αстремится к нулю, а параметр ∈=0. Предметом исследования является количество треугольников связанных узлов в графе на шаге эволюции n– важная характеристика кластеризации сети. Доказано, что количество треугольников стремится к бесконечности с вероятностью единица для предложенной модели эволюции при n→∞, а скорость роста среднего количества треугольников EΔn на шаге эволюции n≥2 выше логарифмической. Компьютерное моделирование использовано длямоделирования последовательностей количества треугольников. Данное моделирование основано на обобщенной модели урн Пойа–Эггенбергера,что предложено впервые.