Well-Connected Communities in Real-World and Synthetic Networks

We assessed the impact of CM on node coverage, here specifically examining clusters of size at least two. As above, we examined Leiden clustering of Open Citations and CEN networks using CPM-optimization at five resolution values and also using modularity, examining the change in node coverage before and after CM treatment (Fig. 4). The results are resolution dependent and network sensitive. For CPM-optimization, the impact of filtering out clusters of size at most 10 is large for the two larger resolution values, but then decreases as the resolution value decreases. In contrast, the impact of the Connectivity Modifier (the middle component of the CM pipeline that iteratively finds and removes small edge cuts and reclusters) also depends on the resolution parameter, with a minimal impact for the large resolution values and an increasing impact as the resolution value decreases. Modularity returned results most similar to CPM-optimization with the smallest tested resolution value. Since the pre-processing (filtering) and post-processing both remove all clusters of size at most 10, the node coverage reported for these stages are with respect to clusters of size at least 11. Given this, we observe that post-CM node coverage is low compared to pre-CM for both networks and clustering methods, and was smallest when using CPM-optimization with resolution value $r=0.5$ and largest when using CPM-optimization with one of the two smallest resolution values, $r=0.001$ for CEN and $r=0.0001$ for Open Citations. Overall, post-CM node coverage of any Leiden clustering never exceeded 24.6% for CEN and 68.7% for Open Citations.

To understand the nature of the modifications effected by CM, we further classified the Leiden clusters based on the impact of CM-processing: extant, reduced, split, and degraded, where “extant” indicates that the cluster was not modified by CM, “reduced” indicates that the cluster is reduced in size, “split” indicates that the cluster was divided into at least two smaller clusters, and “degraded” indicates that the cluster was reduced to singletons or a cluster of size at most 10. We report the fraction in each category (Fig. 5) for six different clustering conditions on the Open Citations and CEN networks. When using CM with CPM-optimization with a very large resolution value, most clusters are extant, the fraction of extant clusters decreases for CPM-optimization as the resolution value decreases, and is low also for modularity (Fig. 2).

An interesting trend with split clusters is seen in Figure 5, indicating the initial cluster contained two or more well connected clusters; this is similar to the observation by Fortunato and Barthélemy in  (?) of modularity’s behaviour on a ring-of-cliques, where modularity returns clusters that contain two or more cliques, instead of returning the individual cliques, under some conditions. Here we see that clusters that are split by CM unsurprisingly occur in both networks with modularity, but also occur in a noticeable way for CPM-optimization with the smallest resolution value for the Open Citations network. Finally, we note that this occurs for CPM-optimization with other resolution values on both networks (Table S5 and Figure S1). The most extreme cluster fate is of course when it is degraded to singletons, which occurs in modularity clusterings and CPM-based clusterings at lower resolution values; however, the degree to which this occurs depends on the network and resolution value in a way that does not suggest any particular pattern (Figure S1).

We examine the impact of CM on IKC (with $k=10$) on the Open Citations and CEN networks (Fig. 6). In comparison to Leiden, IKC-clustering results in relatively low node coverage, 23.6% and 3.8% in the case of the Open Citations and CEN networks respectively. CM treatment of these clusterings also has a small effect on node coverage. We also see that most clusters are extant and some are split, but none are reduced or degraded.

In summary, the response to CM-processing differed across methods. On the CEN and Open Citations networks, and for both IKC and Leiden under modularity or CPM, node coverage in a post-CM clustering did not exceed 68%, either because CM-processing reduces node coverage substantially from the initial clustering in the case of Leiden with modularity or CPM-clustering with smaller resolution values or because the initial clustering was conservative and already had low node coverage. This suggests the possibility that in these real-world networks, only a fraction of the nodes may be in clusters that are sufficiently well connected and sufficiently large. In other words, real-world networks may not be fully covered by what we consider “valid” communities.

