Dense Subgraphs on Dynamic Networks

Atish Das Sarma, Ashwin Lall, Danupon Nanongkai, and Amitabh Trehan

In distributed networks, it is often useful for the nodes to be aware of dense subgraphs, e.g., such a dense subgraph could reveal dense substructures in otherwise sparse graphs (e.g. the World Wide Web or social networks); these might reveal community clusters or dense regions for possibly maintaining good communication infrastructure. In this work, we address the problem of self-awareness of nodes in a dynamic network with regards to graph density, i.e., we give distributed algorithms for maintaining dense subgraphs that the member nodes are aware of. The only knowledge that the nodes need is that of the dynamic diameter , i.e., the maximum number of rounds it takes for a message to traverse the dynamic network. For our work, we consider a model where the number of nodes are fixed, but a powerful adversary can add or remove a limited number of edges from the network at each time step. The communication is by broadcast only and follows the CONGEST model. Our algorithms are continuously executed on the network, and at any time (after some initialization) each node will be aware if it is part (or not) of a particular dense subgraph. We give algorithms that -approximate the densest subgraph and -approximate the at-least-k-densest subgraph (for a given parameter k). Our algorithms work for a wide range of parameter values and run in time. Further, a special case of our results also gives the first fully decentralized approximation algorithms for densest and at-least-k-densest subgraph problems for static distributed graphs.


Guest: Amitabh Trehan
Host: Shantanu Das

Approximate Duality of Multicommodity Multiroute Flows and Cuts: Single Source Case

Petr Kolman and Christian Scheideler


Given an integer h, a graph with arbitrary positive edge capacities and k pairs of vertices , called terminals, an h-route cut is a set of edges such that after the removal of the edges in F no pair is connected by h edge-disjoint paths (i.e., the connectivity of every pair is at most in . The h-route cut is a natural generalization of the classical cut problem for multicommodity flows (take h = 1). The main result of this paper is an -approximation algorithm for the minimum h-route cut problem in the case that , called the single source case. As a corollary of it we obtain an approximate duality theorem for multiroute multicommodity flows and cuts with a single source. This partially answers an open question posted in several previous papers dealing with cuts for multicommodity multiroute problems.

Guest: Christian Scheideler
Host: Shantanu Das