Eur. Phys. J. B (2012) 85: 26
https://doi.org/10.1140/epjb/e2011-20129-7

Regular Article

Community overlays upon real-world complex networks

¹ DaLian Maritime University, School of Information Science and technology, DaLian 116026, P.R. China
² Delft University of Technology, Faculty of Electrical Engineering, Mathematics and Computer Science, 2628 CD, Delft, The Netherlands

^a e-mail: h.wang@tudelft.nl

Received: 21 February 2011
Received in final form: 25 July 2011
Published online: 18 January 2012

Abstract

Many networks are characterized by the presence of communities, densely intra-connected groups with sparser inter-connections between groups. We propose a community overlay network representation to capture large-scale properties of communities. A community overlay G_o can be constructed upon a network G, called the underlying network, by (a) aggregating each community in G as a node in the overlay G_o; (b) connecting two nodes in the overlay if the corresponding two communities in the underlying network have a number of direct links in between, (c) assigning to each node/link in the overlay a node/link weight, which represents e.g. the percentage of links in/between the corresponding underlying communities. The community overlays have been constructed upon a large number of real-world networks based on communities detected via five algorithms. Surprisingly, we find the following seemingly universal properties: (i) an overlay has a smaller degree-degree correlation than its underlying network ρ_o(D_l⁺, D_l⁻) < ρ(D_l⁺, D_l⁻) and is mostly disassortative ρ_o(D_l⁺, D_l⁻) < 0; (ii) a community containing a large number W_i of nodes tends to connect to many other communities ρ_o(W_i, D_i) > 0. We explain the generic observation (i) by two facts: (1) degree-degree correlation or assortativity tends to be positively correlated with modularity; (2) by aggregating each community as a node, the modularity in the overlay is reduced and so is the assortativity. The observation (i) implies that the assortativity of a network depends on the aggregation level of the network representation, which is illustrated by the Internet topology at router and AS level.