Abstract
Centrality of an edge of a graph is proposed to be viewed as a degree of global sensitivity of a graph distance function (i.e., a graph metric) on the weight of the considered edge. For different choices of distance function, contact is made with several previous ideas of centrality, whence their different characteristics are clarified, and strengths or short-comings are indicated, via selected examples. The centrality based on “resistance distance” exhibits several nice features, and might be termed “amongness” centrality.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Jordan C.: Sur les assemblages des lignes. J. Reine Angew. Math. 70, 185–190 (1869)
Goldman A.J.: Optimal locations for centers in a network. Transp. Sci. 3, 352–360 (1969)
Goldman A.J.: Optimal center location in simple networks. Transp. Sci. 5, 212–221 (1971)
Hakimi S.L., Maheshwari S.N.: Optimal locations of centers in networks. Oper. Res. 20, 967–973 (1972)
Hakimi S.L.: Optimum locations of switching centers and absolute centers and medians of a graph. Oper. Res. 12, 450–459 (1964)
Slater P.J.: Centrality of Paths and Vertices in a Graph: Cores and Pits. In: Chartrand, G., Alavi, Y., Goldsmith, D.L., Lesniak-Foster, L., Lick., D.R. (eds) The Theory and Applications of Graphs, pp. 529–542. Wiley, NY (1981)
Brin S., Page L.: The anatomy of a large-scale hypertextual web search engine. Comput. Netw. 30, 107–117 (1998)
Brandes U., Kenis P., Wagner D.: Centrality in policy network drawings. Lect. Notes Comput. Sci. 1731, 250–258 (1999)
Kleinberg J.M.: Authorative sources in a hyperlinked environment. J. Am. Comp. Mach. 46, 604–632 (1999)
Erkan G., Radev D.R.: LexRank: graph-based Lexical centrality as salience in text summarization. J. Artif. Intell. Res. 22, 457–479 (2004)
Katz L.: A new status index derived from sociometric analysis. Psychometrika 18, 39–43 (1953)
Shaw M.E.: Group structure and the behavior of individuals in small groups. J. Psych. 38, 139–149 (1954)
Mackenzie K.D.: Structural centrality in communications networks. Psychometrika 31, 17–25 (1966)
Sabidussi G.: The centrality index of a graph. Psychometrika 31, 581–603 (1966)
Bavelas A.: A mathematical model for small group structures. Hum. Organiz. 7, 16–30 (1948)
Bavelas A.: A mathematical model for group structures. Appl. Anthro. 7, 16–30 (1948)
Harary F.: Status and contrastatus. Sociometry 22, 23–43 (1959)
Taylor M.: Influence structures. Sociometry 32, 490–502 (1969)
Nieminen U.J.: On the centrality in a directed graph. Soc. Sci. Res. 2, 371–378 (1973)
Bonacich P.: Factoring and weighting approaches to clique identification. J. Math. Sociol. 2, 113–120 (1972)
Freeman L.C.: A set of measures of centrality based on betweenness. Sociometry 40, 35–41 (1977)
Moxley R.L., Moxley N.F.: Determining point-centrality in uncontrived networks. Sociometry 37, 122–130 (1974)
Freeman L.C.: Centrality in social networks—conceptual clarification. Soc. Netw. 1, 215–239 (1978/1979)
Bonacich P.: Power and centrality: a family of measures. Am. J. Soc. 92, 1170–1182 (1987)
Bonacich P.: Simultaneous group and individual centralities. Soc. Netw. 13, 155–168 (1991)
White D.R., Borgatti S.P.: Betweenness centrality measures for directed graphs. Soc. Netw. 16, 335–346 (1994)
Pitts F.R.: A graph theoretic approach to historical geography. Prof. Geogr. 17(5), 15–20 (1965)
L.S. Shapely, A value for n-person games. in Contributions to the Theory of Games, vol. 2, Ann. Math. Stud. 28. ed. by H.W. Kuhn, H.W. Tucker (Princeton University Press, Princeton, NJ, 1953), pp. 307–317
Sengoku M., Shinoda S.: A function measuring the centrality (or mediality) of an edge in an undirected network with edge capacity. Electron. Commun. Jpn. Part 1 69(11), 45–54 (1986)
P. Hines, S. Blumsack A centrality measure for electrical networks. in Proceedings of the 41st Hawaii international conference on system sciences IEEE (2008)
Bonchev D., Balaban A.T., Mekenyan O.: Generalization of the graph center concept, and derived topological centric indices. J. Chem. Inf. Comp. Sci. 20, 106–113 (1980)
Bonchev D., Mekenyan O., Balaban A.T.: Iterative procedure for the generalized graph center in polycyclic graphs. J. Chem. Inf. Comp. Sci. 29, 91–97 (1989)
Bonchev D., Balaban A.T.: Central vertices versus central rings in polycyclic systems. J. Math. Chem. 14, 287–304 (1993)
Yoon J., Blumer A., Lee K.: An algorithm for modularity analysis of directed and weighted biological networks based on edge-betweenness centrality. Bioinformatics 22, 3106–3108 (2006)
Yu H., Kim P.M., Sprecher E. , Trifonov V. , Gerstein M. : The importance of bottlenecks in protein net- works: correlation with gene essentiality and expression dynamics. PLoS Comput. Biol. 3, 713–720 (2007)
McRae B.H., Dickson B.G., Keitt T.H., Shah V.B.: Using circuit theory to model connectivity in ecology, evolution, and conservation. Ecology 89, 2712–2724 (2008)
Girvan M., Newman M.E.J.: Community structure in social and biological networks. Proc. Natl. Acad. USA 99, 7821–7826 (2002)
Kishi G.: On centrality functions of a graph. Lect. Notes Comp. Sci. 108, 45–52 (1981)
Brandes U.: A faster algorithm for betweenness centrality. J. Math. Soc. 25, 163–177 (2001)
Eppstein D., Wang J.: Fast approximation of centrality. J. Graph Algorithms Appl. 8, 39–45 (2004)
Bader D.A., Kintali S., Madduri K., Mihail M.: Approximating betweenness centrality. Lect. Notes Comput. Sci. 4863, 124–137 (2007)
Newman M.E.J.: A betweenness centrality based on random walks. Soc. Netw. 27, 39–54 (2005)
Brandes U., Fleischer D.: Centrality measures based on current flow. Lect. Notes Comput. Sci. 3404, 533–544 (2005)
E. Estrada, J.A. Rodriguez-Velazquez, Subgraph centrality in complex networks. Phys. Rev. E 71, 056103-1-9 (2005)
Rodriguez J.A., Estrada E., Gutierrez A.: Functional centrality in graphs. Lin. Multilin. Alg. 55, 293–302 (2007)
Grassi R., Stefani S., Torriero A.: Some new results on the eigenvector centrality. J. Math. Soc. 31, 237–248 (2007)
Everett M., Borgatti S.P.: Ego network betweennness. Soc. Netw. 27, 32–38 (2005)
Bader D.A., Kintali S., Madduri K., Mihail M.: Approximating betweenness centrality. Lect. Notes Comput. Sci. 4863, 124–137 (2007)
Everett M.G., Sinclair P., Dankelmann P.: Some centrality results new and old. J. Math. Soc. 28, 215–227 (2004)
P. Sinclair, Betweenness centralization for bipartite graphs. J. Math. Soc. 29, 25–31; erratum, 29, 263–264 (2005)
Bolland J.M.: Sorting out centrality: an analysis of the performance of four centrality models in real and simulated networks. Soc. Netw. 10, 233–253 (1988)
Freeman L.C., Borgatti S.P., White D.R.: Centrality in valued graphs: a measure of betweenness based on network flow. Soc. Netw. 13, 141–154 (1991)
Maonsuur H., Storcken T.: Centers in connected undirected graphs. Oper. Res. 52, 54–64 (2004)
Borgatti S.P.: Centrality and network flow. Soc. Netw. 27, 55–71 (2005)
Borgatti S.P., Everett M.G.: A graph-theoretic perspective on centrality. Soc. Netw. 28, 466–484 (2006)
Klein D.J., Randic M.: Resistance distance. J. Math. Chem. 12, 81–95 (1993)
Klein D.J.: Geometry, graph metrics, & Wiener. Commun. Math. Chem. (MatCh) 35, 7–27 (1997)
Chebotarev P., Shamis E.: The forest metrics for graph vertices. Electron. Notes Discrete Math. 11, 98–107 (2002)
Chebotarev P., Agaev R.: Forest matrices around the Laplacian matrix. Lin. Alg. Appl. 356, 253–274 (2002)
Wiener H.: Structural determination of paraffin boiling points. J. Am. Chem. Soc. 69, 17–20 (1947)
Wiener H.: Influence of interatomic forces on paraffin properties. J. Chem. Phys. 15, 766 (1947)
Buckley F., Harary F.: Distance in Graphs. Addison-Wesley, Reading, MA (1989)
J.C. Maxwell, Chapter VI in Treatise on Electricity & Magnetism. (Oxford Clarendon Press, Oxford, 1891); reprinted by Dover
Kirchoff G.: Über die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen verteilhung galvanischer Störme geführt wird. Ann. Phys. Chem. 72, 497–508 (1847)
Shapiro L.W.: An electrical lemma. Math. Mag. 60, 36–38 (1989)
P.G. Doyle, J.L. Snell, Random walks & electrical networks (Math. Assoc. Am., Washington, DC, 1984)
Babić D., Klein D.J., Lukovits I., Nikolic S., Trinajstic N.: Resistance-distance matrix: a computational algorithm & its application. Int. J. Quantum Chem. 90, 166–176 (2002)
M. Fiedler, A geometric approach to the laplacian matrix of a graph. in Combinatorial and Graph-Theoretical Problems in Linear Algebra, ed. by R.A. Brualdi, S. Friedland, V. Klee (Springer, Berlin, 1991), pp. 73–98
Klein D.J., Zhu H.-Y.: Distances and volumina for graphs. J. Math. Chem. 23, 179–195 (1998)
D.J. Klein, Graph geometry via metrics. in Topology in Chemistry, ed. by D.H. Rouvray, R.B. King (Horwood, Chichester, 2002), pp. 292–317
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Klein, D.J. Centrality measure in graphs. J Math Chem 47, 1209–1223 (2010). https://doi.org/10.1007/s10910-009-9635-0
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10910-009-9635-0