Premium
Betti numbers of graphs with an application to anomaly detection
Author(s) -
Johannsen David A.,
Marchette David J.
Publication year - 2012
Publication title -
statistical analysis and data mining: the asa data science journal
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.381
H-Index - 33
eISSN - 1932-1872
pISSN - 1932-1864
DOI - 10.1002/sam.11141
Subject(s) - betti number , polynomial ring , commutative algebra , mathematics , algebraic number , intersection (aeronautics) , combinatorics , simple (philosophy) , class (philosophy) , algebraic properties , discrete mathematics , computer science , polynomial , artificial intelligence , mathematical analysis , philosophy , epistemology , engineering , aerospace engineering
This article describes an application of research that sits at the intersection of commutative algebra and combinatorics: Betti numbers of graphs. In particular, we describe a correspondence between simple undirected graphs and a class of ideals in a polynomial ring. We then briefly introduce some of the algebraic invariants that can be associated to the ideal and the relation of these invariants to the existence of induced subgraphs in the original graph. We discuss a novel application of the theory to a problem in anomaly detection—detection of a local non‐homogeneity in a graph. We describe some variants of these ideas designed to make the computations more tractable. © 2012 Wiley Periodicals, Inc. Statistical Analysis and Data Mining 5: 235–242, 2012