Research data sets are growing to unprecedented sizes and network modeling is
commonly used to extract complex relationships in diverse domains, such as
genetic interactions involved in disease, logistics, and social communities. As
the number of nodes increases in a network, an increasing sparsity of edges is
a practical limitation due to memory restrictions. Moreover, many of these
sparse networks exhibit very large numbers of nodes with no adjacent edges, as
well as disjoint components of nodes with no edges connecting them. A prevalent
aim in network modeling is the identification of clusters, or communities, of
nodes that are highly interrelated. Several definitions of strong community
structure have been introduced to facilitate this task, each with inherent
assumptions and biases. We introduce an intuitive objective function for
quantifying the quality of clustering results in large sparse networks. We
utilize a two-step method for identifying communities which is especially
well-suited for this domain as the first step efficiently divides the network
into the disjoint components, while the second step optimizes clustering of the
produced components based on the new objective. Using simulated networks,
optimization based on the new objective function consistently yields
significantly higher accuracy than those based on the modularity function, with
the widest gaps appearing for the noisiest networks. Additionally, applications
to benchmark problems illustrate the intuitive correctness of our approach.
Finally, the practicality of our approach is demonstrated in real-world data in
which we identify complex genetic interactions in large-scale networks
comprised of tens of thousands of nodes. Based on these three different types
of trials, our results clearly demonstrate the usefulness of our two-step
procedure and the accuracy of our simple objective.

在研究中，我们介绍了一种适用于大规模稀疏网络的直观客观函数来量化聚类结果的质量，并且通过模拟网络的优化试验和基准问题的应用来证明了这种方法的实用性和准确性。