Documents in the NTIS Technical Reports collection are the results of federally funded research. They are directly submitted to or collected by NTIS from Federal agencies for permanent accessibility to industry, academia and the public.  Before purchasing from NTIS, you may want to check for free access from (1) the issuing organization's website; (2) the U.S. Government Printing Office's Federal Digital System website; (3) the federal government Internet portal; or (4) a web search conducted using a commercial search engine such as
Accession Number ADA580208
Title Islands and Bridges: Making Sense of Marked Nodes in Large Graphs.
Publication Date Jan 2013
Media Count 29p
Personal Author D. H. Chau H. Tong J. Vreeken L. Akoglu N. Tatti
Abstract Suppose we are given a large graph in which, by some external process, a handful of nodes are marked. What can we say about these marked nodes. Are they all close-by in the graph, or are they segregated into multiple groups. How can we automatically determine how many, if any groups they form as well as find simple paths that connect the nodes in each group. We formalize the problem in terms of the Minimum Description Length principle: a set of paths is simple when we need few bits to describe each path from one node to another. For example, we want to avoid high-degree nodes, unless we need to visit many of its spokes. As such, the best partitioning requires the least number of bits to describe the paths that visit all marked nodes. We show that our formulation for finding simple paths between groups of nodes has connections to well-known other problems in graph theory, and is NP-hard. We propose fast effective solutions, and introduce DOT2DOT, an efficient algorithm for partitioning marked nodes as well as finding simple paths between nodes within parts. Experimentation shows DOT2DOT correctly groups nodes for which good connection paths can be constructed, while separating distant nodes.
Keywords Algorithms
Connection subgraphs
Information theory
Link mining

Source Agency Non Paid ADAS
NTIS Subject Category 72B - Algebra, Analysis, Geometry, & Mathematical Logic
62B - Computer Software
Corporate Author Carnegie-Mellon Univ., Pittsburgh, PA. School of Computer Science.
Document Type Technical report
Title Note N/A
NTIS Issue Number 1325
Contract Number W911NF-09-2-0053 W911NF-11-C-0200

Science and Technology Highlights

See a sampling of the latest scientific, technical and engineering information from NTIS in the NTIS Technical Reports Newsletter

Acrobat Reader Mobile    Acrobat Reader