ERC Starting Grant "Sublinear Algorithms for the Analysis of Very Large Graphs" (2012-2018)
Former Members
Support
This project had received funding from the European Union's Seventh Framework Programme for research, technological development and demonstration under grant agreement no. 307696.
Overview
Large graphs appear in many application areas. Typical examples are the webgraph, the internet graph, friendship graphs of social networks like facebook or Google+, citation graphs, collaboration graphs, and transportation networks.
The structure of these graphs contains valuable information but their size makes them very hard to analyze. Therefore, we need special algorithms that analyze the graph structure via random sampling.
The main objective of the proposed project is to advance our understanding of the foundations of sampling processes for the analysis of the structure of large graphs. We will use the approach of Property Testing, a theoretical framework to analyze such sampling algorithms.
Results
- Hendrik Fchtenberger, Pan Peng, Christian Sohler. Every Testable (Infinite) Property of Bounded-Degree Graphs Contains an Infinite Hyperfinite Subproperty. To appear in proceedings of SODA 2019.
- Hendrik Fichtenberger, Dennis Rohde. A Theory-Based Evaluation of Nearest Neighbor Models Put Into Practice. To appear in proceedings of NIPS 2018.
- Hendrik Fichtenberger, Yadu Vasudev. A Two-Sided Error Distributed Property Tester For Conductance. In proceedings of MFCS 2018.
- Hendrik Fichtenberger, Reut Levi, Yadu Vasudev, Maximilian Wötzel. A Sublinear Tester for Outerplanarity (and Other Forbidden Minors) With One-Sided Error. In proceedings of ICALP 2018.
- David Cohen-Steiner, Weihao Kong, Christian Sohler, Gregory Valiant. Approximating the Spectrum of a Graph. In proceedings of KDD 2018.
- Pan Peng, Christian Sohler. Estimating Graph Parameters from Random Order Streams In proceedings of SODA 2018.
- Morteza Monemizadeh, S. Muthukrishnan, Pan Peng, Christian Sohler. Testable Bounded Degree Graph Properties Are Random Order Streamable. In proceedings of ICALP 2017.
- Ilan Newman, Yuri Rabinovich, Deepak Rajendraprasad, Christian Sohler. Testing for Forbidden Order Patterns in an Array. In proceedings of SODA 2017.
- Artur Czumaj, Pan Peng, Christian Sohler. Relating two property testing models for bounded degree directed graphs>. In proceedings of STOC 2016.
- Hendrik Fichtenberger, Pan Peng, Christian Sohler. On Constant-Size Graphs That Preserve the Local Structure of High-Girth Graphs. In proceedings of RANDOM 2015.
- Artur Czumaj, Pan Peng, Christian Sohler. Testing Cluster Structure of Graphs. In proceedings of STOC 2015.
- Angsheng Li, Pan Peng. Testing Small Set Expansion in General Graphs. In proceedings of STACS 2015.
- Artur Czumaj, Morteza Monemizadeh, Krzysztof Onak, Christian Sohler. Planar Graphs: Random Walks and Bipartiteness Testing. CoRR abs/1407.2109 (2014).
- Christian Sohler. What does the local structure of a planar graph tell us about its global structure? Invited paper. In Proceedings of the 39th MFCS, 2014.
- Frank Hellweg. Property-Testing in gradbeschraenkten gerichteten Graphen unter Nichtsichtbarkeit eingehender Kanten. Dissertation, 2013.
- Frank Hellweg, Christian Sohler. Property-Testing in Sparse Directed Graphs: 3-Star-Freeness and Connectivity. CoRR abs/1312.0497, 2013.
- Angsheng Li, Pan Peng. Detecting and Characterizing Small Dense Bipartite-like Subgraphs by the Bipartiteness Ratio Measure. In proceedings of ISAAC 2013.
- Ilan Newman and Christian Sohler: Every Property of Hyperfinite Graphs Is Testable. In SIAM J. Comput., 42(3), 2013.