Detecting network communities beyond assortativity-related attributes

In network science, assortativity refers to the tendency of links to exist between nodes with similar attributes. In social networks, for example, links tend to exist between individuals of similar age, nationality, location, race, income, educational level, religious belief, and language. Thus, various attributes jointly affect the network topology. An interesting problem is to detect community structure beyond some specific assortativity-related attributes $\rho$, i.e., to take out the effect of $\rho$ on network topology and reveal the hidden community structures which are due to other attributes. An approach to this problem is to redefine the null model of the modularity measure, so as to simulate the effect of $\rho$ on network topology. However, a challenge is that we do not know to what extent the network topology is affected by $\rho$ and by other attributes. In this paper, we propose a distance modularity, which allows us to freely choose any suitable function to simulate the effect of $\rho$. Such freedom can help us probe the effect of $\rho$ and detect the hidden communities which are due to other attributes. We test the effectiveness of distance modularity on synthetic benchmarks and two real-world networks.

Figure 1

The plot of function $f\left(d\right)=e^{-{(d/\sigma )}^2}$ and $f\left(d\right)={[1+{(d/\sigma )}^2]}^{-1}$ at different values of $\sigma$.

Figure 2

Visualization of Cerina's synthetic spatial networks at the four extreme cases: (a) $\epsilon =0.1$, $\beta =0.3$; (b) $\epsilon =0.1$, $\beta =1.0$; (c) $\epsilon =0.5$, $\beta =0.3$; and (d) $\epsilon =0.5$, $\beta =1.0$. For the sake of clarity, only 50 out of the 100 nodes are displayed here. The nodes in community $C_{+1}$ and $C_{-1}$ are painted in black and white, respectively. The between-community and within-community links are plotted by solid and dashed lines, respectively.

Figure 3

The NMI scores by NG modularity, spatial modularity, and distance modularity in Cerina's synthetic spatial networks, for $\beta \in [0.3,1.0]$ and $\epsilon =$0.1, 0.3, and 0.5. Each score is based on an average of 100 implementations. NG stands for scores by NG modularity. Spa-High and Spa-Cons stand for the highest scores and the scores of the consensus partitions by spatial modularity, respectively. Distance-High and Distance-Cons stand for the highest scores and the scores of the consensus partitions by distance modularity, respectively.

Figure 4

Visualization of Lazega's partner advice network. Partners whose practice is litigation and corporate law are symbolized as square and round nodes, respectively. Partners whose office location is Hartford, Providence, and Boston are painted in red (dark gray), white, and blue (light gray), respectively. (a) The partition by NG modularity. (b) The partition by distance modularity. (c) The partition by spatial modularity.

Figure 5

Lazega's partner advice network. (a) The averaged normalized mutual information $\left(I^{\mathrm{avg}}\right)$ as a function of $\sigma$. (b) The effects of office location in the observed network, the spatial modularity null model, the distance modularity null model ($\sigma =0.1)$, and the NG modularity null model.

Figure 6

D4D antenna network. (a) The averaged normalized mutual information $\left(I^{\mathrm{avg}}\right)$ as a function of $\sigma$. (b) The space effect in the observed network, the spatial modularity null model, the distance modularity null model, and the NG modularity null model.

Figure 7

The partitions of the D4D antenna network by (a) NG modularity, (b) spatial modularity, (c) distance modularity at $\sigma =1.5\overline{d}$ (the consensus partition based on the alternative parameter selection), and (d) distance modularity at $\sigma =0.7\overline{d}$.

Figure 8

The ethnic distribution in the Ivory Coast (image reprinted from http://fr.wikipedia.org/).