University of Twente Student Theses
Detecting local clusters in large networks using HyperLogLog
Weedage, Lotte (2020) Detecting local clusters in large networks using HyperLogLog.
|
PDF
2MB |
| Abstract: | In this research we investigate how to find local clusters in large networks based on three measures: conductance, number of triangles and transitivity. We introduce adaptations of the HyperBall algorithm, based on the idea of HyperLogLog counters to find these measures. First of all, we find the conductance of ball subgraphs using the HyperBall algorithm. We also introduce a method to locally count triangles in large networks, where we find the triangle count of ball subgraphs around every node simultaneously. This is useful to identify where in a graph high densities of triangles can be found. Moreover, we introduce a method to find the ball subgraph transitivity in large networks and find clustered groups of nodes in these networks. Lastly, we show methods of extending the HyperBall algorithm to find these three measures in directed, weighted or temporal graphs. The three measures (conductance, number of triangles and transitivity) identify clusters in graphs themselves, but also turn out to be good seed sets for exact community detection algorithms as PageRank-Nibble. We tested the new algorithms on synthetic graphs generated using the LFR model and real-life graphs. The generated graphs behave different than the real-life large networks, and in both kinds of networks the three introduced measures are promising to find clusters. |
| Item Type: | Essay (Master) |
| Faculty: | EEMCS: Electrical Engineering, Mathematics and Computer Science |
| Subject: | 31 mathematics |
| Programme: | Applied Mathematics MSc (60348) |
| Link to this item: | https://purl.utwente.nl/essays/82743 |
| 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