August  2019, 13(3): 405-420. doi: 10.3934/amc.2019026

Exponential generalised network descriptors

1. 

Faculty of Civil Engineering, Architecture and Geodesy, Matice hrvatske 15, University of Split, Croatia

2. 

Faculty of Science, Bijenička cesta 30, University of Zagreb, Croatia

3. 

Faculty of Science, Rudera Boškovića 33, University of Split, Croatia

* Corresponding author

Received  May 2018 Revised  February 2019 Published  April 2019

In communication networks theory the concepts of networkness and network surplus have recently been defined. Together with transmission and betweenness centrality, they were based on the assumption of equal communication between vertices. Generalised versions of these four descriptors were presented, taking into account that communication between vertices $ u $ and $ v $ is decreasing as the distance between them is increasing. Therefore, we weight the quantity of communication by $ \lambda^{d(u,v)} $ where $ \lambda \in \left\langle0,1 \right\rangle $. Extremal values of these descriptors are analysed.

Citation: Suzana Antunović, Tonči Kokan, Tanja Vojković, Damir Vukičević. Exponential generalised network descriptors. Advances in Mathematics of Communications, 2019, 13 (3) : 405-420. doi: 10.3934/amc.2019026
References:
[1]

S. AntunovicT. KokanT. Vojkovic and D. Vukicevic, Generalised network descriptors, Glasnik Matematicki, 48 (2013), 211-230.  doi: 10.3336/gm.48.2.01.  Google Scholar

[2]

A. L. Barabasi, Linked: How Everything is Connected to Everything Else and What It Means, Persus Publishing, Cambridge, 2002. Google Scholar

[3]

B. Bollobas, Modern Graph Theory, Springer, New York, 1998. doi: 10.1007/978-1-4612-0619-4.  Google Scholar

[4]

S. P. Borgatti and M. G. Everett, A graph-theoretic perspective on centrality, Social Networks, 28 (2006), 466-484.  doi: 10.1016/j.socnet.2005.11.005.  Google Scholar

[5]

U. Brandes, A faster algorithm for betweenness centrality, J. Math. Sociol., 25 (2001), 163-177.  doi: 10.1080/0022250X.2001.9990249.  Google Scholar

[6]

G. CaporossiM. PaivaD. Vukicevic and M. Segatto, Centrality and betweenness: Vertex and edge decomposition of the Wiener index, MATCH Commun. Math. Comput. Chem, 68 (2012), 293-302.   Google Scholar

[7]

C. Dangalchev, Residual closeness and generalized closeness, International Journal of Foundations of Computer Science, 22 (2011), 1939-1948.  doi: 10.1142/S0129054111009136.  Google Scholar

[8]

L. Freeman, A set of measures of centrality based on betweenness, Sociometry, 40 (1977), 35-41.  doi: 10.2307/3033543.  Google Scholar

[9]

L. Freeman, Centrality in social networks: Conceptual clarification, Social Networks, 1 (1978), 215-239.  doi: 10.1016/0378-8733(78)90021-7.  Google Scholar

[10]

S. GagoJ. Coroničová Hurajová and T. Mandaras, On decay centrality in graphs, Mathematica Scandinavica, 123 (2018), 39-50.  doi: 10.7146/math.scand.a-106210.  Google Scholar

[11]

M. O. Jackson and A. Wolinsky, A strategic model of social and economic networks, Journal of Economic Theory, 71 (1996), 44-74.  doi: 10.1006/jeth.1996.0108.  Google Scholar

[12] M. E. J. Newman, Networks: An Introduction, Oxford University Press, Oxford, 2010.  doi: 10.1093/acprof:oso/9780199206650.001.0001.  Google Scholar
[13]

D. Vukicevic and G. Caporossi, Network descriptors based on betweenness centrality and transmission and their extremal values, Discrete Applied Mathematics, 161 (2013), 2678-2686.  doi: 10.1016/j.dam.2013.04.005.  Google Scholar

show all references

References:
[1]

