Tree decompositions and social graphs

References

• J. Leskovec, K.J. Lang, A. Dasgupta, and M.W. Mahoney. Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters. Internet Mathematics, 6(1):29–123, 2009. Also available at: arXiv:0810.1355.
   Google Scholar
• L. G. S. Jeub, P. Balachandran, M. A. Porter, P. J. Mucha, and M. W. Mahoney. Think locally, act locally: Detection of small, medium-sized, and large communities in large networks. Physical Review E, 91:012821, 2015.
   Web of Science ®Google Scholar
• A. B. Adcock, B. D. Sullivan, and M. W. Mahoney. Tree-like structure in large social and information networks. In Proc. of the 2013 IEEE ICDM, pages 1–10, 2013.
   Google Scholar
• V. Batagelj and M. Zaversnik. Generalized cores. Technical report. Preprint: arXiv:cs.DS/0202039 (2002).
   Google Scholar
• V. Batagelj and M. Zaversnik. An O(m) algorithm for cores decomposition of networks. Technical report. Preprint: arXiv:cs.DS/0310049 (2003).
   Google Scholar
• V. Batagelj and M. Zaversnik. Fast algorithms for determining (generalized) core groups in social networks. Advances in Data Analysis and Classification, 5(2):129–145, 2011.
   Web of Science ®Google Scholar
• N. Robertson and P. D. Seymour. Graph minors. II. Algorithmic aspects of tree-width. Journal of Algorithms, 7(3):309–322, 1986.
   Web of Science ®Google Scholar
• S. Arnborg and A. Proskurowski. Linear time algorithms for NP-hard problems restricted to partial k-trees. Discrete Applied Mathematics, 23(1):11–24, 1989.
   Web of Science ®Google Scholar
• M. W. Bern, E. L. Lawler, and A. L. Wong. Linear-time computation of optimal subgraphs of decomposable graphs. Journal of Algorithms, 8(2):216–235, 1987.
   Web of Science ®Google Scholar
• A. M. C. A. Koster, S. P. M. van Hoesel, and A. W. J. Kolen. Solving partial constraint satisfaction problems with tree decomposition. Networks, pages 170–180, 2002.
   Web of Science ®Google Scholar
• J. Lagergren. Efficient parallel algorithms for graphs of bounded tree-width. Journal of Algorithms, 20(1):20–44, 1996.
   Web of Science ®Google Scholar
• I. V. Hicks, A. M. C. A. Koster, and E. Kolotoğlu. Branch and tree decomposition techniques for discrete optimization. TutORials in Operation Research: INFORMS–New\sOrleans, 2005.
   Google Scholar
• J. Zhao, R. L. Malmberg, and L. Cai. Rapid ab initio RNA folding including pseudoknots via graph tree decomposition. In Proceedings of the 6th International Workshop on Algorithms in Bioinformatics, pages 262–273, 2006.
   Google Scholar
• J. Zhao, D. Che, and L. Cai. Comparative pathway annotation with protein-DNA interaction and operon information via graph tree decomposition. In Pacific Symposium on Biocomputing, pages 496–507, 2007.
   PubMedGoogle Scholar
• C. Liu, Y. Song, B. Yan, Y. Xu, and L. Cai. Fast de novo peptide sequencing and spectral alignment via tree decomposition. In Pacific Symposium on Biocomputing, pages 255–266, 2006.
   PubMedGoogle Scholar
• S. L. Lauritzen and D. J. Spiegelhalter. Local computations with probabilities on graphical structures and their application to expert systems (with discussion). Journal of the Royal Statistical Society series B, 50:157–224, 1988.
   Google Scholar
• D. Karger and N. Srebro. Learning Markov networks: maximum bounded tree-width graphs. In Proceedings of the 12th ACM-SIAM Symposium on Discrete algorithms, pages 392–401, 2001.
   Google Scholar
• H. Chen. Quantified constraint satisfaction and bounded treewidth. In Proceedings of the 16th European Conference on Artificial Intelligence, pages 161–165, 2004.
   Google Scholar
• H. L. Bodlaender and R. H. Möhring. The pathwidth and treewidth of cographs. SIAM Journal on Discrete Mathematics, 6(2):181–188, 1993.
   Web of Science ®Google Scholar
• C. Chekuri and J. Chuzhoy. Polynomial bounds for the grid-minor theorem. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing, pages 60–69, 2014.
   Google Scholar
• P.D. Seymour and R. Thomas. Call routing and the ratcatcher. Combinatorica, 14(2):217–241, 1994.
   Web of Science ®Google Scholar
