University of Twente Student Theses
Estimating graph properties with HyperLogLog-type algorithms
Huizinga, J.J. (2019) Estimating graph properties with HyperLogLog-type algorithms.
|
PDF
1MB |
| Abstract: | When one is dealing with algorithms in very large networks, the main memory often becomes too small. Therefore, other techniques are necessary to analyse these graphs. Boldi and Vigna showed that vertex ball cardinality can be estimated well using HyperBall, which is based on HyperLogLog probabilistic counters. In this paper HyperEdgeball, similar to HyperBall, is created to estimate edgeball cardinality. Both algorithms are used in HyperSurplus to estimate the number of surplus edges locally, which gives good first practical results. Theory is deduced to count triangles and 4-cycles in a similar fashion, this yielded not yet in a properly performing algorithm. |
| Item Type: | Essay (Bachelor) |
| Faculty: | EEMCS: Electrical Engineering, Mathematics and Computer Science |
| Subject: | 31 mathematics |
| Programme: | Applied Mathematics BSc (56965) |
| Link to this item: | https://purl.utwente.nl/essays/79108 |
| Export this item as: | BibTeX EndNote HTML Citation Reference Manager |
Show download statistics for this publication
Show download statistics for this publicationRepository Staff Only: item control page