1. На главную
  2. Электронные версии
  3. Доклады Российской академии наук. Математика, информатика, процессы управления
  4. T. 490, № 1, 2020

Доклады Российской академии наук. Математика, информатика, процессы управления, 2020, T. 490, № 1, стр. 71-73

Модулярность некоторых дистанционных графов

М. М. Ипатов 1, М. М. Кошелев 1, *, А. М. Райгородский 1, 2, 3, 4, **

1 Московский государственный университет им. М.В. Ломоносова
Москва, Россия

2 Московский физико-технический институт (национальный исследовательский университет)
Московская обл., Долгопрудный, Россия

3 Кавказский математический центр Адыгейского государственного университета
Майкоп, Республика Адыгея, Россия

4 Институт математики и информатики Бурятского государственного университета
Улан-Удэ, Республика Бурятия, Россия

* E-mail: mkoshelev99@gmail.com
** E-mail: mraigor@yandex.ru

Поступила в редакцию 24.07.2019
После доработки 27.07.2019
Принята к публикации 01.11.2019

Полный текст (PDF)

Аннотация

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

Ключевые слова: дистанционные графы, графы Джонсона, модулярность, кластеризация

В настоящей работе речь пойдет об одной характеристике графа, которая отвечает за выделение сообществ в сложных сетях. Эта характеристика называется модулярностью и определяется следующим образом. Пусть $G = (V,E)$ – граф. Пусть $A \subset V$ и

$e(A) = \left| {{\text{\{ \{ }}x,y{\text{\} }} \in E:x \in A,y \in A{\text{\} }}} \right|.$

Пусть $\mathcal{A} = {\text{\{ }}{{A}_{1}},\; \ldots ,\;{{A}_{k}}{\text{\} }}$ – некоторое разбиение множества вершин V на непересекающиеся части. Положим

$\begin{gathered} q(\mathcal{A}) = \sum\limits_{i = 1}^k {\left( {\frac{{e({{A}_{i}})}}{{\left| E \right|}} - \frac{{\mathop {\left( {\sum\limits_{{v} \in {{A}_{i}}} {{\text{deg}}{v}} } \right)}\nolimits^2 }}{{4{{{\left| E \right|}}^{2}}}}} \right),} \\ q{\text{*}}(G) = \mathop {max}\limits_A q(\mathcal{A}). \\ \end{gathered} $

Величина $q{\text{*}}(G)$ и есть модулярность графа G. Эта величина измеряет разницу между реальной плотностью ребер и той, какую мы ожидали бы получить, если бы вершины графа соединялись между собою случайно. Она является одной из самых популярных метрик качества алгоритмов кластеризации сложных сетей (интернета, социальных и экономических сетей, биологических сетей и др.).

Самые свежие результаты о модулярности многих графов и случайных графов можно найти, например, в статьях [1–5]. В настоящей работе мы изучим еще один очень важный класс графов.

Пусть $n > r > s$. Рассмотрим следующее семейство графов:

$\begin{gathered} G(n,r,s) = (V,E),\quad V = \left( {\begin{array}{*{20}{c}} {[n]} \\ r \end{array}} \right), \\ E = {\text{\{ }}(A,B):\left| {A \cap B} \right| = s{\text{\} }}, \\ \end{gathered} $
т.е. вершины графа – это всевозможные r-элементные подмножества $[n]: = {\text{\{ }}1,\; \ldots ,\;n{\text{\} }}$, а ребрами мы соединяем пары множеств, пересекающихся ровно по s-элементам. Эти графы называются графами Джонсона или дистанционными графами, и они играют важную роль в задачах теории кодирования и теории Рамсея (см. [6]), комбинаторной геометрии (см. [7–11]), теории гиперграфов (см. [12–15]).

Нам удалось получить следующие новые результаты.

Теорема 1. Пусть $r \geqslant 2$, $1 \leqslant s \leqslant [r{\text{/}}2]$. Тогда

$\mathop {\lim \,\sup \,}\limits_{n \to \infty } q{\text{*}}(G(n,r,s)) \leqslant 1 - \frac{{\left( \begin{gathered} [r{\text{/}}2] \\ s \\ \end{gathered} \right)}}{{2\left( \begin{gathered} r \\ s \\ \end{gathered} \right)}}.$

Теорема 2. Пусть $r \geqslant 2$. Тогда

$\mathop {lim\,inf\,}\limits_{n \to \infty } q{\text{*}}(G(n,r,1)) \geqslant \frac{1}{{2r - 1}}\left( {1 + \mathop {\left( {\frac{{r - 1}}{r}} \right)}\nolimits^{2r} } \right).$

Теорема 3. Пусть $r > s \geqslant 1$. Тогда

$\mathop {lim\,inf}\limits_{n \to \infty } \,q{\text{*}}(G(n,r,s)) \geqslant s\mathcal{B}(s,2r - 2s + 1),$
где $\mathcal{B}$ – бета-функция.

Теорема 4. Пусть $w = \left\lceil {\tfrac{n}{2}} \right\rceil + 1$. Тогда при $n \geqslant 5$ выполнено

