- Physical Review Journals
All JournalsPhysics Magazine
Access Provided by Xinjiang University

Physical Review E

Export citation

Export citation

Choose format for download:

Download Citation
  • Access by Xinjiang University

Removing spurious interactions in complex networks

An Zeng and Giulio Cimini

  • Department of Physics, University of Fribourg, Chemin du Musée 3, CH-1700 Fribourg, Switzerland

PDF

Phys. Rev. E 85, 036101 – Published 5 March, 2012

DOI: https://doi.org/10.1103/PhysRevE.85.036101

Abstract

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.

View figure in article

Article Text

References (37)

  1. L. A. N. Amaral and J. M. Ottino, Eur. Phys. J. B 38, 147 (2004).
  2. C. von Mering, R. Krause, B. Snel, M. Cornell, S. G. Oliver, S. Field, and P. Bork, Nature (London) 417, 399 (2002).
  3. C. T. Butts, Soc. Networks 25, 103 (2003).
  4. L. Getoor and C. P. Diehl, ACM SIGKDD Explor. Newsl. 7, 3 (2005).
  5. A. Clauset, C. Moore, and M. E. J. Newman, Nature (London) 453, 98 (2008).
  6. S. Redner, Nature (London) 453, 47 (2008).
  7. J. O'Madadhain, J. Hutchins, and P. Smyth, ACM SIGKDD Explor. Newsl. 7, 23 (2005).
  8. D. Liben-Nowell and J. Kleinberg, J. Am. Soc. Inf. Sci. Technol. 58, 1019 (2007).
  9. J. Kunegis, E. W. De Luca, and S. Albayrak, in IPMU Proceedings of the Computational Intelligence for Knowledge-Based Systems Design (Springer-Verlag, Berlin, 2010), pp. 380–389.
  10. Q.-M. Zhang, M.-S. Shang, W. Zeng, Y. Chen, and L. Lü, Phys. Procedia 3, 1887 (2010).
  11. P. Holme and M. Huss, J. R. Soc., Interface 2, 327 (2005).
  12. Z. Huang and D. D. Zeng, in SMC IEEE International Conference on Systems, Man and Cybernetics (Taipei, 2006), pp. 1131–1136.
  13. B. Gallagher, H. Tong, T. Eliassi-Rad, and C. Faloutsos, in Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (ACM, New York, 2008), p. 256.
  14. K. Dasgupta, R. Singh, B. Viswanathan, D. Chakraborty, S. Mukherjea, A. A. Nanavati, and A. Joshi, in Proceedings of the 11th International Conference on Extending Database Technology: Advances in Database Technology (ACM, New York, 2008), p. 668.
  15. L. Lü and T. Zhou, Physica A 390, 1150 (2011).
  16. Y. Wang and J. Chu, in Proceedings of the 20th ACM Conference on Hypertext and Hypermedia (ACM, New York, 2009), p. 377.
  17. D.-H. Kim, J. D. Noh, and H. Jeong, Phys. Rev. E 70, 046126 (2004).
  18. S. V. Buldyrev, R. Parshani, G. Paul, H. E. Stanley, and S. Havlin, Nature (London) 464, 1025 (2010).
  19. R. Guimerà, S. Mossa, A. Turtschi, and L. A. N. Amaral, Proc. Natl. Acad. Sci. USA 102, 7794 (2005).
  20. A. Arenas, A. Díaz-Guilera, J. Kurths, Y. Moreno, and C. Zhou, Phys. Rep. 469, 93 (2008).
  21. D. J. Watts and S. H. Strogatz, Nature (London) 393, 440 (1998).
  22. R. Guimerà, L. Danon, A. Diaz-Guilera, F. Giralt, and A. Arenas, Phys. Rev. E 68, 065103 (2003).
  23. M. E. J. Newman, Phys. Rev. E 74, 036104 (2006).
  24. R. Ackland [http://incsub.org/blogtalk/images/robertackland.pdf]
  25. C. von Mering, R. Krause, B. Snel, M. Cornell, S. G. Oliver, S. Fields, and P. Bork, Nature (London) 417, 399 (2002).
  26. V. Batageli and A. Mrvar [http://vlado.fmf.uni-lj.si/pub/networks/data/default.htm]
  27. J. A. Hanely and B. J. McNeil, Radiology 143, 29 (1982).
  28. When the total number of pairs n is large, it may become prohibitive to go over all possible comparisons. Hence, for analyzing big data sets, one usually only considers a random subset of n, which is big enough to reliably estimate the true AUC value.
  29. L. da F. Costa, F. A. Rodrigues, G. Travieso, and P. R. Villas Boas, Adv. Phys. 56, 167 (2007).
  30. R. Guimerà, A. Diaz-Guilera, F. Vega-Redondo, A. Cabrales, and A. Arenas, Phys. Rev. Lett. 89, 248701 (2002).
  31. T. Zhou, L. Lü, and Y.-C. Zhang, Eur. Phys. J. B 71, 623 (2009).
  32. L. Lü, C.-H. Jin, and T. Zhou, Phys. Rev. E 80, 046122 (2009).
  33. L. Katz, Psychometrika 18, 39 (1953).
  34. For LP and Katz, we set parameters ε and β to the values that maximize the respective AUC.
  35. S. Fortunato, Phys. Rep. 486, 75 (2010).
  36. R. Guimerà and M. Sales-Pardo, Proc. Natl. Acad. Sci. USA 106, 22073 (2009).
  37. U. Brandes, J. Math. Sociol. 25, 163 (2001).

Outline

Information

Phys. Rev. E 85, 036101– Published 5 March, 2012
  • Received 24 October 2011

©2012 American Physical Society

Sign In to Your Journals Account

Filter

Filter

Article Lookup

Enter a citation