Энтропия графа - Graph entropy

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

Определение

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

{ Displaystyle Н (G) = мин _ {X, Y} I (X; Y)}

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

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

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

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

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

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

Пример

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

Доказательство Из-за монотонности ни один двудольный граф не может иметь энтропию выше, чем энтропия полного двудольного графа, которая ограничена ${ displaystyle 1}$ . Таким образом, по субаддитивности объединение ${ displaystyle k}$ двудольные графы не могут иметь энтропию больше, чем ${ displaystyle k}$ . Теперь позвольте ${ Displaystyle G = (V, E)}$ быть полным графом на ${ displaystyle n}$ вершины. По перечисленным выше свойствам ${ Displaystyle Н (G) = журнал _ {2} п}$ . Следовательно, объединение менее чем ${ Displaystyle журнал _ {2} п}$ двудольные графы не могут иметь ту же энтропию, что и ${ displaystyle G}$ , так ${ displaystyle G}$ не может быть выражено как такой союз. ${ displaystyle 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.
^ Г. Симони, "Совершенные графы и энтропия графов. Обновленный обзор," Совершенные графы, Джон Вили и сыновья (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] Г. Симони, "Совершенные графы и энтропия графов. Обновленный обзор," Совершенные графы, Джон Вили и сыновья (2001), стр. 293-328, определение 2 "

[1]

[2]

[3]

[4]

[5]