Lembris Laanyuni Njotto

Show more
Department of Mathematics and ICT, College of Business Education, Dar Es Salaam, Tanzania.
Show less

Abstract: Network is considered naturally as a wide range of different contexts, such as biological systems, social relationships as well as various technological scenarios. Investigation of the dynamic phenomena taking place in the network, determination of the structure of the network and community and description of the interactions between various elements of the network are the key issues in network analysis. One of the huge network structure challenges is the identification of the node(s) with an outstanding structural position within the network. The popular method for doing this is to calculate a measure of centrality. We examine node centrality measures such as degree, closeness, eigenvector, Katz and subgraph centrality for undirected networks. We show how the Katz centrality can be turned into degree and eigenvector centrality by considering limiting cases. Some existing centrality measures are linked to matrix functions. We extend this idea and examine the centrality measures based on general matrix functions and in particular, the logarithmic, cosine, sine, and hyperbolic functions. We also explore the concept of generalised Katz centrality. Various experiments are conducted for different networks generated by using random graph models. The results show that the logarithmic function in particular has potential as a centrality measure. Similar results were obtained for real-world networks.

Keywords: Graph, Centrality Measures, Matrix Functions, Kendall Correlation Coefficient, Random Graph Models

Cite this paper: Njotto, L. (2018) Centrality Measures Based on Matrix Functions. Open Journal of Discrete Mathematics, 8, 79-115. doi: 10.4236/ojdm.2018.84008.

References

[1]   Benzi, M. and Klymko, C. (2013) Total Communicability as a Centrality Measure. Journal of Complex Networks, 1, 124-149.
https://doi.org/10.1093/comnet/cnt007

[2]   Kendall, M.G. (1938) A New Measure of Rank Correlation. Biometrika, 30, 81-93.
https://doi.org/10.1093/biomet/30.1-2.81

[3]   Bavelas, A. (1948) A Mathematical Model for Group Structures. Human Organization, 7, 16-30. https://doi.org/10.17730/humo.7.3.f4033344851gl053

[4]   Bavelas, A. and Barrett, D. (1951) An Experimental Approach to Organizational Communication. American Management Association, New York, 57-62.

[5]   Cohn, B.S. and Marriott, M. (1958) Networks and Centres of Integration in Indian Civilization. Journal of Social Research, 1, 1-9.

[6]   Pitts, F.R. (1965) A Graph Theoretic Approach to Historical Geography. The Professional Geographer, 17, 15-20.
https://doi.org/10.1111/j.0033-0124.1965.015_m.x

[7]   Czepiel, J.A. (1974) Word-of-Mouth Processes in the Diffusion of a Major Technological Innovation. Journal of Marketing Research, 11, 172-180.
https://doi.org/10.2307/3150555

[8]   Bolland, J.M. (1988) Sorting out Centrality: An Analysis of the Performance of Four Centrality Models in Real and Simulated Networks. Social Networks, 10, 233-253.
https://doi.org/10.1016/0378-8733(88)90014-7

[9]   Borgatti, S.P. and Everett, M.G. (2006) A Graph-Theoretic Perspective on Centrality. Social Networks, 28, 466-484.
https://doi.org/10.1016/j.socnet.2005.11.005

[10]   Landherr, A., Friedl, B. and Heidemann, J. (2010) A Critical Review of Centrality Measures in Social Networks. Business & Information Systems Engineering, 2, 371-385.
https://doi.org/10.1007/s12599-010-0127-3

[11]   Estrada, E. (2012) The Structure of Complex Networks: Theory and Applications. Oxford University Press, Oxford.

[12]   Higham, N.J. (2008) Bibliography of Functions of Matrices: Theory and Computation. SIAM.
https://doi.org/10.1137/1.9780898717778

[13]   Boldi, P. and Vigna, S. (2014) Axioms for Centrality. Internet Mathematics, 10, 222-262.
https://doi.org/10.1080/15427951.2013.865686

[14]   Higham, N.J. and Deadman, E. (2016) A Catalogue of Software for Matrix Functions. Version 2.0.

[15]   Bethea, R.M. (2018) Statistical Methods for Engineers and Scientists. Routledge, Abingdon-on-Thames.

[16]   Fredricks, G.A. and Nelsen, R.B. (2007) On the Relationship between Spearman’s Rho and Kendall’s Tau for Pairs of Continuous Random Variables. Journal of Statistical Planning and Inference, 137, 2143-2150.
https://doi.org/10.1016/j.jspi.2006.06.045

[17]   Xu, W., Hou, Y., Hung, Y.S. and Zou, Y. (2010) Comparison of Spearman’s Rho and Kendall’s Tau in Normal and Contaminated Normal Models.

[18]   Prettejohn, B.J., Berryman, M.J. and McDonnell, M.D. (2011) Methods for Generating Complex Networks with Selected Structural Properties for Simulations: A Review and Tutorial for Neuroscientists. Frontiers in Computational Neuroscience, 5, 11. https://doi.org/10.3389/fncom.2011.00011

[19]   Bayati, M., Kim, J.H. and Saberi, A. (2010) A Sequential Algorithm for Generating Random Graphs. Algorithmica, 58, 860-910.
https://doi.org/10.1007/s00453-009-9340-1

[20]   Mej, N. (2010) Networks: An Introduction.

[21]   Albert, R. and Barabási, A.L. (2002) Statistical Mechanics of Complex Networks. Reviews of Modern Physics, 74, 47-97.
https://doi.org/10.1103/RevModPhys.74.47

[22]   Newman, M.E., Strogatz, S.H. and Watts, D.J. (2001) Random Graphs with Arbitrary Degree Distributions and Their Applications. Physical Review E, 64, Article ID: 026118.
https://doi.org/10.1103/PhysRevE.64.026118

[23]   Datasets, Wikipedia, the Free Encyclopedia.
https://wiki.gephi.org/index.php/Datasets

[24]   Old Pajek Data Sets.
http://pajek.imfm.si/doku.php?id=data:pajek:vlado