S. AntunovicT. KokanT. Vojkovic and D. Vukicevic, Generalised network descriptors, Glasnik Matematicki, 48 (2013), 211-230.  doi: 10.3336/gm.48.2.01.  Google Scholar

[2]

A. L. Barabasi, Linked: How Everything is Connected to Everything Else and What It Means, Persus Publishing, Cambridge, 2002. Google Scholar

[3]

B. Bollobas, Modern Graph Theory, Springer, New York, 1998. doi: 10.1007/978-1-4612-0619-4.  Google Scholar

[4]

S. P. Borgatti and M. G. Everett, A graph-theoretic perspective on centrality, Social Networks, 28 (2006), 466-484.  doi: 10.1016/j.socnet.2005.11.005.  Google Scholar

[5]

U. Brandes, A faster algorithm for betweenness centrality, J. Math. Sociol., 25 (2001), 163-177.  doi: 10.1080/0022250X.2001.9990249.  Google Scholar

[6]

G. CaporossiM. PaivaD. Vukicevic and M. Segatto, Centrality and betweenness: Vertex and edge decomposition of the Wiener index, MATCH Commun. Math. Comput. Chem, 68 (2012), 293-302.   Google Scholar

[7]

C. Dangalchev, Residual closeness and generalized closeness, International Journal of Foundations of Computer Science, 22 (2011), 1939-1948.  doi: 10.1142/S0129054111009136.  Google Scholar

[8]

L. Freeman, A set of measures of centrality based on betweenness, Sociometry, 40 (1977), 35-41.  doi: 10.2307/3033543.  Google Scholar

[9]

L. Freeman, Centrality in social networks: Conceptual clarification, Social Networks, 1 (1978), 215-239.  doi: 10.1016/0378-8733(78)90021-7.  Google Scholar

[10]

S. GagoJ. Coroničová Hurajová and T. Mandaras, On decay centrality in graphs, Mathematica Scandinavica, 123 (2018), 39-50.  doi: 10.7146/math.scand.a-106210.  Google Scholar

[11]

M. O. Jackson and A. Wolinsky, A strategic model of social and economic networks, Journal of Economic Theory, 71 (1996), 44-74.  doi: 10.1006/jeth.1996.0108.  Google Scholar

[12] M. E. J. Newman, Networks: An Introduction, Oxford University Press, Oxford, 2010.  doi: 10.1093/acprof:oso/9780199206650.001.0001.  Google Scholar
[13]

D. Vukicevic and G. Caporossi, Network descriptors based on betweenness centrality and transmission and their extremal values, Discrete Applied Mathematics, 161 (2013), 2678-2686.  doi: 10.1016/j.dam.2013.04.005.  Google Scholar

Figure 1.  A broom that minimizes $mt_{\lambda }^{e}(G)$
Table 1.  Extremal values of exponential generalised network descriptors
Descriptor $\lambda \in \left\langle 0,1\right\rangle $
Lower bound Upper bound
$mt_{\lambda }^{e}$ broom (starting vertex) complete graph *
$A_n$ $ (n-1)\lambda $
$Mt_{\lambda }^{e}$ open problem broom (starting vertex)
$B_n$
$mc_{\lambda }^{e}$ path (end vertices) complete graph *
$\frac{\lambda^D-\lambda}{\lambda -1}$ $(n-1)\lambda $
$Mc_{\lambda }^{e}$ open problem star (center)
$(n-1)\left[ \lambda +\frac{1}{2}(n-2)\lambda ^{2}\right] $
$mN_{\lambda }^{e}$ broom (starting vertex) vertex-transitive graph
$C_n$ $1$
$MN_{\lambda }^{e}$ vertex-transitive graph star (center)
$1$ $\frac{1}{2}(n-2)\lambda +1$
$m\nu _{\lambda }^{e}$ broom (starting vertex) vertex-transitive graph
$D_n$ $0$
$M\nu _{\lambda }^{e}$ vertex-transitive graph star (center)
$0$ $\frac{1}{2}(n-1)(n-2)\lambda ^{2}$
Descriptor $\lambda \in \left\langle 0,1\right\rangle $
Lower bound Upper bound
$mt_{\lambda }^{e}$ broom (starting vertex) complete graph *
$A_n$ $ (n-1)\lambda $
$Mt_{\lambda }^{e}$ open problem broom (starting vertex)
$B_n$
$mc_{\lambda }^{e}$ path (end vertices) complete graph *
$\frac{\lambda^D-\lambda}{\lambda -1}$ $(n-1)\lambda $
$Mc_{\lambda }^{e}$ open problem star (center)
$(n-1)\left[ \lambda +\frac{1}{2}(n-2)\lambda ^{2}\right] $
$mN_{\lambda }^{e}$ broom (starting vertex) vertex-transitive graph
$C_n$ $1$
$MN_{\lambda }^{e}$ vertex-transitive graph star (center)
$1$ $\frac{1}{2}(n-2)\lambda +1$
$m\nu _{\lambda }^{e}$ broom (starting vertex) vertex-transitive graph
$D_n$ $0$
$M\nu _{\lambda }^{e}$ vertex-transitive graph star (center)
$0$ $\frac{1}{2}(n-1)(n-2)\lambda ^{2}$
[1]

