"Connectivity Centrality Measure on the Nodes of Graphs as Generalization of Binomial Coefficients"

12-10-2017
GREDEG - Salle Picasso

In graph theory and network analysis, indicators of centrality identify the most important nodes within 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 are answers to the question "What characterizes an important vertex?" The answer is given in terms of a real-valued function on the nodes of a graph, where the values produced are expected to provide a ranking which identifies the most important ones. 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 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.