Skip to content
Назад к результатам поиска

Центральность по близости

Автор метода
Bavelas, A.; formalized by Freeman, L. C.
Год
1950 (formalized 1979)
Тип
Node-level centrality index
Семейство
Network science

Этот текст переведён машинным способом и ещё не проверен. Читать оригинал на английском

Размер шрифта

Что он делает?

Центральность по близости (Closeness centrality) измеряет, насколько быстро узел может достичь всех остальных узлов в сети, вычисляя величину, обратную среднему кратчайшему расстоянию до каждого другого узла.

Впервые описанная Бавеласом (Bavelas, 1950) и формально объединенная Фрименом (Freeman, 1979), она выявляет узлы, которые могут эффективно распространять информацию или ресурсы по всему графу, а не только узлы с большим количеством прямых контактов.

Интуиция метода

Представьте, что вы отправляете сообщение из узла и наблюдаете, как быстро оно достигает каждого уголка сети. Узел с высокой центральностью по близости находится в центре сети связей: ему в среднем требуется меньше «прыжков», чтобы добраться до любого другого узла. Периферийный узел, даже имеющий много соседей, все еще может быть далек от больших частей сети. Центральность по близости отражает эту идею «географии сети»: короткое среднее расстояние означает высокую центральность по близости, а высокая центральность по близости означает эффективное вещание или быстрый доступ к информации, распространяющейся по графу.

История

Алекс Бавелас (Alex Bavelas) ввел концепцию центральности коммуникации, основанную на кратчайших путях, в 1950 году, изучая эффективность решения групповых задач в Массачусетском технологическом институте. Знаковая статья Линтона Фримена (Linton Freeman) 1979 года в журнале Social Networks формализовала центральность по близости наряду со степенью и посредничеством как одну из трех канонических мер центральности на уровне узлов, предоставив единую математическую основу, которая стала фундаментом современного анализа социальных сетей.

Когда применять

Используйте центральность по близости, когда вы хотите определить узлы, которые могут наиболее эффективно распространять информацию, мобилизовать ресурсы или получать доступ к остальной части сети с минимальным количеством посредников — например, для определения оптимальных источников распространения, влиятельных коммуникаторов или транспортных узлов. Она подходит для связных или почти связных графов любого размера. Не используйте ее в качестве основной меры центральности, когда сеть сильно фрагментирована (много несвязных компонентов), потому что «сырые» значения центральности по близости становятся близкими к нулю и бессмысленными; примените нормализацию Вассермана-Фауста или анализируйте компоненты по отдельности. Избегайте путаницы центральности по близости со степенью: узел может иметь много прямых связей, но при этом оставаться периферийным с точки зрения глобального охвата.

Ограничения и замечания

  • Чувствительна к связности графа: в несвязных сетях «сырая» мера становится неинформативной и требует корректировок нормализации.
  • Рассматривает все кратчайшие пути как одинаково важные; не учитывает объем трафика или вероятность того, что конкретный путь действительно используется.
  • Вычислительно затратна на очень больших графах (миллионы узлов), поскольку вычисление кратчайших путей для всех пар плохо масштабируется без алгоритмов аппроксимации.
  • Не различает узел, который близок ко многим слабым связям, и узел, который близок к нескольким сильным, стратегически важным связям.

Условия из источника не заменяют независимую научную проверку или валидацию аналитическим движком.

Сильные стороны

  • Отражает глобальную достижимость, а не только локальную связность, что делает ее идеальной для изучения потоков информации и диффузии.
  • Нормализованная оценка (от 0 до 1) позволяет сравнивать сети разных размеров.
  • Хорошо разработанная теоретическая основа с десятилетиями валидации в социологии, эпидемиологии и информатике.
  • Дополняет центральность по степени и центральность по посредничеству, давая более полную картину ролей узлов.
  • Эффективно вычисляется с помощью BFS (для невзвешенных) или алгоритма Дейкстры (для взвешенных) для большинства эмпирических сетей.

Применение

  • Выявление ключевых информационных брокеров или лидеров мнений в организационных и социальных сетях.
  • Выбор оптимальных начальных узлов для максимизации скорости распространения информации или заболеваний.
  • Ранжирование транзитных станций или дорожных перекрестков по их общей доступности в транспортных сетях.
  • Определение влиятельных белков или генов в биологических сетях взаимодействия.
  • Выявление влиятельных ранних последователей в исследованиях распространения технологий.
  • Приоритизация целей вмешательства в контактных сетях общественного здравоохранения для замедления распространения эпидемии.

Как это работает

Как это работает

1

