What are some examples of naturally dense graphs?
Graphs are very useful for modeling real-world phenomena and relationships.
In general, graph structures and algorithms fall into two categories:
- Those useful for sparse plots (e.g. adjacency lists , Johnson's algorithm )
- Those that are useful for dense graphs (e.g. adjacency matrices , Floyd-Warshall ).
However, in any situation I can think of, real world graphs are sparse. For example:
- Web networks form sparse graphs (each site links to several other sites)
- Social networks form sparse graphs (each person knows several other people).
- Electrical networks form sparse graphs (most circuit elements affect only a few others).
- The road networks form sparse graphs (each road connects to several other roads).
(Note that "multiple" versus total sites / people / items / roads, etc.)
However, I have never found a use case for algorithms and data structures for dense graphs.
Every chart I remember ever came across turned out to be rare.
What real world graphs do 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 not the kind of situation I'm asking because:
- Social networking software is never written for just a few people.
- Any algorithm works great with small data; no need for busy algorithms.
This means that I am also not looking for silly examples like "sparse graphics addition".
Yes, they are dense, but if you cannot give me an example of a problem that would be of practical interest and that would not reasonably be solved using the original sparse graph, this will not answer my question.
source to share
Sparse graph padding is dense (think of all sites that the given web page does not link to). So get started.
Off the top of my head ...
- Small social networks (for example, the people in the club are probably Facebook friends with most of the others in the club).
- Transient closure of a graph or at least partially (for example, a friend of a friend)
- Really poorly written / tightly coupled code (imagine a directed graph where class A points to class B, if A refers to B, perhaps as a member, a return value for a method, etc.)
More generally, try softening certain motion restrictions if you want tighter graphics.
source to share
Well, the denser the graph gets, the closer it gets complete, and a complete edge-weighted graph is generally easier to imagine and think of simply as a square matrix, perhaps with some infinities or negative infinities scattered around to represent the missing "edges". Alternatively, it can become close to a complete bipartite graph, which can also be represented as a matrix (only one that uses different sets of labels along the two axes). For example, the Assignment Problem is usually thought of as a matrix problem rather than a dense edge-weighted bipartite graph.
I think one of the reasons for using dense graph algorithms is to guarantee good worst-case behavior on dense graphs.
There are also some problems associated with other tasks on the completion of the schedule, i.e. a graph in which each pair of vertices has an edge between them if they do not have an edge between them in the original. For example. if you are looking for the maximum clique in a graph that contains more than, say, 30% of all possible edges (really guessing here) and you think this clique is going to be large, you are probably better off creating a complement graph and then looking for the minimum envelope topssince the complement of such a vertex cover in the complement graph would be a clique in the original graph.Although both problems are NP-hard, minimal vertex cover is much faster when there is a small cover, taking O (1.2378 ^ k * n ^ O (1)) to cover size k (corresponding to clique of size nk) versus O (1.1888 ^ n) for maximum clique.
source to share