Sublinear Algorithms for the Analysis of Very Large Graphs

Permanent URI for this collection

http://hdl.handle.net/2003/33523

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.

Browse

Now showing 1 - 3 of 3

Every Property of Hyperfinite Graphs is Testable
(Society for Industrial and Applied Mathematics, 2013-06-13) Newman, Ilan; Sohler, Christian
A k-disc around a vertex v of a graph G=(V,E) is the subgraph induced by all vertices of distance at most k from v. We show that the structure of a planar graph on n vertices, and with constant maximum degree d, is determined, up to the modification (insertion or deletion) of at most εdn edges, by the frequency of k-discs for certain k=k(ε,d) that is independent of the size of the graph. We can replace planar graphs by any hyperfinite class of graphs, which includes, for example, every graph class that does not contain a set of forbidden minors. A pure combinatorial consequence of this result is that two d-bounded degree graphs that have similar frequency vectors (that is, the l_1 difference between the frequency vectors is small) are close to isomorphic (where close here means that by inserting or deleting not too many edges in one of them, it becomes isomorphic to the other). We also obtain the following new results in the area of property testing, which are essentially equivalent to the above statement. We prove that (a) graph isomorphism is testable for every class of hyperfinite graphs, (b) every graph property is testable for every class of hyperfinite graphs, (c) every hyperfinite graph property is testable in the bounded degree graph model, (d) A large class of graph parameters is approximable for hyperfinite graphs. Our results also give a partial explanation of the success of motifs in the analysis of complex networks.
What does the local structure of a planar graph tell us about its global structure?
(2014) Sohler, Christian
The local k-neighborhood of a vertex v in an unweighted graph G = (V,E) with vertex set V and edge set E is the subgraph induced by all vertices of distance at most k from v. The rooted k-neighborhood of v is also called a k-disk around vertex v. If a graph has maximum degree bounded by a constant d, and k is also constant, the number of isomorphism classes of k-disks is constant as well. We can describe the local structure of a bounded-degree graph G by counting the number of isomorphic copies in G of each possible k-disk. We can summarize this information in form of a vector that has an entry for each isomorphism class of k-disks. The value of the entry is the number of isomorphic copies of the corresponding k-disk in G. We call this vector frequency vector of k-disks. If we only know this vector, what does it tell us about the structure of G? In this paper we will survey a series of papers in the area of Property Testing that leads to the following result (stated informally): There is a k = k(ε,d) such that for any planar graph G its local structure (described by the frequency vector of k-disks) determines G up to insertion and deletion of at most εd n edges (and relabelling of vertices).
Property testing in gradbeschränkten gerichteten Graphen unter Nichtsichtbarkeit eingehender Kanten
(2013-12-06) Hellweg, Frank; Sohler, Christian; Westermann, Matthias
Diese Arbeit untersucht Property-Testing in gerichteten gradbeschränkten Graphen. Property-Testing ist eine Technik zum Lösen von Entscheidungsproblemen, wobei durch Relaxierung des Problems und Verwendung von Randomisierung eine sublineare Laufzeit angestrebt wird. Gradbeschränkte Graphen sind das übliche Modell, um Property-Testing in dünn besetzten Graphen zu untersuchen; hierbei wird angenommen, dass der Eingabegraph in Adjazenzlistendarstellung vorliegt und die Länge der Adjazenzlisten durch eine Konstante D beschränkt ist. Im Rahmen dieser Arbeit gehen wir davon aus, dass in gerichteten Graphen jeweils nur die ausgehenden Kanten in den Adjazenzlisten enthalten sind. Die dadurch deutlich eingeschränkten Möglichkeiten der Graphexplorierung führen dazu, dass Probleme im Vergleich zu ihren Pendants in ungerichteten Graphen deutlich schwieriger zu lösen sind; dies konnten Bender und Ron in 2002 zum Beispiel für starken Zusammenhang zeigen. In dieser Arbeit werden Property-Testing-Algorithmen im oben genannten Modell für drei Probleme vorgestellt: Starker Zusammenhang, Subgraphfreiheit mit dem Spezialfall 3-Stern-Freiheit und die Spanner-Eigenschaft in geometrischen gerichteten Graphen.

Browse

Recent Submissions