Маленькие повторяющиеся подграфы, встречающиеся чаще, чем в случайной сети. Хорошие признаки для классификации вершин.
Ключевые тезисы
- Коэффициент кластеризации — доля замкнутых треугольников среди возможных.
- Подсчёт мотивов (graphlets) даёт вектор структурных признаков вершины.
- В биологии мотивы соответствуют функциональным блокам регуляторных сетей.
Подробный разбор
2 подтем — раскройте любую, чтобы увидеть объяснение, формулы, примеры и интерактивные графики.
1Треугольники и кластеризация
Простейший и самый полезный мотив.
- параметр SVM: цена нарушения зазора
- число объектов в выборке
- степень вершины — число её связей
Коэффициент кластеризации отвечает на вопрос «дружат ли между собой друзья вершины». В соцсетях он высок, в случайных графах — почти нулевой; резкое отклонение от типичного значения часто указывает на искусственную активность.
2Graphlet-признаки
Вектор структурного описания вершины.
Считаем, в скольких подграфах каждого типа (путь из трёх вершин, треугольник, звезда, квадрат) участвует вершина. Получается вектор фиксированной длины — готовый признак для любой модели.
Подсчёт мотивов размера 4 и выше дорог: используют сэмплирование или ограничиваются треугольниками и путями длины 2–3.
Связанные темы
Машинное обучение на графах · Структура реальных сетей
Centrality97%
Центральности · Графы и сетиМеры важности вершины: по числу связей, по посредничеству, по близости и по влиянию соседей.
Graph Basics85%
Основы графов · Графы и сетиВершины, рёбра, веса и направления. Матрица смежности и список рёбер — два способа хранить одно и то же.
PageRank85%
PageRank · Графы и сетиСтационарное распределение случайного блуждания по графу с телепортацией. Классический алгоритм ранжирования, который до сих пор используется как признак.
Community Detection85%
Поиск сообществ · Графы и сетиРазбиение графа на плотно связанные группы: клиенты одного круга, связанные аккаунты, тематические кластеры документов.
Graph Embeddings85%
Графовые эмбеддинги · Графы и сетиВекторные представления вершин, в которых близость отражает связанность в графе.
Graph Neural Networks85%
Графовые нейросети · Графы и сетиНейросети, работающие прямо на структуре графа: представление вершины обновляется по представлениям соседей.
Message Passing85%
Передача сообщений · Графы и сетиЕдиная схема, к которой сводятся почти все архитектуры GNN: собрать сообщения от соседей, агрегировать, обновить состояние.
Link Prediction85%
Предсказание связей · Графы и сетиЗадача «появится ли ребро между вершинами»: рекомендации друзей и товаров, достройка графов знаний.
Knowledge Graphs85%
Графы знаний · Графы и сетиФакты в виде троек «субъект — предикат — объект». Структурированная память, которую всё чаще подключают к языковым моделям.
Clustering85%
Кластеризация · Обучение без учителяРазбиение объектов на группы похожих без заранее известных меток.
Eigenvector85%
Собственный вектор · Математический справочникНаправление, сохраняющееся при линейном преобразовании с точностью до масштаба.
Scale-free Networks80%
Безмасштабные сети · Графы и сетиСети, в которых распределение степеней вершин подчиняется степенному закону: немного «хабов» и очень много слабо связанных вершин.
Small World80%
Феномен малого мира · Графы и сетиКороткие пути между любыми двумя вершинами при высокой локальной кластеризации.
Power Law80%
Степенное распределение · Теория вероятностей и распределенияПлотность убывает как степень: редкие события встречаются намного чаще, чем предсказывает нормальный закон. Распределения Парето и Ципфа — его классические формы.
Complex Systems80%
Сложные системы · Динамические системы и фракталыСистемы из множества взаимодействующих элементов, где коллективное поведение не сводится к сумме частей.