Generating graphs that approach a prescribed modularity

Trajanovski, S.; Kuipers, F.A.; Martín-Hernández, J.; Van Mieghem, P.

doi:doi:10.1016/j.comcom.2012.10.004

Generating graphs that approach a prescribed modularity

Title

Generating graphs that approach a prescribed modularity

Author

Trajanovski, S.
Kuipers, F.A.
Martín-Hernández, J.
Van Mieghem, P.

Faculty

Electrical Engineering, Mathematics and Computer Science

Department

Intelligent Systems

Date

2013-02-15

Abstract

Modularity is a quantitative measure for characterizing the existence of a community structure in a network. A network's modularity depends on the chosen partitioning of the network into communities, which makes finding the specific partition that leads to the maximum modularity a hard problem. In this paper, we prove that deciding whether a graph with a given number of links, number of communities, and modularity exists is NP-complete and subsequently propose a heuristic algorithm for generating graphs with a given modularity. Our graph generator allows constructing graphs with a given number of links and different topological properties. The generator can be used in the broad field of modeling and analyzing clustered social or organizational networks.

Subject

modularity
graph generator
modeling community structure

To reference this document use:

http://resolver.tudelft.nl/uuid:8510a759-44be-4e93-96e7-eb3426222369

Publisher

Elsevier

ISSN

0140-3664

Source

Computer Communications, 36 (4), 2013; pre-print

Other version

https://doi.org/10.1016/j.comcom.2012.10.004