Hostname: page-component-cd9895bd7-jn8rn Total loading time: 0 Render date: 2024-12-19T07:18:46.987Z Has data issue: false hasContentIssue false
  • English
  • Français

Rank monotonicity in centrality measures

Published online by Cambridge University Press:  26 July 2017

PAOLO BOLDI Open the ORCID record for PAOLO BOLDI [Opens in a new window] ,
ALESSANDRO LUONGO  and
SEBASTIANO VIGNA
PAOLO BOLDI
Affiliation:
Dipartimento di Informatica, Università degli Studi di Milano, Milano, Italy (e-mail: [email protected], [email protected], [email protected])
ALESSANDRO LUONGO
Affiliation:
Dipartimento di Informatica, Università degli Studi di Milano, Milano, Italy (e-mail: [email protected], [email protected], [email protected])
SEBASTIANO VIGNA
Affiliation:
Dipartimento di Informatica, Università degli Studi di Milano, Milano, Italy (e-mail: [email protected], [email protected], [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

A measure of centrality is rank monotone if after adding an arc x → y, all nodes with a score smaller than (or equal to) y have still a score smaller than (or equal to) y. If, in particular, all nodes with a score smaller than or equal to y get a score smaller than y (i.e., all ties with y are broken in favor of y), the measure is called strictly rank monotone. We prove that harmonic centrality is strictly rank monotone, whereas closeness is just rank monotone on strongly connected graphs, and that some other measures, including betweenness, are not rank monotone at all (sometimes not even on strongly connected graphs). Among spectral measures, damped scores such as Katz's index and PageRank are strictly rank monotone on all graphs, whereas the dominant eigenvector is strictly monotone on strongly connected graphs only.

Keywords

centralitynetwork analysisrank monotonicity
Type
Research Article
Information
Network Science , Volume 5 , Issue 4 , December 2017 , pp. 529 - 550
Copyright
Copyright © Cambridge University Press 2017 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Altman, A., & Tennenholtz, M. (2008). Axiomatic foundations for ranking systems. Journal of Artificial Intelligence Research, 31 (1), 473–495.CrossRefGoogle Scholar
Anthonisse, J. M. (1971). The rush in a directed graph. Tech. rept. BN 9/71. Mathematical Centre, Amsterdam.Google Scholar
Bavelas, A. (1948). A mathematical model for group structures. Human Organization, 7 (3), 16–30.Google Scholar
Bavelas, A., Barrett, D. & American Management Association. (1951). An experimental approach to organizational communication. Publications (Massachusetts Institute of Technology. Dept. of Economics and Social Science). Industrial Relations. New York: American Management Association.Google Scholar
Beauchamp, M. A. (1965). An improved index of centrality. Behavioral Science, 10 (2), 161–163.Google Scholar
Berge, C. (1958). Théorie des graphes et ses applications. Paris, France: Dunod.Google Scholar
Berman, A., & Plemmons, R. J. (1994). Nonnegative matrices in the mathematical sciences, Classics in Applied Mathematics. Philadelphia, PA: SIAM.CrossRefGoogle Scholar
Boldi, P., & Vigna, S. (2014). Axioms for centrality. Internet Mathematics, 10 (3–4), 222–262.Google Scholar
Bonacich, P. (1991). Simultaneous group and individual centralities. Social Networks, 13 (2), 155–168.CrossRefGoogle Scholar
Brandes, U., Kosub, S., & Nick, B. (2012). Was messen Zentralitätsindizes? In Hennig, M., & Stegbauer, C., (Eds.), Die integration von theorie und methode in der netzwerkforschung (pp. 33–52). Springer VS Verlag für Sozialwissenschaften, Springer Fachmedien Wiesbaden.CrossRefGoogle Scholar
Chien, S., Dwork, C., Kumar, R., Simon, D. R., & Sivakumar, D. (2004). Link evolution: Analysis and algorithms. Internet Mathematics, 1 (3), 277–304.Google Scholar
Cohn, B. S., & Marriott, M. (1958). Networks and centres of integration in Indian civilization. Journal of Social Research, 1, 1–9.Google Scholar
Dequiedt, V., & Zenou, Y. (2014). Local and consistent centrality measures in networks. Tech. rept. 2014:4. Stockholm University, Department of Economics.Google Scholar
Elsner, L. F., Johnson, C. R., & Neumann, M. M. (1982). On the effect of the perturbation of a nonnegative matrix on its Perron eigenvector. Czechoslovak Mathematical Journal, 32 (1), 99–109.Google Scholar
Fishburn, P. C. (1982). Monotonicity paradoxes in the theory of elections. Discrete Applied Mathematics, 4 (2), 119–134.CrossRefGoogle Scholar
Freeman, L. (1979). Centrality in social networks: Conceptual clarification. Social Networks, 1 (3), 215–239.CrossRefGoogle Scholar
Freeman, L. C. (1977). A set of measures of centrality based on betweenness. Sociometry, 40 (1), 35–41.Google Scholar
Garg, M. (2009). Axiomatic foundations of centrality in networks. Social Science Research Network. http://dx.doi.org/10.2139/ssrn.1372441.CrossRefGoogle Scholar
Hubbell, C. H. (1965). An input-output approach to clique identification. Sociometry, 28 (4), 377–399.Google Scholar
Katz, L. (1953). A new status index derived from sociometric analysis. Psychometrika, 18 (1), 39–43.Google Scholar
Kitti, M. (2016). Axioms for centrality scoring with principal eigenvectors. Social Choice and Welfare, 46 (3), 639–653.Google Scholar
Kleinberg, J. M. (1999). Authoritative sources in a hyperlinked environment. Journal of the ACM, 46 (5), 604–632.Google Scholar
Leavitt, H. J. (1951). Some effects of certain communication patterns on group performance. Journal of Abnormal Psychology, 46 (1), 38–50.CrossRefGoogle ScholarPubMed
Lempel, R., & Moran, S. (2001). SALSA: The stochastic approach for link-structure analysis. ACM Transactions on Information Systems, 19 (2), 131–160.Google Scholar
Lin, N. (1976). Foundations of social research. New York: McGraw-Hill.Google Scholar
Mackenzie, K. (1966). Structural centrality in communications networks. Psychometrika, 31 (1), 17–25.Google Scholar
McDonald, J. J., Neumann, M., Schneider, H., & Tsatsomeros, M. J. (1995). Inverse M-matrix inequalities and generalized ultrametric matrices. Linear Algebra and its Applications, 220, 321–341.CrossRefGoogle Scholar
Nieminen, U. J. (1973). On the centrality in a directed graph. Social Science Research, 2 (4), 371–378.Google Scholar
Page, L., Brin, S., Motwani, R., & Winograd, T. (1998). The PageRank citation ranking: Bringing order to the web. Tech. rept. SIDL-WP-1999-0120. Stanford Digital Library Technologies Project, Stanford University.Google Scholar
Palacios-Huerta, I., & Volij, O. (2004). The measurement of intellectual influence. Econometrica, 72 (3), 963–977.CrossRefGoogle Scholar
Pinski, G., & Narin, F. (1976). Citation influence for journal aggregates of scientific publications: Theory, with application to the literature of physics. Information Processing & Management, 12 (5), 297–312.Google Scholar
Pitts, F. R. (1965). A graph theoretic approach to historical geography. The Professional Geographer, 17 (5), 15–20.CrossRefGoogle Scholar
Sabidussi, G. (1966). The centrality index of a graph. Psychometrika, 31 (4), 581–603.Google Scholar
Seeley, J. R. (1949). The net of reciprocal influence: A problem in treating sociometric data. Canadian Journal of Psychology, 3 (4), 234–240.Google Scholar
Vigna, S. (2016). Spectral ranking. Network Science, 4 (4), 433–445.CrossRefGoogle Scholar
Wei, T.-H. (1952). The Algebraic Foundations of Ranking Theory. Ph.D. thesis, University of Cambridge.Google Scholar
Willoughby, R. A. (1977). The inverse M-matrix problem. Linear Algebra and its Applications, 18 (1), 75–94.CrossRefGoogle Scholar