Dense Subgraphs on Dynamic Networks
In distributed networks, it is often useful for the nodes to be aware of dense sub-graphs, e.g., such a dense sub-graph 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 paper, the authors address the problem of self-awareness of nodes in a dynamic network with regards to graph density, i.e., they give distributed algorithms for maintaining dense sub-graphs that the member nodes are aware of. The only knowledge that the nodes need is that of the dynamic diameter D, i.e., the maximum number of rounds it takes for a message to traverse the dynamic network.