Finding groups with maximum betweenness centrality

References

• R. Albert and A.-L. Barabási, Statistical mechanics of complex networks, Rev. Modern Phys. 74 (2002), pp. 47–97. doi: 10.1103/RevModPhys.74.47
   Google Scholar
• R. Albert, I. Albert, and G.L. Nakarado, Structural vulnerability of the North American power grid, Phys. Rev. E 69(2) (2004), p. 025103. doi: 10.1103/PhysRevE.69.025103
   Web of Science ®Google Scholar
• J.M. Anthonisse, The rush in a directed graph, Stichting Mathematisch Centrum. Mathematische Besliskunde (BN 9/71) (1971), pp. 1–10.
   Google Scholar
• B. Balasundaram, S. Butenko, and I.V. Hicks, Clique relaxations in social network analysis: The maximum k-plex problem, Oper. Res. 59(1) (2011), pp. 133–142. doi: 10.1287/opre.1100.0851
   Web of Science ®Google Scholar
• A.-L. Barabási and R. Albert, Emergence of scaling in random networks, Science 286(5439) (1999), pp. 509–512. doi: 10.1126/science.286.5439.509
   PubMed Web of Science ®Google Scholar
• V. Batagelj and A. Mrvar, Pajek datasets, 2006. Available at http://vlado.fmf.uni-lj.si/pub/networks/data/ (accessed 13 October 2014).
   Google Scholar
• E. Bompard, D. Wu, and F. Xue, The concept of betweenness in the analysis of power grid vulnerability. Complexity in Engineering, 2010. COMPENG'10., IEEE, 2010, pp. 52–54.
   Google Scholar
• S.P. Borgatti, Centrality and network flow, Soc. Netw. 27(1) (2005), pp. 55–71. doi: 10.1016/j.socnet.2004.11.008
   Web of Science ®Google Scholar
• S.P. Borgatti and M.G. Everett, A graph-theoretic perspective on centrality, Soc. Netw. 28(4) (2006), pp. 466–484. doi: 10.1016/j.socnet.2005.11.005
   Web of Science ®Google Scholar
• S.P. Borgatti, M.G. Everett, and J.C. Johnson, Analyzing Social Networks, SAGE Publications Limited, London, UK, 2013.
   Google Scholar
• U. Brandes, A faster algorithm for betweenness centrality, J. Math. Sociol. 25(2) (2001), pp. 163–177. doi: 10.1080/0022250X.2001.9990249
   Web of Science ®Google Scholar
• U. Brandes, On variants of shortest-path betweenness centrality and their generic computation, Soc. Netw. 30(2) (2008), pp. 136–145. doi: 10.1016/j.socnet.2007.11.001
   Web of Science ®Google Scholar
• COLOR02/03/04: Graph Coloring and its Generalizations. Available at http://mat.gsia.cmu.edu/COLOR03/ (accessed 9 September 2013).
   Google Scholar
• P. Crucitti, V. Latora, M. Marchiori, and A. Rapisarda, Error and attack tolerance of complex networks, Phys. A 340(1) (2004), pp. 388–394. doi: 10.1016/j.physa.2004.04.031
   Web of Science ®Google Scholar
• A. Cuzzocrea, A. Papadimitriou, D. Katsaros, and Y. Manolopoulos, Edge betweenness centrality: A novel algorithm for qos-based topology control over wireless sensor networks, J. Netw. Comput. Appl. 35(4) (2012), pp. 1210–1217. doi: 10.1016/j.jnca.2011.06.001
   Web of Science ®Google Scholar
• T.A. Davis and Y. Hu, The University of Florida sparse matrix collection, ACM Trans. Math. Softw. 38(1) (2011), pp. 1–25.
   Web of Science ®Google Scholar
• DIMACS, 10th DIMACS Implementation Challenge, 2011. Available at http://www.cc.gatech.edu/dimacs10/index.shtml (accessed September 2013).
   Google Scholar
• S. Dolev, Y. Elovici, R. Puzis, and P. Zilberman, Incremental deployment of network monitors based on group betweenness centrality, Inform. Process. Lett. 109(20) (2009), pp. 1172–1176. doi: 10.1016/j.ipl.2009.07.019
   Web of Science ®Google Scholar
• D. Easley and J. Kleinberg, Networks, Crowds, and Markets: Reasoning about a Highly Connected World, Cambridge University Press, New York, NY, 2010.
   Google Scholar
