Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities
Top Cited Papers
- 31 July 2009
- journal article
- research article
- Published by American Physical Society (APS) in Physical Review E
- Vol. 80 (1), 016118
- https://doi.org/10.1103/physreve.80.016118
Abstract
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.Keywords
Other Versions
This publication has 25 references indexed in Scilit:
- Complex networks: Structure and dynamicsPhysics Reports, 2006
- Uncovering the overlapping community structure of complex networks in nature and societyNature, 2005
- Functional cartography of complex metabolic networksNature, 2005
- Identifying the role that animals play in their social networksProceedings. Biological sciences, 2004
- Finding community structure in very large networksPhysical Review E, 2004
- Self-similar community structure in a network of human interactionsPhysical Review E, 2003
- The Structure and Function of Complex NetworksSIAM Review, 2003
- Community structure in social and biological networksProceedings of the National Academy of Sciences of the United States of America, 2002
- Algorithms for graph partitioning on the planted partition modelRandom Structures & Algorithms, 2001
- Diameter of the World-Wide WebNature, 1999