The Star Degree Centrality Problem: A Decomposition Approach

References

• Adulyasak Y, Cordeau JF, Jans R (2015) Benders decomposition for production routing under demand uncertainty. Oper. Res. 63(4):851–867.Link, Google Scholar
• Ahat B, Ekim T, Taşkin ZC (2017) Integer programming formulations and Benders decomposition for the maximum induced matching problem. INFORMS J. Comput. 30(1):43–56.Link, Google Scholar
• Ashtiani M, Salehzadeh-Yazdi A, Razaghi-Moghadam Z, Hennig H, Wolkenhauer O, Mirzaie M, Jafari M (2018) A systematic survey of centrality measures for protein-protein interaction networks. BMC Systems Biol. 12(1):80.Crossref, Google Scholar
• Bai L, Rubin PA (2009) Combinatorial Benders cuts for the minimum tollbooth problem. Oper. Res. 57(6):1510–1522.Link, Google Scholar
• Banerjee A, Chandrasekhar AG, Duflo E, Jackson MO (2013) The diffusion of microfinance. Sci. 341(6144):1236498.Crossref, Google Scholar
• Bavelas A (1948) A mathematical model for group structures. Appl. Anthropology 7(3):16–30.Google Scholar
• Bavelas A (1950) Communication patterns in task-oriented groups. J. Acoustical Soc. Amer. 22(6):725–730.Crossref, Google Scholar
• Benders JF (1962) Partitioning procedures for solving mixed–variables programming problems. Numerische Mathematik 4(1):238–252.Crossref, Google Scholar
• Bhowmick SS, Seah BS (2015) Clustering and summarizing protein-protein interaction networks: A survey. IEEE Trans. Knowledge Data Engrg. 28(3):638–658.Crossref, Google Scholar
• Bonacich P (1972) Factoring and weighting approaches to status scores and clique identification. J. Math. Sociol. 2(1):113–120.Crossref, Google Scholar
• Bonacich P (1987) Power and centrality: A family of measures. Amer. J. Sociol. 92(5):1170–1182.Crossref, Google Scholar
• Botton Q, Fortz B, Gouveia L, Poss M (2013) Benders decomposition for the hop-constrained survivable network design problem. INFORMS J. Comput. 25(1):13–26.Link, Google Scholar
• Chen L, Miller-Hooks E (2012) Resilience: An indicator of recovery capability in intermodal freight transport. Transportation Sci. 46(1):109–123.Link, Google Scholar
• Contreras I, Cordeau JF, Laporte G (2011) Benders decomposition for large-scale uncapacitated hub location. Oper. Res. 59(6):1477–1490.Link, Google Scholar
• Cordeau JF, Furini F, Ljubić I (2019) Benders decomposition for very large scale partial set covering and maximal covering location problems. Eur. J. Oper. Res. 275(3):882–896.Crossref, Google Scholar
• Dalal J, Üster H (2017) Combining worst case and average case considerations in an integrated emergency response network design problem. Transportation Sci. 52(1):171–188.Link, Google Scholar
• Dangalchev C (2006) Residual closeness in networks. Physica A 365(2):556–564.Crossref, Google Scholar
• Emde S, Polten L, Gendreau M (2020) Logic-based benders decomposition for scheduling a batching machine. Comput. Oper. Res. 113:104777.Crossref, Google Scholar
• Estrada E (2006) Virtual identification of essential proteins within the protein interaction network of yeast. Proteomics 6(1):35–40.Crossref, Google Scholar
• Estrada E, Rodríguez-Velázquez JA (2005) Subgraph centrality in complex networks. Physical Rev. E 71:056103.Crossref, Google Scholar
• Everett MG, Borgatti SP (1999) The centrality of groups and classes. J. Math. Sociol. 23(3):181–201.Crossref, Google Scholar
• Everett MG, Borgatti SP (2005) Extending centrality. Models Methods Soc. Network Anal. 35(1):57–76.Crossref, Google Scholar
• Fischetti M, Ljubić I, Sinnl M (2016) Benders decomposition without separability: A computational study for capacitated facility location problems. Eur. J. Oper. Res. 253(3):557–569.Crossref, Google Scholar
• Fischetti M, Ljubić I, Sinnl M (2017) Redesigning benders decomposition for large-scale facility location. Management Sci. 63(7):2146–2162.Link, Google Scholar
• Frank SM, Rebennack S (2015) Optimal design of mixed AC-DC distribution systems for commercial buildings: A nonconvex generalized Benders decomposition approach. Eur. J. Oper. Res. 242(3):710–729.Crossref, Google Scholar
• Freeman LC (1978) Centrality in social networks conceptual clarification. Soc. Networks 1(3):215–239.Crossref, Google Scholar
• Holmberg K (1994) On using approximations of the Benders master problem. Eur. J. Oper. Res. 77(1):111–125.Crossref, Google Scholar
• IBM (2017) CPLEX user’s manual. Accessed December 4, 2020, https://www.ibm.com/support/knowledgecenter/SSSA5P_12.8.0/ilog.odms.studio.help/pdf/usrcplex.pdf.Google Scholar
• Igraph (2020) R igraph manual pages. Accessed December 7, 2020, https://igraph.org/r/doc.Google Scholar
• Jalili M, Salehzadeh-Yazdi A, Asgari Y, Arab SS, Yaghmaie M, Ghavamzadeh A, Alimoghaddam K (2015) Centiserver: A comprehensive resource, web-based application and R package for centrality analysis. PLoS One. 10(11):1–8.Crossref, Google Scholar
• Jeong H, Mason SP, Barabási AL, Oltvai ZN (2001) Lethality and centrality in protein networks. Nature 411(6833):41–42.Crossref, Google Scholar
• Joy MP, Brock A, Ingber DE, Huang S (2005) High-betweenness proteins in the yeast protein interaction network. BioMed Res. Internat. 2005(2):96–103.Google Scholar
• Kamath RS, Fraser AG, Dong Y, Poulin G, Durbin R, Gotta M, Kanapin A, et al. (2003) Systematic functional analysis of the Caenorhabditis elegans genome using RNAi. Nature 421(6920):231–237.Crossref, Google Scholar
• Kleitman DJ, Winston KJ (1982) On the number of graphs without 4-cycles. Discrete Math. 41(2):167–172.Crossref, Google Scholar
• Leavitt HJ (1951) Some effects of certain communication patterns on group performance. J. Abnormal Soc. Psych. 46(1):38–50.Crossref, Google Scholar
• Nasirian F, Pajouh FM, Balasundaram B (2020) Detecting a most closeness-central clique in complex networks. Eur. J. Oper. Res. 283(2):461–475.Crossref, Google Scholar
• Rahmaniani R, Crainic TG, Gendreau M, Rei W (2018) Accelerating the Benders decomposition method: Application to stochastic network design problems. SIAM J. Optim. 28(1):875–903.Crossref, Google Scholar
• Rasti S, Vogiatzis C (2019) A survey of computational methods in protein–protein interaction networks. Ann. Oper. Res. 276(1–2):35–87.Crossref, Google Scholar
• Rysz M, Pajouh FM, Pasiliao EL (2018) Finding clique clusters with the highest betweenness centrality. Eur. J. Oper. Res. 271(1):155–164.Crossref, Google Scholar
• Samotij W (2015) Counting independent sets in graphs. Eur. J. Combinatorics 48:5–18.Crossref, Google Scholar
• Schiermeyer I (2019) Maximum independent sets near the upper bound. Discrete Appl. Math. 266:186–190.Crossref, Google Scholar
• Sherali HD, Bae KH, Haouari M (2010) Integrated airline schedule design and fleet assignment: Polyhedral analysis and Benders’ decomposition approach. INFORMS J. Comput. 22(4):500–513.Link, Google Scholar
• Szklarczyk D, Franceschini A, Wyder S, Forslund K, Heller D, Huerta-Cepas J, Simonovic M, et al. (2014) String v10: Protein–protein interaction networks, integrated over the tree of life. Nucleic Acids Res. 43(D1):D447–D452.Crossref, Google Scholar
• Taşkin ZC, Smith JC, Romeijn HE (2012) Mixed-integer programming techniques for decomposing IMRT fluence maps using rectangular apertures. Ann. Oper. Res. 196(1):799–818.Crossref, Google Scholar
• Veremyev A, Prokopyev OA, Pasiliao EL (2017) Finding groups with maximum betweenness centrality. Optim. Methods Software 32(2):369–399.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 EL, Pardalos PM (2015) An integer programming approach for finding the most and the least central cliques. Optim. Lett. 9(4):615–633.Crossref, Google Scholar
• Wang J, Peng W, Wu FX (2013) Computational approaches to predicting essential proteins: A survey. Proteomics Clinical Appl. 7(1-2):181–192.Crossref, Google Scholar
• Wuchty S, Stadler PF (2003) Centers of complex networks. J. Theoretical Biol. 223(1):45–53.Crossref, Google Scholar