Preview

Труды Института системного программирования РАН

Расширенный поиск

Исследование максимального размера плотного подграфа случайного графа

https://doi.org/10.15514/ISPRAS-2017-29(6)-12

Аннотация

Для описания случайных сетей используется модель случайного графа Эрдёша-Реньи . При исследовании современных случайных сетей часто требуется определить размер максимальной плотной подсети. В настоящей статье приводятся оценки максимального размера c-плотного подграфа, асимптотически почти наверно содержащегося в случайном графе . Было показано, что при , - асимптотически почти наверно c-плотный; получены верхняя и нижняя оценки размера максимального -плотного подграфа, асимптотически почти наверно. содержащегося в ; а при получена оценка сверху на размер максимального с-плотного подграфа асимптотически почти наверно содержащегося в .

Об авторах

Н. Н. Кузюрин
Институт системного программирования им. В.П. Иванникова РАН; Московский физико-технический институт
Россия


Д. О. Лазарев
Московский физико-технический институт
Россия


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

1. P.Erdos and A. Renyi. On Random Graphs. Publicationes Mathematicae (Debrecen), Vol. 6, 1959, pp. 290-297.

2. D.Gibson, R.Kumar and A.Tomkins. Discovering Large Dense Subgraphs in Massive Graphs. Proceedings of the 31st international conference on Very large data bases, 2005, pp. 721-732.

3. Valari E., Kontaki M., Papadopoulos A.N. Discovery of Top-k Dense Subgraphs in Dynamic Graph Collections. In: Ailamaki A., Bowers S. (eds) Scientific and Statistical Database Management. SSDBM 2012, Lecture Notes in Computer Science, vol 7338. Springer, Berlin, Heidelberg, pp 213-230, DOI: 10.1007/978-3-642-31235-9_14.

4. B. Bollobas and P. Erdos. Cliques in Random Graphs. Mathematical Proceedings of the Cambridge Philosophical Society, Volume 80, Issue 3, 1976, pp. 419-427, DOI: 10.1017/S0305004100053056.

5. B. Bollobas. Degree sequences in Random Graphs. Discrete Mathematics, Volume 33, Issue 1, 1981, pp. 1-19, DOI: 10.1016/0012-365X(81)90253-3.


Рецензия

Для цитирования:


Кузюрин Н.Н., Лазарев Д.О. Исследование максимального размера плотного подграфа случайного графа. Труды Института системного программирования РАН. 2017;29(6):213-220. https://doi.org/10.15514/ISPRAS-2017-29(6)-12

For citation:


Kuzyrin N.N., Lazarev D.O. Analysis of size of the largest dense subgraph of random hypergraph. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2017;29(6):213-220. (In Russ.) https://doi.org/10.15514/ISPRAS-2017-29(6)-12



Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 2079-8156 (Print)
ISSN 2220-6426 (Online)