Community detection and decomposing graphs
Community detection is a common data science task and a useful technique to have in your data science toolkit, but let’s start by describing what we mean by a community.
What is a community?
In many real-world networks, nodes are used to represent people. Consequently, when we have a collection of highly connected nodes, forming almost a fully connected separate graph, we can think of this as a community of interacting people.
We can extend this idea to situations where the nodes do not represent people. For example, our trade network example at the beginning of this chapter was fully connected, but if it wasn’t, there might be groups of countries that preferentially trade with each other and don’t trade with other countries. We would have separate trading blocks or trading communities. Similarly, in our pizza example, we have groups of pizzas that are more similar to each other and hence interchangeable. This...
