The rapid growth and availability of data is changing the face of science. One particularly challenging area has been understanding and analyzing complex networks, which naturally model relationships in many types of data (e.g. friendships in a social network or protein/gene interactions in a biological one). Although efficient graph algorithms with guaranteed performance and solution quality are impossible in general networks (according to computational complexity), the theoretical computer science community has been developing a suite of powerful (parameterized) algorithms that exploit specific forms of sparse graph structure to drastically reduce running time. On the other hand, the (extensive) research effort in network science to characterize the structure of real-world graphs has been primarily focused on either coarse, global properties (e.g., diameter) or very localized measurements (e.g., clustering coefficient) -- metrics which are insufficient for ensuring efficient algorithms.
We discuss recent work on bridging the gap between network science and structural graph algorithms, answering questions like: Do real-world networks exhibit structural properties that enable efficient algorithms? Is it observable empirically? Can sparse structure be proven for popular random graph models? How does such a framework help? Are the efficient algorithms associated with this structure relevant for common tasks such as evaluating communities, clustering and motifs? Can we reduce the (often super-exponential) dependence of these approaches on their structural parameters?
This talk includes joint work with E. Demaine, M. Farrell, T. Goodrich, N. Lemons, F. Reidl, P. Rossmanith, F. Sanchez Villaamil & S. Sikdar.