{"622694":{"#nid":"622694","#data":{"type":"news","title":"Georgia Tech Researchers Create New Algorithm for  Compressing Dynamic Graphs","body":[{"value":"\u003Cp\u003EEvery minute on Facebook, millions of people are adding, deleting, and searching for friends. These changes can take up considerable computational power and time. Georgia Tech researchers have offered a new algorithm to hande these updates and queries faster than recomputing the solution from scratch.\u003C\/p\u003E\r\n\r\n\u003Cp\u003ESocial networks like Facebook run on dynamic graphs. In fully dynamic model of graphs, edges can be added or removed. When a query is made, it searches for effective resistances on the graph like creating an electrical circuit for the network and measuring the voltage needed to pass one unit of current.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EThe effective resistance relates to network distance, taking into account the number of paths and their proximity. Adding or deleting one edge could change the resistance fairly dramatically.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EThe researchers are able to maintain the graph by shrinking it to an important subset of vertices in a way that preserves pairwise resistances. Any query or update is answered by adding the involved vertices to this subset. The new algorithm forms a smaller graph.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026ldquo;A major difficulty here is that information in the original graph may be evenly spread among all the vertices, but we want to move them to a much smaller subset while retaining key global structures\u0026rdquo; says \u003Cstrong\u003E\u003Ca href=\u0022https:\/\/www.cc.gatech.edu\/~ddurfee3\/\u0022\u003EDavid Durfee\u003C\/a\u003E\u003C\/strong\u003E, a School of Computer Science (SCS) Ph.D. recent graduate who is now at LinkedIn.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EImproving dynamic graph analysis\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003EThis breakthrough is part of a larger field of compressing and storing graph and network data to make them easier to work with. One method is the graph sparsifier, which allows graphs to be compressed while still having important properties. The two most common sparsifiers are edge and vertex, which both reduce their respective properties.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EThese sparsifiers have been vital in developing machine learning, approximation, and efficient graph algorithms, yet each has its challenges. Most real-world graphs already have a sparse edge count, but vertex sparsifiers are far more applicable and also much harder to generate.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EThis research relies on a connection borrowed from scientific computing and physics to create such vertex sparsifiers, Schur complements, which preserve pairwise resistances between the subset of vertices. In this research, Schur complements are treated as the sum of random walks with one per original edge of the graph, and then a subset with only short random walks is slected.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EAlthough edge sparsifiers and dynamic graph data structures have been studied extensively, the researchers results give the first vertex sparsification based dynamic algorithm for general graphs undergoing edge insertions and deletions. It also extends to a variety of other important numerical quantities including solutions to systems of linear equations,and electrical flow energy.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EThe runtimes obtained, min{n^{0.83}, m^{0.75}}, are the first provably sublinear time result for these important quantities in network science. Yet the researchers believe much faster routines exist for a much wider range of problems on dynamic networks.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EThe paper,\u003Cem\u003E \u003Ca href=\u0022https:\/\/arxiv.org\/abs\/1804.04038\u0022\u003EFully Dynamic Spectral Vertex Sparsifiers and Applications\u003C\/a\u003E,\u003C\/em\u003E is by SCS Ph.D. students Durfee and \u003Cstrong\u003EYu Gao\u003C\/strong\u003E; \u003Cstrong\u003EGramoz Goranci\u003C\/strong\u003E, a visiting student from the University of Vienna; and \u003Cstrong\u003E\u003Ca href=\u0022https:\/\/www.cc.gatech.edu\/~rpeng\/\u0022\u003ERichard Peng\u003C\/a\u003E\u003C\/strong\u003E, an assistant professor in SCS. Gramoz will present this result at the annual \u003Ca href=\u0022http:\/\/acm-stoc.org\/\u0022\u003EACM Symposium on the Theory of Computing\u003C\/a\u003E (STOC) in Phoenix, Arizona, in Session 7B on the morning of June 26.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Georgia Tech researchers have offered a new algorithm to hande these updates and queries faster than recomputing the solution from scratch."}],"uid":"34541","created_gmt":"2019-06-21 19:37:35","changed_gmt":"2019-06-21 19:38:37","author":"Tess Malone","boilerplate_text":"","field_publication":"","field_article_url":"","dateline":{"date":"2019-06-21T00:00:00-04:00","iso_date":"2019-06-21T00:00:00-04:00","tz":"America\/New_York"},"extras":[],"hg_media":{"622695":{"id":"622695","type":"image","title":"Graph Sparsifier","body":null,"created":"1561145901","gmt_created":"2019-06-21 19:38:21","changed":"1561145901","gmt_changed":"2019-06-21 19:38:21","alt":"Graph sparsifier ","file":{"fid":"237156","name":"Screen Shot 2019-06-21 at 3.37.27 PM.png","image_path":"\/sites\/default\/files\/images\/Screen%20Shot%202019-06-21%20at%203.37.27%20PM.png","image_full_path":"http:\/\/www.tlwarc.hg.gatech.edu\/\/sites\/default\/files\/images\/Screen%20Shot%202019-06-21%20at%203.37.27%20PM.png","mime":"image\/png","size":67393,"path_740":"http:\/\/www.tlwarc.hg.gatech.edu\/sites\/default\/files\/styles\/740xx_scale\/public\/images\/Screen%20Shot%202019-06-21%20at%203.37.27%20PM.png?itok=jAZtku6V"}}},"media_ids":["622695"],"groups":[{"id":"50875","name":"School of Computer Science"}],"categories":[],"keywords":[],"core_research_areas":[],"news_room_topics":[],"event_categories":[],"invited_audience":[],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[{"value":"\u003Cp\u003ETess Malone, Communications Officer\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022mailto:tess.malone@cc.gatech.edu\u0022\u003Etess.malone@cc.gatech.edu\u003C\/a\u003E\u003C\/p\u003E\r\n","format":"limited_html"}],"email":["tess.malone@cc.gatech.edu"],"slides":[],"orientation":[],"userdata":""}}}