Структуры для случайных графов со структурой
История вопроса
[Вы можете пропустить это и сразу перейти к Определениям.]
Ключевыми особенностями (случайного) графа или сети являются:
распределение степеней $p(d)$ (экспоненциальный, пуассоновский или степенной закон)
средняя степень $\bar{d}$
средний коэффициент кластеризации $\bar{C}$
среднее расстояние $L$ и диаметр $D$
Графы, сгенерированные случайным образом, часто должны демонстрировать свойство маленького мира , т.е.$L\propto \log N$ и $\bar{C}$«не маленький». Существует несколько моделей случайных графов, которые учитывают хотя бы одно из этих условий:
- Модель Ваттса-Строгаца (с основной регулярной кольцевой решеткой)
- Модель Барабаши-Альберта (с предпочтительной насадкой)
- Модель конфигурации (с заданными последовательностями степеней или распределениями)
- Модель Ньюмана (включающая структуру сообщества )
Хотя модели Уоттса-Строгаца и Барабаши-Альберта являются модификациями модели Эрдеша-Реньи , а модель Ньюмана представляет собой конкретное обобщение модели конфигурации, мне интересно, существует ли уже «метамодель», которая пытается включить лучше всех этих моделей. (Справочный запрос.)
Обобщая модели Уоттса-Строгаца и Ньюмана, я хотел бы исследовать случайные графы, которые «интерполируют между рандомизированной структурой, близкой к графам ER, и [некоторым произвольным регулярным графом] » (цитата из Википедии ).
Для этого хотелось бы иметь под рукой множество регулярных графиков, которые могут
систематически символизировать и нумеровать,
легко генерироваться из их символа (т.е. их матриц смежности), и
возможно, имеют выражения в закрытой форме для характеристик маленького мира $L$ и $\bar{C}$
Какие регулярные графики я имею в виду, проще всего объяснить на примере.
Определения
Пусть конфигурация вершины - это граф, представляющий вершину $\nu$ с рядом ближайших соседей $\nu_0,\nu_2,\dots,\nu_{d-1}$ и кратчайший путь (произвольной длины) между каждой парой последовательных соседей $\nu_i, \nu_{i+1}$. Конфигурацию вершины можно обозначить символом$(n_1.n_2.\dots.n_k)^m$ что говорит, что $\nu$ имеет степень $d = m \cdot k$ и окружен $m$-периодическая последовательность $n_i$-лицы соотв. кратчайшие циклы. (Это не что иное, как стандартное определение конфигураций вершин в геометрии на языке теории графов.)
Пример:
Говорят, что вершина имеет заданную конфигурацию вершин. $\Gamma$ когда его окрестность вместе с одним кратчайшим путем между соседями изоморфна $\Gamma$. Говорят, что граф имеет заданную конфигурацию вершин$\Gamma$ когда все его вершины имеют конфигурацию вершин $\Gamma$. Конфигурация вершины называется реализуемой, если существует граф, в котором она есть.
Теперь рассмотрим конечные графы, в которых все вершины имеют одинаковую конфигурацию вершин.
Вопросы
Все конфигурации вершин $\Gamma$реализуемо графами более-менее произвольного размера? Как это доказать или опровергнуть?
Это связано с вопросом, все ли конфигурации вершин (в смысле геометрии), которые не определяют периодическую мозаику сферы (т.е. правильный многогранник), определяют периодическую мозаику евклидовой или гиперболической плоскости.Если есть нереализуемые конфигурации вершин: как мне проверить, реализуема ли данная конфигурация вершин?
Создает ли граф с заданной конфигурацией вершин $\Gamma$ должны быть вершинно-транзитивными?
Поскольку (равное) количество вершин двух вершинно-транзитивных графов с одинаковой конфигурацией вершин не гарантирует, что они изоморфны: какими общими средствами можно определить их «форму», чтобы два одинаково определенных графа были изоморфны? (Пример: см. Ниже.)
Есть ли систематический способ сгенерировать матрицу смежности для данной реализуемой конфигурации вершины и «формы»?
Под «формой» я подразумеваю то, что Долбилин и Шульте называют «соседними комплексами (коронами)» в своей статье «Локальная теорема для монотипных мозаик» .
Примеры
Рассмотрим конфигурацию вершины $(4)^4$ и "форма", определяемая числами $(4, 6)$
При связывании вершин на противоположных сторонах фигуры все вершины имеют одинаковую конфигурацию вершин. $(4)^4$, причем получившийся граф вершинно-транзитивный:
Находим диаметр $D = 5$, коэффициент кластеризации $\bar{C} = 0$, и среднее расстояние $L =\frac{1}{23}(4\times 1 + 7 \times 2 + 7 \times 3 + 4 \times 4 + 1 \times 5) \approx 2.61$ для которого нужно найти закрытое или рекурсивное явное выражение (в зависимости от $(n,m)$) кажется осуществимым.
Для «формы»
с той же конфигурацией вершин и количеством вершин находим $D = 5$ и среднее расстояние $L =\frac{1}{23}(4\times 1 + 6 \times 2 + 6 \times 3 + 5 \times 4 + 2 \times 5) \approx 2.78$
Для «формы»
примерно с таким же количеством вершин находим $D = 4$ и среднее расстояние $L =\frac{1}{24}(4\times 1 + 8 \times 2 + 8 \times 3 + 4 \times 4 ) \approx 2.5$.
Если вам нужен кластерный коэффициент $\bar{C} = 1/2$ вы можете начать с конфигурации вершины $(3.n)^m$, например $(3.4)^2$:
К сожалению, эта конфигурация не подходит, потому что она разбивает не плоскость, а сферу (что дает начало кубооктаэдру ). Итак, вам нужно выбрать$(3.4)^3$по крайней мере. Чтобы нарисовать красивую "форму" некоторого размера, которую можно превратить в конечный граф с конфигурацией вершин$(3.4)^m$, $m > 2$, требует гиперболической геометрии . Как я понимаю, найти матрицу смежности еще сложнее (см. Вопрос 5). Также диаметр$D$ и среднее расстояние $L$ (как закрытые выражения).
Как вариант, можно добавить край к половине $n\cdot m$ $4$-циклы (выбираются случайным образом) $(4)^4$ график - таким образом уменьшая диаметр $D$ и среднее расстояние $L$.
Ответы
Следующая конфигурация вершин имеет обозначения $(3.4.4.4)^1$ и должен предоставить контрпримеры к вопросу 1 (существование графов произвольного размера) и вопросу 3 (транзитивность вершин).
Есть только конечное число графов, реализующих эту конфигурацию, и все они конечны с не более чем 24 вершинами. Ровно два из них являются планарными: граф ребер ромбокубооктаэдра (слева) и граф ребер тесно связанного псевдоромбокубооктаэдра (справа). Только первый из них вершинно-транзитивен.
Все остальные графы могут быть получены из них путем идентификации вершин. Например, идентификация противоположных вершин в левом графе дает «проективный многогранник»:
Я выделил конфигурацию вершин на правом изображении, потому что это неочевидно на этом рисунке.
Думаю, это все графики с такой конфигурацией. Возможно, я ошибаюсь, но таких графов с более чем 24 вершинами точно не существует.
В более общем плане вас может заинтересовать Локальная теорема из
- "Локальная теорема для монотипных мозаик" Долбилина и Шульте
который связан с вопросом, когда определенные локальные ограничения подразумевают глобальную симметрию. Обычно это дает уникальность и транзитивность вершин, но это применимо только в том случае, если топология «односвязна» (так, для мозаики сферы, евклидовой / гиперболической плоскости, но не для тора, как вы видели в своем вопросе, что график не уникален для$(4)^4$).
В начале раздела 3 (ниже теоремы 3.1) утверждается, что конфигурация $(3.5.5.5)^1$может быть реализован как бесконечный граф, но не как вершинно-транзитивный. Я пытался отследить это утверждение, но они относятся только к книге «Плитки и шаблоны», которая содержит буквально тысячи плиток, и мне не удалось найти желаемое.
Наконец, следующая конфигурация $(3.4.5)^1$ вообще не должно быть реализовано:
Чтобы увидеть это, обратите внимание, что граф должен содержать «треугольную грань» (поскольку конфигурация содержит). Каждое из трех краев этого треугольника является общим либо с четырехугольником, либо с пятиугольником. Wlog предполагает, что два ребра используются совместно с четырехугольником. Но эти два ребра имеют общую вершину, поэтому эта вершина не может быть типа$(3.4.5)^1$.
Вообще, отличить реализуемую конфигурацию от нереализуемой бывает довольно сложно. Как показывает практика, странные лица создают проблему, как и в предыдущем примере. Так, например, конфигурация$(\mathbf 5.8.10)^1$ также не может существовать по той же причине, поскольку существует пятиугольная грань, ограничивающая два разных типа граней, и нет типа граней, повторяющегося в вершине.
Поскольку вы упоминаете (в комментариях), что вас больше всего интересует $(3.n)^m$ (при условии $n\ge 3$, $m\ge 2$):
Эта конфигурация всегда существует, уникальна и вершинно-транзитивна (в предположении «односвязной топологии», которую мы можем перевести как «граф плоский»).
Это конечно только для $(3.3)^2$( октаэдр ),$(3.4)^2$( кубооктаэдр ) и$(3.5)^2$( икосододекаэдр ). Вы можете считать его "плоским" для$\smash{(3.3)^3}$( треугольная мозаика ) и$\smash{(3.6)^2}$( тригексагональная мозаика ) и гиперболическая во всех остальных случаях.
Единственность и симметрия по существу являются следствием Локальной теоремы (и связанной с ней теоремы о расширении), упомянутой ранее. Но проще говоря: если вы попытаетесь построить граф с такой конфигурацией вершин и начнете с любой вершины, а затем попытаетесь завершить конфигурацию вершины вокруг любой из других вершин, вы сможете сделать это только уникальным способом. (правда, попробуйте на бумаге). Поскольку вы не делаете выбора ни на одном из шагов (из бесконечного множества), результат будет уникальным.