Real world networks, such as the air transportation network and metabolic networks, are strongly modular, that is the patterns of connectivity among agents are not homogeneous. For many cases of interest, there are groups of agents or components in the network that preferentially connect to one another [1-4]. However, the assignment of agents into groups still remains challenging because agents typically also connect to agents that are not in their group [1-4]. Additionally, agents may be members of more than one group [3,4]. Here, we introduce an ensemble of networks that have overlapping communities by construction. Using these model networks, we analyze the performance of three different classes of community detection methods: a modularity maximization method [2], the recently proposed k-clique [3], and a modularity-landscape surveying method [4]. We find that the modularity-landscape surveying method provides the best change to detect the presence of agents holding multiple memberships. We also find that the k-clique method performs poorly at detecting agent membership for both single membership and multi-membership cases.

To compare the performance of the methods for the ensemble of model networks with overlapping communities previously introduced, we generate ten networks for each set of parameter values, and run all community detection algorithms on each network. For each set of the ten networks, we also construct ``co-classification'' matrices, that is, we calculate the fraction of times a pair of nodes is classified in the same community according to each of the three methods. We also quantify the mutual information for the k-clique method and modularity maximization, which compares the partitions from the community detection algorithms against the known partition of agents.

References:

[1] Watts, D. J., Dodds, P. S., & Newman, M. E. J. (2002) Science 296, 1302-1305.

[2] Newman, M. E. J. (2004) Phys. Rev. E 69 art. no. 066133.

[3] Palla, G., Derenyi, I., Farkas, I., & Vicsek, T. (2005) Nature 435 814-818.

[4] Sales-Pardo, M., Guimerą, R., Moreira, A. A., & Amaral, L. A. N. (2006) submitted.

Extended Abstract Status: Not Uploaded