Discovering Communities and Anomalies in Attributed Graphs: Interactive Visual Exploration and Summarization

摘要: Given a network with node attributes, how can we identify communities and spot anomalies? How characterize, describe, or summarize the in succinct way? Community extraction requires measure of quality for connected subgraphs (e.g., social circles). Existing subgraph measures, however, either consider only connectedness nodes inside community ignore cross-edges at boundary density) quantify structure attributes conductance). In this work, focus on node-attributed networks introduce: (1) new attributed called normality, (2) algorithm that uses normality to extract few characterizing per community, (3) summarization interactive visualization approach graph exploration. More specifically, first introduce to normality an subgraph. Our normality measure carefully utilizes together both internal consistency external separability. We then formulate objective function automatically infer (called “focus”) respective attribute weights, so as maximize normality  score given Most notably, unlike many other approaches, our allows long they be “exonerated;” i.e., (i) are expected under null model, and/or (ii) their do not exhibit attributes. Next, propose AMEN (for Attributed Mining Entity Networks), simultaneously discovers graph, goal total normality. Communities which yields high cannot found considered low anomalous. Last, task multi-criteria objective, selects subset cover entire well, (iii) diverse further design interface presents user interpretable, user-friendly fashion. The explore all communities, analyze various algorithm-generated summaries, well devise own summaries interactively characterize way. As experiments real-world graphs show, proposed approaches effectively find anomalous outperform several existing measures methods, such conductance, density, OddBall, SODA. also conduct extensive studies capability efficiency provides users toward summarization, exploration, sensemaking.