A Comparison of Batch Versus Iterative Approaches to Vertex Nomination

• Activity Number: 136
• Type: Contributed
• Date/Time: Monday, August 1, 2011 : 8:30 AM to 10:20 AM
• Sponsor: Section on Statistical Learning and Data Mining
• Author(s): Minh Tang*+ and Glen Coppersmith and Carey Priebe
• Companies: The Johns Hopkins University and The Johns Hopkins University and The Johns Hopkins University
• Keywords: sequential analysis ; attributed graphs

Abstract

Let G be an attributed graph, i.e., a graph whose vertices and edges have attributes in some discrete sets L_V and L_E, respectively. Suppose that we observe the edge attributes for all the edges and the vertex attributes for a subset of the vertices and that all of these vertices have the same attribute, say 1. The vertex nomination problem is then concerned with nominating a set of vertices whose (unobserved) attribute is most likely to be 1. The nomination of a single vertex can be done using a variety of techniques, one of which is by computing a simple adjacency statistic T(v) for each vertex v with unknown attribute and nominating the vertex v^{*} whose T(v^{*}) is maximum. We investigate the difference between a batch and an iterative approach to vertex nomination that employ these T(v). We aim to show, under a simple model of attributed graphs construction, that depending on the probability that the attribute of a nominated vertex is indeed 1, the batch approach will be better than, comparable to, or worse than the iterative approach.