On dense subgraphs in signed network streams

Abstract

Signed networks remain relatively under explored despite the fact that many real networks are of this kind. Here, we study the problem of subgraph density in signed networks and show connections to the event detection task. Notions of density have been used in prior studies on anomaly detection, but all existing methods have been developed for unsigned networks. We develop the first algorithms for finding dense subgraphs in signed networks using semi-definite programming based rounding. We give rigorous guarantees for our algorithms, and develop a heuristic EGOSCAN which is significantly faster. We evaluate the performance of EGOSCAN for different notions of density, and observe that it performs significantly better than natural adaptations of prior algorithms for unsigned networks. In particular, the improvement in edge density over previous methods is as much as 85% and usually over 50%. These results are consistent across signed and unsigned networks in different domains. The improvement in performance is even more significant for a constrained version of the problem involving finding subgraphs containing a subset of query nodes. We also develop an event detection method for signed and unsigned networks based on subgraph density. We apply this to three different temporal datasets, and show that our method based on EGOSCAN significantly outperforms existing approaches and baseline methods in terms of the precision-recall tradeoff (by as much as 25-50% in some instances).