• H. L. Bodlaender and A. M. C. A. Koster. Treewidth computations I. Upper bounds. Inf. Comput., 208(3):259–275, 2010.
   Web of Science ®Google Scholar
• H. L. Bodlaender. A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM Journal on Computing, 25(6):1305–1317, 1996.
   Web of Science ®Google Scholar
• E. Amir. Approximation algorithms for treewidth. Algorithmica, 56(4):448–479, 2010.
   Web of Science ®Google Scholar
• H. Röhrig. Tree decomposition: a feasibility study. Master's thesis, Universität des Saarlandes, Saarbrücken, Germany, 1998.
   Google Scholar
• K. Shoikhet and D. Geiger. A practical algorithm for finding optimal triangulations. In Proceedings of AAAI/IAAI, pages 185–190, 1997.
   Google Scholar
• C. Groër, B. D. Sullivan, and D. Weerapurage. INDDGO: Integrated network decomposition & dynamic programming for graph optimization. Technical Report ORNL/TM-2012/176, Oak Ridge National Laboratory, 2012.
   Google Scholar
• B. D. Sullivan et al. Integrated Network Decompositions and Dynamic programming for Graph Optimization (INDDGO), 2012, 2013. http://github.com/bdsullivan/inddgo.
   Google Scholar
• F. Gavril. The intersection graphs of subtrees in trees are exactly the chordal graphs. Journal of Combinatorial Theory, Series B, 16(1):47–56, 1974.
   Google Scholar
• D. J. Rose and R. E. Tarjan. Algorithmic aspects of vertex elimination. In Proceedings of the 7th Annual ACM Symposium on Theory of Computing, pages 245–254, 1975.
   Google Scholar
• A. Berry, J. R. S. Blair, and P. Heggernes. Maximum cardinality search for computing minimal triangulations. In Proceeding of the 28th International Workshop on Graph-Theoretic Concepts in Computer Science, pages 1–12, 2002.
   Google Scholar
• A. Berry, J. R. S. Blair, P. Heggernes, and B. W. Peyton. Maximum cardinality search for computing minimal triangulations of graphs. Algorithmica, 39(4):287–298, 2004.
   Web of Science ®Google Scholar
• D. Rose, R. Tarjan, and G. Lueker. Algorithmic aspects of vertex elimination on graphs. SIAM Journal on Computing, 5:266–283, 1976.
   Google Scholar
• R. E. Tarjan and M. Yannakakis. Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM Journal on Computing, 13:566–579, 1984.
   Web of Science ®Google Scholar
• R. E. Tarjan and M. Yannakakis. Addendum: Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM Journal on Computing, 14(1):254–255, 1985.
   Web of Science ®Google Scholar
• A. Becker and D. Geiger. A sufficiently fast algorithm for finding close to optimal clique trees. Artificial Intelligence, 125(1–2):3–17, 2001.
   Web of Science ®Google Scholar
• H. L. Bodlaender, J. R. Gilbert, H. Hafsteinsson, and T. Kloks. Approximating treewidth, pathwidth, and minimum elimination tree height. Journal of Algorithms, 18:238–255, 1995.
   Web of Science ®Google Scholar
• V. Bouchitté, D. Kratsch, H. Müller, and I. Todinca. On treewidth approximations. Discrete Appl. Math., 136(2–3):183–196, 2004.
   Web of Science ®Google Scholar
• B. A. Reed. Finding approximate separators and computing tree width quickly. In Proceedings of the 24th Annual ACM Symposium on Theory of Computing, pages 221–228, 1992.
   Google Scholar
• J. A. George. Nested dissection of a regular finite element mesh. SIAM Journal of Numerical Analysis, 10:345–363, 1973.
   Web of Science ®Google Scholar
• J. R. Gilbert and R. E. Tarjan. The analysis of a nested dissection algorithm. Numerische Mathematik, 50(4):377–404, 1986.
   Web of Science ®Google Scholar
• G. Karypis and V. Kumar. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM Journal on Scientific Computing, 20:359–392, 1998.
   Web of Science ®Google Scholar
• H. M. Markowitz. The elimination form of the inverse and its application to linear programming. Management Science, 3(3):255–269, 1957.
   Web of Science ®Google Scholar
• P. R. Amestoy, T. A. Davis, and I. S. Duff. Algorithm 837: AMD, an approximate minimum degree ordering algorithm. ACM Transactions on Mathematical Software (TOMS), 30(3):381–388, 2004.
   Web of Science ®Google Scholar
