Language and Environment

Language:

• Python >3.5

Tools and Packages:

• networkx 2.4 https://networkx.github.io/ (Python 3.5, 3.6, 3.7)

To run the experiments

• Use linear_py.py's main function

• Load the appropriate dataset, select p values and algorithms to run experiments on

• Visualizations can be made using parse_results.py

Presentation link

• https://docs.google.com/presentation/d/1joTlZ1P9bB1sMlzlv6Jaa_d7TbPMRakLyyJCgDwfsPA/edit?usp=sharing

Implemented Algorithms

1. node/edge iterator

2. "Counting Triangles in Large Graphs using Randomized Matrix Trace Estimation"

3. "A space efficient streaming algorithm for estimating transitivity and triangle counts using the birthday paradox"

4. "Spectral Counting of Triangles via Element-Wise Sparsification and Triangle-Based Link Recommendation"

Papers

This section lists the papers we used for the implementation of this project:

DOULION

• https://dl.acm.org/citation.cfm?id=1557111 "DOULION: Counting Triangles in Massive Graphs with a Coin"

wedge sampling

• https://arxiv.org/pdf/1202.5230.pdf "Triadic Measures on Graphs: The Power of Wedge Sampling"

  https://onlinelibrary.wiley.com/doi/pdf/10.1002/sam.11224 "Wedge Sampling for Computing Clustering Coefficients and Triangle Countson Large Graphs"

  Algorithm 4, set d = 1

Trace Estimation

• https://pdfs.semanticscholar.org/2471/6ee2bf34934e8eb70a7aca4ffa38b544ca81.pdf "Counting Triangles in Large Graphs using Randomized Matrix Trace Estimation"

Eigenvalue

• http://www.math.cmu.edu/~ctsourak/asonam_book.pdf "Spectral Counting of Triangles via Element-Wise Sparsification andTriangle-Based Link Recommendation"

Birthday Paradox

• https://arxiv.org/pdf/1212.2264.pdf "A space efficient streaming algorithm for estimating transitivity and triangle counts using the birthday paradox"
• http://chbrown.github.io/kdd-2013-usb/kdd/p589.pdf basically the same paper, but the algorithms are written out slightly differently (most notably, first paper made it seem like every edge could be added to edge_res many times, but this paper makes it clear that it is only added once).

Datasets:

• https://sparse.tamu.edu/Pajek/HEP-th-new HEP-th-new, a academic collaboration network, N = 27,770 E = 352,285
• https://sparse.tamu.edu/SNAP/soc-Epinions1 Epinions network, a product review social network N = 75,877, E = 405,740 (this social network could be changed to facebook if too expensive to compute)
• https://sparse.tamu.edu/Pajek/EAT_RS A language network, N = 23,219, E = 304,937
• ER graph of (N, p) = (,)