Rad HAZU, Matematičke znanosti, Vol. 23 (2019), 31-49.

ONE-ALPHA WEIGHTED NETWORK DESCRIPTORS

Tanja Vojković and Damir Vukičević

Abstract.   Complex networks are often used to model objects and their relations. Network descriptors are graph-theoretical invariants assigned to graphs that correspond to complex networks. Transmission and betweenness centrality are well known network descriptors and networkness and network surplus have been recently analyzed. All these four descriptors are based on the unrealistic assumption about equal communication between all vertices. Here, we amend this by assuming that vertices on the distance larger then one communicate less than those that are neighbors. We analyze network descriptors for all possible values of the factor  that measures reduction in the communication of the vertices that are not neighbors. We term these descriptors one-alpha descriptors and determine their extremal values.

2010 Mathematics Subject Classification.   05C82, 05C35.

Key words and phrases.   Network descriptors, complex networks, extremal graph theory.

DOI: https://doi.org/10.21857/94kl4cxxjm

References:

1. R. Albert, Scale-free networks in cell biology, J. Cell Sci. 118 (2005), 4947-4957.
   CrossRef

2. J. M. Anthonisse, The Rush in a Graph, (1st edition), Mathematisch Centrum, Amsterdam, 1971.

3. S. Antunović, T. Kokan, T. Vojković and D. Vukičević, Generalised network descriptors, Glas. Mat. Ser. III 48 (2013), 211-230.
   MathSciNet     CrossRef

4. S. Antunović, T. Kokan, T. Vojković and D. Vukičević, Exponential Generalised Network Descriptors, Adv. Math. Commun. 13 (2019), 405-420.
   MathSciNet

5. A. L. Barabási, Linked: How Everything is Connected to Everything Else and What It Means, (1st edition), Persus Publishing, Cambridge, 2002.

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

7. B. Bollobás, Modern Graph Theory, (1st edition), Springer, New York, 1998.
   MathSciNet     CrossRef

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. T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to Algorithms, (2nd edition), MIT Press and McGraw-Hill, Cambridge, 2001.
   MathSciNet

10. L. Freeman, A Set of Measures of Centrality Based on Betweenness, Sociometry 40 (1977), 35-41.

11. L. Freeman, Centrality in social networks: Conceptual clarification, Soc. Networks 1 (1978), 215-239.

12. P. De Leenheer, D. Angeli and E. D. Sontag, Monotone chemical reaction networks, J. Math. Chem. 41 (2007), 295-314.
    MathSciNet     CrossRef

13. S. Majstorović and G. Caporossi, Bounds and relations involving adjusted centrality of the vertices of a tree, Graph. Combin. 31.6 (2015), 2319-2334.
    MathSciNet     CrossRef

14. P. R. Monge and N. Contractor, Theories of Communication Networks, Oxford University Press, Oxford, 2003.

15. M. E. J. Newman, Networks: An Introduction, (1st edition), Oxford University Press, Oxford, 2010.
    MathSciNet     CrossRef

16. N. D. Price, J. L. Reed, J. A. Papin, S. J. Wiback and B. O. Palsson, Network-based analysis of metabolic regulation in the human red blood cell, J. Theor. Biol. 225 (2003), 185-94.
    CrossRef

17. J. Šiagiová and J. Širán, Approaching the Moore bound for diameter two by Cayley graphs, J. Combin. Theory B 102 (2012), 470-473.
    MathSciNet     CrossRef

18. D. Vukičević and G. Caporossi, Network descriptors based on betweenness centrality and transmission and their extremal values, Discrete Appl. Math. 161 (2013), 2678-2686.
    MathSciNet     CrossRef

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