Performance of locally linear embedding on LFR networks of 1000 nodes (a) and nodes (b). The NMI values are averaged over 10 realizations of the same LFR configuration for each . The baseline performances are those of Infomap (star) and Louvain (filled triangle). The cosine distance metric (bullet) performs better than the Euclidean distance () in the regime of low and high embedding dimension (). The best possible NMI (filled square) is found by doing an exhaustive search across 50 different values of ranging from 2 to 500, for each network and selecting the one with the largest NMI.

Performance of higher-order preserving embedding on LFR networks with 1000 nodes. The baseline performances are those of Infomap (star) and Louvain (filled triangle). For each value of the mixing parameter , the average NMI over 10 configurations is reported. The best parameters are found by employing a genetic optimization in two different ways: finding the best parameters for each configuration separately (brown) and finding the optimum parameter set across all values of (green and red, the optimal parameters are indicated) by optimizing the area under the curve. The spherical distance metric (dashed) performs better than the Euclidean metric (solid lines).

Performance of modularized non-negative matrix factorization for LFR benchmark graphs of 1000 nodes (a) and nodes (b). The baseline performances are those of Infomap (star) and Louvain (filled triangle). The performance obtained by using the default parameters (blue and orange) is almost as good as the best performance obtained by doing an evolutionary optimization over the parameters. The latter can be done optimizing NMI for each graph configuration separately (brown) or optimizing the area under the curve (green and red). For graphs of nodes the default parameters lead to a poor performance. There is no significant difference between the two different metrics (Euclidean and spherical).

Performance of DeepWalk on LFR benchmark graphs of 1000 nodes (a) and nodes (b). The baseline performances are those of Infomap (star) and Louvain (filled triangle). The performance of the algorithm using the default parameter set is better if we adopt the Euclidean distance (blue, solid) instead of the spherical distance (orange, dashed). The default parameter performance is not significantly worse than the optimum performance found by doing an evolutionary optimization over each configuration (filled square) or a single parameter set across all configurations (star). For each value of , 10 different LFR graphs are generated and the NMI value shown is the average across them.

Performance of node2vec on LFR benchmark graphs of 1000 nodes (a) and nodes (b). The baseline performances are those of Infomap (star) and Louvain (filled triangle). The performance of the algorithm using the default parameter set is better if we adopt the Euclidean distance (blue, solid) instead of the spherical distance (orange, dashed). The default parameter performance is not significantly worse than the optimum performance found by doing an evolutionary optimization over each configuration (filled square) or a single parameter set across all configurations (star). For each value of , 10 different LFR graphs are generated and the NMI value shown is the average across them.

Performance of all the considered embedding methods on a stochastic block model (SBM) of 20 groups of 50 nodes each. The average degree is set to 20. The mixing parameter is reported on the axis, for each value 10 graphs are generated and the average NMI over them is shown on the axis. (a) Curves corresponding to the default parameters. (b) Best curves obtained via the genetic optimization over the parameters (Sec. ).

Performance of all the considered embedding methods on a stochastic block model (SBM) of 200 groups of 50 nodes each. The average degree is set to 20. The mixing parameter is reported on the axis, for each value 10 graphs are generated and the average NMI over them is shown on the axis for the default parameters.

A comparison of traditional community detection methods: Infomap, Louvain, Label propagation, and OSLOM on the LFR benchmark. The average degree, , and number of nodes . The additional parameters for the LFR benchmark are , and .

Problem of spectral embeddings for well-separated communities. The network is generated by an SBM with two blocks, and , and in each block. Laplacian eigenmap is applied for dimensions (top to bottom). The cosine similarity for within cluster node pairs overlaps with that of the node pairs across clusters for higher embedding dimension, making the identification of the clusters hard even for this straightforward example.

Problem of spectral embeddings for well-separated communities. The network is generated by an SBM with two blocks, and , and in each block. Laplacian eigenmap is applied for dimensions (top to bottom). The cosine similarity for within cluster node pairs has limited overlap with that of the node pairs across clusters for higher embedding dimension, making the identification of the clusters easier.

Improving Laplacian eigenmap. The network is generated by the same SBM as in Fig. . A modified version of Laplacian eigenmap for is applied, in that the eigenvector components are multiplied by the (inverse) eigenvalue. In the first row we show analogous diagrams as in Figs.  and , for the Euclidean distance (top row) and the cosine similarity (bottom row). The clusters are now well separated.