Given our hypothesis that the large reduction in node coverage that we observe on real-world networks may be the result of them not being universally covered by well connected true communities, we examined synthetic networks, noting that synthetic networks generated using LFR software  (?) assign every node to a non-singleton ground-truth community. If node coverage after CM-processing of LFR networks were similar to real-world networks, it would argue against this hypothesis. Examining synthetic networks also enables us to evaluate the impact of CM-processing on accuracy.

For this experiment, we computed statistics for the Leiden clusterings of the 7 real-world networks we explored, Open Citations, CEN, and 5 networks from the SNAP collection  (?)), and used them as input to the LFR software  (?) (see Materials and Methods). Using this software, we were not able to build synthetic networks for the CEN and Open Citations with the number of nodes in the empirical networks; therefore, for these two specific cases, we constructed the LFR networks to $3$M nodes. For some combinations of network and Leiden clustering, we were unable to produce any synthetic networks, for example, we were unable to produce LFR networks for the Orkut social network. We produced a collection of 34 LFR networks with ground truth communities that had similar empirical statistics as their corresponding real-world networks (Supplementary Materials Section S3). We clustered each of these 34 LFR networks using the same clustering method used to provide empirical statistics to LFR.

Results in Figure 7 show node coverage after clustering for both the empirical network and its corresponding LFR network. The general trends we observed in previous experiments for OC and CEN also hold for the five other empirical networks examined here both with respect to node coverage in Leiden clustering and how CM-processing impacts node coverage. An interesting trend we see here is that node coverage drops for some CPM clusterings of empirical networks though not for LFR networks after the filtering stage. Since node coverage in this figure is with respect to clusters of size 11 or larger, any drop in node coverage resulting from filtering is due only to removing trees. The large drop in node coverage for Leiden with CPM-optimization in these cases means that CPM-optimization in some conditions produces a large number of tree clusters. We note this did not occur for resolution value $r=0.5$, where clusters tend to be small but did occur for other resolution values (Supplementary Tables S3 and S4).

Of specific interest is whether clusterings of the LFR networks respond similarly to CM-processing as clusterings of their corresponding empirical networks, as this addresses our hypothesis regarding why CM-processing impacts node coverage in empirical networks. While node coverage does drop to the same degree for some LFR networks as for the empirical networks on which they are based, there are many cases where node coverage drops much more for the real-world network than for the corresponding LFR network, and no cases where there is a bigger drop in node coverage for the LFR network than for the real-world network. Thus, the idea that real-world networks not having universal coverage by valid communities cannot be ruled out.

We examined the impact of CM-processing on clustering accuracy; results for Normalized Mutual Information (NMI) and Adjusted Mutual Information (AMI) are shown in Figure 8, and results for the Adjusted Rand Index (ARI) are similar to AMI and are provided in Supplementary Materials, Figure S11  (?, ?, ?). We see that CM-processing improves NMI accuracy for modularity and also for CPM-optimization when used with small resolution values. CM-processing tends to be neutral for NMI otherwise, and was only detrimental on two network:clustering pairs. The impact on AMI accuracy is more variable. For example, CM-processing reduced AMI accuracy for all wiki_talk network:clustering pairs except for CPM-optimization with $r=0.1$ where accuracy was very low and the impact was neutral. CM-processing also reduced accuracy for CPM-optimization on some network:clustering pairs for large resolution values.

However, when examining the properties of the ground-truth clusterings of these networks, we see that the cases where CM-processing produced a noteworthy reduction in accuracy for NMI or AMI are those where there are many disconnected ground truth clusters, for example all wiki_talk clusters, or where the node coverage by clusters of size at least 11 is small, for example cit_patents at the three largest resolution values and wiki_topcats with the two largest resolution values. However, there are conditions with low node coverage or a large fraction of disconnected clusters where CM-processing is neutral or even beneficial.

The occurrence of disconnected ground-truth clusters in the LFR networks is striking and problematic, since a basic expectation of a community is that it is connected, if not well-connected  (?). Hence, we assert that it is unreasonable to evaluate accuracy with respect to a ground-truth set of communities if the communities are not connected. In other words, it does not make sense to evaluate clustering accuracy for those LFR networks that contain many disconnected ground truth communities, including the entire set of LFR networks constructed for wiki_talk invalid, which is one of the conditions where CM-processing reduces AMI accuracy. The fact that LFR networks had ground truth clusters that were not connected also indicates the failure of LFR software to reproduce features of the input network:clustering pairs, which by construction always have 100% of the clusters connected.