• P. R. Amestoy, T. A. Davis, and I. S. Duff. An approximate minimum degree ordering algorithm. SIAM Journal on Matrix Analysis and Applications, 17(4):886–905, 1996.
   Web of Science ®Google Scholar
• D. Koller and N. Friedman. Probabilistic Graphical Models: Principles and Techniques. MIT Press, 2009.
   Google Scholar
• H. L. Bodlaender. A tourist guide through treewidth. Acta Cybernetica, 11:1–23, 1993.
   Google Scholar
• H. L. Bodlaender. Discovering treewidth. In Proceedings of the 31st international conference on Theory and Practice of Computer Science, pages 1–16, 2005.
   Google Scholar
• H. L. Bodlaender. Treewidth: Characterizations, applications, and computations. In Proceeding of the 32nd International Workshop on Graph-Theoretic Concepts in Computer Science, pages 1–14, 2006.
   Google Scholar
• H. L. Bodlaender and A. M. C. A. Koster. Combinatorial optimization on graphs of bounded treewidth. The Computer Journal, 51(3):255–269, 2007.
   Web of Science ®Google Scholar
• J. R. S. Blair and B. Peyton. An introduction to chordal graphs and clique trees. In A. George, J. R. Gilbert, and J. W. H. Liu, editors, Graph Theory and Sparse Matrix Computation, The IMA Volumes in Mathematics and its Applications, Volume 56, pages 1–29. Springer-Verlag, 1993.
   Google Scholar
• E. Amir. Efficient approximation for triangulation of minimum treewidth. In Proceedings of the 17th Annual Conference on Uncertainty in Artificial Intelligence, pages 7–15, 2001.
   Google Scholar
• A. M. C. A. Koster, H. L. Bodlaender, and S. P. M. van Hoesel. Treewidth: Computational experiments. Electronic Notes in Discrete Mathematics, 8:54–57, 2001.
   Google Scholar
• A. Berry, P. Heggernes, and G. Simonet. The minimum degree heuristic and the minimal triangulation process. In H. L. Bodlaender, editor, Graph-Theoretic Concepts in Computer Science, Lecture Notes in Computer Science, pages 58–70. Springer, 2003.
   Google Scholar
• P. Heggernes. Minimal triangulations of graphs: A survey. Discrete Mathematics, 306(3):297–317, 2006.
   Web of Science ®Google Scholar
• C. Wang, T. Liu, P. Cui, and K. Xu. A note on treewidth in random graphs. In Proceeding of the 5th International Conference on Combinatorial Optimization and Applications, pages 491–499, 2011.
   Google Scholar
• Y. Gao. Treewidth of Erdős-Rényi random graphs, random intersection graphs, and scale-free random graphs. Discrete Applied Mathematics, 160(4–5):566–578, 2012.
   Web of Science ®Google Scholar
• A. B. Adcock, B. D. Sullivan, O. R. Hernandez, and M. W. Mahoney. Evaluating OpenMP tasking at scale for the computation of graph hyperbolicity. In Proc. of the 9th IWOMP, pages 71–83, 2013.
   Google Scholar
• A. B. Adcock. Characterizing, identifying, and using tree-like structure in social and information networks. PhD thesis, Stanford University, 2014.
   Google Scholar
• M. Gromov. Hyperbolic groups. In S. M. Gersten, editor, Essays in Group Theory, Math. Sci. Res. Inst. Publ., 8, pages 75–263. Springer, 1987.
   Google Scholar
• J. M. Alonso, T. Brady, D. Cooper, V. Ferlini, M. Lustig, M. Mihalik, H. Shapiro, and H. Short. Notes on word hyperbolic groups. In E. Ghys, A. Haefliger, and A. Verjovski, editors, Group Theory from a Geometrical Viewpoint, ICTP Trieste Italy, pages 3–63. World Scientific, 1991.
   Google Scholar
• E. A. Jonckheere, P. Lohsoonthorn, and F. Bonahon. Scaled Gromov hyperbolic graphs. Journal of Graph Theory, 57(2):157–180, 2008.
   Web of Science ®Google Scholar
• E. A. Jonckheere, P. Lohsoonthorn, and F. Ariaei. Scaled Gromov four-point condition for network graph curvature computation. Internet Mathematics, 7(3):137–177, 2011.
   Google Scholar
• W. Chen, W. Fang, G. Hu, and M. W. Mahoney. On the hyperbolicity of small-world and tree-like random graphs. Internet Mathematics, 9(4):434–491, 2013. Also available at: arXiv:1201.1717.
   Google Scholar
