Article ID Journal Published Year Pages File Type
446046 Computer Communications 2013 10 Pages PDF
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.

Keywords
Related Topics
Physical Sciences and Engineering Computer Science Computer Networks and Communications
Authors
, , , ,