It is easy to see why a low node coverage by clusters of size at least 11 could reduce accuracy for CM-processing, since CM automatically removes all small clusters. However, this property depends on the network:clustering pair, which depends on network features as well as the clustering methodology. In this study, clustering real-world networks produced a large fraction of small clusters when we used CPM-optimization with large resolution values; the conditions where CM-processing reduced AMI accuracy on the LFR networks with low node coverage by clusters of size at least 11 are drawn from those conditions. We also note that users typically select the clustering method that produces cluster sizes that match their interest. Therefore, CM-processing will not be beneficial where there is interest in recovering small communities unless the bound $B$ is replaced by a smaller value.

In interpreting these results, we also note the discrepancy between some empirical statistics of LFR networks and those of the real-world network:clustering pairs that were used to simulate the LFR network. Beyond incomplete matching of features, differences such as the frequency of disconnected clusters and the percentage of clusters that are small make it questionable whether accuracy on LFR networks is suggestive of accuracy on real-world networks.

In this study, we considered the question of whether clusters produced by community detection methods are well connected. We use a mild definition to demonstrate that five different clustering paradigms generate, to varying extents, output clusters that are not well connected. An important implication of these results is that portions of a network may not exhibit community structure. Further, at parameter settings that maximize node coverage, weakly connected parts of a network may be forced into communities. Related prior work  (?, ?) address whether a graph in general is clusterable, which is a related question.

We developed CM to convert, through partitioning, poorly connected clusters into well connected ones. For flexibility, the function in CM that defines “well connected” can be modified by users to be more or less stringent. Similarly, we provide a parameter $B$, tunable by the user, that specifies the smallest size of a cluster for it to be retained; this too can be modified by the user to be more or less stringent. At present, CM provides support only for Leiden and IKC, the most scalable of the methods we tested. CM is being extended to provide support for Infomap and MCL and concurrently being redesigned for developers to integrate their own clustering methods into it. CM allows the user to explore cluster quality in the input, as it reveals which clusters are poorly connected, and, in some cases, finds substructure within clusters. Thus, CM-processing can be used to evaluate and improve clustering outputs, and interrogate and explore the community structure within a given network.

Several factors affect how significantly CM-processing changes a given clustering. These include the network itself, as some networks seem to be more impacted by CM-processing. We also see that the choice of resolution parameter for Leiden-CPM has an influence on how much the clustering changes, with generally larger impact for small resolution values.

The findings that LFR networks produce different patterns than empirical networks is perhaps not surprising, but here we consider potential explanations. First, the LFR methodology assumes that the degree distribution and cluster size distributions follow a power law, however, it is not clear that this is universal to citation and real-world networks  (?, ?, ?, ?). Furthermore, we also observed that the degree distribution and cluster size distributions were imperfectly fit by LFR software in our study (Supplementary Materials, Figs. S2 and S3). Hence, the assumptions about node degree and cluster size distributions that govern the LFR model may not result in adequate simulation of real-world networks.

Another assumption in the LFR methodology is that every node is in a community, which is one that would benefit from deeper investigation. Intuitively, we posit that the assumption that every node in a real world community is in a community may only be reasonable if the communities can be small and/or poorly connected.

We recognize that our perspective on well connected clusters may result in narrow descriptions of communities, perhaps akin to cores of core-periphery structures  (?, ?, ?). Additionally, informative weaker links  (?) may be lost from communities since CM partitions input clusters that are poorly connected into sets of well connected clusters. However, such weak links are not lost from the network being analyzed.

Having developed CM and ascertained its quantitative effects, a direction for our future work is to evaluate it in the context of specific evaluations that are supported by mixed methods. More generally, we emphasize leaving the definition, use, and interpretation of well connected to users.

