Centrality of Shortest Paths: Algorithms and Complexity Results

References

• Barabási AL, Albert R (1999) Emergence of scaling in random networks. Science 286(5439):509–512.Crossref, Google Scholar
• Batagelj V, Mrvar A (2006) Pajek datasets. Accessed September 1, 2024, https://sparse.tamu.edu/Pajek.Google Scholar
• Brandes U (2001) A faster algorithm for betweenness centrality. J. Math. Sociol. 25(2):163–177.Crossref, Google Scholar
• Brandes U (2008) On variants of shortest-path betweenness centrality and their generic computation. Soc. Networks 30(2):136–145.Crossref, Google Scholar
• Brandes U, Erlebach T (2005) Network Analysis: Methodological Foundations, Lecture Notes in Computer Science, 1st ed. (Springer, Berlin).Crossref, Google Scholar
• Camur MC, Vogiatzis C (2024) A survey on optimization studies of group centrality metrics. Networks 84(4):491–508.Crossref, Google Scholar
• Camur MC, Sharkey T, Vogiatzis C (2022) The star degree centrality problem: A decomposition approach. INFORMS J. Comput. 34(1):93–112.Link, Google Scholar
• Davis TA, Hu Y (2011) The University of Florida sparse matrix collection. ACM Trans. Math. Software 38(1):1.Crossref, Google Scholar
• Dawande M, Mookerjee V, Sriskandarajah C, Zhu Y (2012) Structural search and optimization in social networks. INFORMS J. Comput. 24(4):611–623.Link, Google Scholar
• de Sá EM, Contreras I, Cordeau JF, de Camargo RS, de Miranda G (2015) The hub line location problem. Transportation Sci. 49(3):500–518.Link, Google Scholar
• Dijkstra EW (1959) A note on two problems in connexion with graphs. Numerische Mathematik 1(1):269–271.Crossref, Google Scholar
• Everett MG, Borgatti SP (1999) The centrality of groups and classes. J. Math. Sociol. 23(3):181–201.Crossref, Google Scholar
• Garey MR, Johnson DS (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness, A Series of Books in the Mathematical Sciences (W. H. Freeman, San Francisco).Google Scholar
• Girvan M, Newman ME (2002) Community structure in social and biological networks. Proc. Natl. Acad. Sci. USA 99(12):7821–7826.Crossref, Google Scholar
• Gómez R, Gutiérrez J (2023) Path eccentricity of graphs. Discrete Appl. Math. 337:1–13.Crossref, Google Scholar
• Guimerà R, Danon L, Díaz-Guilera A, Giralt F, Arenas A (2003) Self-similar community structure in a network of human interactions. Phys. Rev. E 68(6):065103.Crossref, Google Scholar
• Gutiérrez-Jarpa G, Donoso M, Obreque C, Marianov V (2010) Minimum cost path location for maximum traffic capture. Comput. Indust. Engrg. 58(2):332–341.Crossref, Google Scholar
• Hedetniemi SM, Cockayne EJ, Hedetniemi ST (1981) Linear algorithms for finding the Jordan center and path center of a tree. Transportation Sci. 15(2):98–114.Link, Google Scholar
• Krentel MW (1988) The complexity of optimization problems. J. Comput. Systems Sci. 36(3):490–509.Crossref, Google Scholar
• Kumar S, Spezzano F, Subrahmanian V, Faloutsos C (2016) Edge weight prediction in weighted signed networks. Bonchi F, Domingo-Ferrer J, Baeza-Yates R, Zhou Z-H, Wu X, eds. 2016 IEEE 16th Internat. Conf. Data Mining (ICDM) (IEEE, Piscataway, NJ), 221–230.Google Scholar
• Massa P, Salvetti M, Tomasoni D (2009) Bowling alone and trust decline in social network sites. Yang B, Zhu W, Dai Y, Yang LT, Ma J, eds. 2009 Eighth IEEE Internat. Conf. Dependable Autonomic Secure Comput. (IEEE, Piscataway, NJ), 658–663.Google Scholar
• Matsypura D, Veremyev A, Pasiliao EL, Prokopyev OA (2023) Finding the most degree-central walks and paths in a graph: Exact and heuristic approaches. Eur. J. Oper. Res. 308(3):1021–1036.Crossref, Google Scholar
• Peng S, Zhou Y, Cao L, Yu S, Niu J, Jia W (2018) Influence analysis in social networks: A survey. J. Network Comput. Appl. 106:17–32.Crossref, Google Scholar
• Phosavanh J, Matsypura D (2025) Centrality of shortest paths: Algorithms and complexity results. https://doi.org/10.1287/ijoc.2024.0945.cd, https://github.com/INFORMSJoC/2024.0945.Google Scholar
• Puzis R, Elovici Y, Dolev S (2007) Fast algorithm for successive computation of group betweenness centrality. Phys. Rev. E Statist. Nonlinear Soft Matter Phys. 76(5 Pt 2):056709.Crossref, Google Scholar
• Rossi R, Ahmed N (2015) The network data repository with interactive graph analytics and visualization. Proc. AAAI Conf. Artificial Intelligence (AAAI Press, Palo Alto, CA).Google Scholar
• Sapiezynski P, Stopczynski A, Lassen DD, Lehmann S (2019) Interaction data from the Copenhagen Networks Study. Sci. Data 6(1):315.Crossref, Google Scholar
• Shimbel A (1953) Structural parameters of communication networks. Bull. Math. Biophysics 15(4):501–507.Crossref, Google Scholar
• Slater PJ (1982) Locating central paths in a graph. Transportation Sci. 16(1):1–18.Link, Google Scholar
• To WM (2015) Centrality of an urban rail system. Urban Rail Transit 1(4):249–256.Crossref, Google Scholar
• Vogiatzis C, Camur MC (2019) Identification of essential proteins using induced stars in protein–protein interaction networks. INFORMS J. Comput. 31(4):703–718.Link, Google Scholar
• Vogiatzis C, Veremyev A, Pasiliao E, Pardalos P (2015) An integer programming approach for finding the most and the least central cliques. Optim. Lett. 9:1–19.Crossref, Google Scholar
• Watts DJ, Strogatz SH (1998) Collective dynamics of ‘small-world’ networks. Nature 393(6684):440–442.Crossref, Google Scholar