• Go Mobile »
  • Access by Staats- und Universitaetsbibliothek Bremen

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

Phys. Rev. E 80, 016118 – Published 31 July 2009
Andrea Lancichinetti and Santo Fortunato

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.

DOI: http://dx.doi.org/10.1103/PhysRevE.80.016118

  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
6 More
  • Received 24 April 2009
  • Revised 10 June 2009
  • Published 31 July 2009

© 2009 The American Physical Society

Authors & Affiliations

Andrea Lancichinetti and Santo Fortunato

  • Complex Networks Lagrange Laboratory (CNLL), Institute for Scientific Interchange (ISI), Viale S. Severo 65, 10133 Torino, Italy

References

Click to Expand

Authorization Required


×

Download & Share


PDF Export Citing Articles (37)
×

Images

1 of 13
×

Log In

Cancel
×

Search


Article Lookup
Paste a citation or DOI

Enter a citation
×
  1. Enter a citation to look up or terms to search.

    Ex: "PRL 112 068103", "Phys. Rev. Lett. 112, 068103", "10.1103/PhysRevLett.112.068103"

Enter a citation to look up or terms to search.

Ex: "PRL 112 068103", "Phys. Rev. Lett. 112, 068103", "10.1103/PhysRevLett.112.068103"

Close×