Can We Quantify & Exploit Tree-like Intermediate Structure in Complex Networks?
Tuesday, October 25, 2011 - 4:15pm - 5:15pm
Large complex networks naturally represent relationships in a variety of settings, e.g. social interactions, computer/communication networks, and genomic sequences. A significant challenge in analyzing these networks has been understanding the “intermediate structure” – those properties not captured by metrics which are local (e.g. clustering coefficient) or global (e.g. degree distribution). It is often this structure which governs the dynamic evolution of the network and behavior of diffusion-like processes on it. Although there is a large body of empirical evidence suggesting that complex networks are often “tree-like” at intermediate to large size-scales (e.g. work of Boguna et al in physics, Kleinberg on internet routing, and Chung & Lu on power-law graphs), it remains a challenge to take algorithmic advantage of this structure in data analysis. We discuss several approaches and heuristics for quantifying and elucidating tree-like structure in networks, including various tree-decompositions and Gromov's delta-hyperbolicity. These approaches were developed with very different tree-like applications in mind, and thus we discuss the strengths and short-comings of each in the context of complex networks and how each might aid in identifying intermediate-scale structure in these graphs.