2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки



Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Мера "сложности" графа
Сообщение13.06.2016, 19:33 


20/12/14
42
Согласно некоторым современным теориям сознания, важную роль в них играет
т.н. степень интеграции элементов. Обозначив её $\mathcal{I}$,
отметим два важнейших свойства:
  • Если граф представляет собой только вершины без связей (рёбер), то $\mathcal{I}\equiv 0$
  • Но и для любого полного графа $\mathcal{I}\equiv 0$. Т.е. "всё связано со всем" - это тоже слишком примитивно.
Очевидно, $\mathcal{I}$ возрастает при наличии кластеризации, когда группы элементов более связны,
чем "пространство" между ними (но и последнее не должно быть пустым).

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

(Оффтоп)

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

 Профиль  
                  
 
 Re: Мера "сложности" графа
Сообщение13.06.2016, 21:15 
Заслуженный участник


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

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

 Профиль  
                  
 
 Re: Мера "сложности" графа
Сообщение13.06.2016, 21:30 


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

 Профиль  
                  
 
 Re: Мера "сложности" графа
Сообщение13.06.2016, 21:33 
Аватара пользователя


11/06/12
6689
Минск

(Графы в Mathematica)

denny в сообщении #1131341 писал(а):
Буду очень благодарен за ответ на основе пакета исследования графов из Mathematica.
Что за пакет такой? В современных версиях графы встроены в ядро.

 Профиль  
                  
 
 Re: Мера "сложности" графа
Сообщение13.06.2016, 21:34 


20/12/14
42

(Оффтоп)

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

 Профиль  
                  
 
 Re: Мера "сложности" графа
Сообщение14.06.2016, 01:41 
Заслуженный участник
Аватара пользователя


27/04/09
19125
Уфа
denny в сообщении #1131368 писал(а):
Мера кластеризации - разве суперсложное понятие?
Пока это даже не понятие. У понятия должно быть определение. :wink:

 Профиль  
                  
 
 Re: Мера "сложности" графа
Сообщение14.06.2016, 16:45 


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

 Профиль  
                  
 
 Re: Мера "сложности" графа
Сообщение14.06.2016, 16:55 
Заслуженный участник


14/01/11
1036
denny в сообщении #1131368 писал(а):
Хотелось бы хот какую-то формализацию увидеть, не обязательно на Mathematica.

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

 Профиль  
                  
 
 Re: Мера "сложности" графа
Сообщение14.06.2016, 20:45 


12/07/15
667

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

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

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

 Профиль  
                  
 
 Re: Мера "сложности" графа
Сообщение14.06.2016, 20:49 
Заслуженный участник
Аватара пользователя


27/04/09
19125
Уфа

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

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

 Профиль  
                  
 
 Re: Мера "сложности" графа
Сообщение15.06.2016, 00:39 
Заслуженный участник
Аватара пользователя


01/03/06
12712
Москва
Создается ощущение, что лемма Семереди о регулярности ставит под сомнение наличие требуемой меры для графа.

 Профиль  
                  
 
 Re: Мера "сложности" графа
Сообщение15.06.2016, 05:24 


12/07/15
667
denny в сообщении #1131368 писал(а):
Если следовать определению объединения, то $0$. Ведь всё равно "слишком однородно".

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

 Профиль  
                  
 
 Re: Мера "сложности" графа
Сообщение15.06.2016, 07:46 


20/12/14
42
Sender в сообщении #1131554 писал(а):
denny в сообщении #1131368 писал(а):
Хотелось бы хот какую-то формализацию увидеть, не обязательно на Mathematica.

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

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

-- 15.06.2016, 09:07 --

Mihaylo в сообщении #1131668 писал(а):
denny в сообщении #1131368 писал(а):
Если следовать определению объединения, то $0$. Ведь всё равно "слишком однородно".

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


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

-- 15.06.2016, 09:22 --

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

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

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 13 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: Purus_Idiota


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group