What are examples of naturally dense graphs?

Question

Graphs are very useful for modeling real-world phenomena and relationships.

Broadly, graph data structures and algorithms are divided into two categories:

• Those useful for sparse graphs (e.g. adjacency lists, Johnson's algorithm)
• Those useful for dense graphs (e.g. adjacency matrices, Floyd-Warshall).

However, in every situation I can think of, real-world graphs are sparse. For example:

1. Web networks form sparse graphs (every site links to a few other sites)
2. Social networks form sparse graphs (every person is knows a few other people)
3. Electrical networks form sparse graphs (most circuit elements only affect only a few others nearby)
4. Road networks form sparse graphs (every road links to a few other roads)

(Note that "few" is in comparison to the total number of sites/people/elements/roads/etc.)

However, I've never found a use case for algorithms and data structures for dense graphs.
Every graph I remember ever encountering has turned out to be sparse.

What kinds of real-world graphs would I need to use dense graph algorithms for?

Please note: Yes, I know that a small group of people in which everyone knows each other forms a dense graph, but that's not the kind of situation I'm asking about, because:

1. Social network software is never written for just a handful of people
2. Any algorithm works just fine with small data; there's no need for dense-graph algorithms.

That means I'm also not looking for silly examples like "the complement of a sparse graph" either.
Yes, those are dense, but unless you can give me an example of a problem that would be of practical interest and which would not be reasonable solved with the original sparse graph, that's not going to answer my question.

Answer 1

The complement of a sparse graph is a dense one (think of all the sites a given web page doesn't link to). So there's a start.

Off the top of my head...

• Small social networks (e.g. people in a club probably are Facebook friends with most of the others in the club)
• The transitive closure of a graph, or at least partially (e.g. a friend of a friend)
• Really badly-written/tightly-coupled code (imagine a directed graph where class A points to class B if A references B; maybe as a member, a return value for a method, etc.)

More generally, try relaxing certain travel constraints if you want denser graphs.