Every 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.

Social 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.

The 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.

The 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.

“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” says David Durfee, a School of Computer Science (SCS) Ph.D. recent graduate who is now at LinkedIn.

Improving dynamic graph analysis

This 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.

These 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.

This 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.

Although 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.

The 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.

The paper, Fully Dynamic Spectral Vertex Sparsifiers and Applications, is by SCS Ph.D. students Durfee and Yu Gao; Gramoz Goranci, a visiting student from the University of Vienna; and Richard Peng, an assistant professor in SCS. Gramoz will present this result at the annual ACM Symposium on the Theory of Computing (STOC) in Phoenix, Arizona, in Session 7B on the morning of June 26.