• M. Ercsey-Ravasz, R.N. Lichtenwalter, N.V. Chawla, and Z. Toroczkai, Range-limited centrality measures in complex networks, Phys. Rev. E 85(6) (2012), p. 066103. doi: 10.1103/PhysRevE.85.066103
   Google Scholar
• M. Ercsey-Ravasz and Z. Toroczkai, Centrality scaling in large networks, Phys. Rev. Lett. 105(3) (2010), p. 038701. doi: 10.1103/PhysRevLett.105.038701
   Google Scholar
• P. Erdős and A. Rényi, On random graphs, Publ. Math. Debrecen 6 (1959), pp. 290–297.
   Google Scholar
• E. Estrada, Characterization of topological keystone species: Local, global and ‘meso-scale’ centralities in food webs, Ecol. Complex. 4(1) (2007), pp. 48–57. doi: 10.1016/j.ecocom.2007.02.018
   Web of Science ®Google Scholar
• M.G. Everett and S.P. Borgatti, The centrality of groups and classes, J. Math. Sociol. 23(3) (1999), pp. 181–201. doi: 10.1080/0022250X.1999.9990219
   Web of Science ®Google Scholar
• M.G. Everett and S.P. Borgatti, Extending centrality, Models Methods Soc. Netw. Anal. 35(1) (2005), pp. 57–76. doi: 10.1017/CBO9780511811395.004
   Google Scholar
• FICOTM Xpress Optimization Suite 7.5. Available at http://www.fico.com (accessed 15 May 2015).
   Google Scholar
• M. Fink and J. Spoerhase, Maximum betweenness centrality: Approximability and tractable cases, WALCOM: Algorithms and computation, Springer, 2011, pp. 9–20.
   Google Scholar
• L.C. Freeman, Centrality in social networks conceptual clarification, Soc. Netw. 1(3) (1979), pp. 215–239. doi: 10.1016/0378-8733(78)90021-7
   Web of Science ®Google Scholar
• N.E. Friedkin, Theoretical foundations for centrality measures, Amer. J. Sociol. 96(6) (1991), pp. 1478–1504. doi: 10.1086/229694
   Web of Science ®Google Scholar
• V. Gilsing, B. Nooteboom, W. Vanhaverbeke, G. Duysters, and A. van den Oord, Network embeddedness and the exploration of novel technologies: Technological distance, betweenness centrality and density, Res. Policy 37(10) (2008), pp. 1717–1731. doi: 10.1016/j.respol.2008.08.010
   Web of Science ®Google Scholar
• M. Girvan and M.E.J. Newman, Community structure in social and biological networks, Proc. Natl. Acad. Sci. 99(12) (2002), pp. 7821–7826. doi: 10.1073/pnas.122653799
   PubMed Web of Science ®Google Scholar
• A.M.M. González, B. Dalsgaard, and J.M. Olesen, Centrality measures and the importance of generalist species in pollination networks, Ecol. Complex. 7(1) (2010), pp. 36–43. doi: 10.1016/j.ecocom.2009.03.008
   Web of Science ®Google Scholar
• R.V. Gould and R.M. Fernandez, Structures of mediation: A formal approach to brokerage in transaction networks, Sociol. Methodol. (1989), pp. 89–126. doi: 10.2307/270949
   Google Scholar
• P. Holme, B.J. Kim, C.N. Yoon, and S.K. Han, Attack vulnerability of complex networks, Phys. Rev. E 65(5) (2002), p. 056109. doi: 10.1103/PhysRevE.65.056109
   Google Scholar
• V. Ishakian, D. Erdős, E. Terzi, and A. Bestavros, A framework for the evaluation and management of network centrality, SDM, SIAM, 2012, pp. 427–438.
   Google Scholar
• M.O. Jackson, Social and Economic Networks, Princeton University Press, Princeton, NJ, 2010.
   Google Scholar
• M.P. Joy, A. Brock, D.E. Ingber, and S. Huang, High-betweenness proteins in the yeast protein interaction network, BioMed Res. Int. 2005(2) (2005), pp. 96–103.
   Google Scholar
• E.D. Kolaczyk, D.B. Chua, and M. Barthélemy, Group betweenness and co-betweenness: Inter-related notions of coalition centrality, Soc. Netw. 31(3) (2009), pp. 190–203. doi: 10.1016/j.socnet.2009.02.003
   Web of Science ®Google Scholar
• L. Leydesdorff, Betweenness centrality as an indicator of the interdisciplinarity of scientific journals, J. Am. Soc. Inf. Sci. Technol. 58(9) (2007), pp. 1303–1319. doi: 10.1002/asi.20614
   Web of Science ®Google Scholar
