Glasnik Matematicki, Vol. 48, No. 2 (2013), 211-230.

GENERALISED NETWORK DESCRIPTORS

Suzana Antunović, Tonći Kokan, Tanja Vojković and Damir Vukičević

Faculty of Civil Engineering, Architecture and Geodesy, University of Split, Matice hrvatske 15, 21 000 Split, Croatia
e-mail: santunovic@gradst.hr

Faculty of Economics, University of Split, Cvite Fiskovića 5, 21000 Split , Croatia
e-mail: tkokan@gmail.com

Department of Mathematics, University of Split, Teslina 12, 21 000 Split, Croatia
e-mail: tanja@pmfst.hr

Department of Mathematics, University of Split, Teslina 12, 21 000 Split, Croatia
e-mail: vukicevic@pmfst.hr


Abstract.   Transmission and betweenness centrality are key concepts in communication networks theory. Based on this concept, new concepts of networkness and network surplus have recently been defined. However, all these four concepts include unrealistic assumption about equal communication between vertices. Here, we propose more realistic assumption that the amount of communication of vertices decreases as their distance increases. We assume that amount of communication between vertices u and v is proportional to d(u,v)Λ where Λ < 0. Taking this into account generalised versions of these four descriptors are defined. Extremal values of these descriptors are analysed.

2010 Mathematics Subject Classification.   05C35, 05C12.

Key words and phrases.   Betweenness, transmission, networkness, network surplus, complex networks.


Full text (PDF) (access from subscribing institutions only)

DOI: 10.3336/gm.48.2.01


References:

  1. J. M. Anthonisse, The rush in a directed graph, Stichting Mathematisch Centrum, Amsterdam, 1971, 1-10.

  2. A.-L. Barabási, Linked: How everything is connected to everything else and what it means, Persus Publishing, Cambridge, 2002.

  3. A. Barrat, M. Barthélemy and A. Vespignani, Dynamical processes on complex networks, Cambridge University Press, Cambridge, 2008.
    MathSciNet     CrossRef

  4. B. Bollobás, Modern graph theory, Springer-Verlag, New York, 1998.
    MathSciNet     CrossRef

  5. S. P. Borgatti and M. G. Everett, A graph-theoretic perspective on centrality, Social Networks 28 (2006), 466-484.
    CrossRef

  6. U. Brandes, A faster algorithm for betweenness centrality, J. Math. Sociol. 25 (2001), 163-177.
    CrossRef

  7. U. Brandes and T. Erlebach (eds.), Network analysis - methodological foundations, Springer-Verlag, Berlin, 2005.

  8. G. Caporossi, M. Paiva, D. Vukičević and M. Segatto, Centrality and betweenness: vertex and edge decomposition of the Wiener index, MATCH Commun. Math. Comput. Chem 68 (2012), 293-302.
    MathSciNet    

  9. L. Freeman, A set of measures of centrality based on betweenness, Sociometry 40 (1977), 35-41.
    CrossRef

  10. L. Freeman, Centrality in social networks: conceptual clarification, Social Networks 1 (1978), 215-239.
    CrossRef

  11. S. Gago, J. Hurajová and T. Madaras, Nodes on the betweenness centrality of a graph, Math. Slovaca 62 (2012), 1-12.
    MathSciNet     CrossRef

  12. M. Girvan, M. E. J. Newman, Community structure in social and biological networks, Proc. Natl. Acad. Sci. USA 99 (2002), 7821-7826.
    MathSciNet     CrossRef

  13. I. Gutman, A property of the Wiener number and its modifications, Indian J. Chem. 36 (1997), 128-132.

  14. I. Gutman, D. Vidović and Lj. Popović, On graph representation of organic molecules - Cayley's plerograms vs. his kenograms, J. Chem. Soc. Faraday Trans. 94 (1998), 857-860.
    CrossRef

  15. M. E. J. Newman, Networks. An introduction, Oxford University Press, Oxford, 2010.
    MathSciNet     CrossRef

  16. D. Vukičević and G. Caporossi, Network descriptors based on betweenness centrality and transmission and their extremal values, submitted to Discrete Appl. Math.

  17. H. Wiener, Structural determination of paraffin boiling points, J. Amer. Chem. Soc. 69 (1947), 17-20.
    CrossRef

Glasnik Matematicki Home Page