О возможной динамике в модели ранжирования web-страниц PageRank и модернизированной модели расчета матрицы корреспонденций
Автор: Гасников Александр Владимирович, Гасникова Евгения Владимировна, Федько Ольга Сергеевна
Журнал: Труды Московского физико-технического института @trudy-mipt
Рубрика: Математика, информатика, управление, экономика
Статья в выпуске: 2 (14) т.4, 2012 года.
Бесплатный доступ
Приводится основной аппарат, необходимый для исследования динамики макроси- стем (систем, описывающих динамику взаимодействия большого числа агентов) при больших значениях времени. В основе динамики лежит эргодическая марковская цепь с огромным числом состояний. При больших значениях времени распределение мак- росистемы по макросостояниям будет близко к стационарному. С ростом размерности макросистемы (количества состояний марковской цепи) стационарное распределение будет концентрироваться в окрестности наиболее вероятного макросостояния, которое и принимается за равновесное для данной макросистемы. В качестве примеров при- менения описанного формализма приводится вывод известного способа ранжирования web-страниц PageRank и вывод модернизированной статической энтропийной модели расчета матрицы корреспонденций исходя из «разумной» (индивидуально выгодной) динамики обменов местами жительства. В конце статьи приводится общая схема ис- следования равновесий макросистем, отличительной особенностью которой является возможность учитывать рост размерности пространства макросостояний системы вме- сте с ростом числа агентов.
Эргодическая теорема, функция ляпунова, энтропия, ранжирование web-страниц pagerank, гравитационная модель расчета матрицы корреспонден- ций, концентрация инвариантной (стационарной) меры, канонический скейлинг, усло- вие динамического равновесия, принцип детального равновесия
Короткий адрес: https://sciup.org/142185816
IDR: 142185816
Список литературы О возможной динамике в модели ранжирования web-страниц PageRank и модернизированной модели расчета матрицы корреспонденций
- Jaynes E. T. Probability theory. The logic of science. -Cambridge: Cambridge University Press, 2003; Papers on probability, statistics and statistical physics. Dordrecht: Kluwer Academic Publisher, 1989.
- Вильсон А. Дж. Энтропийные методы моделирования сложных систем. -М.: Наука, 1978.
- Николис Г., Пригожин И. Самоорганизация в неравновесных системах. -М.: Мир, 1979.
- Хакен Г. Информация и самоорганизация. Макроскопический подход к сложным системам. -М.: УРСС, 2005.
- Шредингер Э. Статистическая термодинамика. -М.: ИЛ, 1948.
- Крылов Н. С.Работы по обоснованию статистической физики. -М.-Л.: Издательство АН СССР, 1950.
- Хинчин А. Я. Математические основания статистической механики. -М.-Ижевск: НИЦ «РХД», ИКИ, 2003.
- Кац М. Вероятность и смежные вопросы в физике. -М.: Мир, 1965.
- Хуанг К. Статистическая механика. -М.: Мир, 1966.
- Рюэль Д. Статистическая механика. Строгие результаты. -М.: Мир, 1971.
- Корнфельд И. П., Синай Я. Г., Фомин С. В. Эргодическая теория. -М.: Наука, 1980.
- Evans L. C. Entropy and partial differential equations. Department of mathematics, UC Berkeley, 2003. http://math.berkeley.edu/˜evans/
- Минлос Р. А. Введение в математическую статистическую физику. -М.: МЦНМО, 2002.
- Козлов В. В. Ансамбли Гиббса и неравновесная статистическая механика. -М.-Ижевск: НИЦ «РХД», ИКИ, 2008.
- Марри Дж. Нелинейные дифференциальные уравнения в биологии. -М.: Мир, 1983.
- Свирежев Ю. М. Нелинейные волны, диссипативные структуры и катастрофы в экологии. -М.: Наука, 1987.
- Гардинер К. В. Стохастические методы в естественных науках. -М.: Мир, 1986.
- Веденяпин В. В. Кинетическая уравнения Больцмана и Власова. -М.: Физматлит, 2001.
- Малышев В. А., Пирогов С. А. Обратимость и необратимость в стохастической химической кинетике//УМН. -2008. -Т. 63, № 1. -С. 3-36.
- Вайдлих В. Социодинамика: системный подход к математическому моделированию в социальных науках. -М.: УРСС, 2010.
- Castellano C., Fortunato S., Loreto V. Statistical physics of social behavior//Review of modern physics. -2009. -V. 81. -P. 591-646. arXiv:0710.3256v2
- Занг В. Б. Синергетическая экономика: время и перемены в нелинейной экономической теории. -М.: Мир, 1999. 23. Drˇ𝑎gulescu A., Yakovenko V. M. Statistical mechanics of money//The European Physical Journal. B. -2000. -V. 17. -P. 723-729. arXiv:cond-mat/0001432v4
- Baldi P., Frasconi P., Smyth P. Modeling the Internet and the Web: Probabilistic methods and algorithms. -Published by John Wiley & Sons, 2003.
- Розоноэр Л. И. Обмен и распределение ресурсов (обобщенный термодинамический подход) I, II, III//Автоматика и телемеханика. -1973, -№ 5, № 6, № 8.
- Горбань А. Н. Обход равновесия. -Новосибирск: Наука, 1984.
- Опойцев В. И. Нелинейная системостатика. -М.: Наука, 1986.
- Малишевский А. В. Качественные модели в теории сложных систем. -М.: Наука, 1998.
- Сергеев В. М. Пределы рациональности. -М.: Фазис, 1999.
- Попков Ю. С. Теория макросистем: равновесные модели. -М.: УРСС, 1999.
- Цирлин А. М. Методы оптимизации в необратимой термодинамике и микроэкономике. -М.: Физматлит, 2003.
- Швецов В. И. Математическое моделирование транспортных потоков//Автоматика и телемеханика. -2003. -№ 11. -С. 3-46.
- Маслов В. П. Квантовая экономика. -М.: Наука, 2006.
- Олемской А. И. Синергетика сложных систем: Феноменология и статистическая теория. -М.: КРАСАНД, 2009.
- Веретенников А. Ю. Параметрическое и непараметрическое оценивание для цепей Маркова. -М.: Изд-во ЦПИ при механико-математическом факультете МГУ, 2000.
- Боровков А. А. Эргодичность и устойчивость случайных процессов. -М.: УРСС, 1999.
- Булинский А. В., Ширяев А. Н. Теория случайных процессов. -М.: Физматлит; Лаборатория базовых знаний, 2003.
- Кельберт М. Я., Сухов Ю. М. Вероятность и статистика в примерах и задачах. -Т. 2. -М.: МЦНМО, 2010.
- Вишневский В. М. Теоретические основы проектирования компьютерных сетей. -М.: Техносфера, 2003.
- Ивницкий В. А. Теория сетей массового обслуживания. -М.: Физматлит, 2004.
- The maximum entropy formalism, ed. by R. D. Levin, M. Tribus//Conf. Mass. Inst. Tech., Cambridge, 1978. MIT Press, 1979.
- International workshops on Bayesian inference and maximum entropy methods in science and engineering. AIP Conf. Proceedings (holds every year from 1980).
- Kapur J. N. Maximum -entropy models in science and engineering. -John Wiley & Sons, Inc., 1989.
- Golan A., Judge G., Miller D. Maximum entropy econometrics: Robust estimation with limited data. Chichester, Wiley, 1996.
- Fang S.-C., Rajasekera J. R., Tsao H.-S. J. Entropy optimization and mathematical programming. -Kluwer's International Series, 1997.
- Маслов В. П., Черный А. С. О минимизации и максимизации энтропии в различных дисциплинах//ТВП. -2003. -Т. 48, № 3. -С. 466-486.
- Гасников А. В., Кленов С. Л., Нурминский Е. А., Холодов Я. А., Шамрай Н. Б. Введение в математическое моделирование транспортных потоков/под ред. А.В. Гасникова с приложениями М.Л. Бланка, Е.В. Гасниковой, А.А. Замятина и В.А. Малышева, А.В. Колесникова, Ю.Е. Нестерова и С.В. Шпирко, А.М. Райгородского. -М.: МЦНМО, 2012. http://zoneos.com/traffic/
- Гасников А. В., Гасникова Е. В. О возможной динамике в модели расчета матрицы корреспонденций (А. Дж. Вильсона)//Труды МФТИ (специальный выпуск, посвященный математическому моделированию транспортных потоков, под ред. акад. В.В. Козлова). -2010. -Т. 2, № 4(8). -С. 45-54.
- Brin S., Page L. The anatomy of a large-scale hypertextual web search engine//Comput. Network ISDN Syst. -1998. -V. 30(1-7). -P. 107-117.
- Langville A. N., Meyer C. D. Google's PageRank and Beyond: The Science of Search Engine Rankings. -Princeton University Press, 2006.
- Назин А. В., Поляк Б. Т. Рандомизированный алгоритм нахождения собственного вектора стохастической матрицы с применением к задаче PageRank//Автоматика и телемеханика. -2011. № 2, -C. 131-141.
- Nesterov Y. E. Subgradient methods for huge-scale optimization problems//CORE Discussion Paper 2012/2, 2012. http://www.uclouvain.be/32349.html
- Tomlin J. A. A new paradigm for ranking pages on the World Wide Web//Proceedings of the WWW2003, CityplaceBudapest, countryregionHungary, pages ACM 1-58113-680-3/03/0005, May 20-24, 2003. http://www2003.org/cdrom/papers/refereed/p042/paper42_html/p42-tomlin.htm; http://www.stanford.edu/group/SOL/software/pdco.html
- Шананин А. А. Математические модели в экономике//Годовой курс лекций для студентов ФУПМ МФТИ, ВМиК МГУ и РУДН http://dame.mipt.ru/video/matmodeli/
- Гасникова Е. В. Двойственные мультипликативные алгоритмы для задач энтропийно-линейного программирования//ЖВМ и МФ. -2009. -Т. 49, № 3. -С. 453-464.
- Кнут Д., Яо Э. Сложность моделирования неравномерных распределений//Кибернетический сборник. Новая серия. Вып. 19. -М.: Мир, 1983. -С. 97-158.
- Ермольев Ю. М. Методы стохастического программирования. -М.: Наука, 1976.
- http://www2.isye.gatech.edu/˜nemirovs/
- http://www.core.ucl.ac.be/˜nesterov/
- Гасникова Е. В. Исследование задач энтропийного программирования: диссертация на соискание звания магистра по специальности 05.13.18. ФУПМ МФТИ, ИСА РАН, 16 июня 2009.
- Stouffer S. A. Intervening opportunities: a theory relating mobility and distance//Amer. Sociolog. Rev. -1940. -V. 5. -P. 845-867.
- Fotheringham A. S. A new set of special-interaction models: the theory of competing destinations//Envir. & Plan. A. -1983. -V. 15. -P. 15-36.
- Fotheringham A. S. Modelling hierarchical destination choice//Envir. & Plan. A. -1986. -V. 18. -P. 401-418.
- Gon.calves M. B., Ulyssea-Neto I. Equilibrium values and dynamics of attractiveness terms in production-constrained spatial-interaction models//Envir. & Plan. -A. 1993. -V. 25. -P. 817-826.
- Стенбринк П. А. Оптимизация транспортных сетей. -М.: Транспорт, 1981.
- Patriksson M. The traffic assignment problem. Models and methods. -Utrecht, Netherlands: VSP, 1994.
- Sheffi Y. Urban transportation networks: Equilibrium analysis with mathematical programming methods. -N.J.: Prentice-Hall Inc., Englewood Cliffs, 1985.
- Bar-Gera H. Origin-based algorithms for transportation network modeling//Report. Univ. of Illinois at Chicago, 1999.
- Швецов В. И. Проблемы моделирования передвижений в транспортных сетях//Труды МФТИ (специальный выпуск, посвященный математическому моделированию транспортных потоков, под ред. акад. В.В. Козлова). -2010. -Т. 2. № 4(8). -С. 169-179.
- Foster D., Young P. Stochastic evolutionary game dynamics//Theoretical population biology. -1990. -V. 38, N 2.
- Cressman R. Evolutionary game theory and extensive form games. -Cambridge, Mass.: MIT Press, 2003.
- Hofbauer J., Sigmund K. Evolutionary game dynamics//Bulletin of the AMS. -2003. -V. 40, N 4. -P. 479-519.
- McKelvey R. D., Palfrey T. R. Quantal response equilibria for extensive form games//Experimental economics. -1998. -V. 1. -P. 9-41.
- Fogel D. B. Evolutionary Computation: Towards a New Philosophy of Machine Intelligence. -New York: IEEE Press, 2000.
- Хачиян Л.Г. Избранные труды/сост. С. П. Тарасов. -М.: МЦНМО, 2009. -С. 38-48.
- Como G., Salva K., Acemoglu D., Dahleh M.A., Frazzoli E. Stability analysis of transportation networks with multiscale driver decisions//e-print arXiv:1101.2220v1, 2011.
- Gasnikova E. V., Nagapetyan T. A. About new dynamical interpretations of entropic model of correspondence matrix calculation and Nash-Wardrop's equilibrium in Beckmann's traffic flow distribution model//Ninth International Conference on Traffic and Granular Flow, 28 September -1 October 2011. -Moscow: Springer, 2012. arXiv:1112.1628v3
- Juditsky A., Lan G., Nemirovski A., Shapiro A. Stochastic approximation approach to stochastic programming//SIAM Journal on Optimization. -2009. -V. 19, N 4. -P. 1574-1609.
- Nesterov Y., de Palma A. Static equilibrium in congested transportation networks//Networks Spatial Econ. -2003. -N 3(3). -P. 371-395.
- Разжевайкин В. Н. Эволюционная оптимальность и построение функционалов отбора в моделях структурированных биосистем//Труды VI Всероссийской научной конференции «Математическое моделирование развивающейся экономики и экологии» (ЭКОМОД-2011), Киров, 27 июня -3 июля 2011. -Киров: Изд-во ВятГУ, 2011. -С. 309-316.
- Malyshev V. A., Pirogov S. A., Rubco A. N. Random walks and chemical networks//Mosc. Math. J. -2004. -V. 4, N 2. -P. 441-453.
- Батищева Я. Г., Веденяпин В. В. II закон термодинамики для химической кинетики//Мат. мод. -2005. -Т. 17, № 8. -С. 106-110.
- Веденяпин В. В., Орлов Ю. Н. О законах сохранения для полиномиальных гамильтонианов и для дискретных моделей уравнения Больцмана//ТМФ. -1999. -Т. 121, № 2. -С. 307-315.
- Montenegro R., Tetali P. Mathematical aspects of mixing times in Markov chains. 2006. http://people.math.gatech.edu/˜tetali/PUBLIS/survey.pdf
- Diaconis P. The Markov chain Monte Carlo revolution//Bulletin (New Series) of the AMS. -2009. -V. 49, N 2. -P. 179-205.
- Joulin A., Ollivier Y. Curvature, concentration and error estimates for Markov chain Monte Carlo//Ann. Prob. -2010. -V. 38, N 6. -P. 2418-2442. http://www.yann-ollivier.org/rech/publs/surveycurvmarkov.pdf
- Sinclair A., Jerrum M. Approximate counting, uniform generation and rapidly mixing Markov chains//Information and Computation. -1989. -V. 82, N 1. -P. 93-133.
- Dyer M., Frieze A., Kannan R. A random polynomial-time algorithm for approximating of the volume of convex bodies//Journal of ACM. -1991. -V. 38, N 1. -P. 1-17.
- Rybko A., Shlosman S. Poisson hypothesis for information networks I, II//e-prints http://arxiv.org/abs/math/0406110v1; http://arxiv.org/abs/math-ph/0410053v1, 2004.
- Рыбко А. Н. Пуассоновская гипотеза для больших симметричных коммуникационных сетей//Глобус. Общематематический семинар/под ред. М. А. Цфасмана и В. В. Прасолова. № 4. -М.: МЦНМО, 2009. -С. 105-126.
- Богданов К. Ю. Прогулки с физикой. Библиотечка «Квант» В. 98. -М.: Бюро Квантум, 2006. Глава 18.
- Лигетт Т. Марковские процессы с локальным взаимодействием. -М.: Мир, 1989.
- Вентцель А. Д., Фрейдлин М. И. Флуктуации в динамических системах под действием малых случайных возмущений. -М.: Наука, 1979.
- Калинкин А. В. Марковские ветвящиеся процессы с взаимодействием//УМН. -2002. -Т. 57:2(344). -С. 23-84.
Статья научная
