49120

Автор(ы): 

Автор(ов): 

3

Параметры публикации

Тип публикации: 

Тезисы доклада

Название: 

Связуемости центральности узлов графа, как обобщение биномиальных коэффициентов

Электронная публикация: 

Да

Наименование конференции: 

  • 2-я всероссийская междисциплинарная конференция «СОЦИОФИЗИКА И СОЦИОИНЖЕНЕРИЯ» (Москва, ИПУ РАН, 2018)

Наименование источника: 

  • Материалы 2-й всероссийской междисциплинарной конференции «СОЦИОФИЗИКА И СОЦИОИНЖЕНЕРИЯ» (Москва, ИПУ РАН, 2018)

Город: 

  • Москва

Издательство: 

  • ИПУ РАН

Год издания: 

2018

Страницы: 

http://soc-phys.ipu.ru/node/10867
Аннотация
In graph theory and network analysis, indicators of centrality identify the most important nodes in a graph. Applications include identifying the most influential person(s) in a social network, key infrastructure nodes in the Internet or urban networks, and super-spreaders of disease. Centrality indices answer the question about importance of the nodes in a graph in terms of a real-valued function, which provides ranking of the nodes. The word "importance" has a wide number of meanings, leading to many different definitions of centrality. We introduce the connectivity centrality measure on the nodes of connected undirected graphs that assigns to each node of a graph its connectivity centrality index equal to the number of ways the graph can be constructed by a sequence of increasing connected subgraphs starting from this node. It turns out that on the linear graph the connectivity centrality of a node is equal to the corresponding binomial coefficient. Moreover, we show that the connectivity centrality indices of nodes possess the properties very similar to the properties of binomial coefficients. This allows to consider the connectivity centralities as a generalization of the binomial coefficients to the numbers on the nodes of graphs and this also provides a new interpretation of the binomial coefficient as the number of ways the linear graph can be constructed when starting with a node and adding neighboring nodes one by one. On the subclass of connected cycle-free graphs we provide an axiomatic characterization of the connectivity centrality measure. Furthermore, we show that for a given connected cycle-free graph the connectivity centralities of nodes, when normalized to sum up to one, are equal to the steady state probabilities of some Markov chain on the nodes of the graph.

Библиографическая ссылка: 

Хмельницкая А.Б., van der Laan G., Talman A. J. J. Связуемости центральности узлов графа, как обобщение биномиальных коэффициентов / Материалы 2-й всероссийской междисциплинарной конференции «СОЦИОФИЗИКА И СОЦИОИНЖЕНЕРИЯ» (Москва, ИПУ РАН, 2018). М.: ИПУ РАН, 2018. С. http://soc-phys.ipu.ru/node/10867.