• E. Moradi and B. Balasundaram, Finding a maximum k-club using the k-clique formulation and canonical hypercube cuts, Optim. Lett. (2015), forthcoming.
   Google Scholar
• A.E. Motter and Y.-C. Lai, Cascade-based attacks on complex networks, Phys. Rev. E 66(6) (2002), p. 065102.
   Web of Science ®Google Scholar
• Moviegalaxies. Available at http://moviegalaxies.com/ (accessed 3 April 2015).
   Google Scholar
• M.E.J. Newman, Networks: An Introduction, Oxford University Press, New York, NY, 2010.
   Google Scholar
• C.H. Papadimitriou and K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Courier Corporation, Englewood Cliffs, NJ, 1998.
   Google Scholar
• J. Pattillo, A. Veremyev, S. Butenko, and V. Boginski, On the maximum quasi-clique problem, Discrete Appl. Math. 161(1) (2013), pp. 244–257. doi: 10.1016/j.dam.2012.07.019
   Web of Science ®Google Scholar
• J. Pattillo, N. Youssef, and S. Butenko, On clique relaxation models in network analysis, European J. Oper. Res. 226(1) (2013), pp. 9–18. doi: 10.1016/j.ejor.2012.10.021
   Web of Science ®Google Scholar
• F.R. Pitts, The medieval river trade network of Russia revisited, Soc. Netw. 1(3) (1979), pp. 285–292. doi: 10.1016/0378-8733(78)90025-4
   Web of Science ®Google Scholar
• R. Puzis, Y. Elovici, and S. Dolev, Finding the most prominent group in complex networks, AI Commun. 20(4) (2007), pp. 287–296.
   Web of Science ®Google Scholar
• R. Puzis, Y. Altshuler, Y. Elovici, S. Bekhor, Y. Shiftan, and A. Pentland, Augmented betweenness centrality for environmentally aware traffic monitoring in transportation networks, J. Intell. Transp. Syst. 17(1) (2013), pp. 91–105. doi: 10.1080/15472450.2012.716663
   Web of Science ®Google Scholar
• A. Shimbel, Structural parameters of communication networks, Bull. Math. Biophys. 15(4) (1953), pp. 501–507. doi: 10.1007/BF02476438
   Google Scholar
• A. Veremyev and V. Boginski, Identifying large robust network clusters via new compact formulations of maximum k-club problems, European J. Oper. Res. 218(2) (2012), pp. 316–326. doi: 10.1016/j.ejor.2011.10.027
   Web of Science ®Google Scholar
• A. Veremyev, O.A. Prokopyev, V. Boginski, and E.L. Pasiliao, Finding maximum subgraphs with relatively large vertex connectivity, European J. Oper. Res. 239(2) (2014), pp. 349–362. doi: 10.1016/j.ejor.2014.05.041
   Web of Science ®Google Scholar
• A. Veremyev, O.A. Prokopyev, S. Butenko, and E.L. Pasiliao, Exact MIP-based approaches for finding maximum quasi-cliques and dense subgraphs, Comput. Optim. Appl. (2015), forthcoming.
   PubMed Web of Science ®Google Scholar
• A. Veremyev, O.A. Prokopyev, and E.L. Pasiliao, Critical nodes for distance-based connectivity and related problems in graphs, Networks 66(3) (2015), pp. 170–195. doi: 10.1002/net.21622
   Web of Science ®Google Scholar
• C. Vogiatzis, A. Veremyev, E.L Pasiliao, and P.M. Pardalos, An integer programming approach for finding the most and the least central cliques, Optim. Lett. 9(4) (2015), pp. 615–633. doi: 10.1007/s11590-014-0782-2
   Web of Science ®Google Scholar
• S. Wasserman, Social Network Analysis: Methods and Applications, Vol. 8, Cambridge University Press, New York, NY, 1994.
   Google Scholar
• D.J. Watts and S.H. Strogatz, Collective dynamics of ‘small-world’ networks, Nature 393(6684) (1998), pp. 440–442. doi: 10.1038/30918
   PubMed Web of Science ®Google Scholar
• J. Yoon, A. Blumer, and K. Lee, An algorithm for modularity analysis of directed and weighted biological networks based on edge-betweenness centrality, Bioinformatics 22(24) (2006), pp. 3106–3108. doi: 10.1093/bioinformatics/btl533
   PubMed Web of Science ®Google Scholar