Community overlays upon real-world complex networks

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.