Jan Bronec's REU 2022 Web Page
About Me
| Name: | Jan Bronec |
|---|---|
| Email: | jan [at] bronec.tech |
| Home Institution: | Charles University - Faculty Of Mathematics And Physics |
| Project: | Graph Cities - Semi and Fully External Graph Decomposition |
| Mentor: | James Abello |
Member of Charles University group consisting of Jan Soukup, Jan Bronec, Guillermo Gaboa, Svetlana Ivanova, Gaurav Kucheriya, Jáchym Mierva, David Miksanik, David Sychrovsky, Tung Anh Vu, Ilia Zavidnyi.
About My Project
I will be analyzing the I/O complexity of core decomposition. First I will be considering the case where the vertices fit in the memory but the edges don't. Next I will be looking into the problem where not even the vertices fit into the memory.
Research Log
Week 1: June 1 - June 8
In the first week I've met online with professor James Abello some of the core definitions. I've read through the corresponding papers and some of the reference papers to understand the notion of fixed point decomposition and how it's used to construct a graph city. I've also read through some of the reference papers to better understand the analyzing of external memory algorithm complexity.
Week 2: June 8 - June 15
I've looked into more papers that propose algorithms for k-core decomposition. I've identified 2 algorithms from those papers that can be easily modified such that they compute the vertex/edge core decomposition without affecting their original asymptotic I/O complexity.
- The first algorithm works with external graphs but has no memory bound. It works with $\mathcal{O}(peel_{max})$ I/O passes.
- The second algorithm works with semi-external graphs and uses $\mathcal{O}(l) \in \mathcal{O}(|V|)$ I/O passes. However the authors show that in practice on network graphs: $l < peel_{max}$.
Week 3: June 15 - June 22
I tried to look into divide-and-conquer approache for k-core decomposition and vertex/edge core decomposition since a possibility of a linearithmic algorithm for (semi-)external decompositions would be a major breakthrough.
That approach proved to be hard to grasp and I spent some time trying to analyze what happens on a cut between to parts of a graph that already have their local peeling values precomputed. I didn't find any helpful property however.
I've also read through a paper that tries out a type of divide-and-counques strategy for k-core decomposition. While the strategy seems to give good real-time results, it doesn't seem to improve the asymptotic complexity.
Week 4: June 22 - June 29
Professor Abello gave me an idea for a different edge decomposition to think about, which I named N-edge for the sake of having a name. I realized soon that I can compute the k-core decomposition in a single I/O pass given that the graph is semi-external and that we already have the N-edge decomposition.
I also worked on the other way and tried to show that I can construct the N-edge decomposition using $\mathcal{O}(1)$ I/O passes in the semi-external scenario. I showed that computing the edge decomposition can in fact be done in $\mathcal{O}(1)$ passes. However I found challenge in computing the intersection graph since my current method would require either $\mathcal{O}(k_{max}n)$ memory or nonconstant amount of I/O passes.
Week 5: June 29 - July 6
I spent some time thinking about the rule of peeling values of vertices being the maximum over the peeling values of it's edges and p. of edges being the minimum over p. of it's vertices. I tried to see if this rule can be used in any way to update upper bounds of the peeling values but showed that using this as an update rule by itself doesn't help upper bounds converge to the correct values. Infact I showed that already established rule based on the local peeling property is always better and so the min-max rule cannot be used to enhance it.
Week 6: July 6 - July 13
I tried to think about finding a way to compute the peeling values in reverse, given I already know the highest peeling value or that I know the highest core. I didn't find any clear property that would help me compute the previous step of peeling. I tried to come up with an update rule that would help me construct the current highest core but showed that this approach wouldn't perform better than the already established approaches. The rest of the time I spent working on the final report paper.
References & Links
- J. Abello, H. Zhang, D. Nakhimovich, C. Han and M. Aanjaneya, ”Giga Graph Cities: Their Buckets, Buildings, Waves, and Fragments,” in IEEE Computer Graphics and Applications, doi: 10.1109/MCG.2022.3172650.
- James Abello, François Queyroi. Fixed Points of Graph Peeling. 2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, Aug 2013, Niagara Falls, Canada. ffhal-00832807f
- J. Cheng, Y. Ke, S. Chu and M. T. Özsu, "Efficient core decomposition in massive networks," 2011 IEEE 27th International Conference on Data Engineering, 2011, pp. 51-62, doi: 10.1109/ICDE.2011.5767911.
- D. Wen, L. Qin, Y. Zhang, X. Lin and J. X. Yu, "I/O efficient Core Graph Decomposition at web scale," 2016 IEEE 32nd International Conference on Data Engineering (ICDE), 2016, pp. 133-144, doi: 10.1109/ICDE.2016.7498235.
Funding
Supported by the H2020-MSCA-RISE project CoSP- GA No. 823748.