In  (?), Traag et al. proved that every cluster $C$ in a CPM-optimal clustering of a network (with resolution parameter $r$) would satisfy the following property: any edge cut $X$ of $C$ splitting the nodes into two sets $A$ and $B$ would have at least $r\times|A|\times|B|$ edges. This function is maximized when $|A|=|B|$ and minimized when $|A|=1$ and $|B|=n-1$, where $C$ has $n$ nodes. Hence in particular, this establishes that the minimum cut for any cluster with $n$ nodes has size at least $r\times(n-1)$.

We have already observed that this bound (which we refer to as Traag’s bound) is weak when $n$ is not large and $r$ is very small. For example, when $r=0.01$ and $n=50$, the bound only establishes that the minimum edge cut is at least $1$, which therefore simply asserts that the cluster is connected. Hence, we seek lower bounds on the size of the minimum edge cut that are larger than Traag’s bound of $r\times(n-1)$ for small values of $n$ but grow very slowly, and so do not exceed Traag’s bound for larger $n$.

In the text, we discussed the bound that requires that for a cluster of $n$ nodes to be well connected, the size of its min cut must be strictly greater than $f(n)=\log_{10}n$. We compare $f(n)$ to Traag’s lower bound when $r=0.01$, which we refer to as $t(n)$, as well as two other functions, $g(n)=\log_{2}n$ and $h(n)=\frac{\sqrt{n}}{5}$; note that each of $f(n),g(n)$ and $h(n)$ is strictly positive and increasing, and yet grows more slowly than Traag’s function $t(n)$.

The comparison between these functions in the range of cluster sizes $1\leq n\leq 2000$ is shown in Figure 9. As desired, for large enough $n$, Traag’s function $t(n)$ dominates the other functions, thus imposing a much stronger guarantee on the minimum cut size for the cluster. We also note that $f(n)<g(n)$ for all $n>1$, but that the relationship between $f(n),h(n)$, and $t(n)$ depends on $n$. For large $n$, however, $f(n)$ is less than all the other functions, making it the most slowly growing function.

Based on this comparison, we used $f(n)$ to define when a cluster of $n$ nodes is well connected: the min cut size is strictly greater than $\log_{10}(n)$; otherwise we say that the cluster is poorly connected.

Note that if we had picked $g(n)$ instead, we would have considered more clusters poorly connected, since $f(n)<g(n)$ for all $n$. Similarly, picking $h(n)$ would have generally been more stringent a requirement (at least for all but very small values of $n$), and so would have ruled more clusters as being poorly connected. Thus, $f(n)$ represents a very modest constraint on the size of the min cut for a cluster, in order for it to qualify as being well connected.

To remediate poorly-connected clusters, we developed a modular pipeline that we now describe (Fig. 2). By design, this pipeline is guaranteed to return a clustering where each cluster is well connected according to the function $f(n)$ and has size at least $B$. The values of $f(n)$ and B used in this study are set as default but can be easily modified by a user. Note that if an input cluster meets these two criteria, it will be present in the output clustering. Furthermore, every cluster in the output will either be one of the input clusters or will be a subset of one of the input clusters.

The CM pipeline requires the user to specify values for three algorithmic parameters:

• •

  $B$, the minimum allowed size of any “valid” vertex community (default $B=11$)

• •

  $f(n)$, so that a cluster is well connected only if its min cut size exceeds $f(n)$ (default: $f(n)=\log_{10}n$)

• •

  A clustering method, presently selected from Leiden optimizing CPM, Leiden optimizing modularity, or the Iterative k-core (IKC) method with $k=10$. Support for additional methods is in active development.

The Connectivity Modifier was developed using Python 3.10. The original implementation of VieCut  (?) in C++17 was wrapped into a Python package using PyBind11. In our analysis we use unbalanced minimum cuts computed with the NOI algorithm  (?).

Due to memory constraints, IKC fails to run with the connectivity modifier on the entirety of the OpenCitations network. To solve this, we modified IKC to run in memory as an imported Python module rather than as a separate executable. Moreover, we split the initial IKC clustering of OpenCitations into separate clusters, and the Connectivity Modifier was then run on the largest clusters independently (see Supplementary Section S2 for full details).

