Проводимость (теория графов)

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

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

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

История

Проводимость была впервые определена Марком Джеррамом и Алистером Синклером в 1988 году, чтобы доказать, что перманент матрицы с элементами из {0,1} имеет схему аппроксимации с полиномиальным временем . В доказательстве Джеррам и Синклер изучали цепь Маркова, которая переключается между идеальными и почти идеальными паросочетаниями в двудольных графах путем добавления или удаления отдельных ребер. Они определили и использовали проводимость, чтобы доказать, что эта цепь Маркова быстро перемешивается . Это означает, что после запуска цепи Маркова за полиномиальное число шагов полученное распределение гарантированно будет близко к стационарному распределению, которое в данном случае является равномерным распределением на множестве всех совершенных и почти идеальных паросочетаний. Эта быстро перемешивающаяся цепь Маркова позволяет за полиномиальное время получить приблизительно однородные случайные выборки из набора всех идеальных паросочетаний в двудольном графе, что, в свою очередь, приводит к схеме аппроксимации за полиномиальное время для вычисления перманента.

Определение

Для неориентированных d -регулярных графов $G$ без весов ребер проводимость $\varphi (G)$ равна константе Чигера $h(G)$ разделить на d , то есть имеем $\varphi (G)=h(G)/d$.

В более общем смысле, пусть $G$ быть ориентированным графом с $n$ вершины, набор вершин $V$, набор кромок $E$и реальные веса $a_{ij}\geq 0$ на каждом краю $ij\in E$. Позволять $S\subseteq V$ быть любым подмножеством вершин. проводимость $\varphi (S)$ разреза ​ $(S,{\bar {S}})$ определяется через $$\varphi (S)={\frac {\displaystyle a(S,{\bar {S}})}{\min(\mathrm {vol} (S),\mathrm {vol} ({\bar {S}}))}}\,,$$где $$a(S,T)=\sum _{i\in S}\sum _{j\in T}a_{ij}\,,$$и так $a(S,{\bar {S}})$ — общий вес всех ребер, пересекающих разрез из $S$ к ${\bar {S}}$ и $$\mathrm {vol} (S)=a(S,V)=\sum _{i\in S}\sum _{j\in V}a_{ij}$$это объем ​ $S$, то есть общий вес всех ребер, начинающихся с $S$. Если $\mathrm {vol} (S)$ равно $0$, затем $a(S,{\bar {S}})$ также равно $0$ и $\varphi (S)$ определяется как $1$.

проводимость ​ $\varphi (G)$ графика $G$ теперь определяется как минимальная проводимость по всем возможным разрезам: $$\varphi (G)=\min _{S\subseteq V}\varphi (S).$$Эквивалентно, проводимость удовлетворяет $$\varphi (G)=\min \left\{{\frac {a(S,{\bar {S}})}{\mathrm {vol} (S)}}\;\colon \;{\mathrm {vol} (S)\leq {\frac {\mathrm {vol} (V)}{2}}}\right\}\,.$$

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

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

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

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

Цепи Маркова

Для эргодической обратимой цепи Маркова с базовым графом G проводимость — это способ измерить, насколько сложно покинуть небольшой набор узлов. Формально проводимость графа определяется как минимум во всех множествах. $S$ потенциала ​ ​ $S$ разделенный эргодическим потоком из $S$. Алистер Синклер показал, что проводимость тесно связана со временем смешивания в эргодических обратимых цепях Маркова. Мы также можем рассматривать проводимость более вероятностно, как вероятность выхода из набора узлов, учитывая, что мы начали с этого набора с самого начала. Это также можно записать как

$\Phi =\min _{S\subseteq V,0<\pi (S)\leq {\frac {1}{2}}}\Phi _{S}=\min _{S\subseteq V,0<\pi (S)\leq {\frac {1}{2}}}{\frac {\sum _{x\in S,y\in {\bar {S}}}\pi (x)P(x,y)}{\pi (S)}},$

где $\pi$ – стационарное распределение цепи. еще называют коэффициентом узкого места G. В некоторой литературе эту величину

Проводимость связана со временем перемешивания цепи Маркова в обратимом случае. Точно, для любой неприводимой обратимой цепи Маркова с вероятностями самопетли $P(y,y)\geq 1/2$ для всех штатов $y$ и исходное состояние $x\in \Omega$,

${\frac {1}{4\Phi }}\leq \tau _{x}(\delta )\leq {\frac {2}{\Phi ^{2}}}{\big (}\ln \pi (x)^{-1}+\ln \delta ^{-1}{\big )}$.

См. также

• Расстояние сопротивления
• Теория перколяции
• Соотношение Кракхардта E/I

Ссылки

• Джеррам, Марк ; Синклер, Алистер (1988). Проводимость и свойство быстрого перемешивания для цепей Маркова: приближение постоянного разрешения . АКМ Пресс. дои : 10.1145/62212.62234 . ISBN  978-0-89791-264-8 .
• Бела, Боллобас (1998). Современная теория графов . ГТМ . Том 184. Springer Verlag . п. 321. ИСБН  0-387-98488-7 .
• Каннан, Рави; Вемпала, Сантош; Ветта, Адриан (2004). «О кластеризациях: хорошо, плохо и призрачно». Журнал АКМ . 51 (3): 497–515. дои : 10.1145/990308.990313 . ISSN   0004-5411 .
• Чанг, Фан РК (1997). Спектральная теория графов . Провиденс (Род-Айленд): Американское математическое соц. ISBN  0-8218-0315-8 .
• Синклер, Алистер (1993). Алгоритмы случайной генерации и подсчета: подход с использованием цепей Маркова . Бостон, Массачусетс: Биркхойзер Бостон. дои : 10.1007/978-1-4612-0323-0 . ISBN  978-1-4612-6707-2 .
• Левин, Дэвид А.; Перес, Юваль (31 октября 2017 г.). Цепи Маркова и времена смешивания : Второе издание . Провиденс, Род-Айленд: Американское математическое общество. ISBN  978-1-4704-2962-1 .
• Чигер, Джефф (1971). «Нижняя граница наименьшего собственного значения лапласиана». Проблемы анализа: симпозиум в честь Саломона Бохнера (PMS-31) . Издательство Принстонского университета. стр. 195–200. дои : 10.1515/9781400869312-013 . ISBN  978-1-4008-6931-2 .
• Диаконис, Перси; Строк, Дэниел (1991). «Геометрические границы собственных значений цепей Маркова» . Анналы прикладной теории вероятности . 1 (1). Институт математической статистики: 36–61. ISSN   1050-5164 . JSTOR   2959624 . Проверено 14 апреля 2024 г.