I'm looking for a good definition of sparse graphs. Is a sparse graph effectively a big one, with millions/billions of nodes? An example from real world is the Facebook graph. Or can sparse graphs be in small networks as well?
$\begingroup$
$\endgroup$
3
-
8$\begingroup$ Did you already check the Wikipedia entry? $\endgroup$– JuhoCommented Apr 8, 2014 at 11:42
-
$\begingroup$ given the above comment, removing the question might be a wise idea, unless you have some reason to be dissatisfied with the wikipedia answer. In that case, you should explain why. $\endgroup$– babouCommented Apr 8, 2014 at 13:00
-
$\begingroup$ @Juho I did, and it does not seem to contain a definition of "sparse". $\endgroup$– RaphaelCommented Aug 4, 2015 at 12:29
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
1
The common definition is that a family of graphs $G = (V, E)$ is sparse if $m \in o(n^2)$, with $n = |V|$ and $m = |E|$. Formally, that requires the family to be infinite, and we only know something in the limit.
The definition does not apply to graphs of a fixed size per se. One would certainly want $m \ll n^2$ in some sense. For instance, if $m \leq 5n$ or $m \approx \log n$ you would probably say that your graph is "sparse".
You can bridge this gap by requiring a bit more on the asymptotic side. Say we call a family of graphs sparse if
$\qquad\displaystyle m \leq f(n) + O(1)$ with $f \in o(n^2)$;
then we may want to call every graph with $m \leq f(n)$ sparse. The implicit assumption is that the error term hidden in $O(1)$ is well-behaved.
-
$\begingroup$ That said, I think people want smallish graphs to be "sparse" or "dense", but they got so used to abusing Landau notation to not notice that they don't give a definition for graphs of fixed size. In the folklore department, at least; the Wikipedia entry references definitions that work for all sizes, but I've never seen or heard anyone use them. (Disclaimer: I'm not a member of a research community that regularly deals with sparse graphs.) $\endgroup$– RaphaelCommented Aug 4, 2015 at 12:53
$\begingroup$
$\endgroup$
Sparsity is a fuzzy notion, and its meaning will depend on the context. It can be argued a graph is not sparse "by itself", but rather it is sparse relative to other graphs. Indeed, there are several ways to define or measure sparseness.
We can say a connected graph is maximally sparse if it is a tree. Intuitively, a tree-like graph is sparse. But what could be a "tree-like graph"? Perhaps the number of cycles is bounded, or by removing a constant number of vertices we get a tree. One very popular definition of sparseness rises from these considerations. Informally, the treewidth of a graph is a measure of how close a graph is to being a tree.
To address your question, a graph of low treewidth can be either small or large. For instance, forests, trees, and outerplanar graphs all have constant treewidth. In contrast, a complete graph on $n$ vertices has treewidth $n-1$. This corresponds to our intuition that complete graphs are not sparse.
Treewidth is just one measure of sparseness. You can dig deeper into the literature and explore other measures as well.
$\begingroup$
$\endgroup$
A graph is dense if the number of edges is closer to the maximum number of edges there could be. Formally, a graph is dense if $e=\cal \Omega(v^2)$ where $v,e$ are the number of vertices and edges. A graph is sparse if the above is not true.
