Ранжирование вершин графа публикаций математического портала Math-Net.ru

Булат Тимурович Цынгуев, Алексей Борисович Жижченко, Владимир Викторович Мазалов, Bulat Tsynguev, Aleksei Zhizhchenko, Vladimir Mazalov

Аннотация


В данной работе предлагается новый способ определения центральности для взвешенных графов на основе законов Кирхгофа. Рассматриваемый метод имеет относительно невысокую вычислительную сложность. Метод иллюстрируется результатами расчетов электрической центральности для ранжирования вершин графа публикаций математического портала Math-Net.ru. Сделано сравнение с широко используемым методом PageRank.

Ключевые слова


мера центральности; взвешенный граф; анализ социальных сетей

Полный текст:

PDF

Литература


Жижченко А. Б., Изаак А. Д. Информационная система Math-Net.Ru. Применение современных технологий в научной работе математика // Успехи математических наук. 2007. T. 62, № 5 (377). С. 107--132.

Avrachenkov K., Litvak N., Medyanikov V., Sokol M. Alpha current flow betweenness centrality // Lecture Notes in Computer Science. 2013. Vol. 8305. P. 106–117.

Bastian M., Heymann S., Jacomy M. Gephi: an open source software for exploring and manipulating networks // International AAAI Conference on Weblogs and Social Media. 2009.

Borgatti S. P., Everett M. G., Freeman L. C. Ucinet for Windows: Software for Social Network Analysis // MA: Analytic Technologies. 2002.

Brandes U. A faster algorithm for betweenness centrality // Journal of Mathematical Sociology. 2001. Vol. 25. P. 163–177.

Brandes U., Fleischer D. Centrality measures based on current flow // In Proceedings of the 22nd annual conference on Theoretical Aspects of Computer Science. 2005. P. 533–544.

Brin S., Page L. The anatomy of a largescale hypertextual Web search engine. Computer Networks and ISDN Systems. 1998. Vol. 30, N 17. P. 107–117.

Chebukov D., Izaak A., Misurina O., Pupyrev Yu., Zhizhchenko A. Math-Net.Ru as a digital archive of the Russian mathematical knowledge from the XIX century to today. Lecture Notes in Computer Science. 2013. Vol. 7961. P. 344–348.

Freeman L. C. A set of measures of centrality based on betweenness // Sociometry. 1977. Vol. 40. P. 35–41.

Mazalov V. V., Trukhina L. I. Generating functions and the Myerson vector in communication networks // Discrete Mathematics and Applications. 2014. Vol. 24, N 5. P. 295–303.

Myerson R. B. Graphs and cooperation in games // Math. Oper. Res. 1977. Vol. 2. P. 225–229.

Newman M. E. J. A measure of betweenness centrality based on random walks // Social networks. 2005. Vol. 27. P. 39–54.

REFERENCES in ENGLISH

Zhizhchenko A.B., Izaak A.D. Informatsionnaya sistema Math-Net.Ru. Primenenie sovremennykh tekhnologii v nauchnoi rabote matematika [Informational system Math-Net.Ru. Application of modern technologies in mathematical scientific work]. Uspekhi Matematicheskikh Nauk [Russian Mathematical Surveys]. 2007. Vol. 62, N 5 (377). P. 107–132.

Avrachenkov K., Litvak N., Medyanikov V., Sokol M. Alpha current flow betweenness centrality. Lecture Notes in Computer Science. 2013. Vol. 8305. P. 106–117.

Bastian M., Heymann S., Jacomy M. Gephi: an open source software for exploring and manipulating networks. International AAAI Conference on Weblogs and Social Media. 2009.

Borgatti S.P., Everett M.G., Freeman L.C. Ucinet for Windows: Software for Social Network Analysis. MA: Analytic Technologies. 2002.

Brandes U. A faster algorithm for betweenness centrality. Journal of Mathematical Sociology. 2001. Vol. 25. P. 163–177.

Brandes U., Fleischer D. Centrality measures based on current flow. In Proceedings of the 22nd annual conference on Theoretical Aspects of Computer Science. 2005. P. 533–544.

Brin S. and Page L. The anatomy of a largescale hypertextual Web search engine. Computer Networks and ISDN Systems. 1998. Vol. 30, N 17. P. 107–117.

Chebukov D., Izaak A., Misurina O., Pupyrev Yu., Zhizhchenko A. Math-Net.Ru as a digital archive of the Russian mathematical knowledge from the XIX century to today. Lecture Notes in Computer Science. 2013. Vol. 7961. P. 344–348.

Freeman L. C. A set of measures of centrality based on betweenness. Sociometry. 1977. Vol. 40. P. 35–41.

Mazalov V. V., Trukhina L. I. Generating functions and the Myerson vector in communication networks. Discrete Mathematics and Applications. 2014. Vol. 24, N 5. P. 295–303.

Myerson R. B. Graphs and cooperation in games. Math. Oper. Res. 1977. Vol. 2. P. 225–229.

Newman M. E. J. A measure of betweenness centrality based on random walks. Social networks. 2005. Vol. 27. P. 39–54.




DOI: http://dx.doi.org/10.17076/mat167

Ссылки

  • На текущий момент ссылки отсутствуют.


© Труды КарНЦ РАН, 2014-2016