Triangle Counting Task

A Triangle Counting Task is a ML Counting Task for triangles in a graph.

• Context:
  • It can range from being an Exact Triangle Counting Task to being an Approximate Triangle Counting Task.
  • It can be solved by a Triangle Counting System (that implements a Triangle Counting Algorithm).
• Example(s):
  • Distributed Triangle Counting (DistTC) Task,
  • Distributed Shared-Memory Parallel Triangle Counting Task,
  • KokkosKernels-based Triangle Counting Task,
  • Burkhardt's Triangle Counting Task,
  • Parallel Triangle Counting Task.
  • …
• Counter-Example(s):
  • Unigram Counting Task,
  • Leaf Counting Task,
  • Blood Cell Counting Task,
  • Bigram Counting Task,
  • Dynamic Itemset Counting (DIC) Task.
• See: Triangle Tiling.

---

---

References

2020

• (Samsi et al., 2020) ⇒ Siddharth Samsi, Jeremy Kepner, Vijay Gadepally, Michael Hurley, Michael Jones, Edward Kao, Sanjeev Mohindra, Albert Reuther, Steven Smith, William Song, Diane Staheli, Paul Monticciolo (2020). "GraphChallenge. org Triangle Counting Performance". In: Preprint arXiv:2003.09269.
  • QUOTE: The number of triangles in a given graph $G$ can be calculated in several ways. We highlight two algorithms based on linear algebra primitives. The first algorithm proposed by Wolf et al. (2015) uses an overloaded matrix multiplication approach on the adjacency and incidence matrices of the graph and is shown in Algorithm 1. The second approach proposed by Burkhardt et al (2016) uses only the adjacency matrix of the given graph and is shown in Algorithm 2.

2019

• (Hoang et al., 2019) ⇒ Loc Hoang, Vishwesh Jatala, Xuhao Chen, Udit Agarwal, Roshan Dathathri, Gurbinder Gill, and Keshav Pingali (2019, September). "DistTC: High Performance Distributed Triangle Counting". In: The Proceedings of the 2019 IEEE High Performance Extreme Computing Conference (HPEC) (pp. 1-7). IEEE.

2018

• (Kanewala et al., 2018) ⇒ Thejaka Amila Kanewala, Marcin Zalewski, and Andrew Lumsdaine (2018, July). "Distributed, Shared-Memory Parallel Triangle Counting". In: Proceedings of the Platform for Advanced Scientific Computing Conference (pp. 1-12).

2017a

• (Wolf et al., 2017) ⇒ Michael M. Wolf, Mehmet Deveci, Jonathan W. Berry, Simon D. Hammond, and Sivasankaran Rajamanickam (2017, September). "Fast Linear Algebra-Based Triangle Counting with KokkosKernels". In: The Proceedings of the 2017 IEEE High Performance Extreme Computing Conference (HPEC) (pp. 1-7). IEEE.

2017b

• (Burkhardt, 2017) ⇒ Paul Burkhardt (2017). "Graphing Trillions Of Triangles". In: Information Visualization, 16(3), 157-166.

2015a

• (Azad et al., 2015) ⇒ Ariful Azad, Aydın Buluc, and John Gilbert (2015, May). "Parallel Triangle Counting And Enumeration Using Matrix Algebra". In: The Proceedings of the 2015 IEEE International Parallel and Distributed Processing Symposium Workshop (pp. 804-811). IEEE.

2015b

• (Wolf et al., 2015) ⇒ Michael M. Wolf, Jonathan W. Berry, and Dylan T. Stark (2015, September). "A Task-Based Linear Algebra Building Blocks Approach For Scalable Graph Analytics". In: The Proceedings of the 2015 IEEE High Performance Extreme Computing Conference (HPEC) (pp. 1-6). IEEE.

2014

• http://mathworld.wolfram.com/TriangleCounting.html
  • QUOTE: Given rods of length 1, 2, ..., n, how many distinct triangles T(n) can be made? Lengths for which [math]\displaystyle{ l_i\gt =l_j+l_k \ (1) }[/math] obviously do not give triangles, but all other combinations of three rods do. The answer is : [math]\displaystyle{ T(n) = \begin{cases} \frac{1}{24} n(n-2)(2n-5), & \mbox{for } n \mbox{ even} \\ \frac{1}{24} (n-1)(n-3)(2n-1) & \mbox{for } n \mbox{ odd}. \end{cases} (2) }[/math] The values for n=1, 2, ... are 0, 0, 0, 1, 3, 7, 13, 22, 34, 50, ... (OEIS A002623). Somewhat surprisingly, this sequence is also given by the generating function : [math]\displaystyle{ f(x)=\frac{(x^4)}{(1-x)^3(1-x^2)} =x^4+3x^5+7x^6+13x^7+.... }[/math]

2011

• (Tsourakakis et al., 2011) ⇒ Charalampos E. Tsourakakis (2011). "Counting Triangles In Real-World Networks Using Projections". In: Knowledge and Information Systems, 26(3), 501-520.

2009

• (Tsourakakis et al., 2009) ⇒ Charalampos E. Tsourakakis, Mihail N. Kolountzakis, and Gary L. Miller (2009). "Approximate triangle counting". In: Preprint arXiv:0904.3761.

2008

• (Becchetti et al., 2008) ⇒ Luca Becchetti, Paolo Boldi, Carlos Castillo, and Aristides Gionis. (2008). “Efficient Semi-streaming Algorithms for Local Triangle Counting in Massive Graphs.” In: Proceedings of the 14th ACM SIGKDD International Conference on Knowledge discovery and data mining, pp. 16-24 . ACM,

---