Given an arbitrary group of computers, how to identify abnormal changes in their communication pattern? How to assess if the absence of some communications is normal or due to a failure? How to distinguish local from global events when communication data are extremely sparse and volatile? Existing approaches for anomaly detection in interaction streams, focusing on edge, nodes or graphs, lack flexibility to monitor arbitrary communication topologies. Moreover, they rely on structural features that are not adapted to highly sparse settings. In this work, we introduce MAD, a novel Multi-scale Anomaly Detection algorithm that (i) allows to query for the normality/abnormality state of an arbitrary group of observed/non-observed communications at a given time; and (ii) handles the highly sparse and uncertain nature of interaction data through a scoring method that is based on a novel probabilistic and multi-scale analysis of sub-graphs. In particular, MAD is (a) flexible: it can assess if any time-stamped subgraph is anomalous, making edge, node and graph anomalies particular instances; (b) interpretable: its multi-scale analysis allows to characterize the scope and nature of the anomalies; (c) efficient: given historical data of length N and M observed/non-observed communications to analyze, MAD produces an anomaly score in O (NM); and (d) effective: it significantly outperforms state-of-the-art alternatives tailored for edge, node or graph anomalies.

Measuring the influence of users in social networks is key for numerous applications. A recently proposed influence metric, coined as Ψ-score, allows to go beyond traditional centrality metrics, which only assess structural graph importance, by further incorporating the rich information provided by the posting and re-posting activity of users. The Ψ-score is shown in fact to generalize PageRank for non-homogeneous node activity. Despite its significance, it scales poorly to large datasets; for a network of$N$users, it requires to solve$N$linear systems of equations of size$N$. To address this problem, this work introduces a novel scalable algorithm for the fast approximation of Ψ- score, named Power-Ψ. The proposed algorithm is based on a novel equation indicating that it suffices to solve one system of equations of size$N$to compute the Ψ-score. Then, our algorithm exploits the fact that such a system can be recursively and distributedly approximated to any desired error. This permits the Ψ-score, summarizing both structural and behavioral information for the nodes, to run as fast as PageRank. We validate the effectiveness of the proposed algorithm, which we release as an open source Python library, on several real-world datasets.