Theoretical Computer Science special issue on Complex Networks

Complex networks are large networks encountered in practice that seem to lack any apparent structure. Typical complex networks include internet topologies, web graphs, peer-to-peer networks, social networks (cooperation between peo-ple, economical exchanges, friendships, and others), biological networks (pro-tein/gene interactions, brain, food webs), linguistic networks (co-occurrence graphs, synonyms), and many more. Precisely dening a complex network is a tricky proposition since it is hard to set up a denition that is broad enough to capture the above examples, yet restrictive enough to make mathematical sense. Notice that the above networks are very dierent in nature. Some are sub-mitted to physical constraints (e.g., the internet or the brain) while others are purely virtual (e.g., social friendship networks); some come from natural sciences (e.g., biological networks) and others arise from technology (e.g., the internet); some are explicitly optimized with a notion of eciency (e.g., eco-nomic networks or the internet) while others are not (e.g., the web). All these networks, however, have several properties in common [56]. In particular, they have low global density|the number of links grows roughly linearly with the number of nodes, leading to a constant average degree; low average distance, typically logarithmic or sub-logarithmic in the number of nodes; heavy-tailed degree distributions, often modeled by power laws, Zipf, or log-normal distributions; high local density|the probability that two neighbors of any nodes are themselves connected (i.e., the clustering coecient) is large compared to the global density