Случайный веб-граф.
На последней лекции наш лектор решил нас "поразвлекать", расказав простейшую модель формализации интернета. Мне она чем-то очень понравилась, что решил поделиться. В посте присутствует элементарная теория графов.
Итак, формализация интернета. Наипростейшая.
Пусть задан направленный граф с кратными ребрами и кратными кольцами. Вершины графа - сайты, ребра графа - ссылки. Пример, на рисунке:
Граф должен удовлетворять некоторым эмпирическим параметрам.
1)Preferential attachment.
"По идее", новая вершина должна цитировать (ссылаться) какую-либо из старых, с вероятностью, пропорциональной степени данной вершины. Степень вершины - количество входящих в нее ребер.
2)"Мир тесен"
Почти для любых двух сайтв есть цепочка "кликов" длины 5-7, которые их соединяют.
3)Распределение степеней вершин.
Пусть d - степень вершины, d - натуральное, тогда
Р(степень вершины = d)=с/(d^t). Р(степень вершины = d) - вероятность того, что степень выбранной вершины равна d, c и t какие-то конечные константы.
Такая вот модель. По данным из первых рук, сейчас в рунете около 15 миллионов сайтов и 200 миллионов ссылок. Значение t лежит где-то между 2,5 и 3.
Итак, формализация интернета. Наипростейшая.
Пусть задан направленный граф с кратными ребрами и кратными кольцами. Вершины графа - сайты, ребра графа - ссылки. Пример, на рисунке:
Граф должен удовлетворять некоторым эмпирическим параметрам.
1)Preferential attachment.
"По идее", новая вершина должна цитировать (ссылаться) какую-либо из старых, с вероятностью, пропорциональной степени данной вершины. Степень вершины - количество входящих в нее ребер.
2)"Мир тесен"
Почти для любых двух сайтв есть цепочка "кликов" длины 5-7, которые их соединяют.
3)Распределение степеней вершин.
Пусть d - степень вершины, d - натуральное, тогда
Р(степень вершины = d)=с/(d^t). Р(степень вершины = d) - вероятность того, что степень выбранной вершины равна d, c и t какие-то конечные константы.
Такая вот модель. По данным из первых рук, сейчас в рунете около 15 миллионов сайтов и 200 миллионов ссылок. Значение t лежит где-то между 2,5 и 3.