• K. Verbeek and S. Suri. Metric embedding, hyperbolic space, and social networks. In Proceedings of the 30th Annual Symposium on Computational Geometry, pages 501–510, 2014.
   Google Scholar
• G. Brinkmann, J. H. Koolen, and V. Moulton. On the hyperbolicity of chordal graphs. Annals of Combinatorics, 5(1):61–69, 2001.
   Google Scholar
• Y. Wu and C. Zhang. Hyperbolicity and chordality of a graph. The Electronic Journal of Combinatorics, 18(1):P43, 2011.
   Google Scholar
• Y. Dourisboure and C. Gavoille. Tree-decompositions with bags of small diameter. Discrete Mathematics, 307(16):2008–2029, 2007.
   Web of Science ®Google Scholar
• D. Lokshtanov. On the complexity of computing treelength. In Proceedings of the 32nd international conference on Mathematical Foundations of Computer Science, pages 276–287, 2007.
   Google Scholar
• M. Grohe and D. Marx. On tree width, bramble size, and expansion. Journal of Combinatorial Theory Series B, 99(1):218–228, 2009.
   Web of Science ®Google Scholar
• A. Kosowski, B. Li, N. Nisse, and K. Suchan. k-chordal graphs: From cops and robber to compact routing via treewidth. In Proceedings of the 39th international colloquium conference on Automata, Languages, and Programming, pages 610–622, 2012.
   Google Scholar
• F. F. Dragan. Tree-like structures in graphs: A metric point of view. In Proceeding of the 39th International Workshop on Graph-Theoretic Concepts in Computer Science, pages 1–4, 2013.
   Google Scholar
• M. Abu-Ata and F. F. Dragan. Metric tree-like structures in real-life networks: an empirical study. Networks, 67(1):49–68, 2016.
   Web of Science ®Google Scholar
• M. M. Abu-Ata. Tree-Like Structure in Graphs and Embeddability to Trees. PhD thesis, Kent State University, 2014.
   Google Scholar
• Y. Shavitt and T. Tankel. Hyperbolic embedding of Internet graph for distance estimation and overlay construction. IEEE/ACM Transactions on Networking, 16(1):25–36, 2008.
   Web of Science ®Google Scholar
• M. P. Rombach, M. A. Porter, J. H. Fowler, and P. J. Mucha. Core-periphery structure in networks. SIAM Journal on Applied Mathematics, 74(1):167–190, 2014.
   Web of Science ®Google Scholar
• S. B. Seidman. Network structure and minimum degree. Social Networks, 5(3):269–287, 1983.
   Web of Science ®Google Scholar
• J. Ignacio Alvarez-Hamelin, L. Dall'Asta, A. Barrat, and A. Vespignani. Large scale networks fingerprinting and visualization using the k-core decomposition. In Annual Advances in Neural Information Processing Systems 18: Proceedings of the 2005 Conference, pages 41–50, 2006.
   Google Scholar
• J. Ignacio Alvarez-Hamelin, L. Dall'Asta, A. Barrat, and A. Vespignani. K-core decomposition of internet graphs: hierarchies, self-similarity and measurement biases. Networks and Heterogeneous Media, 3(2):371–393, 2008.
   Web of Science ®Google Scholar
• J. Healy, J. Janssen, E. Milios, and W. Aiello. Characterization of graphs using degree cores. In WAW ’08: Proceedings of the 6th Workshop on Algorithms and Models for the Web-Graph, pages 137–148, 2008.
   Google Scholar
• V. Batagelj and A. Mrvar. Pajek—analysis and visualization of large networks. In Proceedings of Graph Drawing, pages 477–478, 2001.
   Google Scholar
• J. Cheng, Y. Ke, S. Chu, and M. T. Ozsu. Efficient core decomposition in massive networks. In Proceedings of the 27th IEEE International Conference on Data Engineering, pages 51–62, 2011.
   Google Scholar
• P. Colomer-de Simon, A. Serrano, M. G. Beiro, J. Ignacio Alvarez-Hamelin, and M. Boguna. Deciphering the global organization of clustering in real complex networks. Scientific Reports, 3:2517, 2013.
   Google Scholar
• M. Kitsak, L. K. Gallos, S. Havlin, F. Liljeros, L. Muchnik, H. E. Stanley, and H. A. Makse. Identification of influential spreaders in complex networks. Nature Physics, 6(11):888–893, 2010.
   Web of Science ®Google Scholar
