Question

Suppose we have a graph where all edge weights are equal to 1. In the video, we saw how to split a graph up into highly-interconnected communities. Now, instead we want to split the nodes into large groups that have very few connections between them (for example, if a marketer wants to find sets of people in a social network who probably have very different sets of friends). How might you do that?

Answer 1

To split nodes into large groups with very few connections between them in a graph with equal edge weights, you can use clustering algorithms like Girvan-Newman or Louvain. Girvan-Newman removes edges with high betweenness centrality, while Louvain optimizes modularity.

Step-by-step explanation:

To split the nodes into large groups that have very few connections between them in a graph where all edge weights are equal to 1, one approach is to use a clustering algorithm called the Girvan-Newman algorithm.

This algorithm iteratively removes the edges with the highest betweenness centrality, which are the edges that connect different communities. By removing these edges, the graph is split into smaller communities with fewer connections between them.

Another approach is to use a modularity optimization algorithm, such as the Louvain algorithm. This algorithm optimizes a measure called modularity, which quantifies the degree of community structure in a graph.

The Louvain algorithm iteratively moves nodes between communities to maximize the modularity, resulting in the formation of communities with very few connections between them.