Modularity density of network community divisions

The problem of dividing a network into communities is extremely complex and grows very rapidly with the number of nodes and edges that are involved. In order to develop good algorithms to identify optimal community divisions it is extremely beneficial to identify properties that are similar for most networks. We introduce the concept of modularity density, the distribution of modularity Values as a function of the number of communities, and find strong indications that the general features of this modularity density are quite similar for different networks. The region of high modularity generally has very low probability density and Occurs where the number of communities is small. The properties and shape of the modularity density may give valuable information and aid in the search for efficient algorithms to find community divisions with high modularities. (C) 2009 Elsevier B.V. All rights reserved.