Shapley Distance and Shapley Index for Some Special Graphs
Abstract
The Shapley distance in a graph is defined based on Shapley value in cooperative game theory. It is used to measure the cost for a vertex in a graph to access another vertex. In this paper, we establish the Shapley distance between two arbitrary vertices for some special graphs, i.e., path, tree, cycle, complete graph, complete bipartite, and complete multipartite graph. Moreover, based on the Shapley distance, we propose a new index, namely Shapley index, and then compare Shapley index with Wiener index and Kirchhoff index for these special graphs. We also characterize the extremal graphs in which these three indices are equal.
References
- 1. ,
A value for n-person games , in eds. H. KuhnW. Tucker, Contributions to the Theory of Games, II,Ann. of Math. Studies , Vol. 28 (Princeton University Press, Princeton, NJ, 1953). Crossref, Google Scholar - 2. , A cooperative game framework for detecting overlapping communities in social networks, Phys. A 491 (2018) 498–515. Crossref, ISI, Google Scholar
- 3. , Enumerating connected subgraphs and computing the myerson and shapley values in graph-restricted games, ACM Trans. Intell. Syst. Technol. 10(2) (2019) 1–25. Crossref, ISI, Google Scholar
- 4. , A Shapley value-based approach to discover influential nodes in social networks, IEEE Trans. Autom. Sci. Eng. 8(1) (2011) 130–147. Crossref, ISI, Google Scholar
- 5. , Characterizations of a Shapley value for multichoice games, Int. J. Gen. Syst. 48(2) (2019) 186–209. Crossref, ISI, Google Scholar
- 6. , An approach to transportation network analysis via transferable utility games, Transp. Res. Part B 105 (2017) 120–143. Crossref, ISI, Google Scholar
- 7. , Loss allocation for weakly meshed distribution system using analytical formulation of Shapley value, IEEE Trans. Power Syst. 32(2) (2017) 1369–1377. ISI, Google Scholar
- 8. , Hybrid minimum pearson and Euclidean distance detection, IEEE Trans. Commun. 63(9) (2015) 3290–3298. Crossref, ISI, Google Scholar
- 9. , Application of mahalanobis distance as a lean assessment metric, Int. J. Adv. Manuf. Technol. 29(11-12) (2006) 1159–1168. Crossref, ISI, Google Scholar
- 10. , A comparative analysis of new graph distance measures and graph edit distance, Inf. Sci. 403–404 (2017) 15–21. Crossref, ISI, Google Scholar
- 11. , A study of the cosine distance-based mean shift for telephone speech diarization, IEEE/ACM Trans. Audio, Speech, Lang. Process. 22(1) (2014) 217–227. Crossref, Google Scholar
- 12. , A Shapley distance in graphs, Inf. Sci. 432 (2018) 269–277. Crossref, ISI, Google Scholar
- 13. , Structural determination of paraffin boiling points, J. Am. Chem. Soc. 69 (1947) 17–20. Crossref, ISI, Google Scholar
- 14. , Molecular cyclicity and centricity of polycyclic graphs. I. Cyclicity based on resistance distances or reciprocal distances, Int. J. Quantum Chem. 50(1) (1994) 1–20. Crossref, ISI, Google Scholar
- 15. , Graph Theory,
Graduate Texts in Mathematics , Vol. 244 (2008). Crossref, Google Scholar - 16. , Resistance distance, J. Math. Chem. 12 (1993) 81–95. Crossref, ISI, Google Scholar
- 17. , Resistance distance in regular graphs, Int. J. Quantum Chem. 71(3) (1999) 217–225. Crossref, ISI, Google Scholar
- 18. , Resistance-distance sum rules, Croat. Chem. Acta 75(2) (2002) 633–649. ISI, Google Scholar
- 19. , Resistance distance in complete -partite graphs, Discret. Appl. Math. 203 (2016) 53–61. Crossref, ISI, Google Scholar
- 20. , Wiener index of trees: Theory and applications, Acta Appl. Math. 66 (2001) 211–249. Crossref, ISI, Google Scholar