$\begin{gathered} q{\text{*}}(G(n,2,1)) = \frac{{3w(w - 1)(w - 2) + {{n}^{3}} - {{w}^{3}}}}{{3n(n - 1)(n - 2)}} - \\ - \;\frac{{3{{w}^{2}}{{{(w - 1)}}^{2}} + 4({{n}^{3}} - {{w}^{3}}) + 6({{n}^{2}} - {{w}^{2}})}}{{3{{n}^{2}}{{{(n - 1)}}^{2}}}}. \\ \end{gathered} $

Сделаем несколько замечаний о соотношениях между результатами теорем 1–4. При $r = 2$, s = 1 теорема 2 дает асимптотическую нижнюю оценку величиной $\frac{{17}}{{48}}$. Предел правой части равенства в теореме 4 также равен $\frac{{17}}{{48}}$. Таким образом, нижняя оценка в теореме 2 при $r = 2$ асимптотически по $n$ точна. Более того, она слегка сильнее оценки из теоремы 3, коль скоро s = 1. Действительно, если в теореме 3 получается оценка величиной

$1 \cdot \mathcal{B}(1,2r - 1) = \frac{{(2r - 2)!}}{{(2r - 1)!}} = \frac{1}{{2r - 1}},$
то в теореме 2 эта же величина умножается на строго большую единицы при каждом конкретном r величину

$1 + \mathop {\left( {\frac{{r - 1}}{r}} \right)}\nolimits^{2r} .$

Тем не менее, теорема 3 работает для всех $s$, тогда как теорема 2 верна лишь для s = 1. К сожалению, верхняя оценка из теоремы 1 все еще достаточно далека от нижних оценок из теорем 2 и 3. Например, при том же s = 1 верхняя оценка асимптотически по r равна 3/4, в то время как нижняя оценка ведет себя как $\tfrac{1}{{2r - 1}}$, т.е. с ростом r зазор растет. А скажем, при $r = 2s$ оценка из теоремы 1 экспоненциально стремится к единице с ростом $s$, тогда как оценка из теоремы 3 экспоненциально по s стремится к нулю.

Список литературы

  1. Ostroumova-Prokhorenkova L., Pralat P., Raigorodskii A. Modularity in Several Random Graph Models // Electronic Notes in Discrete Mathematics. 2017. V. 61. P. 947–953.

  2. Ostroumova-Prokhorenkova L., Pralat P., Raigorodskii A. Modularity of Complex Networks Models, Internet Mathematics. http://www.internetmathematicsjournal.com/article/1916-modularity-of-complex-networks-models. https://doi.org/10.24166/im.12.2017.

  3. Исхаков Л., Миронов М., Прохоренкова Л., Камински Б., Пралат П. Кластерный коэффициент в модели пространственного предпочтительного присоединения // ДАН. 2018. Т. 481. № 1. С. 10–14.

  4. Iskhakov L., Kaminski B., Mironov M., Ostroumova-Prokhorenkova L., Pralat P. Clustering Properties of Spatial Preferential Attachment Model. Proceedings of the 15th Workshop on Algorithms and Models for the Web Graph (WAW 2018), Lecture Notes in Computer Science 10836. Springer, 2018. P. 30–43.

  5. Iskhakov L., Kaminski B., Mironov M., Ostroumova-Prokhorenkova L., Pralat P. Local Clustering Coefficient of Spatial Preferential Attachment Model // J. Complex Networks.

  6. Sagdeev A.A., Raigorodskii A.M. On a Frankl–Wilson theorem and its geometric corollaries. Acta Math. Univ. Comenianae, 2019.

  7. Боголюбский Л.И., Райгородский А.М. Замечание о нижних оценках хроматических чисел пространств малой размерности с метриками l1 и l2 // Матем. заметки. 2019. Т. 105. № 2. С. 187–213.

  8. Пушняков Ф.А. О количествах ребер в порожденных подграфах некоторых дистанционных графов // Матем. заметки. 2019. Т. 105. № 4. С. 592–602.

  9. Шишунов Е.Д., Райгородский А.М. О числах независимости некоторых дистанционных графов с вершинами в ${{\{ - 1,0,1\} }^{n}}$ // ДАН. 2019. Т. 485. № 3. С. 269–271.

  10. Просанов Р.И. Контрпримеры к гипотезе Борсука, имеющие большой обхват // Матем. заметки. 2019. Т. 105. № 6. С. 890–898.

  11. Kostina O.A. On Lower Bounds for the Chromatic Number of Spheres // Math. Notes. 2010. V. 105. № 1. P. 16–27.

  12. Frankl P., Kupavskii A. Partition-free families of sets // Proceedings of the London Math. Society. 2019. https://doi.org/10.1112/plms.12236.

  13. Frankl P., Kupavskii A. Families of Sets with No Matching of Sizes 3 and 4 // Europ. J. Combinatorics. 2019. V. 75. P. 123–135.

  14. Shabanov D.A., Krokhmal N.E., Kravtsov D.A. Panchromatic 3-colorings of random hypergraphs // Europ. J. Combinatorics. 2019. V. 78. P. 28–43.

  15. Balogh J., Cherkashin D., Kiselev S. Coloring General Kneser Graphs and Hypergraphs via High-Discrepancy Hypergraphs // Europ. J. Combinatorics. 2019. V. 79C. P. 228–236.

Дополнительные материалы отсутствуют.

Инструменты

следующая статья выпуска предыдущая статья выпуска содержание выпуска

Доклады Российской академии наук. Математика, информатика, процессы управления

Архивы выпусков Информация о журнале Отправить рукопись в журнал