The max-cut algorithm divides a graph into 2 subsets, for instance:
While I understand the algorithm, I do not really understand the meaning of the result. In the above picture, what does the groupings of black circles vs white circles mean?
If these lines were network connections between different locations, what do the subgroups of black & white location mean/indicate?
The colors of the vertices simply indicate which subset the vertex belongs to after the algorithm is completed. In the image provided, we can say the black vertices belong to the set $S$ and the white vertices belong to the set $T$, and that the number of edges between these two sets is as large as possible. Equivalently, we can say the result of the max-cut algorithm gives us a spanning bipartite subgraph of our original graph $G$ such that the number of edges between the partite sets $S, T$ within $G$ is maximized.
Using the analogy of network connections between different locations, these subgroups indicate a partitioning of vertices in this graph that maximizes the number of network connections between the partitions. You could think of vertices of the same color forming a country, and the edges as roads between countries as an alternative analogy. We are forming our countries such that there are as many roads between them as possible.
I've spent quite a bit of time scratching my head around this same question for a while now and here is what I've understood. Read this till the end and hopefully, you'll get a clear idea of the algorithm.
Given a weighted graph with G(V,E) where V = #vertices and E= #edges, we want to partition the graph into two sets by cutting edges such that the sum of the weights of the cut edges is maximized.
If, in the graph, there are vertices that have complementary or opposite characteristics relative to each other and they are connected by a strong edge i.e. an edge with relatively larger weight compared to other edges and we want to partition such vertices into two groups.
Consider a system of many people that can interact and influence each other. Individuals can be represented by vertices of a graph, and their interactions seen as pairwise connections between vertices of the graph, or edges. Suppose that it is assumed that individuals will influence each other’s buying decisions, and knowledge is given about how strong they will influence each other. The influence can be modeled by weights assigned on each edge of the graph. It is possible then to predict the outcome of a marketing strategy in which products are offered for free to some individuals, and then ask which is the optimal subset of individuals that should get the free products, in order to maximize revenues.
Example scenario taken from Qiskit
In the above example, an influencer and a target person are strongly connected to each other in the graph. We have many such pairs in this graph and our goal is to partition the graph such that we have influencers in one set and rest audience in other. This can be achieved by cutting all the strong edges i.e. one end of the edge has influencer and other end has target. Hence this problem can be solved by max-cut technique.
So, for the graph that you've given, you can compare it with my example and based on that the white nodes can be said as influencers and the black ones can be the target audience.
The significance of the two partitions depends on the use case. For example, there might be some activities to be specifically performed on group 1 or group 2 for which we need to correctly partition like showing influencer-specific ads to influencer nodes or product-specific ads to target nodes.
Cutting or in other words maximizing the sum of weight simply means that we try to partition as accurately as possible solely based on weights and not based on attributes/properties of nodes (like age, gender, etc if the node represents a user) as in this type of problem the weights represent some meaningful and important information specific to the system.
