Implementation of this algorithm is based on the work Modularity and community structure in networks by M. E. J. Newman. This algorithm is based on the modularity matrix for a network or a graph and it is not based on particular graph theory, but it has instead some similarities with spectral clustering because it also uses eigenvectors.

The Dlib library implements this algorithm in the newman_cluster() function, which takes a vector of weighted graph edges and outputs the container with cluster indices for each vertex. The initial step for using this algorithm is the definition of graph edges. In the following code sample, we make edges between almost every pair of dataset objects. Notice that we use pairs only with a distance greater than a threshold (this was done for performance considerations).

Also, this algorithm does not require prior knowledge of the number of clusters. It can determine the number of clusters by itself. The code can be seen in the following block:

 std::vector<sample_pair> edges;
 for (long i = 0; i < inputs.nr(); ++i) {
     for (long j = 0; j < inputs.nr(); ++j) {
         auto dist = length(subm(inputs, i, 0, 1, 2) - subm(inputs, j, 0, 
         1, 2));
         if (dist < 0.5)
             edges.push_back(sample_pair(i, j, dist));
     }
 }
 remove_duplicate_edges(edges);
 std::vector<unsigned long> clusters;
 const auto num_clusters = newman_cluster(edges, clusters);

The newman_cluster() function call filled the clusters object with cluster index values, which we can use to visualize the clustering result. Notice that another approach for edge weight calculation can lead to another clustering result. Also, edge weight values should be initialized according to a certain task. The edge length was chosen only for demonstration purposes.

The result can be seen in the following screenshot:

In the preceding screenshot, we can see how the Newman clustering algorithm implemented in the Dlib library works on different artificial datasets.