Аннотация:
В докладе будут обсуждаться модели веб-графов. В основу наиболее известной модели веб-графа положен принцип предпочтительного присоединения: новая вершина с большей вероятностью ссылается на те уже существующие вершины, у которых текущая степень больше. Было показано, что распределение степеней в графах предпочтительного присоединения подчиняется степенному закону. Кроме того, у таких графов маленький диаметр. Такими же свойствами обладают и многие реальные структуры.
Однако было замечено, что некоторые графы, например веб-граф, обладают так называемым свойством устаревания. А именно, очень большая доля ребер соединяет близкие по дате создания страницы. Поэтому возникла идея добавить фактор устаревания в модели предпочтительного присоединения. Когда появляется новая вершина, из нее проводятся ребра в предыдущие вершины. При этом вершины выбираются с вероятностью, пропорциональной их привлекательности. Привлекательность вершины – некоторая функция от «качества» вершины, ее степени и возраста. В докладе пойдет речь о различных функциях привлекательности и о том, какие из них приводят к степенному распределению степеней вершин.
|
