ARC Colloquium: Blair Sullivan - North Carolina State University

Event Details
Contact

denton at cc dot gatech dot edu

Summaries

Summary Sentence: ARC Colloquium: Blair Sullivan

Full Summary: Blair Sullivan presents a talk as part of the ARC Colloquiuim series.

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.

 

 

Additional Information

In Campus Calendar
No
Groups

College of Computing, School of Computer Science, ARC

Invited Audience
Undergraduate students, Faculty/Staff, Public, Graduate students
Categories
Seminar/Lecture/Colloquium
Keywords
algorithms & randomness center, ARC Colloquium, Blair Sullivan, Looking for Structure in Real-World Networks, theory
Status
  • Created By: Dani Denton
  • Workflow Status: Published
  • Created On: Dec 31, 2014 - 11:01am
  • Last Updated: Apr 13, 2017 - 5:20pm