Testing centrality in random graphs

Christian Tallberg^{*}

**Abstract**

When testing centrality in random graphs it is of importance to specify models that capture the irregularities in the structure due to centrality. In this paper we propose using the well-known block models in an attempt to capture such irregularities. The baseline model, revealing no centrality structure, used in this paper is the Bernoulli model. It is shown that the maximum likelihood estimators of the parameters in the block model are tedious to obtain, and that the distribution of the likelihood ratio is difficult to derive analytically. Therefore, various tests of centrality in random graphs are presented where the power functions of the test quantities are estimated by performing computer simulations. The tests are based on centrality indices that are evaluated at actor level. These indices are then aggregated across all actors in order to obtain a centrality index at group level. Two of the tests proposed are based on degree and eight of them are based on distance. None of the tests is uniformly most powerful. The tests where the group level index is defined as an average of the actor level indices show poor power compared to the tests that indicate the variability of the actor level indices. Among the tests based on variability of the actor level indices, the test quantities that include the maximum of the actor level indices generate a higher power than the tests based on the variance of the actor level indices.

Keywords: Random block models, Bernoulli graph, Degree centrality, Closeness centrality, Power of centrality tests

________________________

* Department of Statistics, Stockholm University. E-mail: Christian.Tallberg@stat.su.se.
The author would like to thank Ove Frank and Mattias Villani for helpful
comments. Partial financial support from the Swedish Council of Research
in Humanities and Social Sciences (HSFR), grant No. F0750/96, is gratefully
acknowledged.