- Semi-external approach for fixed point
decomposition
- Project Year:
2022
- REU Student (s):
Jan Bronec | Charles University (Prague, Czech Republic)
- Student 1 Institution:
Charles University (Prague, Czech Republic)
- Project Mentor:
James Abello
- Project Mentor Area:
Computer Science
- Project Abstract:
Decomposition of a graph into sub-graphs that are invariant with respect to degree peeling, i.e. fixed points, is a useful method of community detection in networks and visualisation of massive graphs. However, with the analysis of massive graph comes the problem of memory size limitations. Currently, present algorithms for fixed point decomposition cannot be used in the scenario where the whole graph doesn't fit into memory,since those approaches would result in too large I/O time. We present two methods for the computation of these decompositions and we also propose a different decomposition that is not based on fixed points but can be computed more efficiently.
