Why is a given node in a time-evolving graph ($t$-graph) marked as an anomaly
by an off-the-shelf detection algorithm? Is it because of the number of its
outgoing or incoming edges, or their timings? How can we best convince a human
analyst that the node is anomalous? Our work aims to provide succinct,
interpretable, and simple explanations of anomalous behavior in $t$-graphs
(communications, IP-IP interactions, etc.) while respecting the limited
attention of human analysts. Specifically, we extract key features from such
graphs, and propose to output a few pair (scatter) plots from this feature
space which "best" explain known anomalies. To this end, our work has four main
contributions: (a) problem formulation: we introduce an "analyst-friendly"
problem formulation for explaining anomalies via pair plots, (b) explanation
algorithm: we propose a plot-selection objective and the LookOut algorithm to
approximate it with optimality guarantees, (c) generality: our explanation
algorithm is both domain- and detector-agnostic, and (d) scalability: we show
that LookOut scales linearly on the number of edges of the input graph. Our
experiments show that LookOut performs near-ideally in terms of maximizing
explanation objective on several real datasets including Enron e-mail and DBLP
coauthorship. Furthermore, LookOut produces fast, visually interpretable and
intuitive results in explaining "ground-truth" anomalies from Enron, DBLP and
LBNL (computer network) data.

We consider goods that can be shared with k-hop neighbors (i.e., the set of
nodes within k hops from an owner) on a social network. We examine incentives
to buy such a good by devising game-theoretic models where each node decides
whether to buy the good or free ride. First, we find that social inefficiency,
specifically excessive purchase of the good, occurs in Nash equilibria. Second,
the social inefficiency decreases as k increases and thus a good can be shared
with more nodes. Third, and most importantly, the social inefficiency can also
be significantly reduced by charging free riders an access cost and paying it
to owners, leading to the conclusion that organizations and system designers
should impose such a cost. These findings are supported by our theoretical
analysis in terms of the price of anarchy and the price of stability; and by
simulations based on synthetic and real social networks.