## 5 Experimental Results
### Synthetic Data in Native Network Form
#### 5.2.3 Large LFR Networks  
To demonstrate the feasibility of NBR-Clust on larger graphs, two series of LFR networks were generated (10,000 nodes and 100,000 nodes). These networks contain 30 to 40 clusters of varying cluster sizes, ranging from 100 to 500 nodes for the 10,000-node graphs, and 1000 to 5000 nodes for the 100,000-node graphs. The degree distributions are highly irregular, with a typical degree distribution ranging from 20 to 60. Different values of \(\mu\) were used ranging from 0.01 to 0.10 for the 10,000-node graphs, and from 0.001 to 0.010 for the 100,000-node graphs. To determine if the number of edges  
\begin{table}
\begin{tabular}{c c c c c c c c c c c c c c c c c c c c c} \hline \hline  & \multicolumn{3}{c}{**VAT**} & \multicolumn{3}{c}{**Integrity**} & \multicolumn{3}{c}{**Toughness**} & \multicolumn{3}{c}{**Tenacity**} & \multicolumn{3}{c}{**Scattering**} \\ \hline \multirow{2}{*}{\#} & **1** & **1** & **1** & **3** & **1** & **1** & **1** & **3** & **1** & **1** & **3** & **1** & **1** & **3** & **1** & **1** & **3** & **1** & **1** & **3** & **1** \\ \hline
8 & 100 & 100 & 100 & 100 & 100 & 100 & 100 & 100 & 100 & 97 & **97** & **99** & **100** & 97 & **97** & **99** & 69 & 64 & 92 & 63 \\
16 & 99 & 100 & 100 & 100 & 99 & 100 & 100 & 100 & **100** & **98** & **94** & **96** & **100** & **98** & **94** & **96** & 46 & 59 & 86 & 49 \\
32 & 100 & 99 & 100 & 99 & 100 & 95 & 100 & 97 & **98** & **97** & **96** & **95** & **98** & 97 & 96 & 95 & 48 & 48 & 85 & 58 \\
64 & 100 & 100 & 99 & 93 & 100 & **100** & **96** & 85 & **100** & **96** & **94** & **92** & **100** & **96** & **94** & **92** & 36 & 30 & 74 & 37 \\ \hline \hline \end{tabular}
\end{table}
Table 2: Percent accuracy for NBR–Clust on Girvan–Newman graphs for varying mixing factors \(\mu\). Bold text indicates one-step clustering.  
\begin{table}
\begin{tabular}{c c c c c c} \hline \hline
**Measure** & \(\mu\) = 0.05 & **0.10** & **0.15** & **0.20** & **0.25** \\ \hline VAT & **96** & **82** & **71** & **67** & **48** \\ integrity & **97** & **92** & **84** & **74** & **61** \\ toughness & **97** & **95** & **90** & **85** & **55** \\ tenacity & **97** & **95** & **90** & **85** & **55** \\ scattering & 44 & 19 & 18 & 17 & 17 \\ \hline \hline \end{tabular}
\end{table}
Table 3: Percent Accuracy for NBR–Clustering on LFR Networks of 1024 Nodes. Bold text indicates one-step clustering.  
affects the clustering accuracy, two variations of the 100,000-node graphs were tried. One set of graphs had approximately 275,000 edges, and one set had approximately 825,000 edges.  
To cluster these larger graphs, Greedy-BC was executed in a distributed fashion using a graphics processing unit (GPU) betweenness centrality approximation algorithm called Hybrid-BC [55], as described in [66]. Results are shown in Table 4. In two cases, the approximation provided by the GPU algorithm was not sufficient to successfully complete clustering with VAT.  
With LFR networks, higher mixing factors imply increased difficulty of clustering. Despite the fact that exact betweenness centrality values were not used, clustering accuracies are still quite high. As is shown in Table 4, 10,000-node graphs with \(\mu\) less than 0.10 were clustered with at least 96% accuracy. To give some idea of execution time, graphs 1 to 5 were clustered in less than five minutes. The last and most difficult graph was clustered in approximately 35 minutes, with 92% accuracy.  
Results for the 100,000-node graphs are also shown in Table 4. Clustering accuracy is high for both the high and low density graphs. Only two of the graphs were clustered with less than 97% accuracy. Clustering times varied a great deal, depending on \(\mu\) and degree. Graphs 1-4 were clustered in less than 30 min, graph 5 took about 2.5 h, and graph 6 took approximately 9.5 h.