Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities.

By Andrea Lancichinetti, Santo Fortunato. Physical review. E, Statistical, nonlinear, and soft matter physics, 2009

1,033 citations recorded by the source corpus.

Many complex networks display a mesoscopic structure with groups of nodes sharing many links with the other nodes in their group and comparatively few with nodes of different groups. This feature is known as community structure and encodes precious information about the organization and the function of the nodes. Many algorithms have been proposed but it is not yet clear how they should be tested. Recently we have proposed a general class of undirected and unweighted benchmark graphs, with heterogeneous distributions of node degree and community size. An increasing attention has been recently devoted to develop algorithms able to consider the direction and the weight of the links, which require suitable benchmark graphs for testing. In this paper we extend the basic ideas behind our previous benchmark to generate directed and weighted networks with built-in community structure. We also consider the possibility that nodes belong to more communities, a feature occurring in real systems, such as social networks. As a practical application, we show how modularity optimization performs on our benchmark.

Subfields: Artificial Intelligence, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/c531ceb8c3400f5082873b1b52e49525ac6f85b0

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistical and Nonlinear Physics

Citations in the corpus

On the permanence of vertices in network communities (2014, methodology): “For the rest of the parameters, we use the default values mentioned in the authors’ implementation 3 [15].”
Community Discovery in Dynamic Networks (2017, positive): “Recently LFR has been generalized in order to handle weighted and directed graphs, as well as to generate overlapping communities (Lancichinetti and Fortunato, 2009).”
Community detection in graphs (2009, methodology): “Quality functions that, like modularity, are based on a null model such that the horizon of vertices is of the order of the size of the whole graph, are likely to be affected by a resolution limit (Fortunato, 2007).”
A Comprehensive Survey on Community Detection With Deep Learning (2021, methodology): “GN networks [3] and Lancichinetti–Fortunato– Radicchi (LFR) networks [148], [149] are two widely applied synthetic benchmarks, described in Appendix B-B (synthetic benchmark datasets) of the Supplementary Material.”
Community detection in social networks (2016, background): “116 A number of datasets are also available at the web pages, www-personal.umich.edu/~mejn/netdata 117 and https://snap.stanford.edu/data/.”
Community detection in networks: A user guide (2016, methodology): “Validation of algorithms, like the comparative analysis of (Lancichinetti and Fortunato, 2009), have allowed to identify a set of methods that perform well on artificial benchmarks.”
A Comparative Analysis of Community Detection Algorithms on Artificial Networks (2016, methodology): “This is a measure borrowed from information theory which has been regularly used in papers comparing community detection algorithms 13 .”
Overlapping community detection in networks: The state-of-the-art and comparative study (2011, methodology): “Instead of ﬁxing O m [Lancichinetti and Fortunato 2009; Gregory 2010], we also allow it to vary from 2 to 8 indicating the overlapping diversity of overlapping nodes.”
Efficient discovery of overlapping communities in massive networks (2013, methodology): “We measure accuracy with normalized mutual information (NMI) (44).”
A survey of community search over big graphs (2019, background): “irected networks that makes explicit use of information contained in edge directions. In [70], Flake et al. identied communities from websites network, which can be considered as directed graphs. In [120], Lancichinetti et al. introduced new benchmark graphs to test CD methods on directed networks. ”