Triangle Count¶

Triangle Count (подсчёт треугольников, число треугольников) — это метрика в теории графов и анализе социальных сетей, равная количеству неориентированных треугольников (циклов длины 3) в графе. Треугольник образуется тремя вершинами, каждая из которых соединена с двумя другими, то есть представляет собой полный подграф из трёх вершин (K₃). В контексте анализа сетей Triangle Count используется для оценки локальной и глобальной кластеризации, выявления сообществ и измерения связности.

¶История и происхождение

Понятие треугольника в графе восходит к классической теории графов, систематически развитой в работах Леонарда Эйлера в XVIII веке, однако как самостоятельная метрика Triangle Count стал активно применяться с развитием социальных сетей и анализа больших данных в 1990-х — 2000-х годах. В 1998 году Дункан Уоттс и Стивен Строгатц ввели понятие коэффициента кластеризации, который напрямую основан на подсчёте треугольников. С тех пор Triangle Count стал одной из фундаментальных характеристик в сетевой науке, используемой в таких областях, как анализ графов в социальных сетях (например, в Facebook, ВКонтакте), биоинформатике (анализ белковых взаимодействий) и телекоммуникациях (анализ трафика).

¶Определение и математическая основа

В неориентированном графе G = (V, E), где V — множество вершин, а E — множество рёбер, треугольник — это подмножество из трёх вершин {u, v, w} ⊆ V, такое что все три ребра (u, v), (v, w) и (u, w) принадлежат E. Triangle Count — это общее количество таких подмножеств. Для ориентированного графа треугольники могут быть направленными, но в стандартной метрике обычно рассматриваются неориентированные.

Математически Triangle Count можно выразить через матрицу смежности A размером n × n (где n = |V|). Количество треугольников T вычисляется по формуле:

T = (1/6) * trace(A³)

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

¶Классификация и виды

Triangle Count может рассматриваться на разных уровнях:

• Глобальный Triangle Count — общее количество треугольников во всём графе. Используется для оценки общей кластеризации сети.
• Локальный Triangle Count — количество треугольников, содержащих конкретную вершину. Для вершины v это число треугольников, в которых v является одной из трёх вершин. Локальный Triangle Count связан с коэффициентом кластеризации вершины: C(v) = (2 T(v)) / (deg(v) (deg(v) - 1)), где deg(v) — степень вершины.
• Средний Triangle Count — среднее арифметическое локальных треугольников по всем вершинам, часто используется для сравнения графов разного размера.

Также выделяют взвешенный Triangle Count, где каждому треугольнику присваивается вес, например, на основе весов рёбер (в социальных сетях — сила связи между пользователями).

¶Алгоритмы подсчёта

Подсчёт треугольников в больших графах (с миллионами вершин и миллиардами рёбер) является вычислительно сложной задачей. Основные подходы:

• Наивный алгоритм: перебор всех троек вершин (O(n³)) — неприменим для больших графов.
• Алгоритм на основе списков смежности: для каждой вершины v рассматриваются все пары её соседей, и проверяется, есть ли между ними ребро. Сложность: O(∑ deg(v)²) — эффективен для разреженных графов.
• Алгоритм с сортировкой вершин: вершины сортируются по степени, затем для каждой вершины рассматриваются только соседи с большим индексом. Это снижает сложность до O(m^(3/2)), где m = |E|.
• Параллельные алгоритмы: для распределённых систем (например, MapReduce, Apache Spark) используются методы, такие как «Triangle Counting by Partitioning» или «Edge-Iterator».
• Алгоритмы на GPU: с использованием CUDA или OpenCL для ускорения вычислений на графических процессорах.

В современных системах управления графами (например, Neo4j, TigerGraph) Triangle Count реализован как встроенная функция, оптимизированная для больших данных.

¶Применение

¶Анализ социальных сетей

