World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

Shapley Distance and Shapley Index for Some Special Graphs

    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. L. Shapley, 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). CrossrefGoogle Scholar
    • 2. A. Jonnalagadda and L. Kuppusamy, A cooperative game framework for detecting overlapping communities in social networks, Phys. A 491 (2018) 498–515. Crossref, ISIGoogle Scholar
    • 3. O. Skibski, T. Rahwan, T. P. Michalak and M. Wooldridge, 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, ISIGoogle Scholar
    • 4. R. Narayanam and Y. Narahari, A Shapley value-based approach to discover influential nodes in social networks, IEEE Trans. Autom. Sci. Eng. 8(1) (2011) 130–147. Crossref, ISIGoogle Scholar
    • 5. J. Tang, F. Y. Meng and Q. Zhang, Characterizations of a Shapley value for multichoice games, Int. J. Gen. Syst. 48(2) (2019) 186–209. Crossref, ISIGoogle Scholar
    • 6. Y. Hadas, G. Gnecco and M. Sanguineti, An approach to transportation network analysis via transferable utility games, Transp. Res. Part B 105 (2017) 120–143. Crossref, ISIGoogle Scholar
    • 7. S. Sharma and A. R. Abhyankar, Loss allocation for weakly meshed distribution system using analytical formulation of Shapley value, IEEE Trans. Power Syst. 32(2) (2017) 1369–1377. ISIGoogle Scholar
    • 8. K. A. Schouhamer Immink and J. H. Weber, Hybrid minimum pearson and Euclidean distance detection, IEEE Trans. Commun. 63(9) (2015) 3290–3298. Crossref, ISIGoogle Scholar
    • 9. S. Jayanth and A. Venkat, Application of mahalanobis distance as a lean assessment metric, Int. J. Adv. Manuf. Technol. 29(11-12) (2006) 1159–1168. Crossref, ISIGoogle Scholar
    • 10. T. Li, H. Dong, Y. T. Shi and M. Dehmer, A comparative analysis of new graph distance measures and graph edit distance, Inf. Sci. 403–404 (2017) 15–21. Crossref, ISIGoogle Scholar
    • 11. M. Senoussaoui, P. Kenny, T. Stafylakis and P. Dumouchel, 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. CrossrefGoogle Scholar
    • 12. J. M. Gallardo, N. Jiménez and A. Jiménez-Losada, A Shapley distance in graphs, Inf. Sci. 432 (2018) 269–277. Crossref, ISIGoogle Scholar
    • 13. H. Wiener, Structural determination of paraffin boiling points, J. Am. Chem. Soc. 69 (1947) 17–20. Crossref, ISIGoogle Scholar
    • 14. D. Bonchev, A. T. Balaban, X. Y. Liu and D. J. Klein, 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, ISIGoogle Scholar
    • 15. J. A. Bondy and U. S. R. Murty, Graph Theory, Graduate Texts in Mathematics, Vol. 244 (2008). CrossrefGoogle Scholar
    • 16. D. J. Klein and M. Randić, Resistance distance, J. Math. Chem. 12 (1993) 81–95. Crossref, ISIGoogle Scholar
    • 17. I. Lukovits, S. Nikolić and N. Trinajstić, Resistance distance in regular graphs, Int. J. Quantum Chem. 71(3) (1999) 217–225. Crossref, ISIGoogle Scholar
    • 18. D. J. Klein, Resistance-distance sum rules, Croat. Chem. Acta 75(2) (2002) 633–649. ISIGoogle Scholar
    • 19. S. V. Gervacio, Resistance distance in complete n-partite graphs, Discret. Appl. Math. 203 (2016) 53–61. Crossref, ISIGoogle Scholar
    • 20. A. A. Dobrynin, R. Entringer and I. Gutman, Wiener index of trees: Theory and applications, Acta Appl. Math. 66 (2001) 211–249. Crossref, ISIGoogle Scholar