{"359681":{"#nid":"359681","#data":{"type":"event","title":"ARC Colloquium: Blair Sullivan - North Carolina State University","body":[{"value":"\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003ERefreshments served in Klaus 2222 at 2 pm\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003ETitle:\u0026nbsp;\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003ELooking for Structure in Real-World Networks\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EGraphs 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.\u0026nbsp; Unfortunately, efficient graph algorithms with guaranteed performance and solution quality are impossible in general networks (according to computational complexity).\u0026nbsp;\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;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.\u0026nbsp; 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.\u0026nbsp;\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;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?\u0026nbsp; 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?\u0026nbsp;\u003C\/p\u003E\u003Cp\u003EJoint work with E. Demaine, M. Farrell, T. Goodrich, N. Lemons, F. Reidl, P. Rossmanith, F. Sanchez Villaamil \u0026amp; S. Sikdar.\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":[{"value":"\u003Cp\u003EBlair Sullivan presents a talk as part of the ARC Colloquiuim series.\u003C\/p\u003E","format":"limited_html"}],"field_summary_sentence":[{"value":"ARC Colloquium: Blair Sullivan"}],"uid":"27466","created_gmt":"2014-12-31 16:01:09","changed_gmt":"2017-04-13 21:20:51","author":"Dani Denton","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2015-02-16T12:00:00-05:00","event_time_end":"2015-02-16T13:00:00-05:00","event_time_end_last":"2015-02-16T13:00:00-05:00","gmt_time_start":"2015-02-16 17:00:00","gmt_time_end":"2015-02-16 18:00:00","gmt_time_end_last":"2015-02-16 18:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"47223","name":"College of Computing"},{"id":"50875","name":"School of Computer Science"},{"id":"70263","name":"ARC"}],"categories":[],"keywords":[{"id":"12781","name":"algorithms \u0026 randomness center"},{"id":"9267","name":"ARC Colloquium"},{"id":"118411","name":"Blair Sullivan"},{"id":"118401","name":"Looking for Structure in Real-World Networks"},{"id":"14673","name":"theory"}],"core_research_areas":[],"news_room_topics":[],"event_categories":[{"id":"1795","name":"Seminar\/Lecture\/Colloquium"}],"invited_audience":[{"id":"78751","name":"Undergraduate students"},{"id":"78761","name":"Faculty\/Staff"},{"id":"78771","name":"Public"},{"id":"174045","name":"Graduate students"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[{"value":"\u003Cp\u003Edenton at cc dot gatech dot edu\u003C\/p\u003E","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}}}