• J. Ugander, L. Backstrom, C. Marlow, and J. Kleinberg. Structural diversity in social contagion. Proceedings of the National Academy of Sciences, 109(16):5962–5966, 2012.
   Google Scholar
• V. Ramasubramanian, D. Malkhi, F. Kuhn, M. Balakrishnan, A. Gupta, and A. Akella. On the treeness of internet latency and bandwidth. In Proceedings of the 2009 ACM SIGMETRICS International Conference on Measurement and modeling of computer systems, pages 61–72, 2009.
   Google Scholar
• F. de Montgolfier, M. Soto, and L. Viennot. Treewidth and hyperbolicity of the internet. In Proceedings of the 10th IEEE International Symposium on Network Computing and Applications (NCA), pages 25–32, 2011.
   Google Scholar
• T. Maehara, T. Akiba, Y. Iwata, and K. Kawarabayashi. Computing personalized PageRank quickly by exploiting graph structures. Proceedings of the VLDB Endowment, 7:1023–1034, 2014.
   Google Scholar
• B. Courcelle and M. Mosbah. Monadic second-order evaluations on tree-decomposable graphs. Theoretical Computer Science, 109(1–2):49–82, 1993.
   Web of Science ®Google Scholar
• A. G. Percus, G. Istrate, B. Goncalves, R. Z. Sumi, and S. Boettcher. The peculiar phase structure of random graph bisection. Journal of Mathematical Physics, 49(12):125219, 2008.
   Web of Science ®Google Scholar
• F.R.K. Chung and L. Lu. Complex Graphs and Networks, volume 107 of CBMS Regional Conference Series in Mathematics. American Mathematical Society, 2006.
   Google Scholar
• Supporting website. http://snap.stanford.edu/data/index.html.
   Google Scholar
• A. L. Traud, P. J. Mucha, and M. A. Porter. Social structure of Facebook networks. Physica A, 391:4165–4180, 2012.
   Web of Science ®Google Scholar
• L.A. Adamic and N. Glance. The political blogosphere and the 2004 U.S. election: divided they blog. In LinkKDD ’05: Proceedings of the 3rd International Workshop on Link Discovery, pages 36–43, 2005.
   Google Scholar
• D.J. Watts and S.H. Strogatz. Collective dynamics of small-world networks. Nature, 393:440–442, 1998.
   PubMed Web of Science ®Google Scholar
• E. R. Gansner and S. C. North. An open graph visualization system and its applications to software engineering. Software—Practice and Experience, 30(11):1203–1233, 2000.
   Web of Science ®Google Scholar
• T. A. Davis and Y. Hu. The University of Florida Sparse Matrix Collection. ACM Transactions on Mathematical Software (TOMS), 38(1):1:1–1:25, 2011.
   Google Scholar
• T. Malisiewicz. Open source code: Graphviz matlab magic. https://github.com/quantombone/graphviz_matlab_magic, May 2010.
   Google Scholar
• P. Erdős and A. Rényi. On the evolution of random graphs. Publ. Math. Inst. Hungar. Acad. Sci., 5:17–61, 1960.
   Google Scholar
• B. Bollobás. Random Graphs. Academic Press, London, 1985.
   Google Scholar
• R. Andersen, F.R.K. Chung, and K. Lang. Local graph partitioning using PageRank vectors. In FOCS ’06: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, pages 475–486, 2006.
   Google Scholar
• R. Diestel and M. Müller. Connected tree-width. Technical report. Preprint: arXiv:arXiv:1211.7353 (2012).
   Google Scholar
• F. F. Dragan and I. Lomonosov. On compact and efficient routing in certain graph classes. Discrete Applied Mathematics, 155(11):1458–1470, 2007.
   Web of Science ®Google Scholar
• V. Chepoi, F. Dragan, B. Estellon, M. Habib, and Y. Vaxès. Diameters, centers, and approximating trees of δ-hyperbolic geodesic spaces and graphs. In Proceedings of the 24th Annual Symposium on Computational Geometry, pages 59–68, 2008.
   Google Scholar
• F. Reidl and B. Sullivan. Personal communication, 2014.
   Google Scholar
• P. Bellenbaum and R. Diestel. Two short proofs concerning tree-decompositions. Combinatorics, Probability, and Computing, 11:541–547, 2002.
   Web of Science ®Google Scholar
• A. Georgakopoulos and P. Sprussel. Geodesic topological cycles in locally finite graphs. The Electronic Journal of Combinatorics, 16(1):R144, 2009.
   Google Scholar