Представьте сеть как граф, где узлы — это акторы (люди, организации, веб-страницы, гены и т. д.), а ребра кодируют отношения или взаимодействия. Граф может быть неориентированным или ориентированным; ребра могут быть невзвешенными (каждый «прыжок» стоит 1) или взвешенными (стоимость равна весу ребра, интерпретируемому как расстояние или обратная сила).

2

Для каждого узла v вычислите кратчайшее расстояние d(u, v) до каждого другого достижимого узла u, используя поиск в ширину (Breadth-First Search) для невзвешенных графов или алгоритм Дейкстры для взвешенных графов. Для ориентированных графов действительны только пути, следующие направлению ребра, поэтому входящая центральность по близости (in-closeness) и исходящая центральность по близости (out-closeness) могут различаться.

Формула
d(u,v) = \text{shortest path length between nodes } u \text{ and } v
3

Просуммируйте все кратчайшие расстояния от v до каждого другого узла, чтобы получить «отдаленность» (farness) узла v. Малая отдаленность означает, что v в среднем близок к остальной части сети; большая отдаленность указывает на периферийность.

Формула
\text{farness}(v) = \sum_{u \neq v} d(u, v)
4

Возьмите обратную величину среднего кратчайшего расстояния: C(v) = (n-1) / сумма d(u,v). Умножение на (n-1) дает нормализованную оценку в диапазоне (0, 1], что позволяет сравнивать узлы в сетях разного размера. Более высокие значения указывают на более центральное, доступное положение.

Формула
C(v) = \frac{n-1}{\sum_{u \neq v} d(u, v)}
5

В несвязных графах узел не может достичь всех остальных, поэтому «сырая» центральность по близости равна нулю или не определена для недостижимых пар. Нормализация Вассермана-Фауста (Wasserman-Faust) расширяет центральность по близости на несвязные графы, суммируя только по достижимым узлам и масштабируя на долю достижимой части графа, предотвращая ложные околонулевые значения для изолированных компонентов.

Частые ошибки

  • Представление «сырой» центральности по близости в сети с несвязными компонентами без применения нормализации Вассермана-Фауста, что приводит к вводящим в заблуждение околонулевым значениям.
  • Рассмотрение центральности по близости и центральности по степени как взаимозаменяемых — высокая степень не подразумевает высокой центральности по близости, и наоборот.
  • Игнорирование того, являются ли ребра ориентированными: в ориентированных сетях центральность по близости должна вычисляться отдельно для входящих и исходящих направлений.
  • Применение невзвешенной центральности по близости к взвешенной сети, где веса ребер кодируют значимые расстояния, что приводит к потере информации о силе отношений.
  • Сравнение «сырых» (ненормализованных) значений центральности по близости в сетях разных размеров без учета n.

Часто задаваемые вопросы

Чем центральность по близости отличается от центральности по степени?

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

Что делать, если моя сеть имеет несвязные компоненты?

Примените гармоническую нормализацию Вассермана-Фауста (Wasserman-Faust, 1994) или нормализацию, скорректированную по достижимости, которая суммирует только достижимые пары и масштабирует на долю достижимой части сети. В качестве альтернативы, анализируйте самый большой связный компонент отдельно или используйте гармоническую центральность (сумму обратных расстояний), которая естественным образом обрабатывает недостижимые пары, присваивая им нулевой вклад.

Работает ли центральность по близости во взвешенных сетях?

Да. Замените BFS алгоритмом Дейкстры, используя веса ребер в качестве расстояний (или обратные веса силы/сходства, если больший вес означает большую близость). Полученная взвешенная центральность по близости отражает как топологию, так и качество связей.

Как интерпретировать нормализованную оценку центральности по близости?

Оценка, близкая к 1, означает, что узел может достичь каждого другого узла в среднем примерно за один «прыжок» — он находится в центре сети. Оценка, близкая к 0, означает, что узел очень периферичен. Оценки выше примерно 0.6 обычно указывают на действительно центральные позиции в большинстве эмпирических сетей.

Подходит ли центральность по близости для ориентированных сетей?

Да, но вычисляйте ее отдельно для каждого направления. Входящая центральность по близости (in-closeness) измеряет, насколько легко другие могут достичь фокального узла (полезно для изучения престижа или восприимчивости узла), в то время как исходящая центральность по близости (out-closeness) измеряет, насколько легко фокальный узел может достичь других (полезно для изучения способности к вещанию).

Похожие методы

Источники

  1. Freeman, L. C. (1979). Centrality in social networks: Conceptual clarification. Social Networks, 1(3), 215–239.

    Открыть ссылку DOI
    Скопировано.
  2. Bavelas, A. (1950). Communication patterns in task-oriented groups. Journal of the Acoustical Society of America, 22(6), 725–730.

    Открыть ссылку DOI
    Скопировано.