Sublinear Algorithms for the Analysis of Very Large Graphs : [3]

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.
This project has received funding from the European Union’s Seventh Framework Programme for research, technological development and demonstration under grant agreement no. 307696.

Subscribe to this collection to receive daily e-mail notification of new additions RSS Feed RSS Feed RSS Feed
Collection's Items (Sorted by Submit Date in Descending order): 1 to 3 of 3
Issue DateTitleAuthor(s)
2013-06-13Every Property of Hyperfinite Graphs is TestableNewman, Ilan; Sohler, Christian
2014What does the local structure of a planar graph tell us about its global structure?Sohler, Christian
2013-12-06Property testing in gradbeschränkten gerichteten Graphen unter Nichtsichtbarkeit eingehender KantenSohler, Christian; Hellweg, Frank; Westermann, Matthias
Collection's Items (Sorted by Submit Date in Descending order): 1 to 3 of 3