Мера "сложности" графа

[denny]

Согласно некоторым современным теориям сознания, важную роль в них играет
т.н. степень интеграции элементов. Обозначив её $\mathcal{I}$,
отметим два важнейших свойства:

• Если граф представляет собой только вершины без связей (рёбер), то $\mathcal{I}\equiv 0$
• Но и для любого полного графа $\mathcal{I}\equiv 0$. Т.е. "всё связано со всем" - это тоже слишком примитивно.
  

Очевидно, $\mathcal{I}$ возрастает при наличии кластеризации, когда группы элементов более связны,
чем "пространство" между ними (но и последнее не должно быть пустым).

Существует ли подобная мера в строгой теории графов?

(Оффтоп)

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

[Sonic86]

Ну елы-палы, мало того, что пытаетесь формализовывать какое-то суперсложное понятие, так еще и пытаетесь его найти в недрах Mathematica

А у объединения нескольких полных графов какая мера сложности?

[denny]

Если следовать определению объединения, то $0$. Ведь всё равно "слишком однородно".
Мера кластеризации - разве суперсложное понятие? Хотелось бы хот какую-то формализацию увидеть, не обязательно на Mathematica.

[Aritaborian]

(Графы в Mathematica)

denny в сообщении #1131341 писал(а):

Буду очень благодарен за ответ на основе пакета исследования графов из Mathematica.

Что за пакет такой? В современных версиях графы встроены в ядро.

[denny]

(Оффтоп)

Да. По старинке, назвал "пакетом" все функции, связанные с графами.

[arseniiv]

denny в сообщении #1131368 писал(а):

Мера кластеризации - разве суперсложное понятие?

Пока это даже не понятие. У понятия должно быть определение.

[Mihaylo]

Так и понятия "современные теории сознания" тоже нет. Существует колмогоровская сложность и теория, связанная с ней. Вот эту теорию учите, она даст ответы.

[Sender]

denny в сообщении #1131368 писал(а):

Хотелось бы хот какую-то формализацию увидеть, не обязательно на Mathematica.

Вот тут, например, мера вычислительной сложности графа определяется как количество элементарных операций (объединений и пересечений), необходимых для получения графа из элементарных графов, таких как звёзды или клики.

[Mihaylo]

(Энтропия как сложность)

Еще можно рассмотреть сложность с помощью оценки энтропии. Правда этот подход даст немного не то, что желаете получить Вы, так как энтропия - это все-таки не мера сложности, но все же некоторая корреляция имеется.
Например, если известно, что граф представляет собой произвольный граф из $n$ вершин, тогда энтропия составит
$H = \log[K(n)]$, где
$K(n)$ - количество всех возможных графов с $n$ вершинами.

При этом (что плохо) любой граф из $n$ вершин будет обладать одинаковой энтропией. Хоть полный, хоть граф без дуг, хоть некоторый сложный. Дело в том, что энтропия - это характеристика того неопределенного графа из $n$ вершин, а не какого-то конкретного.

[arseniiv]

(Энтропия как что-то недописанное)

Такая энтропия получится, если принять все такие графы равновероятными. Но не обязательно так делать, так же как не обязательно считать, что мы выбираем граф из множества графов с одинаковым числом вершин. Можно брать его из другого множества.

[Brukvalub]

Создается ощущение, что лемма Семереди о регулярности ставит под сомнение наличие требуемой меры для графа.

[Mihaylo]

denny в сообщении #1131368 писал(а):

Если следовать определению объединения, то $0$. Ведь всё равно "слишком однородно".

Я бы не сказал. А попробуйте объединить два полных графа с четырьмя и тремя вершинами. С точки зрения схемотехники, значительное усложнение. Должен быть какой-то критерий. Вот, например, колмогоровская сложность предполагает определение чего-то вроде элементарных графов (генераторов) и их элементарных преобразований. В зависимости от того, какой будет базис элементарных объектов ("способ описания" в терминологии колмогоровской теории сложности), такова будет сложность.
Несомненно нужно плясать от способа описания, который будет включать примерно следующее описание "граф из 10 вершин, полный". То есть способ описания должен содержать понятие полного графа, тогда такой граф будет обладать небольшой сложностью.

[denny]

Sender в сообщении #1131554 писал(а):

denny в сообщении #1131368 писал(а):

Хотелось бы хот какую-то формализацию увидеть, не обязательно на Mathematica.

Вот тут, например, мера вычислительной сложности графа определяется как количество элементарных операций (объединений и пересечений), необходимых для получения графа из элементарных графов, таких как звёзды или клики.

Идеология этой статьи очень близко к тому, что я имел в виду. Но надо еще поразбираться.

-- 15.06.2016, 09:07 --

Mihaylo в сообщении #1131668 писал(а):

denny в сообщении #1131368 писал(а):

Если следовать определению объединения, то $0$. Ведь всё равно "слишком однородно".

Я бы не сказал. А попробуйте объединить два полных графа с четырьмя и тремя вершинами. С точки зрения схемотехники, значительное усложнение. Должен быть какой-то критерий. Вот, например, колмогоровская сложность предполагает определение чего-то вроде элементарных графов (генераторов) и их элементарных преобразований. В зависимости от того, какой будет базис элементарных объектов ("способ описания" в терминологии колмогоровской теории сложности), такова будет сложность.
Несомненно нужно плясать от способа описания, который будет включать примерно следующее описание "граф из 10 вершин, полный". То есть способ описания должен содержать понятие полного графа, тогда такой граф будет обладать небольшой сложностью.

Мне кажется, мы о разном говорим! Объединение по стандартному определению никак не может увеличить ту сложность, которую я пытаюсь сформулировать.
Но в той же статье упоминается функция GraphUnion Mathematica. Там объединение происходит по-другому, и конечно, увеличивает сложность.

-- 15.06.2016, 09:22 --

Вот здесь явно говориться о том, что имею в виду. И даже картинка (стр. 32) такая же, как я представляю:


Оба графа содержат одинаковое количество ребер и вершин. Но второй обладает гораздо большей структуризацией. Можно еще представить, что внутри каждого кластера также имеется подобная структура и т.д.

Но всю статью пока не осилил.