Exponential generalised network descriptors

Previous Article
Optimal subspace codes in $ {{\rm{PG}}}(4,q) $
AMC Home
This Issue
Next Article
New non-binary quantum codes from constacyclic codes over $ \mathbb{F}_q[u,v]/\langle u^{2}-1, v^{2}-v, uv-vu\rangle $

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

Exponential generalised network descriptors

Suzana Antunović ^1,, , Tonči Kokan ^2, , Tanja Vojković ^3, and Damir Vukičević ^3,

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.

Keywords: Centrality, transmission, networkness, network surplus.

Mathematics Subject Classification: Primary: 58F15, 58F17; Secondary: 53C35.

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. Antunovic, T. Kokan, T. Vojkovic and D. Vukicevic, Generalised network descriptors, Glasnik Matematicki, 48 (2013), 211-230. doi: 10.3336/gm.48.2.01.
[2]	A. L. Barabasi, Linked: How Everything is Connected to Everything Else and What It Means, Persus Publishing, Cambridge, 2002.
[3]	B. Bollobas, Modern Graph Theory, Springer, New York, 1998. doi: 10.1007/978-1-4612-0619-4.
[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.
[5]	U. Brandes, A faster algorithm for betweenness centrality, J. Math. Sociol., 25 (2001), 163-177. doi: 10.1080/0022250X.2001.9990249.
[6]	G. Caporossi, M. Paiva, D. Vukicevic and M. Segatto, Centrality and betweenness: Vertex and edge decomposition of the Wiener index, MATCH Commun. Math. Comput. Chem, 68 (2012), 293-302.
[7]	C. Dangalchev, Residual closeness and generalized closeness, International Journal of Foundations of Computer Science, 22 (2011), 1939-1948. doi: 10.1142/S0129054111009136.
[8]	L. Freeman, A set of measures of centrality based on betweenness, Sociometry, 40 (1977), 35-41. doi: 10.2307/3033543.
[9]	L. Freeman, Centrality in social networks: Conceptual clarification, Social Networks, 1 (1978), 215-239. doi: 10.1016/0378-8733(78)90021-7.
[10]	S. Gago, J. Coroničová Hurajová and T. Mandaras, On decay centrality in graphs, Mathematica Scandinavica, 123 (2018), 39-50. doi: 10.7146/math.scand.a-106210.
[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.
[12]	M. E. J. Newman, Networks: An Introduction, Oxford University Press, Oxford, 2010. doi: 10.1093/acprof:oso/9780199206650.001.0001.
[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.

show all references

References:

[1]	S. Antunovic, T. Kokan, T. Vojkovic and D. Vukicevic, Generalised network descriptors, Glasnik Matematicki, 48 (2013), 211-230. doi: 10.3336/gm.48.2.01.
[2]	A. L. Barabasi, Linked: How Everything is Connected to Everything Else and What It Means, Persus Publishing, Cambridge, 2002.
[3]	B. Bollobas, Modern Graph Theory, Springer, New York, 1998. doi: 10.1007/978-1-4612-0619-4.
[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.
[5]	U. Brandes, A faster algorithm for betweenness centrality, J. Math. Sociol., 25 (2001), 163-177. doi: 10.1080/0022250X.2001.9990249.
[6]	G. Caporossi, M. Paiva, D. Vukicevic and M. Segatto, Centrality and betweenness: Vertex and edge decomposition of the Wiener index, MATCH Commun. Math. Comput. Chem, 68 (2012), 293-302.
[7]	C. Dangalchev, Residual closeness and generalized closeness, International Journal of Foundations of Computer Science, 22 (2011), 1939-1948. doi: 10.1142/S0129054111009136.
[8]	L. Freeman, A set of measures of centrality based on betweenness, Sociometry, 40 (1977), 35-41. doi: 10.2307/3033543.
[9]	L. Freeman, Centrality in social networks: Conceptual clarification, Social Networks, 1 (1978), 215-239. doi: 10.1016/0378-8733(78)90021-7.
[10]	S. Gago, J. Coroničová Hurajová and T. Mandaras, On decay centrality in graphs, Mathematica Scandinavica, 123 (2018), 39-50. doi: 10.7146/math.scand.a-106210.
[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.
[12]	M. E. J. Newman, Networks: An Introduction, Oxford University Press, Oxford, 2010. doi: 10.1093/acprof:oso/9780199206650.001.0001.
[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.

Figure 1. A broom that minimizes $mt_{\lambda }^{e}(G)$

Figure Options

Download full-size image

Download as PowerPoint slide

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}$

Table Options

Download as excel

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]	Rumi Ghosh, Kristina Lerman. Rethinking centrality: The role of dynamical processes in social network analysis. Discrete & Continuous Dynamical Systems - B, 2014, 19 (5) : 1355-1372. doi: 10.3934/dcdsb.2014.19.1355
[2]	Zuolin Shen, Junjie Wei. Hopf bifurcation analysis in a diffusive predator-prey system with delay and surplus killing effect. Mathematical Biosciences & Engineering, 2018, 15 (3) : 693-715. doi: 10.3934/mbe.2018031
[3]	Wuyuan Jiang. The maximum surplus before ruin in a jump-diffusion insurance risk process with dependence. Discrete & Continuous Dynamical Systems - B, 2019, 24 (7) : 3037-3050. doi: 10.3934/dcdsb.2018298
[4]	David Colton, Lassi Päivärinta, John Sylvester. The interior transmission problem. Inverse Problems & Imaging, 2007, 1 (1) : 13-28. doi: 10.3934/ipi.2007.1.13
[5]	Hui Wan, Jing-An Cui. A model for the transmission of malaria. Discrete & Continuous Dynamical Systems - B, 2009, 11 (2) : 479-496. doi: 10.3934/dcdsb.2009.11.479
[6]	Fioralba Cakoni, Drossos Gintides. New results on transmission eigenvalues. Inverse Problems & Imaging, 2010, 4 (1) : 39-48. doi: 10.3934/ipi.2010.4.39
[7]	Andreas Kirsch. On the existence of transmission eigenvalues. Inverse Problems & Imaging, 2009, 3 (2) : 155-172. doi: 10.3934/ipi.2009.3.155
[8]	Jiangtao Mo, Liqun Qi, Zengxin Wei. A network simplex algorithm for simple manufacturing network model. Journal of Industrial & Management Optimization, 2005, 1 (2) : 251-273. doi: 10.3934/jimo.2005.1.251
[9]	Mahin Salmani, P. van den Driessche. A model for disease transmission in a patchy environment. Discrete & Continuous Dynamical Systems - B, 2006, 6 (1) : 185-202. doi: 10.3934/dcdsb.2006.6.185
[10]	Vesselin Petkov, Georgi Vodev. Localization of the interior transmission eigenvalues for a ball. Inverse Problems & Imaging, 2017, 11 (2) : 355-372. doi: 10.3934/ipi.2017017
[11]	Burcu Adivar, Ebru Selin Selen. Compartmental disease transmission models for smallpox. Conference Publications, 2011, 2011 (Special) : 13-21. doi: 10.3934/proc.2011.2011.13
[12]	Angela Cadena, Adriana Marcucci, Juan F. Pérez, Hernando Durán, Hernando Mutis, Camilo Taútiva, Fernando Palacios. Efficiency analysis in electricity transmission utilities. Journal of Industrial & Management Optimization, 2009, 5 (2) : 253-274. doi: 10.3934/jimo.2009.5.253
[13]	Armin Lechleiter. The factorization method is independent of transmission eigenvalues. Inverse Problems & Imaging, 2009, 3 (1) : 123-138. doi: 10.3934/ipi.2009.3.123
[14]	Didier Aussel, Rafael Correa, Matthieu Marechal. Electricity spot market with transmission losses. Journal of Industrial & Management Optimization, 2013, 9 (2) : 275-290. doi: 10.3934/jimo.2013.9.275
[15]	Luc Robbiano. Counting function for interior transmission eigenvalues. Mathematical Control & Related Fields, 2016, 6 (1) : 167-183. doi: 10.3934/mcrf.2016.6.167
[16]	Christopher M. Kribs-Zaleta. Alternative transmission modes for Trypanosoma cruzi . Mathematical Biosciences & Engineering, 2010, 7 (3) : 657-673. doi: 10.3934/mbe.2010.7.657
[17]	Konstantin Avrachenkov, Giovanni Neglia, Vikas Vikram Singh. Network formation games with teams. Journal of Dynamics & Games, 2016, 3 (4) : 303-318. doi: 10.3934/jdg.2016016
[18]	Joanna Tyrcha, John Hertz. Network inference with hidden units. Mathematical Biosciences & Engineering, 2014, 11 (1) : 149-165. doi: 10.3934/mbe.2014.11.149
[19]	T. S. Evans, A. D. K. Plato. Network rewiring models. Networks & Heterogeneous Media, 2008, 3 (2) : 221-238. doi: 10.3934/nhm.2008.3.221
[20]	David J. Aldous. A stochastic complex network model. Electronic Research Announcements, 2003, 9: 152-161.

2017 Impact Factor: 0.564

Tools

Metrics

Tools

Article outline

Figures and Tables

2017 Impact Factor: 0.564

Tools

Figures and Tables

2017 Impact Factor: 0.564

American Institute of Mathematical Sciences