Abstract
Subgraphs and cycles are often used to characterize the local properties of complex networks. Here we show that the subgraph structure of real networks is highly time dependent: as the network grows, the density of some subgraphs remains unchanged, while the density of others increase at a rate that is determined by the network’s degree distribution and clustering properties. This inhomogeneous evolution process, supported by direct measurements on several real networks, leads to systematic shifts in the overall subgraph spectrum and to an inevitable overrepresentation of some subgraphs and cycles.
Keywords
complex networks, subgraphs
Subject Categories
Paths and cycles (Graph theory)
Disciplines
Physics
Publisher
The American Physical Society
Publication Date
2-2005
Rights Holder
©2005 The American Physical Society
Permanent URL
Recommended Citation
Vázquez, Alexei; Oliveira, J. G.; and Barabási, Albert-László, "Inhomogeneous evolution of subgraphs and cycles in complex networks" (2005). Physics Faculty Publications. Paper 116. http://hdl.handle.net/2047/d20000689
Click button above to open, or right-click to save.
Notes
Originally published in Physical Review E 71(2), 2005. doi:10.1103/PhysRevE.71.025103