Removing spurious interactions in complex networks

Identifying and removing spurious links in complex networks is meaningful for many real applications and is crucial for improving the reliability of network data, which, in turn, can lead to a better understanding of the highly interconnected nature of various social, biological, and communication systems. In this paper, we study the features of different simple spurious link elimination methods, revealing that they may lead to the distortion of networks’ structural and dynamical properties. Accordingly, we propose a hybrid method that combines similarity-based index and edge-betweenness centrality. We show that our method can effectively eliminate the spurious interactions while leaving the network connected and preserving the network's functionalities.

Figure 1

A simple example to illustrate how an improper spurious link removal method can disconnect a network.

Figure 2

AUC for various indices and for different values of $f$. The true networks are (a) CE, (b) Email, (c) SC, (d) PB, (e) PPI, and (f) USAir. Results are averaged over 100 independent realizations. Note that the curves for EB are not shown as the respective AUC values are too low. The same holds for PA in panel (c).

Figure 3

Relative size of the GC in $A^r$ with respect to the one in $A^t$ when various indices are used to build $A^r$ (here, $f^{\prime }=f$) and for different $f$. The true networks are (a) CE, (b) Email, (c) SC, (d) PB, (e) PPI, and (f) USAir. Results are averaged over 100 independent realizations. Refer to Appendix for the nonmonotonic trend in the RA case.

Figure 4

Relative errors of clustering coefficient [(a) and (b)], average shortest path length [(c) and (d)], and transportation congestability [(e) and (f)] for different $f$. The different lines correspond to the errors in $A^o$ and in the two $A^r$ built by the CN and hybrid methods, respectively, with $f^{\prime }=f$. Left plots refer to PB, whereas, right plots refer to USAir. Results are averaged over 100 independent realizations.

Figure 5

Relative size of the GC when different fractions of links $f^{\prime }$ are removed from $A^o$ by the CN, hybrid, and EB methods. The true networks are (a) CE, (b) Email, (c) SC, (d) PB, (e) PPI, and (f) USAir. Results are averaged over 100 independent realizations.

Figure 6

The residual fraction of spurious links in $A^r$ when different fractions of links $f^{\prime }$ are removed from $A^o$ by the CN, hybrid, and EB methods. The true networks are (a) CE, (b) Email, (c) SC, (d) PB, (e) PPI, and (f) USAir. Results are averaged over 100 independent realizations.

Figure 7

Relative size of the GC in the networks reconstructed by the hybrid method with different values of $\lambda$. (Insets) The AUC for different $\lambda$'s. The respective true networks are (a) CE, (b) Email, (c) SC, (d) PB, (e) PPI, and (f) USAir. Results are averaged over 100 independent realizations.

Figure 8

Relative errors of clustering coefficient [(a) and (b)], average shortest path length [(c) and (d)], and transportation congestability [(e) and (f)] for different $f$'s. The different lines correspond to the relative errors in $A^o$ and in the two $A^r$ built by the CN and hybrid methods, respectively, with $f^{\prime }=f$. The left plots refer to the CE, whereas, the right plots refer to Email. Results are averaged over 100 independent realizations.

Figure 9

Relative errors of clustering coefficient [(a) and (b)], average shortest path length [(c) and (d)], and transportation congestability [(e) and (f)] for different $f$'s. The different lines correspond to the relative errors in $A^o$ and in the two $A^r$ built by the CN and hybrid methods, respectively with $f^{\prime }=f$. The left plots refer to the SC, whereas, the right plots refer to the PPI. Results are averaged over 100 independent realizations.