Geodesic
Eccentricity of Networks with Structural Constraints
Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 4, pp. 1141-1162.

Voir la notice de l'article provenant de la source Library of Science

The eccentricity of a node v in a network is the maximum distance from v to any other node. In social networks, the reciprocal of eccentricity is used as a measure of the importance of a node within a network. The associated centralization measure then calculates the degree to which a network is dominated by a particular node. In this work, we determine the maximum value of eccentricity centralization as well as the most centralized networks for various classes of networks including the families of bipartite networks (two-mode data) with given partition sizes and tree networks with fixed number of nodes and fixed maximum degree. To this end, we introduce and study a new way of enumerating the nodes of a tree which might be of independent interest.
Keywords: eccentricity, network, bipartite graph, complex network, maximum degree 
@article{DMGT_2020_40_4_a13,
     author = {Krnc, Matja\v{z} and Sereni, Jean-S\'ebastien and \v{S}krekovski, Riste and Yilma, Zelealem B.},
     title = {Eccentricity of {Networks} with {Structural} {Constraints}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {1141--1162},
     publisher = {mathdoc},
     volume = {40},
     number = {4},
     year = {2020},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2020_40_4_a13/}
}
TY  - JOUR
AU  - Krnc, Matjaž
AU  - Sereni, Jean-Sébastien
AU  - Škrekovski, Riste
AU  - Yilma, Zelealem B.
TI  - Eccentricity of Networks with Structural Constraints
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2020
SP  - 1141
EP  - 1162
VL  - 40
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2020_40_4_a13/
LA  - en
ID  - DMGT_2020_40_4_a13
ER  - 
%0 Journal Article
%A Krnc, Matjaž
%A Sereni, Jean-Sébastien
%A Škrekovski, Riste
%A Yilma, Zelealem B.
%T Eccentricity of Networks with Structural Constraints
%J Discussiones Mathematicae. Graph Theory
%D 2020
%P 1141-1162
%V 40
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2020_40_4_a13/
%G en
%F DMGT_2020_40_4_a13
Krnc, Matjaž; Sereni, Jean-Sébastien; Škrekovski, Riste; Yilma, Zelealem B. Eccentricity of Networks with Structural Constraints. Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 4, pp. 1141-1162. http://geodesic.mathdoc.fr/item/DMGT_2020_40_4_a13/

[1] P. Bonacich, Simultaneous group and individual centralities, Soc. Netw. 13 (1991) 155–168. doi:10.1016/0378-8733(91)90018-O

[2] S.P. Borgatti and M.G. Everett, Network analysis of 2 -mode data, Soc. Netw. 19 (1997) 243–269. doi:10.1016/S0378-8733(96)00301-2

[3] A. Davis, B.B. Gardner and M.R. Gardner, Deep South: A Social Anthropological Study of Caste and Class (University of Chicago Press, Chicago, 1941).

[4] R. Dunbar, The social brain hypothesis, Evolutionary Anthropology 6 (1998) 178–190. doi:10.1016/S0378-8733(96)00301-2

[5] M.G. Everett, P. Sinclair and P. Dankelmann, Some centrality results new and old, J. Math. Sociol. 28 (2004) 215–227. doi:10.1080/00222500490516671

[6] K. Faust, Centrality in affiliation networks, Soc. Netw. 19 (1997) 157–191. doi:10.1016/S0378-8733(96)00300-0

[7] L.C. Freeman, A set of measures of centrality based on betweenness, Sociometry 40 (1977) 35–41. doi:10.2307/3033543

[8] L.C. Freeman, Centrality in social networks conceptual clarification, Soc. Netw. 1 (979) 215–239.

[9] P. Hage and F. Harary, Eccentricity and centrality in networks, Soc. Netw. 17 (1995) 57–63. doi:10.1016/0378-8733(94)00248-9

[10] C. Heuberger and S. Wagner, Maximizing the number of independent subsets over trees with bounded degree, J. Graph Theory 58 (2008) 49–68. doi:10.1002/jgt.20294

[11] C. Heuberger and S. Wagner, Chemical trees minimizing energy and Hosoya index, J. Math. Chem. 46 (2009) 214–230. doi:10.1007/s10910-008-9456-6

[12] A. Ilić, Eccentric connectivity index, in: Novel Molecular Structure Descriptors — Theory and Applications II, Mathematical Chemistry Monographs 9, I. Gutman and B. Furtula (Ed(s)), (University of Kragujevac and Faculty of Science Kragujevac, 2010) 139–168.

[13] C. Jordan, Sur les assemblages de lignes, J. Reine Angew. Math. 70 (1869) 185–190. doi:10.1515/crll.1869.70.185

[14] M. Krnc, J.-S. Sereni, R.Škrekovski and Z.B. Yilma, Closeness centralization measure for two-mode data of prescribed sizes, Netw. Sci. 4 (2016) 474–490. doi:0.1017/nws.2016.14

[15] J.A. McHugh, Algorithmic Graph Theory (Prentice-Hall, Inc., Upper Saddle River, NJ, 1990).

[16] M.E.J. Newman, Networks: An Introduction (Oxford University Press, Oxford, 2010). doi:10.1093/acprof:oso/9780199206650.001.0001

[17] P. Sinclair, Betweenness centralization for bipartite graphs, J. Math. Sociol. 29 (2004) 25–31. doi:10.1080/00222500590889730

[18] P. Sinclair, Erratum: Betweenness centralization for bipartite graphs, J. Math. Sociol. 29 (2005) 263–264. doi:10.1080/00222500590961630

[19] P. Sinclair, Network centralization with the Gil Schmidt power centrality index, Soc. Netw. 31 (2009) 214–219. doi:10.1016/j.socnet.2009.04.004

[20] S. Wasserman and K. Faust, Social Network Analysis: Methods and Applications (Cambridge University Press, Cambridge, 1994). doi:10.1017/CBO9780511815478

[21] D.B. West, Introduction to Graph Theory (Prentice Hall, Inc., Upper Saddle River, NJ, 1996).

[22] G. Yu, L. Feng and A. Ilić, On the eccentric distance sum of trees and unicyclic graphs, J. Math. Anal. Appl. 375 (2011) 99–107.