Given a graph such as a social network or communication graph, one important problem is to classify the vertices according to a prespecified classification scheme. Examples include classifying hosts on the Internet as malware sites or not; determining which authors in a citation graph are authoritative; distinguishing persons of interest from others in a social network. We consider a variant of the problem in which the edges of the graph have labels (for example, topics in a communication graph or a coauthorship graph), a small number of vertices have known class labels, and we seek to suggest a ranked list of vertices to investigate such that a distinguished class appears early in the list: we seek to nominate a list of vertices as of potential interest. Our approach uses a simple model of edge-attributed random graphs that associates to each vertex a vector of attributes whose dot products determine the distributions of the edges and attributes in the graph. We illustrate the method through simulations, and discuss several variations on the theme.
Keywords: Network Analysis; Social Networks; Classification; Vertex clustering
Biography: Dr. David Marchette is a Principal Scientist at the Naval Surface Warfare Center, Dahlgren Division (NSWCDD), Dahlgren, VA where he is responsible for leading basic and applied research projects in computational statistics, graph theory, network analysis, pattern recognition, computer intrusion detection and image analysis. Dr. Marchette has a B.A. and an M.A. in mathematics from the University of California, San Diego, and a Ph.D. from George Mason University in Computational Sciences and Informatics (specializing in computational statistics).