WikiDer > Проводимость (график)

Сетевая наука
Теория
График Комплексная сеть Заражение Маленький мир Без накипи Структура сообщества Перколяция Эволюция Управляемость Рисование графика Социальный капитал Анализ ссылок Оптимизация Взаимность Закрытие Гомофилия Транзитивность Предпочтительная привязанность Теория баланса Сетевой эффект Влияние общества
Типы сетей
Информационная (вычислительная) Телекоммуникации Транспорт Социальное Научное сотрудничество Биологические Искусственный нейрон Взаимозависимый Семантический Пространственный Зависимость Поток на чипе
Графики
Функции Клика Компонент Резать Цикл Структура данных Край Петля Район Дорожка Вершина Список смежности / матрица Список заболеваемости / матрица Типы Двудольный Полный Режиссер Гипер Мульти Случайный Взвешенный
Метрики Алгоритмы
Центральность Степень Близость Близость PageRank Мотив Кластеризация Распределение степеней Ассортативность Расстояние Модульность Эффективность
Модели
Топология Случайный график Эрдеш – Реньи Барабаши – Альберт Фитнес модель Уоттс-Строгац Экспоненциальный случайный (ERGM) Случайный геометрический (RGG) Гиперболический (HGN) Иерархический Стохастический блок Максимальная энтропия Мягкая конфигурация Тест LFR Динамика Логическая сеть агент на основе Эпидемия/СЭР
Списки Категории
Темы Программного обеспечения Сетевые ученые Категория: Теория сетей Категория: Теория графов
v т е

Неориентированный граф G и несколько примеров разрезов с соответствующими проводимостью

В теория графов то проводимость из график грамм=(V,E) измеряет, насколько "сплочен" график: он контролирует, насколько быстро случайная прогулка на грамм сходится к своему стационарное распределение. Проводимость графика часто называют Постоянная Чигера графа как аналог его двойник в спектральная геометрия.^{[нужна цитата]} С электрические сети тесно связаны с случайные прогулкис давней историей использования термина «проводимость», это альтернативное название помогает избежать возможной путаницы.

Проводимость резать ${displaystyle (S, {ar {S}})}$ в графе определяется как:

${displaystyle varphi (S) = {frac {sum _ {iin S, jin {ar {S}}} a_ {ij}} {min (a (S), a ({ar {S}}))}}}$

где ${displaystyle a_ {ij}}$ записи матрица смежности за грамм, так что

${displaystyle a (S) = sum _ {iin S} sum _ {jin V} a_ {ij}}$

- общее количество (или вес) ребер, инцидентных S. ${displaystyle a (S)}$ также называется объемом множества ${displaystyle Ssubseteq V}$.

Проводимость всего графика - это минимальная проводимость по всем возможным разрезам:

${displaystyle phi (G) = min _ {Ssubseteq V} varphi (S).}$

Эквивалентно проводимость графика определяется следующим образом:

${displaystyle phi (G): = min _ {Ssubseteq V; 0leq a (S) leq a (V) / 2} {frac {sum _ {iin S, jin {ar {S}}} a_ {ij}} { в качестве)}}.,}$

Для d-регулярный график, проводимость равна изопериметрическое число деленное на d.

Обобщения и приложения

В практических приложениях часто учитывают проводимость только над разрезом. Обычное обобщение проводимости - рассмотрение случая весов, присвоенных ребрам: затем веса добавляются; если вес имеет форму сопротивления, то добавляются обратные веса.

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

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

Цепи Маркова

Для эргодический обратимый Цепь Маркова с лежащим в основе график грамм, проводимость - это способ измерить, насколько сложно оставить небольшой набор узлов. Формально проводимость графа определяется как минимум по всем множествам ${displaystyle S}$ из емкость из ${displaystyle S}$ разделенный на эргодический поток снаружи ${displaystyle S}$. Алистер Синклер показали, что проводимость тесно связана с время смешивания в эргодических обратимых цепях Маркова. Мы также можем рассматривать проводимость более вероятным образом, как минимальную вероятность выхода из небольшого набора узлов, учитывая, что мы начали с этого набора с самого начала. Письмо ${displaystyle Phi _ {S}}$ для условной вероятности выхода из набора узлов S, учитывая, что мы были в этом наборе с самого начала, проводимость является минимальной ${displaystyle Phi _ {S}}$ над наборами ${displaystyle S}$ которые имеют общую стационарную вероятность не более 1/2.

Поведение связано с Время перемешивания цепи Маркова в обратимой настройке.

Смотрите также

• Расстояние сопротивления
• Перколяция
• Коэффициент Кракхардта E / I

Рекомендации

• Béla Bollobás (1998). Современная теория графов. GTM. 184. Springer-Verlag. п. 321. ISBN 0-387-98488-7.
• Kannan, R .; Vempala, S .; Ветта, А. (май 2004 г.). «О кластеризации: хорошее, плохое и призрачное» (PDF). J. ACM. 51 (3): 497–515. Дои:10.1145/990308.990313.
• Фань Чанг (1997). Теория спектральных графов. Конспект лекций CBMS. 92. Публикации AMS. п. 212. ISBN 0-8218-0315-8.
• А. Синклер. Алгоритмы случайной генерации и подсчета: подход цепей Маркова. Биркхаузер, Бостон-Базель-Берлин, 1993.
• Д. Левин, Ю. Перес, Э. Л. Вильмер: Марковские цепи и времена перемешивания