Энтропия графа

В теории информации является энтропия графа мерой скорости передачи информации, достижимой при передаче символов по каналу, в котором определенные пары значений могут быть перепутаны. ^[1] Эта мера, впервые введенная Кёрнером в 1970-х годах, ^[2]^[3] с тех пор также доказал свою полезность и в других областях, включая комбинаторику. ^[4]

Определение

Позволять $G=(V,E)$ быть неориентированным графом . Энтропия графа $G$ , обозначенный $H(G)$ определяется как

H(G)=\min _{X,Y}I(X;Y)

где $X$ выбирается равномерно из $V$ , $Y$ распространяется по независимым наборам G, совместное распределение $X$ и $Y$ таков, что $X\in Y$ с вероятностью единица, и $I(X;Y)$ это информация взаимная $X$ и $Y$ . ^[5]

То есть, если мы позволим ${\mathcal {I}}$ обозначают независимые множества вершин в $G$ , мы хотим найти совместное распределение $X,Y$ на $V\times {\mathcal {I}}$ с наименьшей взаимной информацией, так что (i) предельное распределение первого члена является равномерным и (ii) в выборках из распределения второй член почти наверняка содержит первый член. Взаимная информация $X$ и $Y$ тогда называется энтропией $G$ .

Характеристики

Монотонность. Если $G_{1}$ является подграфом $G_{2}$ на том же наборе вершин, то $H(G_{1})\leq H(G_{2})$ .
Субаддитивность. Учитывая два графика $G_{1}=(V,E_{1})$ и $G_{2}=(V,E_{2})$ на одном и том же множестве вершин объединение графов $G_{1}\cup G_{2}=(V,E_{1}\cup E_{2})$ удовлетворяет $H(G_{1}\cup G_{2})\leq H(G_{1})+H(G_{2})$ .
Среднее арифметическое непересекающихся союзов. Позволять $G_{1},G_{2},\cdots ,G_{k}$ — последовательность графов на непересекающихся множествах вершин, причем $n_{1},n_{2},\cdots ,n_{k}$ вершины соответственно. Затем $H(G_{1}\cup G_{2}\cup \cdots G_{k})={\tfrac {1}{\sum _{i=1}^{k}n_{i}}}\sum _{i=1}^{k}{n_{i}H(G_{i})}$ .

Кроме того, существуют простые формулы для определенных семейств классов графов.

Полные сбалансированные k-дольные графы обладают энтропией. $\log _{2}k$ $\log _{2}k$ . В частности,
- Графы без ребер обладают энтропией $0$ .
- Полные графики на $n$ вершины имеют энтропию $\log _{2}n$ .
- Полные сбалансированные двудольные графы обладают энтропией. $1$ .
Полные двудольные графы с $n$ вершины в одном разделе и $m$ в другом есть энтропия $H\left({\frac {n}{m+n}}\right)$ , где $H$ — двоичная функция энтропии .

Пример

Здесь мы используем свойства энтропии графа, чтобы предоставить простое доказательство того, что полный граф $G$ на $n$ вершины не могут быть выражены как объединение менее чем $\log _{2}n$ двудольные графы.

Доказательство. Ввиду монотонности ни один двудольный граф не может иметь энтропию графа, большую, чем энтропия полного двудольного графа, который ограничен $1$ . Таким образом, в силу субаддитивности объединение $k$ двудольные графы не могут иметь энтропию больше, чем $k$ . Теперь позвольте $G=(V,E)$ быть полным графом на $n$ вершины. По свойствам, перечисленным выше, $H(G)=\log _{2}n$ . Таким образом, объединение менее чем $\log _{2}n$ двудольные графы не могут иметь ту же энтропию, что и $G$ , так $G$ не может быть выражено в виде такого союза. $\blacksquare$

Общие ссылки

Маттиас Демер; Франк Эммерт-Страйб; Цзэнцян Чен; Сюэлян Ли; Юнтан Ши (25 июля 2016 г.). Математические основы и приложения энтропии графов . Уайли. ISBN 978-3-527-69325-2 .

Примечания

^ Маттиас Демер; Аббат Мовшовиц; Франк Эммерт-Штрайб (21 июня 2013 г.). Достижения в области сложности сетей . Джон Уайли и сыновья. стр. 186–. ISBN 978-3-527-67048-2 .
^ Кернер, Янош (1973). «Кодирование источника информации, имеющего неоднозначный алфавит и энтропию графов». 6-я Пражская конференция по теории информации : 411–425.
^ Нильс да Витория Лобо; Такис Каспарис; Майкл Георгиопулос (24 ноября 2008 г.). Структурное, синтаксическое и статистическое распознавание образов: Совместный международный семинар IAPR, SSPR и SPR 2008, Орландо, США, 4-6 декабря 2008 г. Материалы . Springer Science & Business Media. стр. 237–. ISBN 978-3-540-89688-3 .
^ Бернадетт Бушон ; Лоренца Сайтта ; Рональд Р. Ягер (8 июня 1988 г.). Неопределенность и интеллектуальные системы: 2-я Международная конференция по обработке информации и управлению неопределенностью в системах, основанных на знаниях IPMU '88. Урбино, Италия, 4-7 июля 1988 г. Материалы . Springer Science & Business Media. стр. 112–. ISBN 978-3-540-19402-6 .
^ Г. Симони, «Идеальные графы и энтропия графов. Обновленный обзор», Perfect Graphs, John Wiley and Sons (2001), стр. 293-328, Определение 2»

[DehmerMowshowitz2013-1] Маттиас Демер; Аббат Мовшовиц; Франк Эммерт-Штрайб (21 июня 2013 г.). Достижения в области сложности сетей . Джон Уайли и сыновья. стр. 186–. ISBN 978-3-527-67048-2 .

[2] Кернер, Янош (1973). «Кодирование источника информации, имеющего неоднозначный алфавит и энтропию графов». 6-я Пражская конференция по теории информации : 411–425.

[LoboKasparis2008-3] Нильс да Витория Лобо; Такис Каспарис; Майкл Георгиопулос (24 ноября 2008 г.). Структурное, синтаксическое и статистическое распознавание образов: Совместный международный семинар IAPR, SSPR и SPR 2008, Орландо, США, 4-6 декабря 2008 г. Материалы . Springer Science & Business Media. стр. 237–. ISBN 978-3-540-89688-3 .

[BouchonSaitta1988-4] Бернадетт Бушон ; Лоренца Сайтта ; Рональд Р. Ягер (8 июня 1988 г.). Неопределенность и интеллектуальные системы: 2-я Международная конференция по обработке информации и управлению неопределенностью в системах, основанных на знаниях IPMU '88. Урбино, Италия, 4-7 июля 1988 г. Материалы . Springer Science & Business Media. стр. 112–. ISBN 978-3-540-19402-6 .

[5] Г. Симони, «Идеальные графы и энтропия графов. Обновленный обзор», Perfect Graphs, John Wiley and Sons (2001), стр. 293-328, Определение 2»

[1]

[2]

[3]

[4]

[5]