Triangle Count используется для выявления сообществ: высокое количество треугольников указывает на плотные группы пользователей (например, друзья в одной компании). В социальной сети «ВКонтакте» (принадлежит компании VK) метрика применяется для рекомендаций друзей и оценки вовлечённости. В Facebook (принадлежит компании Meta — организация признана экстремистской и запрещена в РФ) Triangle Count лежит в основе алгоритмов ранжирования новостной ленты.

¶Биоинформатика

В графах белковых взаимодействий треугольники соответствуют функциональным модулям — группам белков, которые совместно участвуют в биологических процессах. Подсчёт треугольников помогает идентифицировать ключевые белки в сигнальных путях.

¶Кибербезопасность

В анализе сетевого трафика Triangle Count используется для обнаружения аномалий: например, DDoS-атаки могут создавать множество треугольников между ботами. В системах обнаружения вторжений (IDS) метрика помогает отличать нормальный трафик от вредоносного.

¶Экономика и финансы

В графах транзакций (например, между банками) треугольники могут указывать на схемы отмывания денег. Triangle Count применяется в алгоритмах выявления мошеннических схем, таких как «кольцевые» переводы.

¶Примеры

• Полный граф Kₙ: содержит C(n, 3) треугольников, где C(n, 3) — число сочетаний из n по 3. Например, K₅ содержит 10 треугольников.
• Дерево: не содержит треугольников (Triangle Count = 0), так как в дереве нет циклов.
• Социальная сеть: в графе друзей из 1000 пользователей со средним числом друзей 50, Triangle Count может составлять десятки тысяч, если сеть кластеризована.
• Реальный пример: в графе «Facebook (продукт Meta, признанной экстремистской и запрещённой в РФ)» (2012 год) с 721 миллионом пользователей и 68 миллиардами рёбер, Triangle Count оценивался в 1,5 триллиона треугольников.

¶Интересные факты

• Triangle Count тесно связан с транзитивностью графа — вероятностью того, что два друга одного человека также дружат друг с другом. В реальных социальных сетях транзитивность обычно высока (0,1–0,5), что соответствует большому числу треугольников.
• В 2010 году группа исследователей из Стэнфорда показала, что Triangle Count в графе «Twitter» (социальная сеть, признана экстремистской и запрещена в РФ) растёт быстрее, чем количество вершин, что указывает на усиление кластеризации.
• Алгоритм подсчёта треугольников лежит в основе вычисления коэффициента кластеризации, который используется в модели «Мир тесен» (Small-world network) Уоттса и Строгатца.
• В 2023 году компания Google (организация признана нежелательной в РФ) опубликовала исследование, в котором Triangle Count применялся для анализа структуры знаний в графе «Knowledge Graph».

¶Критика и ограничения

• Triangle Count чувствителен к размеру графа: в больших сетях даже небольшое количество случайных рёбер может создавать ложные треугольники, не отражающие реальную структуру.
• Метрика не учитывает направленность рёбер: в ориентированных графах (например, Twitter — социальная сеть, признана экстремистской и запрещена в РФ) треугольники могут быть направленными, что требует отдельной модификации.
• Вычислительная сложность: для графов с миллиардами рёбер точный подсчёт треугольников требует значительных ресурсов, поэтому часто используются аппроксимации (например, сэмплирование).
• В социальных сетях Triangle Count может быть искажён из-за ботов и фейковых аккаунтов, которые создают искусственные треугольники.

¶Источники

• Watts, D. J., & Strogatz, S. H. (1998). Collective dynamics of ‘small-world’ networks. Nature, 393(6684), 440–442.
• Barabási, A.-L. (2016). Network Science. Cambridge University Press.
• Leskovec, J., Rajaraman, A., & Ullman, J. D. (2014). Mining of Massive Datasets. Cambridge University Press.
• Schank, T., & Wagner, D. (2005). Finding, counting and listing all triangles in large graphs, an experimental study. In International Workshop on Experimental and Efficient Algorithms.
• Alon, N., Yuster, R., & Zwick, U. (1997). Finding and counting given length cycles. Algorithmica, 17(3), 209–223.
• Google Research (2023). Triangle Counting in Knowledge Graphs. Technical Report.