Qiang Fu, Yanlong Zhang, Yushu Zhu, Ting Li. Network centralities, demographic disparities, and voluntary participation. Mathematical Foundations of Computing, 2020, 3 (4) : 249-262. doi: 10.3934/mfc.2020011

[2]

Cuicui Li, Lin Zhou, Zhidong Teng, Buyu Wen. The threshold dynamics of a discrete-time echinococcosis transmission model. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020339

[3]

Fioralba Cakoni, Pu-Zhao Kow, Jenn-Nan Wang. The interior transmission eigenvalue problem for elastic waves in media with obstacles. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020075

[4]

Shipra Singh, Aviv Gibali, Xiaolong Qin. Cooperation in traffic network problems via evolutionary split variational inequalities. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020170

[5]

Yicheng Liu, Yipeng Chen, Jun Wu, Xiao Wang. Periodic consensus in network systems with general distributed processing delays. Networks & Heterogeneous Media, 2020  doi: 10.3934/nhm.2021002

[6]

Rajendra K C Khatri, Brendan J Caseria, Yifei Lou, Guanghua Xiao, Yan Cao. Automatic extraction of cell nuclei using dilated convolutional network. Inverse Problems & Imaging, 2021, 15 (1) : 27-40. doi: 10.3934/ipi.2020049

[7]

Md. Masum Murshed, Kouta Futai, Masato Kimura, Hirofumi Notsu. Theoretical and numerical studies for energy estimates of the shallow water equations with a transmission boundary condition. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 1063-1078. doi: 10.3934/dcdss.2020230

[8]

Ali Wehbe, Rayan Nasser, Nahla Noun. Stability of N-D transmission problem in viscoelasticity with localized Kelvin-Voigt damping under different types of geometric conditions. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020050

[9]

Editorial Office. Retraction: Honggang Yu, An efficient face recognition algorithm using the improved convolutional neural network. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 901-901. doi: 10.3934/dcdss.2019060

[10]

Yu-Jhe Huang, Zhong-Fu Huang, Jonq Juang, Yu-Hao Liang. Flocking of non-identical Cucker-Smale models on general coupling network. Discrete & Continuous Dynamical Systems - B, 2021, 26 (2) : 1111-1127. doi: 10.3934/dcdsb.2020155

[11]

Ziang Long, Penghang Yin, Jack Xin. Global convergence and geometric characterization of slow to fast weight evolution in neural network training for classifying linearly non-separable data. Inverse Problems & Imaging, 2021, 15 (1) : 41-62. doi: 10.3934/ipi.2020077

2019 Impact Factor: 0.734

Metrics

  • PDF downloads (209)
  • HTML views (378)
  • Cited by (0)

[Back to Top]