/Tree-Decomposition

Primary LanguageC++

Graph Classification with Tree Decomposition

General

We aim to classify graphs by exploiting the relation between the width and core size of core-tree-decomposition. The concept is well explained in Chap. 5 of An Experimental Study of the Treewidth of Real-World Graph Data (Extended Version). The final goal is to find out some parameter or feature from such charts as Figure 6 in the paper that describes the characteristics of the grahs.

Version History

Version Date Commit Notes
0.1 September 26, 2020 9937d5a Read graph data and create a correct std::vector
0.2 September 27, 2020 b820dc5 Cleaned code and started again
0.3 September 27, 2020 0d1879e Completed strcut graph
0.4 October 16, 2020 600f395 Show width when reducing each node
0.5 October 16, 2020 2de6338 Compute # of nodes removed and width at the time
0.6 October 17, 2020 76d8af3 Create output file that python can read
0.7 October 17, 2020 e5d9f3d Added a Python file for creating charts
0.8 October 17, 2020 4cb5f4f make can create a chart from graph file
0.9 October 19, 2020 941a34d created update_width() and export_info()
0.10 October 27, 2020 61d9881 Decomposition takes max width size
0.11 October 30, 2020 f7a6a00 Added src/min-deg-heu_wo_pq.cpp
0.12 October 30, 2020 d42edfa src/without_pq.cpp can create a chart
0.13 October 30, 2020 9522597 computes degree distribution
0.14 October 31, 2020 1caceaf creates integrated charts
0.15 November 3, 2020 538f71d changed representation: from # of removed nodes to % of removed nodes
0.16 November 6, 2020 5cd58da modified filename rules
0.17 November 8, 2020 a6ea20a Added worst case series to integrated chart
0.18 November 9, 2020 6fdee51 Set interval of plotting
0.19 November 9, 2020 cf56ce7 Refactored worst and random
0.20 November 9, 2020 c47f8f2 First version of src/walk.cpp
0.21 November 21, 2020 84cf670 First version of src/walk.cpp
1.0 December 6, 2020 ebdfc13 Theme fixed!
1.1 December 10, 2020 43fea4b Implemented strahler number
1.2 December 12, 2020 06b8c6e Changed proposed method names
1.3 December 17, 2020 75300e5 Added program tracing metric values over steps
1.4 December 17, 2020 f65d061 Added program tracing metric values over degree of start node
1.5 December 27, 2020 8f06be Added depth-bagsize chart
1.6 December 27, 2020 b08dfb4 Added l-max-dh
2.0 January 7, 2020 f17b219 Theme Changed II
2.1 January 8, 2020 beaa460 Added C++ codes for graph, tree decomposition, and community
2.2 January 8, 2020 c6caad7 subtree size over community size
2.3 January 8, 2020 dcbfd0e chart programm integrated

C++ Version

We recommend to use C++ 20 when you run the codes.

Git Clone to Your Local Machine

git clone https://github.com/TeraokaKanekoLab/Tree-Decomposition.git

Graph Data File Format

The graph data files need to follow the rule below. <endpoint n> needs to be int (edge No.)

<endpoint 1> <endpoint 2>
<endpoint 3> <endpoint 4>
.
.
.

Let's say there is a graph like this.

The following data (graph/simple_graph.gr) represents this simple graph with 9 nodes and 12 edges, which are <0, 1>, ..., <6, 8>.

0 1
0 2
1 2
1 3
2 3
2 6
3 4
3 5
4 7
5 7
5 8
6 8

How to Run the Program

You might want to get a result instantly. Try this, and you get some charts tree decomposition of width 3 of simple_graph.gr. Note that the graph file extension needs to be .gr.

sh exe.sh all simple_graph 3

References

  1. T. Akiba, C. Sommer, and K. Kawarabayashi. Shortest-path queries for complex networks: exploiting low tree-width outside the core. In EDBT, pages 144–155, 2012.
  2. A. Berry, P. Heggernes, and G. Simonet. The minimum degree heuristic and the minimal triangulation process. In Graph-Theoretic Concepts in Computer Science, volume 2880, pages 58–70. 2003.
  3. H. L. Bodlaender. A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput., 25(6):1305–1317, 1996.
  4. H. L. Bodlaender. Treewidth: Characterizations, applications, and computations. In Graph-Theoretic Concepts in Computer Science, pages 1–14, 2006.
  5. J. Lescovec. Stanford Large Network Dataset Collection.
  6. T. Maehara, T. Akiba, Y. Iwata, and K. Kawarabayashi. Computing personalized pagerank quickly by exploiting graph structures. Proceedings of the VLDB Endowment, 7(12):1023–1034, 2014.
  7. F. Malliaros, C. Giatsidis, A. Papadopoulos, M. Vazirgiannis. The Core Decomposition of Networks: Theory, Algorithms and Applications. The VLDB Journal, Springer, 2019.
  8. S. Maniu, P. Senellart, and S. Jog. An Experimental Study of the Treewidth of Real-World Graph Data. In 22nd International Conference on Database Theory, ICDT 2019, March 26-28, 2019, Lisbon, Portugal, pages 12:1–12:18, 2019.
  9. D. Ouyang, L. Qin, L. Chang, X. Lin, Y. Zhang, and Q. Zhu. 2018. When Hierarchy Meets 2-Hop-Labeling: Efficient Shortest Distance Queries on Road Networks. In Proceedings of the SIGMOD '18, pages 709–724.2018.
  10. R. Rossi, N. Ahmed. Network Repository. An Interactive Scientific Network Data Repository.
  11. F. Wei. Tedi: efficient shortest path query answering on graphs. In SIGMOD, pages 99–110, 2010.
  12. J. Xu, F. Jiao, and B. Berger. A tree-decomposition approach to protein structure prediction. In CSB, pages 247–256, 2005.