• Rapid Communication

Giant strongly connected component of directed networks

S. N. Dorogovtsev, J. F. F. Mendes, and A. N. Samukhin
Phys. Rev. E 64, 025101(R) – Published 19 July 2001
PDFExport Citation

Abstract

We describe how to calculate the sizes of all giant connected components of a directed graph, including the strongly connected one. In particular, the World Wide Web is a directed network. The results are obtained for graphs with statistically uncorrelated vertices and an arbitrary joint in and out-degree distribution P(ki,ko). We show that if P(ki,ko) does not factorize, the relative size of the giant strongly connected component deviates from the product of the relative sizes of the giant in- and out-components. The calculations of the relative sizes of all the giant components are demonstrated using the simplest examples. We explain that the giant strongly connected component may be less resilient to random damage than the giant weakly connected one.

  • Received 30 March 2001

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

©2001 American Physical Society

Authors & Affiliations

S. N. Dorogovtsev1,2,*, J. F. F. Mendes1,†, and A. N. Samukhin2,‡

  • 1Departamento de Física and Centro de Física do Porto, Faculdade de Ciências, Universidade do Porto, Rua do Campo Alegre 687, 4169-007 Porto, Portugal
  • 2A.F. Ioffe Physico-Technical Institute, 194021 St. Petersburg, Russia

  • *Electronic address: sdorogov@fc.up.pt
  • Electronic address: jfmendes@fc.up.pt
  • Electronic address: alnis@samaln.ioffe.rssi.ru

References (Subscription Required)

Click to Expand
Issue

Vol. 64, Iss. 2 — August 2001

Reuse & Permissions
Access Options
Author publication services for translation and copyediting assistance advertisement

Authorization Required


×
×

Images

×

Sign up to receive regular email alerts from Physical Review E

Log In

Cancel
×

Search


Article Lookup

Paste a citation or DOI

Enter a citation
×