Improving community detection in networks by targeted node removal

How a network breaks up into subnetworks or communities is of wide interest. Here we show that vertices connected to many other vertices across a network can disturb the community structures of otherwise ordered networks, introducing noise. We investigate strategies to identify and remove noisy vertices (“violators”) and develop a quantitative approach using statistical breakpoints to identify when the largest enhancement to a modularity measure is achieved. We show that removing nodes thus identified reduces noise in detected community structures for a range of different types of real networks in software systems and in biological systems.

Figure 1

Community structures of a sample network (a) before and (b) after violator removal, showing the effect of two violators out of 40 nodes. Vertices are initially assigned to one of four communities at random (identified via node shape and shading). The two vertices with the largest degree are violators (hexagons) and do not preferentially connect to any single community. The remaining edges fall within communities with 85% probability and between them with 15%. Boxes illustrate the communities detected using the algorithm in Ref. 4.

Figure 2

Change in modularity in response to degree targeted and to random vertex removal for the Apache callgraph (CG), with $N=2213$ vertices and $E=6455$ edges, and the Apache email social network (Email), with $N=1232$ and $E=8064$.

Figure 3

$Q$ for the real networks plotted in black and the modularity of an ensemble of random networks with a degree sequence identical to the real network, $Q_{\mathrm{config}}$, in gray, both as functions of in-degree targeted removal for (a) the Apache callgraph and (b) the Apache developer email network. The points in the main figure indicate “breakpoints” as discussed in Sec. 3c. The inset plot shows $Q-Q_{\mathrm{config}}$, with the vertical dashed line indicating the location of the first breakpoint.

Figure 4

Modularity change for simulated networks having the degree sequence of the Apache callgraph and with three nodes set to be violators. Inset is $Q-Q_{\mathrm{config}}$, with the vertical dashed line indicating the location of the first breakpoint. (a) Modularity change by removing high-degree vertices. (b) Modularity change by removing high-$\Delta Q$ vertices.

Figure 5

Modularity change resulting from successively removing high-$\Delta Q$ vertices, shown for (a) the Apache callgraph and (b) the Apache email network. The inset plot shows $Q-Q_{\mathrm{config}}$, with the vertical dashed line indicating the first breakpoint.

Figure 6

Modularity change for four biological networks with high-$\Delta Q$ vertex removal. Breakpoints for each network are shown respectively; all the first breakpoints occur at three.