Yana Volkovich, Cornell Tech
Core decomposition has proven to be a useful primitive for a wide range of graph analyses. One of the most appealing features of such a tool is that, unlike other notions of dense subgraph, it can be computed very efficiently. In this paper we provide an analogous tool for uncertain graphs, i.e., graphs whose edges have a probability of existence. The fact that core decomposition can be performed efficiently in deterministic graphs does not guarantee efficiency in uncertain graphs, where even the simplest graph operations may become very complicated. Our main contribution is to show that core decomposition of uncertain graphs can be carried out efficiently as well. We extensively validate our definitions and methods on a number of real-world datasets and applications, such as influence maximization and task-driven team formation.