Javascript must be enabled

Blair Sullivan : Can we Quantify & Exploit Tree-like Intermediate Structure in Complex Networks?



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.

Please select playlist name from following

Report Video

Please select the category that most closely reflects your concern about the video, so that we can review it and determine whether it violates our Community Guidelines or isn’t appropriate for all viewers. Abusing this feature is also a violation of the Community Guidelines, so don’t do it.


Comments Disabled For This Video