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 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.

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