A custom-implemented Extract-Transform-Load (ETL) process was designed to process the publicly available Open Citations dataset, downloaded in Aug 2022, and load it into a PostgreSQL table. The resultant network contained 75,025,194 nodes and 1,363,605,603 edges. The CEN is a citation network constructed from the literature on exosome research. From the SNAP repository, we downloaded cit_hepph, an Arxiv High Energy Physics paper citation network; cit_patents, a citation network among US patents; orkut, a social media network; wiki_talk, a network containing users and discussion from the inception of Wikipedia until January 2008; and wiki_topcats, a web graph of Wikimedia hyperlinks. Before clustering, all networks were processed to remove self-loops as well as duplicate and parallel edges.

To create simulated networks with ground truth communities, while attempting to emulate the properties of each empirical network and its corresponding Leiden clustering, we used the LFR software from  (?). The generative model of the LFR graphs assume that the node degree and the community size distributions are power-law distributions  (?). The software for generating LFR benchmark graphs  (?) takes the following eight parameters as input:

• •

  Network properties: Number of nodes $N$, average and maximum node degrees ($k$ and $k_{max}$ respectively), and negative exponent for degree sequence ($\tau_{1}$) that is assumed to be a power-law.

• •

  Community properties: Maximum and minimum community sizes ($c_{max}$ and $c_{min}$), and negative exponent for the community size distribution ($\tau_{2}$), also modeled as a power-law.

• •

  Mixing parameter $\mu$, that is the ratio between the degree of a node outside its community and its total degree, averaged over all nodes in the network. Lower $\mu$ values suggest that a network consists of well-separated communities, as nodes are mostly connected to other nodes inside their communities, rather than outside of it.

To emulate the empirical networks using LFR graphs, we estimated all eight parameters described above for a given pair of network $\mathcal{G}$ and a clustering $\mathcal{C}$. Computing $N,k,k_{max},c_{min}$ and $c_{max}$ is straightforward using networkX  (?, ?). To estimate $\mu$, we perform a single iteration over all edges of the network, and for each edge, if the nodes on the two sides of it were in different communities, that edge contributes to the ratio $\mu$ of these two nodes. The total $\mu$ of the network:clustering pair is the average $\mu$ across all the nodes.

To estimate $\tau_{1}$ and $\tau_{2}$, we fit a power-law distribution to the node degree sequence and the community size distribution, using the approach from  (?) that is implemented in the power-law Python package  (?). Note that the power-law property may hold for the tail of the degree or community size sequence and not the whole distributions. Therefore, following  (?), we estimate $x_{min}$, the minimum value for which the power-law property holds as well as the exponent $\alpha$ for the tail of the distribution.

After computing these parameters based on the Leiden clusterings of the empirical networks using both modulatiry and CPM with a range of resolution parameters, we simulated LFR networks using the software from  (?), producing empirical statistics reported in Supplementary Tables S7 and S8.

For networks with more than 10 million nodes, i.e., Open Citations and the CEN, we limited the number of vertices to 3 million, due to scalability limitations of the LFR benchmark graph generator  (?), while preserving the edge density reflected by average degree, and the mixing parameter. The numbers of nodes of the other LFR graphs exactly match the number of nodes in the corresponding empirical network. In some cases, due to the inherent limitations of the LFR graph generator, we had to modify the ranges of the community sizes, i.e., increase $c_{min}$ and decrease $c_{max}$, to generate the network. These values are available with the datasets.

As shown in the statistics reported in Supplementary Tables S7 and S8, the average node degree, the mixing parameter, and the exponents for the degree and community size distributions are in all cases very well-preserved. Further details about the pipeline for producing LFR graphs and the statistics of the graphs are provided in Supplementary Materials Section 3. We calculated NMI, AMI, and ARI using the Python Scikit-Learn package  (?). Other software used includes Leiden and IKC  (?, ?).