Теория графов в социальных сетях: Метрики центральности и кластеризация

Ключевым понятием в анализе социальных графов является Центральность (Centrality). Она отвечает на вопрос "кто самый важный в сети?". Существует несколько различных математических метрик важности, в зависимости от контекста задачи:

• Степеневая центральность (Degree Centrality): самая простая метрика, равная количеству связей (ребер) у узла. Человек с наибольшим числом друзей является локальным лидером, но его влияние может не распространяться далеко.
• Центральность по близости (Closeness Centrality): вычисляется как величина, обратная сумме кратчайших путей от данного узла до всех остальных узлов в сети. Человек с высокой центральностью по близости может быстро распространить слух по всей сети, так как он находится "в центре" графа.
• Центральность по посредничеству (Betweenness Centrality): это доля всех кратчайших путей в графе, которые проходят через данный узел. Люди с высоким посредничеством (брокеры) играют критическую роль: они соединяют разные изолированные кластеры (например, связывают отдел IT и отдел продаж). Если удалить этот узел, сеть может распасться на куски.

Еще один важный параметр — Коэффициент кластеризации. Он показывает, насколько друзья конкретного человека склонны быть друзьями между собой (образуя "треугольники"). В реальных социальных сетях этот коэффициент всегда аномально высок, что отличает их от чисто случайных математических графов. Свойство высокой кластеризации в сочетании с небольшим средним расстоянием между узлами называется эффектом "Тесного мира" (Small-world network) — это математическое обоснование популярной теории "шести рукопожатий".

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