*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
Refreshments served in Klaus 2222 at 2 pm
Title:
Looking for Structure in Real-World Networks
Abstract:
Graphs offer a natural representation of relationships within data -- for example, edges can be defined based on any user-defined measure of similarity (e.g. word frequencies, geographic proximity of observation, gene expression levels, or overlap in sample populations) or interaction (e.g. social friendship, communication, chemical bonds/protein bindings, or migration). As such, network analysis is playing an increasingly important role in understanding the data collected in a wide variety of social, scientific, and engineering settings. Unfortunately, efficient graph algorithms with guaranteed performance and solution quality are impossible in general networks (according to computational complexity).
One tantalizing approach to increasing scalability without sacrificing accuracy is to employ a suite of powerful (parameterized) algorithms developed by the theoretical computer science community which exploit specific forms of sparse graph structure to drastically reduce running time. The applicability of these algorithms, however, is unclear, since 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 analysis 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?
Joint work with E. Demaine, M. Farrell, T. Goodrich, N. Lemons, F. Reidl, P. Rossmanith, F. Sanchez Villaamil & S. Sikdar.
