Уже размещал вопрос на подобную тему. Но это не повторение, а совершенно новая идея!
Итак, меня интересует мера сложности графов (или сетей), которая
была бы малой
как для полных графов, так и для сильно разреженных.В свой время столкнулся с гипотезой, что если сети и связаны с мышлением и сознанием, то стоит рассматривать именно такие:
В предыдущем посте мне посоветовали перевести матрицу графа в двоичный формат
и считать разные характеристики - энтропию, степень сжимаемости архиваторами и т.д.
Как-то не пошло это. Никаких явных результатов.
И вот идея другого рода. Очевидно, что у простой (что это точно значит - чуть далее) сети
есть лишь два варианта работы -
цикл и стационарное состояние (которое можно считать циклом 1).
Наблюдения показывают, что при одинаковом количестве узлов и ребер
,
длины циклов у сетей разной "структуры" заметно отличаются.
Более того, как я и предполагал,
наиболее длинные циклы выдают "средние" сети,
когда число связей заметно менее половины максимального
Что значит "простая" сеть? Значения узлов и веса рёбер - только 0 и 1
(но матрица несимметрична, т.е. связи направлены и допустимы 0-циклы):
Самый тонкий вопрос - это
функция перехода, вычисляющая новое состояние
узла-персептрона по его входам.
Очевидно, она должна быть линейной (иначе можно и динамический хаос получить).
Собственно, простейший вариант:
Код:
int result;
switch ( total ) {
case 0:
result = ?
break;
case 1:
result = ?
break;
...
}
Здесь total - арифметическая сумма входов, а вместо ? ставится 0 или 1.
Т.к. входов конечное число, таких конструкций также будет конечное количество.
И наконец, собственно процедура оценки "сложности" данного графа.
Для всех возможных начальных условий (от {0, 0, 0, ...} до {1, 1, 1,...})
и всех типов функций перехода находится длина цикла, на который выходит сеть.
Максимальная длина и будет характеристикой сложности графа. Для небольшого числа вершин не составляет труда найти максимум и по всем возможным графам
данного порядка.
Для "взрослых" графов приходится ограничиваться выборочными исследованиями.
Но уже ясно, что данная характеристика вполне рабочая.
Например, если сеть выдаёт длинные циклы для выборочно взятых сотни-другой начальных условий,
наверняка это подтвердится и для большего количества.
Интересно, есть ли исследования на эту тему?
Например, заинтересовали такие вопросы.
1. Очевидно, максимальная длина цикла формально равна
. Но я никогда не наблюдал подобное.
Реальные длины всегда меньше. Существуют ли теоретические оценки?
2. Тем не менее, для графов с числом вершин несколько сотен длина цикла уже может составлять
десятки тысяч. Любопытно, а что представляет собой собственно цикл как "набор данных"?
Чистый хаос? Возможна ли квазипериодическая структура?
)