Об r-диаметрах случайных графов в модели Боллобаша-Риордана
Автор: Остроумова Людмила Александровна
Журнал: Труды Московского физико-технического института @trudy-mipt
Рубрика: Случайные графы
Статья в выпуске: 1 (13) т.4, 2012 года.
Бесплатный доступ
Работа посвящена модели Боллобаша-Риордана случайного веб-графа. Эта модель адекватно описывае- поведение реального веба. Рассмотрено обобще- ние понятия диаметра графа - так назывемый r-диаметр, который опреде- ляется как максимум по всем множествам вершин мощности r от минимума расстояний между парами вершин в данном множестве. Доказана теорема о том, что почти наверное веб-граф на n вершинах имеет r-диаметр Ln n-lnr/lnlnn..
Случайный граф, веб-граф, диаметр
Короткий адрес: https://sciup.org/142186205
IDR: 142186205
Список литературы Об r-диаметрах случайных графов в модели Боллобаша-Риордана
- B. Bollobas B. Random Graphs.-Cambridge Univ. Press, 2001.
- Janson S., Luczak T., Rucinski A. Random graphs.-New York: Wiley, 2000.
- Колчин В.Ф. Случайные графы.-М.: Физматлит, 2002.
- Bollobas B., Riordan O.M. Mathematical results on scale-free random graphs//Handbook of graphs and networks. -Wiley-VCH, Weinheim, 2003.
- Barabasi A.-L., Albert R. Emergence of scaling in random networks//Science. -1999. -V. 286. -P. 509-512.
- Bollobas B., Riordan O.M. The degree sequence of a scale-free random graph process//Random Structures and Algorithms. -2001. -V. 18, N 3. -P. 279-290.
- Bollobas B., Riordan O.M. The diameter of a scale-free random graph//Combinatorica. -2004. -V. 24, N 1. -P. 5-34.
- Харари Ф. Теория графов.-М.: Мир, 1973.
Статья научная
